---

Cryptography / Cryptographie
(D. Stinson and H. Williams, Organizers)

---

M. BAUER, University of Waterloo, Waterloo, Ontario  N2L 3G1
Comparative efficiency of cubic function fields

In this talk, we will consider curves of the form y³=f(x) over a given field K of characteristic different from 3. If f(x) satisfies certain properties, then the Jacobian of such a curve is isomorphic to the ideal class group of the maximal order in the corresponding function field. Thus, by developing explicit techniques for performing arithmetic in this ideal class group, we are able to do computations in the Jacobian of such curves. While the resulting arithmetic is efficient enough to make it practical for cryptographic applications, it is still less efficient than using hyperelliptic curves. We will attempt to derive a more efficient arithmetic by restricting our attention to curves of genus 3 or 4, since curves of higher genus are arguably not of cryptographic interest.

D. BERNSTEIN, Department of Mathematics, Statistics, and Computer Science, University of Chicago, Illinois  60607, USA
Speed records for cryptographic software: an update

I'll present the latest speed records for software implementations of secret-key message authentication, public-key signature verification, and public-key secret sharing.

I. BLAKE, University of Toronto, Department of Electrical and Computer Engineering, Toronto, Ontario  M5S 3G4
Certificates for primes and RSA modulii

The problem of generating and testing primality is an important aspect of many public key cryptosystems. Both probabilistic and deterministic tests are available and perform well in practice. There is also the notion of a certificate (Goldwasser-Kilian certificate) whereby one is able to derive additional information making it relatively easy for a second party to verify the primality of a given integer. An overview of these notions is given in the talk. In particular it is shown how the notion of a GK primality certificate can be extended to an RSA modulus.

P. D'ARCO, University of Waterloo, Waterloo, Ontario
Distributed oblivious transfer and applications in cryptography

A Distributed Oblivious Transfer protocol can be described as follows: a Sender has n secrets and a Receiver is interested in one of them. During a set up phase, the Sender gives information about the secrets to m servers. Afterwards, in a recovering phase, the Receiver can compute the secret she wishes by interacting with k of them. More precisely, from the answers received she computes the secret in which is interested but gets no information on the others and, at the same time, any coalition of k-1 servers can neither compute any secret nor figure out which one the receiver has recovered.

We present an analysis and new results holding for this model: some impossibility results for one-round distributed oblivious transfer protocols; two polynomial-based constructions implementing 1-out-of-n distributed oblivious transfer, which generalize the two constructions for 1-out-of-2 proposed by M. Naor and B. Pinkas; as well as, new one-round and two-round distributed oblivious transfer protocols, both for threshold and general access structures on the set of servers. These constructions are unconditionally secure and basically combinatorial in nature. Finally, we discuss some possible applications.

KARL DILCHER, Dalhousie University, Halifax, Nova Scotia  B3H 3J5
Fermat numbers, Wieferich and Wilson primes: computations and generalizations

In this survey of recent and ongoing computational and theoretical work I report on the following interrelated topics, all dealing with very large integers: Fermat numbers, generalized Fermat numbers, the search for Wieferich and Wilson primes, and Fermat and Wilson quotients for composite moduli. A number of related topics will also be briefly discussed.

S. HAMDY, University of Calgary, Calgary, Alberta
IQ cryptography: a secure and efficient alternative

IQ cryptography is a synonym for cryptography based on class groups of imaginary quadratic fields. Class groups are finite abelian groups, and many cryptographic schemes (such as the Diffie-Hellman key exchange or the Integrated Encryption Scheme) defined for other groups can be easily adapted to class groups. IQ cryptography hasn't enjoyed much attention in the past. However, it has been shown recently that there are secure and efficient IQ crypto-systems. In this talk I report on such crypto-systems, and I present the latest results on the efficiency of some IQ crypto-systems, where I use other yet unpublished results.

A. HASAN, University of Waterloo, Waterloo, Ontario
DPA attack resistant Koblitz curve cryptosystems

Because of their shorter key sizes, crypto-systems based on elliptic curves are being increasingly used in practical applications. A special class of elliptic curves, namely, Koblitz curves, offers an additional but crucial advantage of considerably reduced processing time. This talk is about differential power analysis (DPA) attacks against crypto-systems that use scalar or point multiplications on Koblitz curves. For the resistance of such DPA attacks, this talks also presents a number of countermeasures which depend on randomizing the secret key prior to each execution of the scalar multiplication. These countermeasures are computationally efficient and suitable for hardware implementation.

M. JACOBSON, University of Manitoba, Winnipeg
Unconditionally computing fundamental units of real quadratic fields in parallel

We present two parallel versions of the well-known baby-step giant-step algorithm. The first algorithm achieves a speedup of Ön on an n-procesor machine, and is suitable for use on large clusters or servers. The second acieves a speedup of n and is suitable for use on shared-memory multiprocessors. As an application, we present a parallel algorithm which unconditionally computes the fundamental unit of a real quadratic field in expected time O(D^{1/6 +e}). This is joint work with Hugh Williams (Calgary).

