International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

David Naccache

Affiliation: ENS, France

Publications

Year
Venue
Title
2016
JOFC
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2012
EUROCRYPT
2012
CHES
2011
PKC
2011
CRYPTO
2011
CHES
2010
TCC
2010
EPRINT
On The Broadcast and Validity-Checking Security of PKCS \#1 v1.5 Encryption
This paper describes new attacks on PKCS \#1 v1.5, a deprecated but still widely used RSA encryption standard. The first cryptanalysis is a broadcast attack, allowing the opponent to reveal an identical plaintext sent to different recipients. This is nontrivial because different randomizers are used for different encryptions (in other words, plaintexts coincide only partially). The second attack predicts, using a single query to a validity checking oracle, which of two chosen plaintexts corresponds to a challenge ciphertext. The attack's success odds are very high. The two new attacks rely on different mathematical tools and underline the need to accelerate the phase out of PKCS \#1 v1.5.
2010
CHES
2009
EPRINT
Comparing With RSA
A multi-set (MS) is a set where an element can occur more than once. MS hash functions (MSHFs) map MSs of arbitrary cardinality to fixed-length strings. This paper introduces a new RSA-based MSHF. The new function is efficient and produces small hashes. We prove that the proposed MSHF is collision-resistant under the assumption of unforgeability of deterministic RSA signatures. In many practical applications, programmers need to compare two (unordered) sets of integers. A trivial solution consists in sorting both sets ($\mathcal{O}(n \log n)$) and comparing them linearly. We show how MS hash functions can be turned into a linear-time, constant-space integer set equality test.
2009
EPRINT
Thermocommunication
Looking up -- you realize that one of the twelve light bulbs of your living room chandelier has to be replaced. You turn electricity off, move a table to the center of the room, put a chair on top of the table and, new bulb in hand, you climb up on top of the chair. As you reach the chandelier, you notice that\ldots all bulbs look alike and that you have forgotten which bulb needed to be changed.\smallskip Restart all over again?\smallskip Luckily, an effortless creative solution exists. By just touching the light bulbs you can determine the cold one and replace it! Put differently, information about the device's malfunction leaked-out via its temperature...
2009
CHES
2009
CRYPTO
2008
JOFC
2008
PKC
2008
EPRINT
Efficient Rational Secret Sharing in the Standard Communication Model
We propose a new methodology for rational secret sharing leading to various instantiations that are simple and efficient in terms of computation, share size, and round complexity. Our protocols do not require physical assumptions or simultaneous channels, and can even be run over asynchronous, point-to-point networks. Of additional interest, we propose new equilibrium notions for this setting (namely, computational versions of strict Nash equilibrium and stability with respect to trembles), show relations between them, and prove that our protocols satisfy them.
2008
EPRINT
Linear Bandwidth Naccache-Stern Encryption
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.
2008
EPRINT
Oracle-Assisted Static Diffie-Hellman Is Easier Than Discrete Logarithms
This paper extends Joux-Naccache-Thom\'e's $e$-th root algorithm to the static Diffie-Hellman problem ({\sc sdhp}). The new algorithm can be adapted to diverse finite fields by customizing it with an {\sc nfs}-like core or an {\sc ffs}-like core. In both cases, after a number of {\sc sdhp} oracle queries, the attacker builds-up the ability to solve new {\sc sdhp} instances {\sl unknown before the query phase}. While sub-exponential, the algorithm is still significantly faster than all currently known {\sc dlp} and {\sc sdhp} resolution methods. We explore the applicability of the technique to various cryptosystems. The attacks were implemented in ${\mathbb F}_{2^{1025}}$ and also in ${\mathbb F}_{p}$, for a $516$-bit $p$.
2007
ASIACRYPT
2007
EPRINT
When e-th Roots Become Easier Than Factoring
Antoine Joux David Naccache Emmanuel Thomé
We show that computing $e$-th roots modulo $n$ is easier than factoring $n$ with currently known methods, given subexponential access to an oracle outputting the roots of numbers of the form $x_i + c$. Here $c$ is fixed and $x_i$ denotes small integers of the attacker's choosing. Several variants of the attack are presented, with varying assumptions on the oracle, and goals ranging from selective to universal forgeries. The computational complexity of the attack is $L_n(\frac{1}{3}, \sqrt[3]{\frac{32}{9}})$ in most significant situations, which matches the {\sl special} number field sieve's ({\sc snfs}) complexity. This sheds additional light on {\sc rsa}'s malleability in general and on {\sc rsa}'s resistance to affine forgeries in particular -- a problem known to be polynomial for $x_i > \sqrt[3]{n}$, but for which no algorithm faster than factoring was known before this work.
2006
EUROCRYPT
2005
PKC
2005
PKC
2005
EPRINT
Secure Delegation of Elliptic-Curve Pairing
In this paper we describe a simple protocol for securely delegating elliptic-curve pairings. A computationally limited device (typically a smart-card) will delegate the computation of the pairing e(A,B) to a more powerful device (for example a PC), in such a way that: 1. the powerful device learns nothing about the points being paired (A and B), nor about the pairing?s result e(A,B), 2. and the limited device is able to detect when the powerful device is cheating. We also describe more efficient variants of our protocol when one of the points or both are already known, and further efficiency gains when constant points are used.
2005
EPRINT
Secure and {\sl Practical} Identity-Based Encryption
David Naccache
In this paper, we present a variant of Waters' Identity-Based Encryption scheme with a much smaller public-key size (only a few kilobytes). We show that this variant is semantically secure against passive adversaries in the standard model.\smallskip In essence, the new scheme divides Waters' public key size by a factor $\ell$ at the cost of (negligibly) reducing security by $\ell$ bits. Therefore, our construction settles an open question asked by Waters and constitutes the first fully secure {\sl practical} Identity-Based Encryption scheme.
2005
EPRINT
Blind Attacks on Engineering Samples
Vanessa Gratzer David Naccache
In addition to its usual complexity assumptions, cryptography silently assumes that information can be physically protected in a single location. As we now know, real-life devices are not ideal and confidential information leaks through different physical channels.\smallskip Whilst most aspects of side channel leakage (cryptophthora) are now well understood, no attacks on totally unknown algorithms are known to date. This paper describes such an attack.\smallskip By {\sl totally unknown} we mean that no information on the algorithm's mathematical description (including the plaintext size), the microprocessor or the chip's power consumption model is available to the attacker.\smallskip We successfully experimented the attack on a commercially available device produced by a non-European smart-card manufacturer.
2004
CHES
2004
EUROCRYPT
2004
EPRINT
The Sorcerer?s Apprentice Guide to Fault Attacks
The effect of faults on electronic systems has been studied since the 1970s when it was noticed that radioactive particles caused errors in chips. This led to further research on the effect of charged particles on silicon, motivated by the aerospace industry who was becoming concerned about the effect of faults in airborn electronic systems. Since then various mechanisms for fault creation and propagation have been discovered and researched. This paper covers the various methods that can be used to induce faults in semiconductors and exploit such errors maliciously. Several examples of attacks stemming from the exploiting of faults are explained. Finally a series of countermeasures to thwart these attacks are described.
2004
EPRINT
The Polynomial Composition Problem in $(\mathbb{Z}/n\mathbb{Z})[X]$
Marc Joye David Naccache St\'ephanie Porte
Let $n$ be an RSA modulus and let $P,Q \in (\mathbb{Z}/n\mathbb{Z})[X]$. This paper explores the following problem: Given $Q$ and $Q(P)$, find~$P$. We shed light on the connections between the above problem to the RSA problem and derive from it new zero-knowledge protocols.
2004
EPRINT
Externalized Fingerprint Matching
The 9/11 tragedy triggered an increased interest in biometric passports. According to several sources \cite{sp2}, the electronic ID market is expected to increase by more than 50\% {\sl per annum} over the three coming years, excluding China. \smallskip To cost-effectively address this foreseen explosion, a very inexpensive memory card (phonecard-like card) capable of performing fingerprint matching is paramount.\smallskip This paper presents such a solution. The proposed protocol is based on the following idea: the card stores the user's fingerprint information to which random minutiae were added at enrolment time (we denote this scrambled template by $t$). The card also stores a binary string $w$ encoding which of the minutiae in $t$ actually belong to the holder. When an identification session starts, the terminal reads $t$ from the card and, based upon the incoming scanner data, determines which of the minutiae in $t$ are genuine. The terminal forms a candidate $w'$ and sends it to the card. All the card needs to do is test that the Hamming weight of $w \oplus w'$ is smaller than a security threshold $d$. \smallskip It follows that the card only needs to embark passive data storage capabilities, one exclusive-or gate, a shift register, a counter and a comparator (less than 40 logical gates).
2004
EPRINT
How to Disembed a Program?
This paper presents the theoretical blueprint of a new secure token called the Externalized Microprocessor (XmP). Unlike a smart-card, the XmP contains no ROM at all. While exporting all the device's executable code to potentially untrustworthy terminals poses formidable security problems, the advantages of ROM-less secure tokens are numerous: chip masking time disappears, bug patching becomes a mere terminal update and hence does not imply any roll-out of cards in the field. Most importantly, code size ceases to be a limiting factor. This is particularly significant given the steady increase in on-board software complexity. After describing the machine's instruction-set we will introduce two XmP variants. The first design is a public-key oriented architecture which relies on a new RSA screening scheme and features a relatively low communication overhead at the cost of computational complexity, whereas the second variant is secret-key oriented and relies on simple MACs and hash functions but requires more communication. For each of these two designs, we propose two protocols that execute and dynamically authenticate arbitrary programs. We also provide a strong security model for these protocols and prove their security under appropriate complexity assumptions.
2004
EPRINT
Mobile Terminal Security
The miniaturization of electronics and recent developments in biometric and screen technologies will permit a pervasive presence of embedded systems. This - and the inclusion of networking capabilities and IP addresses in many handheld devices - will foster the widespread deployment of personal mobile equipment.\smallskip This work attempts to overview these diverse aspects of mobile device security. We will describe mobile networks' security (WLAN and WPAN security, GSM and 3GPP security) and address platform security issues such as bytecode verification for mobile equipment and protection against viruses and Trojan horses in mobile environment - with a concrete J2ME implementation example. Finally we will turn to hardware attacks and briefly survey the physical weaknesses that can be exploited to compromise mobile equipment.\smallskip
2004
EPRINT
Experimenting with Faults, Lattices and the DSA
We present an attack on DSA smart-cards which combines physical fault injection and lattice reduction techniques. This seems to be the first (publicly reported) physical experiment allowing to concretely pull-out DSA keys out of smart-cards. We employ a particular type of fault attack known as a glitch attack, which will be used to actively modify the DSA nonce k used for generating the signature: k will be tampered with so that a number of its least significant bytes will flip to zero. Then we apply well-known lattice attacks on El Gamal-type signatures which can recover the private key, given sufficiently many signatures such that a few bits of each corresponding k are known. In practice, when one byte of each k is zeroed, 27 signatures are sufficient to disclose the private key. The more bytes of k we can reset, the fewer signatures will be required. This paper presents the theory, methodology and results of the attack as well as possible countermeasures.
2003
ASIACRYPT
2003
EPRINT
Trading-Off Type-Inference Memory Complexity Against Communication
While bringing considerable flexibility and extending the horizons of mobile computing, mobile code raises major security issues. Hence, mobile code, such as Java applets, needs to be analyzed before execution. The byte-code verifier checks low-level security properties that ensure that the downloaded code cannot bypass the virtual machine's security mechanisms. One of the statically ensured properties is {\sl type safety}. The type-inference phase is the overwhelming resource-consuming part of the verification process. This paper addresses the RAM bottleneck met while verifying mobile code in memory-constrained environments such as smart-cards. We propose to modify classic type-inference in a way that significantly reduces the memory consumption in the memory-constrained device at the detriment of its distrusted memory-rich environment. The outline of our idea is the following, throughout execution, the memory frames used by the verifier are MAC-ed and exported to the terminal and then retrieved upon request. Hence a distrusted memory-rich terminal can be safely used for convincing the embedded device that the downloaded code is secure. The proposed protocol was implemented on JCOP20 and JCOP30 Java cards using IBM's JCOP development tool.
2003
EPRINT
Double-Speed Safe Prime Generation
David Naccache
Safe primes are prime numbers of the form $p=2\/q+1$ where $q$ is prime. This note introduces a simple method for doubling the speed of safe prime generation. The method is particularly suited to settings where a large number of RSA moduli must be generated.
2003
EPRINT
Projective Coordinates Leak
David Naccache Nigel P. Smart Jacques Stern
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.
2003
EPRINT
Chemical Combinatorial Attacks on Keyboards
Eric Brier David Naccache Pascal Paillier
This paper presents a new attack on keyboards. \smallskip The attack consists in depositing on each keyboard key a small ionic salt quantity ({\sl e.g.} some NaCl on key 0, some KCl on key 1, LiCl on key 2, SrCl$_2$ on key 3, BaCl$_2$ on key 4, CaCl$_2$ on key 5...). As the user enters his PIN, salts get mixed and leave the keyboard in a state that leaks secret information. Nicely enough, evaluating the entropy loss due to the chemical trace turns out to be a very interesting combinatorial exercise. \smallskip Under the assumption that mass spectroscopic analysis can reveal with accuracy the mixture of chemical compounds generated by the user, we show that, for moderate-size decimal PINs, the attack would generally disclose the PIN. \smallskip The attack may apply to door PIN codes, phone numbers dialed from a hotel rooms, computer keyboards or even ATMs. \ss While we did not implement the chemical part of the attack, a number of mass spectrometry specialists confirmed to the authors its feasibility.
2002
CRYPTO
2002
EPRINT
Cut and Paste Attacks with Java
Serge Lefranc David Naccache
This paper describes malicious applets that use Java's sophisticated graphic features to rectify the browser's padlock area and cover the address bar with a false https domain name. The attack was successfully tested on Netscape's Navigator and Microsoft's Internet Explorer; we consequently recommend to neutralize Java whenever funds or private data transit via these browsers and patch the flaw in the coming releases. The degree of novelty of our attack is unclear since similar (yet non-identical) results can be achieved by spoofing as described by Felten; however our scenario is much simpler to mount as it only demands the inclusion of an applet in the attacker's web page. In any case, we believe that the technical dissection of our malicious Java code has an illustrative value in itself.
2002
EPRINT
Universal Padding Schemes for RSA
A common practice to encrypt with RSA is to first apply a padding scheme to the message and then to exponentiate the result with the public exponent; an example of this is OAEP. Similarly, the usual way of signing with RSA is to apply some padding scheme and then to exponentiate the result with the private exponent, as for example in PSS. Usually, the RSA modulus used for encrypting is different from the one used for signing. The goal of this paper is to simplify this common setting. First, we show that PSS can also be used for encryption, and gives an encryption scheme semantically secure against adaptive chosen-ciphertext attacks, in the random oracle model. As a result, PSS can be used indifferently for encryption or signature. Moreover, we show that PSS allows to safely use the same RSA key-pairs for both encryption and signature, in a concurrent manner. More generally, we show that using PSS the same set of keys can be used for both encryption and signature for any trapdoor partial-domain one-way permutation. The practical consequences of our result are important: PKIs and public-key implementations can be significantly simplified.
2001
CRYPTO
2000
ASIACRYPT
2000
CHES
2000
EUROCRYPT
2000
EUROCRYPT
1999
ASIACRYPT
1999
CRYPTO
1999
PKC
1999
PKC
1998
EUROCRYPT
1997
EUROCRYPT
1997
FSE
1995
EUROCRYPT
1995
EUROCRYPT
(title unknown)
David Naccache
1994
EUROCRYPT
1993
EUROCRYPT
1992
EUROCRYPT

