Seminar
2004-2005
Standard Seminar
October 6, 2004.
Jorge L. Villar. La aritmética
módulo $n^2$ y su
aplicación al diseño de
criptosistemas de cifrado
October 20, 2004. Germán
Sáez. New Identity-Based Ring
Signature Schemes
October 27, 2004. David Galindo. The Exact Security of Pairing Based
Encryption and Signature Schemes
November 3, 2004. Javier Herranz. Esquemas de firma digital y su seguridad.
El ejemplo de RSA
November 10, 2004 and November 24, 2004.
Marc Heymann. Universally Composable
Security: A New Paradigm for Cryptographic Protocols
November 17, 2004. Jorge L. Villar. Universal Hash Proof Systems from Group
Actions.
December 1, 2004. Jordi Pujolàs. Some highlights from The 8th Workshop on Elliptic Curve
Cryptography
December 15, 2004. Carles
Padró. Ideal secret sharing
schemes whose minimal
qualified subsets have at most three participants
December 22, 2004. Javier Herranz. New ID-Based Ring Signatures for General
Families of Signing Subsets
January 19, 2005. Jorge L. Villar. An instantiation of the Cramer-Shoup
encryption paradigm using bilinear map groups
January 26, 2005. Germán
Sáez. New Proposals for
Self-Healing Key Distribution Schemes
February 23, 2005. Jorge L. Villar.
A paper by Jens Groth: Cryptography
in Subgroups of $Z_n^*$
March 16, 2005. Jordi Pujolàs. Distortion maps in genus two
Seminar of the CRM Research Thematic Semester on Contemporary
Cryptology
March 10-11, 2005. Gerhard Frey and other
speakers. Seminar on Geometric
Methods in Cryptography
March 30, 2005. Javier Herranz. Identity-Based (Ring) Signatures from RSA
April 6, 2005. Josep M. Miret. Halving and trisecting points of an
elliptic curve over a finite field
April 13, 2005. Antonio Acín. Quantum Cryptography
April 20, 2005. David
Galindo. Boneh-Franklin identity
based encryption revisited
April 27, 2005. Javier López. Anonymous attribute certificates, or how to
merge anonymity and authorization services
May 3, 2005. Bas Edixhoven. How fast can one compute Ramanujan's
tau-function?
May 11, 2005. Tatsuaki Okamoto. A Universally Composable Secure Channel
Based on the KEM-DEM Framework
May 18, 2005. Juan A. Garay. Fair Multi-Party Computation
June 1, 2005. Victor Rotger. Pairings and distortion maps
June 14, 2005. Carles Padró. Matroids and ideal secret sharing schemes
June 15, 2005. Serge Fehr. Quantum Cryptography. Achieving Security by
Restricting the Attacker's Memory
June 29, 2005. Robbert de Haan. More efficient secure multiplication of
secrets
July 6, 2005. Pascal Paillier. Discrete-Log-Based Signatures May Not Be
Equivalent to Discrete Log
July
13, 2005. Alexandra Boldyreva. Analysis
of Random Oracle Instantiation Scenarios for OAEP and other Practical
Schemes
July 18, 2005. Ronald Cramer. Black-box secret sharing from primitive
sets in algebraic number fields
July 20, 2005. Marc Fischlin. Communication-Efficient Non-Interactive
Proofs of Knowledge with Online Extractors
Junior Seminar
These sessions of the seminar are addressed to PhD students. They form
an introductory course to the current research topics in our group.
November 2, 2004. Marc Heymann. Universal
Composability
November 22 and 29, 2004; December 13 and 20, 2004; and January
17, 2005. Jorge L. Villar. Modelos
de seguridad de criptosistemas de cifrado de clave pública
January 24, 2005. Carles
Padró. Introducció
a la
Teoria de la Informació
Jorge
L. Villar. Universitat
Politècnica de Catalunya.
La aritmética módulo
$n^2$ y su aplicación al
diseño de criptosistemas de cifrado
Wednesday October 6, 2004, 11.30, Hall 204a, Building C3,
Campus Nord
Abstract
En los orígenes de la criptografía de clave
pública, la seguridad de un criptosistema se reducía a la
dificultad de recuperar el mensaje completo a partir del texto cifrado
(unidireccionalidad). Los principales criptosistemas eran RSA,
relacionado con el problema de factorizar enteros grandes, y ElGamal,
relacionado con el problema del logaritmo discreto. También se
diseñaron criptosistemas análogos, basados en curvas
elípticas.
La introducción del concepto de seguridad semántica, en
1984, obligó a investigar nuevos criptosistemas que alcanzaran
dicho nivel de seguridad. La aparición de los criptosistemas de
Okamoto-Uchiyama, en 1998, y especialmente el de Paillier, en 1999,
abrieron una nueva línea de diseño de criptosistemas
basados en las propiedades de la aritmética módulo $n^2$,
que culmina con la "elevación" de los criptosistemas
tradicionales tipo RSA a esquemas semánticamente seguros y
eficientes, sobre el anillo de enteros módulo $n^2$.
Sin embargo, el rápido avance en el diseño de nuevos
criptosistemas no ha ido acompañado del avance en las
técnicas de criptoanálisis, necesarias para una correcta
evaluación de la seguridad de dichos sistemas. En ese sentido,
no hay avances significativos desde el resultado de Coppersmith, de
1996.
Return
to the top of this page
Germán
Sáez. Universitat Politècnica de Catalunya
New Identity-Based Ring Signature
Schemes
Wednesday October 20, 2004, 11.30, Hall 204a, Building C3,
Campus Nord
Abstract
In identitiy-based (ID-based) cryptography, the public keys of the
users can be derived from their identities. Therefore, it is not
necessary to provide or to check digital certificates linking
identities with public keys. This results in an improvement of the
efficiency of the resulting cryptographic schemes, specially those ones
which involve many public keys.
This is the case of ring signature schemes, where a user anonymously
signs a message on behalf of a set of users including himself. The
verifier is convinced that some member of the set is the author of the
signature, but he does not have any information about who he really is.
In this work, we propose a new ID-based ring signature scheme, which is
in some way more efficient than the only previous proposal. We prove
its anonymity and unforgeability. Finally, we extend this scheme to
allow distributed ring signatures, where a subset of users cooperate to
compute a signature on behalf of a family of possible signing subsets.
Return
to the top of this pageJorge L. Villar
David
Galindo. Universitat
Politècnica de Catalunya.
The Exact Security of Pairing Based Encryption and Signature Schemes
Wednesday October 27, 2004, 11.30, Hall 204a, Building C3,
Campus Nord
Abstract
Bilinear pairings have been intensively used in the design of
cryptographic protocols during the last few years. For instance, short
signatures and non-interactive key exchange protocols have been
designed with them, and they appear as a key component for
identity-based cryptography.
Focusing on encryption and signature schemes built on bilinear
pairings, we look at the security reductions of some known
constructions. For any pair "scheme/security reduction", we deduce key
sizes to securely implement the schemes. It turns out that some
important protocols in the literature appear to be not as efficient as
one would wish, due to the lack of tightness of their security
reductions. Finally, we summarize current trends to obtain tight
security reductions and suggest some open problems.
Return
to the top of this page
Javier Herranz. Universitat
Politècnica de Catalunya.
Esquemas de firma digital y su
seguridad. El ejemplo de RSA
Wednesday November 3, 2004, 12.00, Hall 204a, Building C3,
Campus Nord
Abstract
Anonymous attribute
certificates, or how to merge anonymity and authorization services
En esta charla explicaremos qué es un esquema de firma digital,
detallando los protocolos que lo componen. Después, repasaremos
las diferentes nociones de seguridad que se pueden considerar para
estos esquemas, según el objetivo del atacante y según
los recursos que se ponen a disposición de dicho atacante.
Ejemplificaremos estos conceptos estudiando primero el esquema RSA
original propuesto en 1978 y los posibles ataques contra él.
Después repasaremos el esquema FDH-RSA (Full Domain Hash), que
es una modificación del esquema RSA original que garantiza su
seguridad en el ‘random oracle model’. Explicaremos el análisis
de seguridad de ese esquema (Bellare-Rogaway, 1996), así como
otros análisis o modificaciones posteriores que mejoran los
resultados sobre seguridad (Coron, 2000; Katz-Wang, 2003).
Return
to the top of this page
Marc Heymann.
Universitat Politècnica de Catalunya.
Universally Composable Security: A New
Paradigm for Cryptographic Protocols
Wednesday November 10, 2004 and Wednesday November 24, 2004,
12.00, Hall 204a, Building C3,
Campus Nord
Abstract
Primera sesión:
Estudiaremos el paradigma propuesto por Ran Canetti en 2001 para
definir seguridad de protocolos criptográficos, denominado
universally composable (UC) security. La propiedad más destacada
de las definiciones UC es que garantizan seguridad incluso cuando un
protocolo es compuesto con un conjunto arbitrario de protocolos, o
más general, cuando el protocolo es utilizado como componente de
un sistema arbitrario. En particular, las definiciones UC garantizan
seguridad incluso cuando se ejecuta una cantidad no acotada de
protocolos que están advesarialmente controlados.
En esta primera charla introduciremos el modelo matemático de
protocolo, funcionalidad ideal, seguridad y composición de
protocolos. En charlas posteriores mostraremos como formular
definiciones UC para casi cualquier tarea criptográfica.
Segunda sesión: En el
seminario anterior estudiamos el concepto de Universally Composable
Security, introducido por Ran Canetti en 2001. En esta charla veremos
el modelo híbrido de computación así como el
teorema de composición universal. Después estudiaremos
otros modelos computacionales donde el teorema sigue siendo
válido, y acabaremos viendo el diseño de funcionalidades
ideales para algunas tareas criptográficas, como son los
esquemas de cifrado, commitments, etc.
Return
to the top of this page
Jorge L. Villar. Universitat
Politècnica de Catalunya
Universal Hash Proof Systems from
Group Actions
Wednesday November 17, 2004, 12.00, Hall 204a, Building C3,
Campus Nord
Abstract
In 2002, Cramer & Shoup introduced the notion of Universal
Hash Proof System, and gave a general construction based on abelian
groups, for which 3 instances were described.
In this session, another general construction, based on (no
necessarily) abelian groups acting on sets, is given. No instances of
this contructions are known, except for the ones derived by rewriting
the abelian constructions.
Return
to the top of this page
Jordi
Pujolàs. Universitat Politècnica de Catalunya
Some highlights from The 8th Workshop on Elliptic Curve
Cryptography
Wednesday December 1, 2004, 12.00, Hall 204a, Building C3,
Campus Nord
Abstract
We will focus on three of the contributions presented in the
workshop:
- P. Gaudry. Discrete Logarithm in Elliptic Curves Over Extension
Fields of Small Degree
- M. Joye. Secure Implementation of Elliptic Curve Cryptography
- I. Shparlinski. Pseudorandom Points on Elliptic Curves
Return
to the top of this page
Carles
Padró. Universitat
Politècnica de Catalunya
Ideal secret sharing schemes whose
minimal qualified subsets have at most three participants
Wednesday December 15, 2004, 12.00, Hall 204a, Building C3,
Campus Nord
Abstract
The characterization of the access structures of ideal secret
sharing schemes, which is one of the main open problems in secret
sharing, has important connections with Matroid Theory. To be related
to a matroid in a certain way is a necessary condition for an access
structure to be ideal. The rank of an access strucure is the maximum
cardinality of a minimal qualified subset. We present in this talk some
new results on the characterization of the ideal access structures with
rank three. First, we give a complete characterization of the
matroid-related access structures in that family. Second, we present a
bound on the optimal information rate of the rank three access
structures that are not matroid-related.
Return
to the top of this page
Javier Herranz. Universitat
Politècnica de Catalunya
New ID-Based Ring Signatures for
General Families of Signing Subsets
Wednesday December 22, 2004, 12.00, Hall 204a, Building C3,
Campus Nord
Abstract
In a distributed ring signature scheme, a subset of users
cooperate to compute a distributed anonymous signature on amessage, on
behalf of a family of possible signing subsets. The receiver can verify
that the signature comes from a subset of the family, but he cannot
know which subset has actually signed.
In this seminar we will explain and analyze (correctness, anonymity and
unforgeability) a new distributed ring signature scheme, which uses the
concept of dual access structures, and which works with general
families of possible signing subsets. Although we will explain a
particular case for identity-based scenarios, the scheme can be
extended to more general cases.
Return
to the top of this page
Jorge L. Villar. Universitat
Politècnica de Catalunya
An instantiation of the Cramer-Shoup
encryption paradigm using bilinear map groups
Wednesday January 19, 2005, 12.00, Hall 204a, Building C3,
Campus Nord
Abstract
A new instantiation of the Cramer-Shoup paradigm for secure
encryption is presented, which is built using bilinear map groups. The
security is based on the Decisional Bilinear Diffie-Hellman assumption.
We also apply to our construction the recent efficiency improvements
introduced by Kurosawa and Desmedt (and refined later by Gennaro and
Shoup).
Return
to the top of this page
Germán
Sáez. Universitat Politècnica de Catalunya
New Proposals for Self-Healing Key
Distribution Schemes
Wednesday January 26, 2005, 12.00, Hall 204a, Building C3,
Campus Nord
Abstract
Self-healing key distribution schemes enable a large and dynamic
group of users to establish a group key over an unrealiable network. A
group manager broadcast in every session some packet of information in
order to provide a key to each member of the session group. The goal of
self-healing key distribution schemes is that even if in a certain
sesion the broadcast is lost, the group member can recover the key from
the broadcast packet received before and after the session. In this
work we provide new definitions and proposals of self-healing key
distribution schemes.
Return
to the top of this page
Jorge L. Villar. Universitat Politècnica de
Catalunya
A paper by Jens Groth: Cryptography in
Subgroups of $Z_n^*$
Wednesday February 23, 2005, 12.00, Hall 204a, Building C3,
Campus Nord
Abstract
A new problem related to the hardness of recognizing small
subgroups of $Z_n^*$ have been introduced by Jens Groth, at TCC 2005.
Also, two signature schemes, a homomorphic commitment scheme and an
encryption scheme are described.
Return
to the top of this page
Gerhard Frey.
Institut für Experimentalle Mathematik, Essen
Seminar on Geometric Methods in
Cryptography
Thursday March 10, 2005, Hall C1/034, CRM, Bellaterra
Friday March 11, 2005, Hall 001, FME, Universitat Politècnica de
Catalunya
Program
Thursday March 10, 2005
11.00-12.00 Ramiro Moreno, Univeristat de Lleida. Subgrupos de Sylow de curvas
elípticas definidas sobre cuerpos finitos
12.15-13.15 Gerhard Frey, Institut für Experimentalle
Mathematik, Essen. Realization of
Discrete Logarithms in Ideal Class Groups
15.15-16.15 Jordi Pujolàs, Universitat Politècnica
de Catalunya. Distortion Maps in
Genus 2
16.30-17.30 Gerhard Frey. Transfer
by the Lichtenbaum Pairing to Brauer Groups
Friday March 11, 2005
11.00-12.00 Tanja Lange, Technical University of Denmark, Copenhagen. Pairing computation on non-supersingular
hyperelliptic curves
12.30-13.30 Gerhard Frey. Index-Calculus
in Brauer groups of local and global fields
More information in the CRM web page
(follow the links "Research programmes" and "Contemporary Cryptology").
Return
to the top of this page
Jordi Pujolàs. Universitat
Politècnica de Catalunya
Distortion maps in genus two
Wednesday March 16, 2005, 12.00, Hall 204a, Building C3,
Campus Nord
Abstract
I will show how to solve the DDH problem for certain curves of
genus two. For this one uses pairings. Distortion maps are related to
non trivial values of pairings. I will define them and will give some
examples.
Return
to the top of this page
Javier Herranz. Universitat
Politècnica de Catalunya
Identity-Based (Ring) Signatures from
RSA
Wednesday March 30, 2005, 12.00, Hall 204a, Building C3,
Campus Nord
Abstract
Guillou and Quisquater sketched in 1988 an identity-based
signature scheme, constructed from an identification protocol, whose
security relies on the RSA problem. In this work we explicitly detail
the protocols of this signature scheme and later we formally prove its
exact security, employing the well-known forking lemmas as suggested by
Pointcheval and Stern.
Using similar ideas, we design and analyze a ring signature scheme and
a distributed ring signature scheme for identity-based scenarios whose
security is based on the hardness of the RSA problem. These are the
first identity-based ring signature schemes with do not employ bilinear
pairings. Furthermore, the resulting schemes satisfy an interesting
property: the real author of a ring signature can later open the
anonymity and prove that he is actually the person who signed the
message.
Return
to the top of this page
Josep M. Miret.
Universitat de Lleida
Halving and trisecting points of an
elliptic curve over a finite field
Wednesday April 6, 2005, 12.00, Hall 204a, Building C3,
Campus Nord
Abstract
Given an elliptic curve over a finite field, we present a
polynomial time algorithm to determine the order and the structure,
including generators, of the 2-Sylow subgroup. A successive halving
points process (each of them consisting in solving two quadratic
equations), along with a suitable choice of points at each level,
allows us to reach points whose order is the maximum 2-power. Likewise,
we will see a new version of this algorithm to find out the 3-Sylow
subgroup by using, in this case, an inductive trisecting points process
(by means of the resolution of two cubic equations). Finally, we will
show a Meyer-Muller cryptosystem variant whose encryption process is
based on tripling points instead of doubling them.
Return
to the top of this page
Antonio
Acín. Institut de
Ciències Fotòniques, Universitat Politècnica
de Catalunya
Quantum Cryptography
Wednesday April 13, 2005, 12.00, Hall 204a, Building C3,
Campus Nord
Abstract
Quantum Cryptography is the most successful Quantum Information
application due to its feasibility using present-day technology. It
combines different aspects from Theoretical and Applied Physics,
Information Theory and Engineering. This talk gives an overview of
Quantum Cryptography, with an emphasis on theoretical proposals of key
distribution protocols and their security proofs.
Return
to the top of this page
David Galindo. Radboud
University Nijmegen
Boneh-Franklin identity based
encryption revisited
Wednesday April 20, 2005, 12.00, Hall 204a, Building C3,
Campus Nord
Abstract
The first practical identity based encryption (IBE) scheme was proposed
by Boneh and Franklin. In this work we point out that there is a flawed
step in the security reduction exhibited by the authors. Fortunately,
it is possible to fix it without changing the scheme neither the
underlying assumption. In the second place, we introduce a variant of
the seminal IBE scheme which allows a more efficient security
reduction. The new scheme is simpler, and has more compact ciphertexts
than Boneh-Franklin's proposal, while keeping the computational cost.
Finally, we observe that the flawed step pointed out here is present in
several works, and that our techniques can be applied to obtain tighter
reductions for previous relevant schemes.
Return
to the top of this page
Javier López. Universidad de
Málaga
Anonymous attribute certificates, or
how to merge anonymity and authorization services
Wednesday April 27, 2005, 12.00, Hall 204a, Building C3,
Campus Nord
Abstract
Special attention has been paid during last years to the fact that many
of the operations and transactions that are part of Internet
applications can be easily recorded and collected. Consequently,
anonymity is more than ever a desirable feature for many scenarios. On
the other hand, authorization has become a key service for distributed
applications, and new solutions have been proposed enhancing the
traditional authorization schemes of centralized applications. One may
consider that the authorization service, which is based on
authentication, and the anonymity service are concepts in conflict.
That is, how can we decide if a user is authorized to perform an
operation if at the same time the user does not want to reveal his
identity?
We will explain in this seminar a solution that we have developed to
make both services compatible. The solution is based on the attribute
certificates standards proposed by ITU-T. We have extended the
functionality of those certificates by using fair blind signatures and
traceable signatures schemes, presented at Eurocrypt’95 and
Eurocrypt’04, respectively. The result is a novel family of certificate
structures that we have called anonymous attribute certificates. These
new types of certificates have been designed in a way that any user can
be authorized to perform the operations he is entitled for, without
reveling his identity. Additionally, the new structures designed still
follow the standard format recommended by ITU-T, thus can be easily
integrated into commercial Internet applications.
Return
to the top of this page
Bas Edixhoven. Leiden University
How fast can one compute
Ramanujan's tau-function?
Tuesday May 3, 2005, 12.00, Centre de Recerca Matemàtica
Abstract
Ramanujan's tau-function will be defined (very easy). I will explain
why I expect that for prime numbers p, one should be able to compute
tau(p) in time polynomial in log p, and I will indicate how far we are
from having all details written down. I will also explain why this is
of interest.
Return
to the top of this page
Tatsuaki Okamoto. NTT, Japan
A Universally Composable Secure Channel Based on the KEM-DEM Framework
Wednesday May 11, 2005, 12.00, Hall 204a, Building C3,
Campus Nord
Abstract
For ISO standards on public-key encryption, Shoup introduced the
framework of KEM and DEM for formalizing and realizing one-directional
hybrid encryption; KEM is a formalization of asymmetric encryption
specified for key distribution, and DEM is a formalization of symmetric
encryption. This paper investigates a more general hybrid protocol,
secure channel, using KEM and DEM, such that KEM is used for
distribution of a session key and DEM, along with the session key, is
used for multiple bi-directional encrypted transactions in a session.
In this talk it is shown that IND-CCA2 secure KEM and IND-P2-C2 secure
DEM along with secure signatures and ideal certification authority are
sufficient to realize a universally composable (UC) secure channel. To
obtain the main result, several equivalence results are also shown: UC
KEM, IND-CCA2 KEM and NM-CCA2 KEM are equivalent, and UC DEM, IND-P2-C2
DEM and NM-P2-C2 DEM are equivalent.
Return
to the top of this page
Juan A. Garay. Bell Labs - Lucent
Technologies
Fair Multi-Party Computation
Wednesday May 18, 2005, 12.00, Hall 204a, Building C3,
Campus Nord
Abstract
Secure multi-party computation (MPC) has been one of the most
fundamental problems in cryptography. At a high level, the problem is
concerned with n parties,
each holding a private input, that want to compute a function of those
inputs so that each party learns its own output, but no other
information is revealed, even in the presence of malicious parties that
may deviate arbitrarily from the protocol. Instances of MPC include
password authentication, distributed auctions, contract signing,
on-line bidding, etc.
MPC is called ``fair'' if either all the parties learn the outuput of
the function being computed, or nobody does. A well-known result due to
[Cleve'86] shows that fair MPC is impossible when a majority of the
parties are corrupted (which in particular applies to the case of two
parties and one corruption). In this talk, we show how to circumvent
this impossibility result, and present fair MPC constructions that
tolerate up to (n - 1)
corruptions. The constructions make use of some recent results in
timed-release cryptography.
Return
to the top of this page
Victor Rotger. Universitat
Politècnica de Catalunya
Pairings and distortion maps
Wednesday June 1, 2005, 12.00, Hall 204a, Building C3,
Campus Nord
Return
to the top of this page
Carles
Padró. Universitat Politècnica de Catalunya
Matroids and ideal secret sharing
schemes
Tuesday, June 14, 2005, 17'00, Room C1-028 CRM
Abstract
The aim of this talk is to present and discuss some recent
results and several open problems about the characterization of the
access structures of ideal secret sharing schemes. It is well known
that Matroids play a key role in that characterization. Specifically,
the most important problems are to determine which access structures
are matroid-related and which matroids can be represented by an ideal
secret sharing scheme (or ss-represented). Some important results and
techniques on this latter question were given by Simonis and Ashikhmin
(1998) and by Matus (1999).
We deal with the characterization of the ideal access structures whose
minimal qualified subsets have at most three participants. We
characterize all the structures in that family that are matroid-related
and we prove that the optimal information rate of a non-matroid-related
access structure in that family is at most 2/3. Moreover, we prove that
if such an structure is related to a matroid with rank greater than 3,
then it can be realized by a vector space secret sharing scheme.
Therefore, the only question to be solved is to determine which
matroids with rank 3 can be ss-represented.
The value 2/3 appear as an upper bound for non-matroid-related access
structures in many previously studied families. So, we wonder to which
extend this result can be generalized and we discuss how polymatroids
could be used to answer this question. Another open question is to find
bounds on the optimal information rate of the access structures that
are related to non-ss-representable matroids.
Return
to the top of this page
Serge Fehr. CWI, Amsterdam
Quantum Cryptography. Achieving
Security by Restricting the Attacker's Memory
Wednesday June 15, 2005, 12.00, Hall 204a, Building C3,
Campus Nord
Abstract
Most of todays cryptography relies on unproven complexity
assumptions (like the hardness of factoring large numbers) in
combination with the assumption that an attacker has not overwhelming
computing power. This approach leads to very practical schemes but has
its obvious dangers.
It has been shown in the early 80's that with the use of quantum
mechanics, certain cryptographic problems can be solved
unconditionally, i.e., without any (unproven) assumption:
Quantum-cryptography, and with it the hope that (m)any cryptographic
task(s) can be solved this way, was born.
This hope was smashed in the late 90's, when it was shown that any
non-trivial cryptographic task involving two mutually distrusted
parties cannot be done unconditionally by means of
quantum-cryptography. As a consequence, research shifted towards
schemes which are secure against attackers with limited
quantum-computational power. This approach though is bound again to
rely on unproven complexity assumptions.
We propose a new approach to circumvent the above impossibility result,
namely to construct quantum-cryptographic schemes which are secure
under the sole assumption that the attacker's quantum memory is
limited. This is motivated by the fact that storing even a single qubit
for more than a fraction of a second seems to be out of reach with
today's technology. In this talk, we present a scheme for
1-2-Oblivious-Transfer, an important cryptographic primitive, which is
proven secure in this sense. The scheme is such that it can be
implemented with current technology.
Return
to the top of this page
Robbert de Haan.
CWI, Amsterdam
More efficient secure multiplication
of secrets
Wednesday June 29, 2005, 12.00, Hall 204a, Building C3,
Campus Nord
Abstract
Following the discovery of Shamir´s threshold secret
sharing scheme, Franklin and Yung have proposed a scheme that allows a
group of n players to
multiply a number of secrets in parallel in a manner that leaks no
information to any subgroup of t players, at the cost of some
additional restrictions on the fraction of cheating players. In this
talk, we present a similar algorithm that allows players to perform
multiplication of two secret elements in an extension field using only
arithmetic in the base field. Both techniques are suitable for use in
an ongoing computation, as both before and after the multiplication all
the users will have consistent shares in the secret(s).
Return
to the top of this page
Pascal Paillier.
Gemplus, France
Discrete-Log-Based Signatures May Not
Be Equivalent to Discrete Log
Wednesday July 6, 2005, 12.00, Hall 204a, Building C3,
Campus Nord
Abstract
We provide evidence that the unforgeability of several discrete-log
based signatures such as Schnorr signatures *cannot* be equivalent to
the discrete log problem in the standard model. This contradicts in
nature well-known proofs standing in weakened proof methodologies, in
particular proofs employing various formulations of the Forking Lemma
in the random oracle model. Our impossibility proofs apply to many
discrete-log-based signatures like ElGamal signatures and their
extensions, DSA, ECDSA and KCDSA as well as standard generalizations of
these, and even RSA-based signatures like GQ.
All known reductions attesting the unforgeability of Fiat-Shamir
transformed signatures in the random oracle model lead to a loss factor
close to q_h in terms of execution time or success probability (q_h
denotes the number of oracle queries). There exists no proof that this
loss factor is necessary. We prove, however, that any
random-oracle-based reduction from computing the discrete logarithm to
forging Schnorr signatures must lose at least a factor close to the
square root of q_h. We further conjecture that the 1/q_h loss is
optimal. In any case, we results show that a proof of equivalence in
the ROM (if algebraic) will *never be tight*. We believe our work sheds
a new perspective as to why no efficient proof of equivalence to the
discrete log problem has ever been found for Schnorr signatures despite
considerable research efforts. We stress that our work sheds more light
on the provable (in)security of popular signature schemes but does not
explicitly lead to actual attacks on these.
Return
to the top of this page
Alexandra
Boldyreva. Georgia Institute of Technology, USA
Analysis
of Random Oracle Instantiation Scenarios for OAEP and other Practical
Schemes
Wednesday July 13, 2005, 12.00, Hall 204a, Building C3,
Campus Nord
Abstract
We investigate several previously suggested scenarios of
instantiating random oracles (ROs) with ``realizable'' primitives in
cryptographic schemes. As candidates for such ``instantiating''
primitives we pick perfectly one-way hash functions (POWHFs) and
verifiable pseudorandom functions (VPRFs). Our analysis focuses
on the most practical encryption schemes such as OAEP and its variant
PSS-E and the Fujisaki-Okamoto hybrid encryption scheme. We also
consider the RSA Full Domain Hash (FDH) signature scheme. We first show
that some previous beliefs about instantiations for some of these
schemes are not true. Namely we show that, contrary to Canetti's
conjecture, in general one cannot instantiate either one of the two ROs
in the OAEP encryption scheme by POWHFs without losing security. We
also confirm through the FDH signature scheme that the straightforward
instantiation of ROs with VPRFs may result in insecure schemes, in
contrast to regular pseudorandom functions which can provably replace
ROs (in a well-defined way). But unlike a growing number of papers on
negative results about ROs, we bring some good news. We show that one
can realize one of the two ROs in a variant of the PSS-E encryption
scheme and either one of the two ROs in the Fujisaki-Okamoto hybrid
encryption scheme through POWHFs, while preserving the IND-CCA security
in both cases (still in the RO model). Although this partial
instantiation in form of substituting only one RO does not help to
break out of the random oracle model, it yet gives a better
understanding of the necessary properties of the primitives and also
constitutes a better security heuristic.
Return
to the top of this page
Ronald Cramer.
CWI Amsterdam
Black-box
secret sharing from primitive sets in algebraic number fields
Monday July 18, 2005, 12.00, Hall 005, Building C3,
Campus Nord
Abstract
A black-box secret sharing scheme (BBSSS) for a given access structure
works in exactly the same way over any finite Abelian group, as it only
requires black-box access to group operations and to random group
elements. In particular, there is no dependence on e.g. the structure
of the group or its order. The expansion factor of a BBSSS is the
length of a vector of shares (the number of group elements in it)
divided by the number of players n. At CRYPTO 2002 Cramer and Fehr
proposed a threshold BBSSS with an asymptotically minimal expansion
factor \Theta(\log n). We present a BBSSS that is based on a new
paradigm, namely, primitive sets in algebraic number fields. This leads
to a new BBSSS with an expansion factor that is absolutely minimal up
to an additive term of at most~2, which is an improvement by a constant
additive factor. The construction uses techniques from algebraic number
theory as well as algebraic geometry.
We provide good evidence that our scheme is considerably more efficient
in terms of the computational resources it requires. Indeed, the number
of group operations to be performed is \tilde{O}(n2) instead of
\tilde{O}(n3) for sharing and \tilde{O}(n^{1.6}) instead of
\tilde{O}(n^{2.6}) for reconstruction. Finally, we show that our
scheme, as well as that of Cramer and Fehr, has asymptotically optimal
randomness efficiency.
Return
to the top of this page
Marc Fischlin. ETH
Zurich
Communication-Efficient
Non-Interactive Proofs of Knowledge with Online Extractors
Wednesday July 20, 2005, 11.00, Hall 204a, Building C3,
Campus Nord
Abstract
We show how to turn three-move proofs of knowledge into non-interactive
ones in the random oracle model. Unlike the classical Fiat-Shamir
transformation our solution supports an online extractor which outputs
the witness from such a non-interactive proof instantaneously, without
having to rewind or fork. Additionally, the communication complexity of
our solution is significantly lower than for previous proofs with
online extractors. We furthermore give a superlogarithmic lower bound
on the number of hash function evaluations for such online extractable
proofs, matching the number in our construction, and we also show how
to enhance security of the group signature scheme suggested recently by
Boneh, Boyen and Shacham with our construction.
Return to the top of this page
Back to
MAK's
main page
Last Update: July 18, 2005