R. LAFLAMME, Department of Physics, University of Waterloo, Waterloo, Ontario  N2L 3G1
Quantum computing

Advances in computing are revolutionizing our world. Present day computers advance at a rapid pace toward the barrier defined by the laws of quantum physics. The quantum computation program short-circuits that constraint by exploiting the quantum laws to advantage rather than regarding them as obstacles. Quantum computer accepts any superposition of its inputs as an input, and processes the components simultaneously, performing a sophisticated interference experiment of classical inputs. This ``quantum parallelism'' allows one to explore exponentially many trial solutions with relatively modest means, and to select the correct one. This has a particularly dramatic effect on factoring of large integers, which is at the core of the present day encryption strategies (public key) used in diplomatic communication, and (increasingly) in business. As demonstrated approximately five years ago, quantum computers could yield the most commonly used encryption protocol obsolete. Since then, it was also realized that quantum computation can lead to breakthroughs elsewhere, including simulations of quantum systems, implementation of novel encryption strategies (quantum cryptography), as well as more mundane applications such as sorting. I will describe recent work done in quantum computation, in particular the discovery and implementation of methods to make quantum information robust against corruption, both in theory and experiments. I will end with speculations about the field.

S. MAGLIVERAS, Florida Atlantic University
Group theoretic cryptography

Many well known cryptosystems, symmetric or public-key, have been based on properties of large abelian groups-more precisely properties of certain representations of these groups. Here we discuss cryptosystems based on non-abelian, in fact non-solvable groups. A private-key cryptosystem based on logarithmic signatures for finite groups was proposed by the author in 1986, and its algebraic properties were studied by the author and N. D. Memon in 1992. Here we discuss the symmetric system, and two possible approaches for constructing new public-key cryptosystem using logarithmic signatures and certain uniform group covers we call meshes. Time permitting we will also provide some insight into a question posed by M. I. González Vasco and R. Steinwaldt.

DOMINIC MAYERS, Université de Sherbrooke, Shrebrooke, Québec  J1K 2R1
Non ideal Quantum bit commitment

Bit commitment is one of the most important cryptographic task in the quantum model. For example, a protocol was proposed in 1992 by Bennett, Brassard, Crpeau and Salvail to build string oblivious transfert on top of an ideal bit commitment. The protocol was designed to work over a noisy channel. The security proof of this reduction in the case of (one bit) oblivious transfert over a noiseless channel was obtained by Yao in 1995. The extension to string oblivious transfert over a noisy channel was obtained by Mayers in 1996. Unfortunately, it was shown by Mayers in 1997, building on a previous result of Mayers and Lo and Chau, that a bit commitment secure against all attacks allowed by quantum mechanics is impossible. However, the quantum reduction itself is still interesting since we can use computationally secure bit commitment, or another kind of bit commitment such as the relativistic sustained bit commitment of Kent, in this reduction. Extra care must be taken, however, since the reduction was only proven for the case of ideal bit commitment. This kind of concerns is particularly important and non obvious to deal with in the quantum model. We provide a new definition for non ideal bit commitment and show that a large class of reduction which are valid on top of ideal bit commitment, including the above reduction, are also valid on top of this non ideal bit commitment.

MIKE MOSCA, University of Waterloo, Waterloo, Ontario  N2L 3G1
Private quantum channels

We investigate how a classical private key can be used by two players, connected by an insecure one-way quantum channel, to perform private communication of quantum information. In particular, we show that in order to transmit n qubits privately, 2n bits of shared private key are necessary and sufficient. This result may be viewed as the quantum analogue of the classical one-time pad encryption scheme.

This is joint work with Andris Ambainis, Alain Tapp, and Ronald de Wolf.

K. MURTY, University of Toronto
Non-linear secret sharing and prime numbers

We study the privacy and correctness of a non-linear secret sharing scheme involving the distribution of prime numbers in arithmetic progressions.

N. PIPPENGER, Department of Computer Science, University of British Columbia, Vancouver, British Columbia  V6T 1Z4
Information attenuation in Quantum channels

The classical Data Processing Theorem states that the mutual information between the output of a channel and an independent source cannot exceed the mutual information between the input of the channel and the source. Evans and Schulman have given a quantitative version of this result for the transmission of a single bit over a binary symmetric channel, with a sharp bound for the factor by which the mutual information decreases. We shall present the generalization of their result to the transmission of of a single qubit over a quantum depolarizing channel, and discuss other possible generalizations.

R. SCHEIDLER, Department of Mathematics and Statistics, University of Calgary, Calgary, Alberta  T2N 1N4
Efficiency and security of real quadratic field based key exchange

Most cryptographic key exchange protocols make use of the presumed difficulty of solving the discrete logarithm problem (DLP) in a certain finite group as the basis of their security. Recently, real quadratic number fields have been proposed for use in the development of such protocols. Breaking such schemes is known to be at least as difficult a problem as integer factorization; furthermore, these are the first discrete logarithm based systems to utilize a structure which is not a group, specifically the collection of reduced ideals which belong to the principal class of the number field. For this structure the DLP is essentially that of determining a generator of a given principal ideal.

