Seminar 2002-2003

 A Practical Public Key Cryptosystem from Paillier and Rabin Schemes

Dimecres 2 d'octubre de 2002, 12 del migdia, sala 204a (Biblioteca de Matemàtiques), Mòdul C3, Campus Nord

Abstract

We present a practical scheme based on factoring and semantically secure (IND-CPA) in the standard model. The scheme is obtained from a modification of the so called RSA-Paillier scheme. This modification is reminiscent from the ones applied by Rabin and Williams to the well-known RSA cryptosystem. Thanks to the special properties of such schemes, we obtain efficiency similar to that of RSA cryptosystem, provably secure encryption (since recovering plaintext from ciphertext is as hard as factoring) and indistinguishability against plaintext attacks. We construct also a new trapdoor permutation based on factoring, which has interest on its own. Semantic security of the scheme is based on an appropiate decisional assumption, named as Decisional Small 2e-Residues assumption.  The robustness of this assumption is also discussed. Compared to Okamoto-Uchiyama's scheme, the previous IND-CPA cryptosystem in the standard model with one-wayness based on factoring, our scheme is drastically more efficient in encryption, and presents higher bandwith, achieving the same expansion factor as Paillier and ElGamal schemes. We believe the new scheme could be an interesting starting point to develop efficient IND-CCA schemes in the standard model with one-wayness based on factoring.

Return to the top of this page

The security of digital signature schemes

Dimecres 9 d'octubre de 2002, 12 del migdia, sala 204a (Biblioteca de Matemàtiques), Mòdul C3, Campus Nord

Abstract

In this talk, we review the different definitions of the security of a digital signature scheme, according to the resources available to the attacker, and according to the possible resulting forgery. The highest level of security is existential unforgeability under chosen message attacks. The security of signature schemes is usually proved by reducing it to a difficult mathematical problem.
We explain two of these schemes and their proofs of security:
(i) the classical RSA hash-and-invert signature scheme, which can be proved secure in the random oracle model, under the RSA Assumption;
(ii) the scheme of Gennaro, Halevi and Rabin, which can be proved secure in the standard model, but under a strongest assumption, the Strong RSA Assumption.

Return to the top of this page

Secret sharing schemes over the integers

Dimecres 9 d'octubre de 2002, 12 del migdia,  aula C3-005, Mòdul C3, Campus Nord

Abstract

In this talk we review some protocols for sharing a secret integer value among a set of players. Some examples are the random additive sharing or Shamir secret sharing scheme. Although they have been previously studied, the secret value had to satisfy some technical properties  to fit to specific proposals. We consider the sharing of a secret integer value s with no other restriction that the fact it lies in an interval [- K, K ]. We go through details of the proof of security of these protocols, which is not perfect but statistical.

Return to the top of this page

Improving the Efficiency of Some Dynamic Group Key Distribution Schemes (Joint work with Vanesa Daza and Javier Herranz)

Dimecres 11 de desembre de 2002, 12 del migdia, sala 204a (Biblioteca de Matemàtiques), Mòdul C3, Campus Nord

Abstract

In a dynamic group key distribution scheme, members of a group themselves generate private common keys, with the help of a group controller in an initialization phase. The system must enable the revocation and the addition of members to the group in the successive periods of time. The resulting scheme must be secure in front of an adversary who corrupts some users and wants to obtain the group key in an interval of time in which neither of the corrupted users belong to the group.

In  this work we present two families of dynamic group key distribution schemes by considering as a tool more general access structures than the threshold ones that Anzai et al. and Kurnio et al. use.We show some new specific group key distribution schemes which are more efficient than the original ones.

Return to the top of this page

Ideal multiplicative linear secret sharing schemes for self-dual access structures (Joint work with V. Daza, I. Gracia, J. Martí-Farre and J. Jiménez)

Dimecres 12 de març de 2003, 11.45 del matí, sala 204a (Biblioteca de Matemàtiques), Mòdul C3, Campus Nord

Abstract

Multiplicative linear secret sharing schemes play an important role in multiparty computation for general adversary structures. A wide new family of selfdual access structures that admit an ideal
multiplicative linear secret sharing scheme is presented

