Roberto Avanzi
The cryptographic
marriage of Frobenius and Point Halving
Abstract:
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
Abstract:
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
group.
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
Abstract:
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
Abstract:
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
Abstract
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
Abstract
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
cryptography.
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
Abstract
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
Abstract
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
Abstract
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.
Abstract
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
TBA