**of the**

Ruhr-Universität Bochum

Scientific Committee:

Prof. Dr. E. Becker (Dortmund)

Prof. Dr. H. Dobbertin (Bochum)

Prof.Dr.L.Gerritzen
(Bochum)

Program

Thursday, Nov. 8:

10.00 Opening

Prof.
Dr. E. Becker (Co-Speaker of the Graduate College, University of
Dortmund)

Prof.
Dr. H. Flenner (Dean of the Faculty of Mathematics, University of
Bochum)

Prof.
Dr. M. Bormann (Representative for Eurubits of the Rektorat of the University
of Bochum)

10.30 Prof. Dr. C.P. Schnorr (Frankfurt am Main):

"New Practical Algorithms for the Approximate Shortest Lattice Vector"

*Abstract: * We present a novel practical algorithm for the
construction of short

vectors in a lattice.

The new algorithm approximates the length of the shortest non-zero

lattice vector much better than any previous practical algorithm. For
a lattice of

dimension n the new method runs in time O(n^3 (k/4)^(k/4) + n^4)
and finds a

lattice vector to within a factor (k/4)^(n/(2k)) of the length of the
shortest non-zero lattice

vector. The constant k can be chosen arbitrarily, 31 < k < n.
Compared to previous practical

algorithms the new method reduces the approximation factor achievable
in a given time to

less than its 4-th root.

The new algorithm is space efficient, its time bound is based
on

reasonable heuristics.

The new algorithm will have an impact on the security of cryptosystems

related to lattice problems.

We also present a sieve algorithm inspired by the recent algorithm
of

Ajtai, Kumar, Sivakumar

[AKS01].

12.00 Prof. Dr. Jung Hee Cheon (ICU, Taejon, Korea):

"Public-key cryptosystems on non-commutative algebraic structures"

*Abstract: *In abelian groups, we have three classes of hard problem,
Discrete Logarithm Problem (DLP), Diffie-Hellman Problem(DHP) and Decisional
Diffie-Hellman Problem (DDHP). In this talk, we introduce the analogue
of three problems, DL-type Conjugacy Problem (DLCP), DH-type Conjugacy
Problem (DHCP) and DDH-type

Conjugacy Problem (DDHCP), in non-abelian groups, and investigate their
complexities via representations. Especially, we propose a polynomial time
algorithm of DDHCP in braid groups. Moreover, we show that the gap problem
between DHCP and DDHCP can be used to design provable encryption scheme

and signature scheme in non-abelian groups.

14.30 Prof. Dr. S. Blackburn (London):

"Yamamura's Cryptosystem based on Group Actions: A Cryptanalysis"

*Abstract: *The talk will describe a public key cryptostystem
recently proposed by

Yamamura, which is based on the action of SL(2,Z) on the upper half
plane.

A cryptanalysis of this system (joint work with Steven Galbraith) will
be

described, and plausible arguments will be given why similar systems
would

also be insecure.

15.45 Prof. Dr. J. Patarin (Louveciennes):

"Quartz, McEliece and Dragons : comparison of the three candidates
for very short public key signature schemes"

17.00 Prof. Dr. N. Courtois (Louveciennes):

"The security of Hidden Field Equations"

20.00 Geselliges Zusammensein (Informal Meeting):

at Gaststätte Lottental, Schänke (downstairs), Grimbergstr.52,
Bochum-Stiepel

Friday, Nov. 9:

9.30 Prof. Dr. L. Goubin (Louveciennes):

"Algebraic systems with more unknowns than equations: applications
to signature schemes"

10.45 Prof. Dr. Phong Nguyen (Paris):

"The two faces of lattices in cryptology"

*Abstract:* Lattices are regular arrangements of points

in n-dimensional space, whose study appeared in the 19th century

in both number theory and crystallography.

Since the appearance of the celebrated Lenstra-Lenstra-Lovasz

lattice basis reduction algorithm twenty years ago, lattices have had

surprising applications in cryptology.

Until recently, the applications of lattices to cryptology

were only negative, as lattices were used to break

various cryptographic schemes.

Paradoxically, several positive cryptographic applications of lattices

have emerged in the past five years: there now exist public-key

cryptosystems based on the hardness of lattice problems, and lattices

play a crucial role in a few security proofs.

We survey some examples of the two faces of lattices in cryptology.

12.00 Prof. Dr. R. Steinwandt (Karlsruhe):

"Some remarks on side-channel attacks on algebraic cryptosystems"

*Abstract: * When using a public key cryptosystem, often more
information is

available to an adversary than one might expect when

designing the system. E.g., the attacker may have access

to some "physical" information like the time required for

performing decryption operations or the power consumption of

a smartcard during a signature computation.

Using algebraic cryptosystems like Polly Cracker as example,

it is illustrated how such "side-channels" can sometimes be

exploited for revealing the secret data, even if the

underlying mathematical problem is considered as intractable.

14.30 Dr. Sang Jin Lee (Marseille):

"The trapdoor oneway functions in braid groups" [ps-file]

*Abstract:* Recently, the braid groups attracted many cryptographers

because the group elements can be encoded efficiently,

group operations can be performed very fast and moreover

the conjugacy problem is very simple but seems to be intractable.

In practice, the conjugacy problem was modified to meet

the requirements for the cryptographic applications.

We discuss the influence of these modifications on security,

and some algebraic or dynamical properties that must be

taken care of when we modify the conjugacy problem.

15.45 Dr. M. Brenner (New York):

"Braid Group: Word and Conjugacy Problems in Web Security"

*Abbreviated Abstract:*

Current and Proposed MITRE Research in Braid Groups and their

applications to Internet Security. Barriers to adaptation. Research

required to implement the techniques.

17.00 Prof. Dr. A. Myasnikov (Cuny, New York):

"Average Case Complexity of Algorithms in Groups"