## CryptoDB

### Jacques Stern

#### Publications

**Year**

**Venue**

**Title**

2008

EPRINT

Linear Bandwidth Naccache-Stern Encryption
Abstract

The Naccache-Stern (NS) knapsack cryptosystem is an original yet
little-known public-key encryption scheme. In this scheme, the
ciphertext is obtained by multiplying public-keys indexed by the
message bits modulo a prime $p$. The cleartext is recovered by
factoring the ciphertext raised to a secret power modulo $p$.
NS encryption requires a multiplication per two plaintext bits on
the average. Decryption is roughly as costly as an RSA decryption.
However, NS features a bandwidth sublinear in $\log p$, namely $\log
p/\log \log p$. As an example, for a $2048$-bit prime $p$, NS
encryption features a 233-bit bandwidth for a 59-kilobyte public key
size.
This paper presents new NS variants achieving bandwidths {\sl
linear} in $\log p$. As linear bandwidth claims a public-key of size
$\log^3 p/\log \log p$, we recommend to combine our scheme with
other bandwidth optimization techniques presented here.
For a $2048$-bit prime $p$, we obtain figures such as 169-bit
plaintext for a 10-kilobyte public key, 255-bit plaintext for a
20-kilobyte public key or a 781-bit plaintext for a 512-kilobyte
public key. Encryption and decryption remain unaffected by our
optimizations: As an example, the 781-bit variant requires 152
multiplications per encryption.

2007

EPRINT

Practical Cryptanalysis of SFLASH
Abstract

In this paper, we present a practical attack on the signature scheme
SFLASH proposed by Patarin, Goubin and Courtois in 2001 following a
design they had introduced in 1998.
The attack only needs the public key and requires about one second
to forge a signature for any message, after a one-time computation of
several minutes. It can be applied to both SFLASHv2 which was
accepted by NESSIE, as well as to SFLASHv3 which is a higher
security version.

2003

EPRINT

Projective Coordinates Leak
Abstract

Denoting by $P=[k]G$ the elliptic-curve double-and-add
multiplication of a public base point $G$ by a secret $k$,
we show that allowing an adversary access to the projective
representation of $P$ results in information being revealed about $k$.
Such access might be granted to an adversary by a poor
software implementation that does not erase the $Z$
coordinate of $P$ from the computer's memory or by a computationally-constrained secure token that
sub-contracts the affine conversion of $P$ to the external world.
From a wider perspective, our result proves that the choice of
representation of elliptic curve points {\sl can reveal}
information about their underlying discrete logarithms, hence
casting potential doubt on the appropriateness of blindly
modelling elliptic-curves as generic groups.
As a conclusion, our result underlines the necessity to sanitize
$Z$ after the affine conversion or, alternatively,
randomize $P$ before releasing it out.

2001

EPRINT

Fully Distributed Threshold RSA under Standard Assumptions
Abstract

The aim of the present article is to propose a fully distributed environment for the RSA scheme.
What we have in mind is highly sensitive applications and even if we are ready to pay a price in
terms of efficiency, we do not want any compromise of the security assumptions that we make.
Recently Shoup proposed a practical RSA threshold signature scheme that allows to share the
ability to sign between a set of players. This scheme can be used for decryption as well.
However, Shoup's protocol assumes a trusted dealer to generate and distribute the keys.
This comes from the fact that the scheme needs a special assumption on the RSA modulus and
this kind of RSA moduli cannot be easily generated in an efficient way with many players.
Of course, it is still possible to call theoretical results on multiparty computation, but we
cannot hope to design efficient protocols. The only practical result to generate RSA moduli
in a distributive manner is Boneh and Franklin protocol but this protocol cannot be easily
modified to generate the kind of RSA moduli that Shoup's protocol requires.
The present work takes a different path by proposing a method to enhance the key generation
with some additional properties and revisits the proof of Shoup to work with the resulting
RSA moduli. Both of these enhancements decrease the performance of the basic protocols.
However, we think that in the applications that we target, these enhancements provide
practical solutions. Indeed, the key generation protocol is usually run only once and the
number of players have time to perform their task so that the communication or time complexity
are not overly important.

2000

EPRINT

RSA-OAEP is Secure under the RSA Assumption
Abstract

Recently Victor Shoup noted that there is a gap in
the widely-believed security result of OAEP against adaptive
chosen-ciphertext attacks. Moreover, he showed that,
presumably,
OAEP cannot be proven secure from the {\it one-wayness}
of the underlying trapdoor permutation.
This paper establishes another result on the security
of OAEP. It proves that OAEP offers semantic security
against adaptive chosen-ciphertext attacks,
in the random oracle model, under the {\it partial-domain}
one-wayness of the underlying permutation.
Therefore, this uses a formally stronger assumption.
Nevertheless, since partial-domain one-wayness of the RSA function
is equivalent to its (full-domain) one-wayness, it follows that
the security of RSA--OAEP can actually
be proven under the sole RSA assumption, although
the reduction is not tight.

1998

EUROCRYPT

1997

CRYPTO

1990

EUROCRYPT

#### Program Committees

- PKC 2003
- CHES 2002
- CHES 2001
- PKC 2001
- Asiacrypt 2000
- Crypto 2000
- Asiacrypt 1999
- Eurocrypt 1999 (Program chair)
- PKC 1998
- Crypto 1996
- Eurocrypt 1995
- Eurocrypt 1994
- Eurocrypt 1992

#### Coauthors

- Simon R. Blackburn (2)
- Emmanuel Bresson (2)
- Dario Catalano (1)
- Florent Chabaud (1)
- Yeow Meng Chee (1)
- Benoît Chevallier-Mames (1)
- Don Coppersmith (2)
- Christophe Coupé (1)
- Vivien Dubois (4)
- Jean-Bernard Fischer (1)
- Pierre-Alain Fouque (9)
- Eiichiro Fujisaki (3)
- Craig Gentry (1)
- Marc Girault (2)
- Louis Granboulan (3)
- Helena Handschuh (1)
- Jakob Jonsson (1)
- Antoine Joux (5)
- Sébastien Kunz-Jacques (1)
- David M'Raïhi (1)
- Gilles Macario-Rat (2)
- John Malone-Lee (1)
- Gwenaëlle Martinet (1)
- Sean Murphy (2)
- David Naccache (5)
- Phong Q. Nguyen (7)
- Tatsuaki Okamoto (4)
- Pascal Paillier (1)
- Ludovic Perret (1)
- David Pointcheval (7)
- Thomas Pornin (1)
- Guillaume Poupard (7)
- Adi Shamir (2)
- Nigel P. Smart (3)
- Michael Szydlo (2)
- Philippe Toffin (1)
- Serge Vaudenay (4)