## CryptoDB

### David Naccache

#### Affiliation: ENS, France

#### Publications

**Year**

**Venue**

**Title**

2015

EPRINT

2012

EUROCRYPT

2010

EPRINT

On The Broadcast and Validity-Checking Security of PKCS \#1 v1.5 Encryption
Abstract

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.

2009

EPRINT

Comparing With RSA
Abstract

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
Abstract

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...

2008

EPRINT

Efficient Rational Secret Sharing in the Standard Communication Model
Abstract

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
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.

2008

EPRINT

Oracle-Assisted Static Diffie-Hellman Is Easier Than Discrete Logarithms
Abstract

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

EPRINT

When e-th Roots Become Easier Than Factoring
Abstract

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

EPRINT

Secure Delegation of Elliptic-Curve Pairing
Abstract

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
Abstract

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
Abstract

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

EPRINT

The Sorcerer?s Apprentice Guide to Fault Attacks
Abstract

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]$
Abstract

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
Abstract

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?
Abstract

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
Abstract

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
Abstract

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
Abstract

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
Abstract

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
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.

2003

EPRINT

Chemical Combinatorial Attacks on Keyboards
Abstract

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

EPRINT

Cut and Paste Attacks with Java
Abstract

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
Abstract

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.

1995

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)