## CryptoDB

### Jacques Stern

#### Publications

Year
Venue
Title
2010
PKC
2008
PKC
2008
EUROCRYPT
2008
EPRINT
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
CRYPTO
2007
EUROCRYPT
2007
PKC
2007
EPRINT
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.
2006
CRYPTO
2006
PKC
2006
JOFC
2005
ASIACRYPT
2005
EUROCRYPT
2004
EUROCRYPT
2004
JOFC
2003
ASIACRYPT
2003
EUROCRYPT
2003
FSE
2003
EPRINT
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.
2002
ASIACRYPT
2002
CRYPTO
2002
CRYPTO
2001
ASIACRYPT
2001
ASIACRYPT
2001
CRYPTO
2001
PKC
2001
PKC
2001
EPRINT
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
CHES
2000
EUROCRYPT
2000
PKC
2000
EPRINT
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.
2000
JOFC
1999
CHES
1999
CRYPTO
1999
PKC
1999
EUROCRYPT
1998
ASIACRYPT
1998
ASIACRYPT
1998
CRYPTO
1998
EUROCRYPT
1998
FSE
1998
PKC
1998
JOFC
1997
CRYPTO
1997
EUROCRYPT
1997
FSE
1997
JOFC
1996
ASIACRYPT
1996
ASIACRYPT
1996
ASIACRYPT
1996
EUROCRYPT
1996
EUROCRYPT
1995
JOFC
1994
ASIACRYPT
1994
CRYPTO
1994
CRYPTO
1993
CRYPTO
1993
CRYPTO
1993
EUROCRYPT
1991
ASIACRYPT
1991
CRYPTO
1990
EUROCRYPT
1989
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