Lorentz Center - Mathematics of Cryptology
  Current Workshop  |   Overview   Back  |   Home   |   Search   |     

    Mathematics of Cryptology

Hans Dobbertin
Roberto Avanzi

The cryptographic marriage of Frobenius and Point Halving



Let E be an elliptic curve over F, a finite field of 2^n elements.

The inverse operation of point doubling, called point halving, is up

to three times as fast as doubling.  Hence some authors have proposed

to perform a scalar multiplication by an "halve-and-add'' algorithm,

which is faster than the classical double-and-add method.


If the coefficients of the equation defining the curve lie in a small

subfield of F, one can use the Frobenius endomorphism tau of the field

extension to replace doublings.  The cost of tau is negligible if

optimal normal bases are used.  The scalar is then written in "base

tau'' and a "tau-and-add'' algorithm gives very good performance.


For elliptic Koblitz curves defined over F, we combine for the first

time the two ideas to achieve a novel decomposition of the scalar.

This gives a new scalar multiplication algorithm which is up to 14.29%

faster than the Frobenius method, *without* any additional

precomputation.  The complexity is carefully analyzed.


This is joint work with Mathieu Ciet and Francesco Sica.


Ronald Cramer

Secure encryption from hard subgroup membership problems



After briefly reviewing public-key crypto-systems and their security,

I'll discuss some recent results on practical public-key crypto-systems that

enjoy the highest level of security for such systems. This is joint work with

Victor Shoup (Courant Institute, NYU).


A Hash Proof System (HPS) is a new cryptographic primitive that enables

generic construction of a public-key crypto-system that withstands adaptively

chosen ciphertext attacks. Concrete instance of HPS can be constructed from

groups that admit certain convenient homomorphisms. Security is derived

from the hardness of distinguishing a given sub-group  from the rest of the



This leads to several new practical schemes. One example is based on

the classical Quadratic Residuosity Assumption, while another is based

on Paillier's Decision Composite Residuosity Assumption. The so-called

Cramer-Shoup scheme (1998), which is based on the Decisional

Diffie/Hellman assumption and which was up to now the only practical

public-key crypto-system proven to be secure against adaptive chosen

cipher-text attack in the standard cryptographic model, is also an

instance of the construction.


Hans Dobbertin

Some Mathematics Behind the Design of Block Ciphers



A core part in the design of block ciphers are substitution operations,

so-called S-boxes. Criteria for S-boxes such as high non-linearity for

instance are derived from the well-known linear attack and the

differtial attack. Power functions on finite fields of characteristic

two have been used to define S-boxes. A prominent example is the

"Advanced Encryption Standard" (AES), the successor of the former world

standard DES.

The mentioned criteria for S-boxes, in order to achieve high resistance

against attacks, then translate to issues located in well-established

mathematical disziplines: weight distribution of BCH codes, correlation

properties of binary sequences, Hasse bound for the number of points on

elliptic curves, and so on. It is an open problem whether the S-boxes in

AES are optimal with respect to fundamental cryptographic properties.


Gerhard Frey

Tentative title: Applications of pairings in cryptography


Alan Lauder

Computing zeta functions of hyperelliptic curves via deformations.


Gregor Leander

On codes, matroids and secure multi-party computation from

linear secret sharing schemes



Error correcting codes and matroids have been widely used in the study

of ordinary secret sharing schemes.


In this paper, we initiate the investigation of connections between

codes, matroids and a special class of secret sharing schemes, namely

multiplicative linear secret sharing schemes (LSSSs).  Such schemes

are known to enable multi-party computation protocols secure against

