




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^{3}=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
secretkey message authentication, publickey signature verification,
and publickey 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 (GoldwasserKilian 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 k1 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 oneround distributed oblivious transfer
protocols; two polynomialbased constructions implementing
1outofn distributed oblivious transfer, which generalize the two
constructions for 1outof2 proposed by M. Naor and B. Pinkas; as
well as, new oneround and tworound 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 DiffieHellman 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 cryptosystems. In this talk I report on
such cryptosystems, and I present the latest results on the efficiency
of some IQ cryptosystems, 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, cryptosystems 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
cryptosystems 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 wellknown babystep giantstep
algorithm. The first algorithm achieves a speedup of Ön on an
nprocesor machine, and is suitable for use on large clusters or
servers. The second acieves a speedup of n and is suitable for use
on sharedmemory 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
shortcircuits 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 publickey, have been based
on properties of large abelian groupsmore precisely properties of
certain representations of these groups. Here we discuss cryptosystems
based on nonabelian, in fact nonsolvable groups. A privatekey
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
publickey 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 oneway 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 onetime pad encryption scheme.
This is joint work with Andris Ambainis, Alain Tapp, and Ronald de
Wolf.
 K. MURTY, University of Toronto
Nonlinear secret sharing and prime numbers

We study the privacy and correctness of a nonlinear 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 implementationrelated 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 secretsharing, identitybased 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 UrbanaChampaign, 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 indexcalculus 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 wellstudied 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
sboxes

In this talk we present a new family of stream ciphers based on a
cascade of small sboxes 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
pointercontrolled sbox used in RC4 by its designer Ron Rivest.
However, we depart from RC4 in several ways. First, RC4 is a fixed
design using one 8bit sbox. In our stream cipher, we use a
variable length cascade of small (typically 2bit) sboxes. The
length of the cascade is determined by the desired security. Further,
the output of each sbox in the cascade controls a pointer to the
succeeding sbox. The output of the last sbox 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_{2161} with #E = 2p, p a 160bit prime, in which the elliptic curve discrete
logarithm problem is computationally feasible, but not trivial, using
the GaudryHessSmart (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
Coverfree problems in cryptography

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

