marriage of Frobenius and Point Halving
E be an elliptic curve over F, a finite field of 2^n elements.
inverse operation of point doubling, called point halving, is up
three times as fast as doubling. Hence some authors have proposed
perform a scalar multiplication by an "halve-and-add'' algorithm,
is faster than the classical double-and-add method.
the coefficients of the equation defining the curve lie in a small
of F, one can use the Frobenius endomorphism tau of the field
to replace doublings. The cost of tau is negligible if
normal bases are used. The scalar is then written in "base
and a "tau-and-add'' algorithm gives very good performance.
elliptic Koblitz curves defined over F, we combine for the first
the two ideas to achieve a novel decomposition of the scalar.
gives a new scalar multiplication algorithm which is up to 14.29%
than the Frobenius method, *without* any additional
The complexity is carefully analyzed.
is joint work with Mathieu Ciet and Francesco Sica.
Secure encryption from
hard subgroup membership problems
briefly reviewing public-key crypto-systems and their security,
discuss some recent results on practical public-key crypto-systems that
the highest level of security for such systems. This is joint work with
Shoup (Courant Institute, NYU).
Hash Proof System (HPS) is a new cryptographic primitive that enables
construction of a public-key crypto-system that withstands adaptively
ciphertext attacks. Concrete instance of HPS can be constructed from
that admit certain convenient homomorphisms. Security is derived
the hardness of distinguishing a given sub-group from the rest of the
leads to several new practical schemes. One example is based on
classical Quadratic Residuosity Assumption, while another is based
Paillier's Decision Composite Residuosity Assumption. The so-called
scheme (1998), which is based on the Decisional
assumption and which was up to now the only practical
crypto-system proven to be secure against adaptive chosen
attack in the standard cryptographic model, is also an
of the construction.
Some Mathematics Behind the
Design of Block Ciphers
part in the design of block ciphers are substitution operations,
S-boxes. Criteria for S-boxes such as high non-linearity for
are derived from the well-known linear attack and the
attack. Power functions on finite fields of characteristic
been used to define S-boxes. A prominent example is the
Encryption Standard" (AES), the successor of the former world
mentioned criteria for S-boxes, in order to achieve high resistance
attacks, then translate to issues located in well-established
disziplines: weight distribution of BCH codes, correlation
of binary sequences, Hasse bound for the number of points on
curves, and so on. It is an open problem whether the S-boxes in
optimal with respect to fundamental cryptographic properties.
Tentative title: Applications of
pairings in cryptography
zeta functions of hyperelliptic curves via deformations.
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
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
We start by showing a connection
between self-dual codes, identically
self-dual matroids and ideal
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
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
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
Joint work with R. Cramer, I.
Gracia, Jorge Jiménez Urroz, Jaume
Martí-Farré and Carles Padró.
factorization and cryptology
talk I will discuss the developments in integer
since the invention in 1976 of the RSA
key cryptosystem, and the impact of these developments
practical applications of RSA. Particular attention
paid to recently proposed hardware factoring
such as TWIRL.
Tentative: Recent developments in
Theory in Cryptography
algebra is perhaps the most important branch of mathematics used
*design* of cryptographic systems, probability theory is the
important branch of mathematics for the *analysis* of
systems. Every reasonable security definition is
in probability-theoretic terms, and most security proofs can
as probability-theoretic theorems, in some cases proved using
theory. This is true even in many cases where the security
computational assumptions such as the hardness of factoring
We take a look at the role of probability theory in
is on security proofs of cryptosystems *not* relying on
assumptions, i.e., cryptosystems secure even against a
unbounded adversary. We describe some of the classical
results, starting from Shannon's theorem, as well as a
results showing that unconditional security is possible. The
include the bounded-storage model, secret-key agreement by
discussion, several open research issues, as well as recent
on security proofs against quantum adversaries of classical
unconditionally secure systems.
on lattice-based cryptography
recent results on the security of lattice-based cryptosystems,
precisely on the Goldreich-Goldwasser-Halevi cryptosystem
of Weil and Tate pairings.
"Hide-and-Seek'' in Finite Fields:
Number Problem and Its Applications
describe several recent results on the hidden number
introduced by Boneh and Venkatesan in 1996.
method is based on a rather surprising, yet powerful, combination
famous number theoretic techniques: bounds of
sums and lattice reduction algorithms.
combination has led to a number of cryptographic
helping to make rigorous several heuristic
It provides a two edge sword which can be used
prove certain security results and to design
examples of the first group include results about the
security of the Diffie-Hellman key exchange system,
Shamir message passing scheme and of the XTR and LUC
The examples of the second group include
on the Digital Signature Algorithm and its
which are provably insecure under
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
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.
provable security meets number theory.
talk, I will discuss the methodology of provable
in the design and analysis of cryptographic algorithms and
several examples where it requires the use of
from number theory.
elliptic curves with a given number of points.
algorithms for counting points on elliptic curves
encryption from hard subgroup membership problems.
generalisation of Schoof's algorithm.