Unfortunately, there are a few implementation-related disadvantages to these schemes, such as the need for high precision floating point arithmetic and an ambiguity problem that requires a short, second round of communication. In collaboration with M. J. Jacobson and H. C. Williams, we have resolved some of these difficulties. Furthermore, the most recent techniques for solving the DLP in a real quadratic number field shed new light on the security of the system.

A. SILVERBERG, Ohio State University, Columbus, Ohio, USA
Abelian varieties in cryptography

In the past, supersingular elliptic curves were viewed as ``weak'' for purposes of cryptography. However, applications of supersingular elliptic curves to cryptography have been found very recently, by Joux, Boneh et al., and others. These new applications include tripartite secret-sharing, identity-based encryption, and short digital signatures. In this talk we show how these applications can be done even better using abelian varieties. Joint work of Rubin and Silverberg determines precisely how much of an improvement is possible using supersingular abelian varieties and gives explicit constructions of optimal supersingular abelian varieties.

A. STEIN, University of Illinois at Urbana-Champaign, Department of Mathematics, Urbana, Illinois  61801, USA
Solving elliptic curve discrete logarithm problems using Weil descent

We provide the first cryptographically interesting instance of the elliptic curve discrete logarithm problem which resists all previously known attacks, but which can be solved with modest computer resources using the Weil descent attack methodology of Frey. We report on our implementation of index-calculus methods for hyperelliptic curves over characteristic two finite fields, and discuss the cryptographic implications of our results.

ALAIN TAPP, Université de Montréal
Quantum authentication

Authentication is a well-studied area of classical cryptography: a sender S and a receiver R sharing a classical private key want to exchange a message with the guarantee that the message has not been modified (or replaced) by a dishonest party with control of the communication line. In this talk I will discuss the authentication of quantum messages. While classically, authentication and encryption are independent tasks, I will show that no scheme to authenticate quantum messages can be secure unless it also encrypts the messages. Assuming S and R have access to an insecure quantum channel and share a private, classical random key, I will present a scheme that both enables S to encrypt and authenticate (with unconditional security) an m qubit message by encoding it into m+s qubits, where the error probability decreases exponentially in the security parameter s. The scheme requires a private key of size 2m+O(s), which is asymptotically optimal. I will also discuss the problem of digitally signing quantum messages, and show that it is impossible, even with only computational security. This is joint work with Howard Branum, Cleude Crépeau, Daniel Gottesman and Adam Smith.

S. TAVARES, Queen's University, Kingston Ontario
GST: A new family of stream ciphers based on a cascade of small s-boxes

In this talk we present a new family of stream ciphers based on a cascade of small s-boxes which permute their contents after each output. Since so many stream ciphers based on linear feedback shift registers (LFSRs) which feed into a nolinear combiner have been successfully attacked, we feel there is a need for new approaches in stream cipher design. We use as a starting point the idea of a pointer-controlled s-box used in RC4 by its designer Ron Rivest. However, we depart from RC4 in several ways. First, RC4 is a fixed design using one 8-bit s-box. In our stream cipher, we use a variable length cascade of small (typically 2-bit) s-boxes. The length of the cascade is determined by the desired security. Further, the output of each s-box in the cascade controls a pointer to the succeeding s-box. The output of the last s-box in the chain is the keystream of the cipher. Advantages of the cascade stream cipher are that it is simple, modular, and efficient in software and hardware implementations. We present some results on the randomness properties of the cipher, and some preliminary efforts at cryptanalysis.

Based on joint work with: Lin Gan, Ivan Lee and Stan Simmons.

E. TESKE, University of Waterloo, Waterloo, Ontario  N2L 3G1
A constructive application of Weil descent in ECC

It is easy to construct an elliptic curve E/F_2¹⁶¹ with #E = 2p, p a 160-bit prime, in which the elliptic curve discrete logarithm problem is computationally feasible, but not trivial, using the Gaudry-Hess-Smart (GHS) Weil descent attack. Given such a curve E, it is easy to construct a cryptographically suitable curve E¢, isogenous to E, for which the GHS attack is worse than Pollard's rho method. The reverse construction, however, is believed to be computationally infeasible. This can be exploited for a trapdoor construction with attractive properties.

G. WALSH, University of Ottawa, Ottawa, Ontario
An applied application of a conjecture of Oesterle

We discuss a connection between a conjecture of Oesterle (the abc conjecture) and the security provided by elliptic curve cryptography.

R. WEI, Lakehead University, Thunder Bay, Ontario
Cover-free problems in cryptography

Several recent topics in cryptography, such as multi-receiver authentication, anti-jamming systems, broadcast encryption, frameproof codes, traceability schemes, key storage problems, etc., applied a same mathematical object: cover-free family. We will briefly review these topics and then discuss the mathematical aspect of cover-free families. Some generalizations and new results will be given.