general ("non-threshold'') adversaries.


We start by showing a connection between self-dual codes, identically

self-dual matroids and ideal multiplicative LSSSs.


There is a known transformation that renders an LSSS multiplicative,

at the cost of a polynomial (in fact, constant) increase in its

complexity.  We conjecture that, in essence, a transformation to that

effect is possible without any such increase, at least for all ideal

LSSSs with self-dual access structures.


By the aforementioned connection, this in fact constitutes a

conjecture about matroid theory, since it can be re-stated in terms of

representability of identically self-dual matroids by self-dual codes.

We also present a new example of a large class of quite natural

self-dual access structures admitting ideal LSSSs and that is

consistent with our conjecture.


Finally, we consider a known open problem concerning strongly

multiplicative LSSSs, and shed some new (and perhaps pessimistic)

light on this problem. As opposed to the case of multiplicative LSSSs,

it is not known whether there is a similar efficient transformation in

the case of strongly multiplicative LSSSs.


Using a suitable generalization of the well-known Berlekamp-Welch

decoder, we show that all strongly multiplicative LSSSs enable

efficient reconstruction of a shared secret in the presence of

malicious faults. On the positive side, certain (verifiable) secret

sharing schemes benefit from this result.


Joint work with R. Cramer, I. Gracia, Jorge Jiménez Urroz, Jaume

Martí-Farré and Carles Padró.


Arjen Lenstra

Integer factorization and cryptology



In this talk I will discuss the developments in integer

factorization since the invention in 1976 of the RSA

public key cryptosystem, and the impact of these developments

on practical applications of RSA. Particular attention

will be paid to recently proposed hardware factoring

devices such as TWIRL.


Hendrik Lenstra

Tentative: Recent developments in primality testing


Ueli Maurer

Probability Theory in Cryptography



While algebra is perhaps the most important branch of mathematics used

in the *design* of cryptographic systems, probability theory is the

most important branch of mathematics for the *analysis* of

cryptographic systems. Every reasonable security definition is

formulated in probability-theoretic terms, and most security proofs can

be seen as probability-theoretic theorems, in some cases proved using

information theory. This is true even in many cases where the security

relies on computational assumptions such as the hardness of factoring

integers. We take a look at the role of probability theory in


Our focus is on security proofs of cryptosystems *not* relying on

computational assumptions, i.e., cryptosystems secure even against a

computationally unbounded adversary. We describe some of the classical

impossibility results, starting from Shannon's theorem, as well as a

number of results showing that unconditional security is possible. The

topics include the bounded-storage model, secret-key agreement by

public discussion, several open research issues, as well as recent

results on security proofs against quantum adversaries of classical

(non-quantum) unconditionally secure systems.


Phong Nguyen

New results on lattice-based cryptography



We survey recent results on the security of lattice-based cryptosystems,

more precisely on the Goldreich-Goldwasser-Halevi cryptosystem

and the NTRU cryptosystem.


Rene Schoof

Construction of Weil and Tate pairings.


Igor Shparlinski

Playing "Hide-and-Seek'' in Finite Fields:

Hidden Number Problem and Its Applications



We describe several recent results  on the hidden number

problem  introduced by Boneh and Venkatesan in 1996.

The method is based on a rather surprising, yet powerful, combination

of two famous number theoretic techniques:   bounds of

exponential sums and  lattice reduction  algorithms.

This combination has led to a number of cryptographic

applications, helping to make rigorous several heuristic

approaches. It provides a two edge sword which can be used

both to prove certain security results and  to design

rather powerful attacks.


The examples of the first group include results about the

bit security  of the Diffie-Hellman key exchange system,

of the Shamir message passing scheme and of the XTR and LUC

cryptosystems. The examples of the second  group include

attacks on the Digital Signature Algorithm and its

modifications which are provably insecure under

certain conditions.


Martijn Stam

Primitive Sets in Number Fields for Absolutely Optimal Black

Box Secret Sharing



A black box secret sharing scheme (BBSSS) for a threshold access

structure is a linear secret sharing scheme that works for any finite abelian

group.  Introduced by Desmedt and Frankel, the problem has been

rigourously analyzed by Cramer and Fehr.


BBSSS can be based on number fields with certain properties.  The

approach by Desmedt and Frankel relies on number fields with large

Lenstra constant, i.e.,number fields over which a "large'' invertible

Vandermonde matrix exists.  The best known choices for these number

fields lead to BBSSS with expansion factor O(n), where n is the number

if players. The expansion factor corresponds to the length of each

share, i.e., the number of group elements received from the dealer by

each player.  The solution of Cramer and Fehr achieves expansion

factor O(log n), which is asymptotically optimal. It relies on low-degree

number fields over which a pair of "large'' Vandermonde matrices exists

whose determinants are co-prime.


We propose a new approach which aims at achieving an *absolutely*

optimal solution. Our approach is based on low-degree number fields

containing a "large primitive set.'' We do not know how to construct

these number fields for an arbitrary extension degree, but for smaller

degree the existence has been shown by computer experiments.


Joint work with Ronald Cramer.


Jacques Stern

When provable security meets number theory.



In this talk, I will discuss the methodology of provable

security in the design and analysis of cryptographic algorithms and

give several examples where it requires the use of

tools from number theory.


Peter Stevenhagen

Constructing elliptic curves with a given number of points.


Frederik Vercauteren

p-adic algorithms for counting points on elliptic curves


Ronald Cramer

Secure encryption from hard subgroup membership problems.


Bas Edixhoven

A possible generalisation of Schoof's algorithm.


Berry Schoenmakers