Return to the top of this page

Ring signatures (I)

Dimecres 19 de març de 2003, 11.45 del matí, sala 204a (Biblioteca de Matemàtiques), Mòdul C3, Campus Nord

Abstract

In a ring signature scheme, a signer in a subset (or ring) of potential signers produces a signature of a message in such a way that the receiver can verify that the signature comes from a member of the ring, but cannot know which member has actually signed.

In this seminar we give an overview of this topic: we explain the first proposals based on RSA and we introduce a new ring signature scheme for a discrete-log scenario, based on the Schnorr scheme. In the following seminar we will discuss the security of this proposal.

Return to the top of this page

Ring signatures (II)

Dimecres 26 de març de 2003, 12 del migdia, sala 204a (Biblioteca de Matemàtiques), Mòdul C3, Campus Nord

Abstract

In this talk we discuss the security of the ring signature scheme presented in the previous seminar. We prove first that the scheme is unconditionally anonymous (every member of the ring has the same probability to be the author of a ring signature).

Then, we prove the scheme to be existentially unforgeable under adaptive chosen-message attacks, in the random oracle model. To prove this fact, we generalize to the ring signatures' scenario the forking lemmas introduced by Pointcheval and Stern.

Return to the top of this page

Some reflections about One-Way functions and CCA security in the Random Oracle Model

Dimecres 9 d'abril, 23 d'abril i 30 d'abril de 2003, 12 del migdia, sala 204a (Biblioteca de Matemàtiques), Mòdul C3, Campus Nord

Abstract

Most of the existing cryptosystems that are IND-CCA secure in the Random Oracle Model (ROM) are based on one way trapdoor functions. Although their security in the ROM seems to be correctly proven, some flaws in the proofs can be found. This is the case of EPOC, as Dent recently pointed out.

In the first session, the basic definition of one-wayness is revisited. Some subtleries about encodings, samplability and recognisability of sets are taken into account. The second session will deal with probabilistic encryption, partial one-wayness and two lemmas related with the Random Oracle Model methodology. The third (and last) session will deal with IND-CCA security in the
ROM, reject timing attacks and the Fujisaki-Okamoto conversion.

Return to the top of this page

Identity-Based Encryption from the Weil Pairing

Dimecres 4 de juny de 2003, 12 del migdia, sala 204a (Biblioteca de Matemàtiques), Mòdul C3, Campus Nord

Abstract

We explain the first fully functional identity-based encryption scheme (IBE) which was proposed by Boneh and Franklin at Crypto 2001. The scheme has chosen ciphertext security in the Random Oracle Model assuming an elliptic curve variant of the computational DH problem. This system is based on bilinear maps between groups, and we briefly comment the features and other nice applications of these functions. Precise definitions for secure identity based encryption schemes are described.

Return to the top of this page

On the Security of Proxy Signature Schemes

Dimecres 11 de juny de 2003, 12 del migdia, sala 204a (Biblioteca de Matemàtiques), Mòdul C3, Campus Nord

Abstract

In a proxy signature scheme, a distributed entity delegates its signing capability to a distributed proxy entity, which signs messages on behalf of the original one. Most of the proposed proxy signature schemes do not have a formal proof of security, i.e. a reduction to a computationally hard problem. They have been considered secure until some attack against them has appeared.

In a recent work, Boldyreva, Palacio and Warinschi give precise definitions of the security requirements that such schemes must satisfy. They revise previous schemes and propose new ones which are proved secure under their formal definitions.

In this seminar, we explain some non-proved-secure proxy signature schemes and some attacks against them, and we comment the new definitions of security proposed by Boldyreva et al.

Return to the top of this page

Distributed Oblivious Transfer

Dimecres 4 de juliol de 2003, 12 del migdia, sala 204a (Biblioteca de Matemàtiques), Mòdul C3, Campus Nord

Abstract

By distributing the sender's task, one can obtain unconditional security in Oblivious Transfer. We review two recent papers on this topic (Naor-Pinkas Asiacrypt'00, Blundo-D'Arco-De Santis-Stinson SAC 2002).

Return to the top of this page

Last Update: June 30, 2003