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"