Program Committees

Asiacrypt 2019
CHES 2016
CHES 2013
PKC 2013
CHES 2011
CHES 2009
PKC 2009
CHES 2008
Eurocrypt 2008
CHES 2007
PKC 2006
Crypto 2005
PKC 2005
CHES 2005
CHES 2002
Crypto 2002
PKC 2002
PKC 2001
Eurocrypt 2001
CHES 2001
PKC 2000
Eurocrypt 1999
Asiacrypt 1999
Crypto 1997
Eurocrypt 1997
Asiacrypt 1996
Eurocrypt 1996
Eurocrypt 1994

Coauthors

Ehsan Aerabi (1)
A. Elhadi Amirouche (1)
Hagai Bar-El (1)
Claude Barral (1)
Aurélie Bauer (1)
Olivier Benoit (1)
Sébastien Briais (1)
Eric Brier (3)
Julien Brouchier (1)
Rodrigo Portella do Canto (2)
Stéphane Caron (1)
Julien Cathalo (2)
Benoît Chevallier-Mames (4)
Hamid Choukri (1)
Jean-Michel Cioranesco (2)
Christophe Clavier (1)
Gérard D. Cohen (1)
Don Coppersmith (1)
Jean-Sébastien Coron (21)
Nora Dabbous (2)
Ivan Damgård (1)
Jean-Luc Danger (2)
Houda Ferradi (4)
Pierre-Alain Fouque (1)
Georg Fuchsbauer (2)
Laurent Gauteron (1)
Rémi Géraud (6)
Pierre Girard (1)
Vanessa Gratzer (2)
François Grieu (1)
Sylvain Guilley (3)
Shai Halevi (1)
Helena Handschuh (2)
Philippe Hoogvorst (1)
Konstantin Hyppönen (1)
Jacques-Henri Jourdan (1)
Antoine Joux (5)
Marc Joye (4)
Charanjit S. Jutla (1)
Jonathan Katz (2)
Tom Kean (1)
Ilya Kizhvatov (1)
François Koeune (1)
Roman Korkikian (1)
Serge Lefranc (1)
Reynald Lercier (1)
Éric Levieil (2)
Antoine Lobstein (1)
David M'Raïhi (3)
Diana-Stefania Maimut (1)
Diana Maimut (3)
Avradip Mandal (2)
Carol Marsh (1)
Noel McCullagh (1)
Arthur Milchior (1)
Cédric Murdica (2)
Phong Q. Nguyen (3)
Pascal Paillier (7)
David Pointcheval (2)
St\'ephanie Porte (1)
Thibault Porteboeuf (1)
Adina di Porto (1)
Jean-Jacques Quisquater (1)
Dan Raphaeli (1)
Michael Scott (1)
Adi Shamir (1)
Emil Simion (1)
Nigel P. Smart (2)
St\'ephane Soci\'e (1)
Julien P. Stern (3)
Jacques Stern (5)
Alexei Tchulkine (1)
Emmanuel Thomé (3)
Mehdi Tibouchi (7)
Assia Tria (1)
Elena Trichina (1)
Michael Tunstall (4)
Serge Vaudenay (2)
Damien Vergnaud (1)
Jean Vuillemin (1)
Amaury de Wargny (1)
Ralf-Philipp Weinmann (2)
Claire Whelan (4)
William Wolfowicz (1)
Gilles Zémor (1)
Hang Zhou (1)