## CryptoDB

### Marc Joye

#### Publications

**Year**

**Venue**

**Title**

2021

ASIACRYPT

Balanced Non-Adjacent Forms
Abstract

Integers can be decomposed in multiple ways. The choice of a recoding technique is generally dictated by performance considerations. The usual metric for optimizing the decomposition is the Hamming weight. In this work, we consider a different metric and propose new modified forms (i.e., integer representations using signed digits) that satisfy minimality requirements under the new metric. Specifically, we introduce what we call balanced non-adjacent forms and prove that they feature a minimal Euclidean weight. We also present efficient algorithms to produce these new minimal forms. We analyze their asymptotic and exact distributions. We extend the definition to modular integers and show similar optimality results. The balanced non adjacent forms find natural applications in fully homomorphic encryption as they optimally reduce the noise variance in LWE-type ciphertexts.

2015

EPRINT

2015

ASIACRYPT

2014

EUROCRYPT

2014

ASIACRYPT

2010

EPRINT

Co-Z Addition Formulae and Binary Ladders on Elliptic Curves
Abstract

Meloni recently introduced a new type of arithmetic on elliptic curves when adding projective points sharing the same Z-coordinate. This paper presents further co-Z addition formulae (and register allocations) for various point additions on Weierstrass elliptic curves. It explains how the use of conjugate point addition and other implementation tricks allow one to develop efficient scalar multiplication algorithms making use of co-Z arithmetic. Specifically, this paper describes efficient co-Z based versions of Montgomery ladder and Joyes double-add algorithm. Further, the resulting implementations are protected against a large variety of implementation attacks.

2010

EPRINT

Huff's Model for Elliptic Curves
Abstract

This paper revisits a model for elliptic curves over Q introduced by Huff in 1948 to study a diophantine problem. Huff's model readily extends over fields of odd characteristic. Every elliptic curve over such a field and containing a copy of Z/4Z×Z/2Z is birationally equivalent to a Huff curve over the original field.
This paper extends and generalizes Huff's model. It presents fast explicit formulas for point addition and doubling on Huff curves. It also addresses the problem of the efficient evaluation of pairings over Huff curves. Remarkably, the formulas we obtain feature some useful properties, including completeness and independence of the curve parameters.

2008

EPRINT

Twisted Edwards Curves
Abstract

This paper introduces ``twisted Edwards curves,''
a generalization of the recently introduced Edwards curves;
shows that twisted Edwards curves include more curves over finite fields,
and in particular every elliptic curve in Montgomery form;
shows how to cover even more curves via isogenies;
presents fast explicit formulas for twisted Edwards curves
in projective and inverted coordinates;
and shows that twisted Edwards curves save time
for many curves that were already expressible as Edwards curves.

2006

EPRINT

Remarks on "Analysis of One Popular Group Signature Scheme'' in Asiacrypt 2006
Abstract

In \cite{Cao}, a putative framing ``attack'' against the ACJT group signature scheme \cite{ACJT00} is presented. This note shows that the attack framework considered in \cite{Cao} is \emph{invalid}. As we clearly illustrate, there is \textbf{no security weakness} in the ACJT group signature scheme as long as all the detailed specifications in \cite{ACJT00} are being followed.

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.

2003

EPRINT

Elliptic Curve Cryptosystems in the Presence of Permanent and Transient Faults
Abstract

Elliptic curve cryptosystems in the presence of faults were studied
by Biehl, Meyer and Mueller (2000). The first fault model they
consider requires that the input point P in the
computation of dP is chosen by the adversary.
Their second and third fault models only require the knowledge of P.
But these two latter models are less `practical' in
the sense that they assume that only a few bits of error are
inserted (typically exactly one bit is supposed to be disturbed)
either into P just prior to the point multiplication or
during the course of the computation in a chosen location.
This report relaxes these assumptions and shows how random
(and thus unknown) errors in either coordinates of point P,
in the elliptic curve parameters or in the field
representation enable the (partial) recovery of multiplier d.
Then, from multiple point multiplications, we explain how this can
be turned into a total key recovery. Simple precautions to prevent
the leakage of secrets are also discussed.

2003

EPRINT

Trading Inversions for Multiplications in Elliptic Curve Cryptography
Abstract

Recently, Eisentraeger-Lauter-Montgomery proposed a method for speeding up scalar multiplication on elliptic curves. That method relies on improved formulae for evaluating S = 2P + Q from given points P and Q on an elliptic curve. Compared to the naive approach, the improved formulae save a field multiplication each time the operation is performed.
This paper proposes a variant which is faster whenever a field inversion is more expensive than six field multiplications. We also give an improvement when tripling or quadrupling a point, and present a ternary/binary method to perform efficient scalar multiplication.

2003

EPRINT

Low-Cost Solutions for Preventing Simple Side-Channel Analysis: Side-Channel Atomicity
Abstract

This paper introduces simple methods to convert a cryptographic algorithm into an algorithm protected against simple side-channel attacks. Contrary to previously known solutions, the proposed techniques are not at the expense of the execution time. Moreover, they are generic and apply to virtually any algorithm.
In particular, we present several novel exponentiation algorithms, namely a protected square-and-multiply algorithm, its right-to-left counterpart, and several protected sliding-window algorithms. We also illustrate our methodology applied to point multiplication on elliptic curves. All these algorithms share the common feature that the complexity is globally unchanged compared to the corresponding
unprotected implementations.

2002

EPRINT

Optimal Chosen-Ciphertext Secure Encryption of Arbitrary-Length Messages
Abstract

This paper considers arbitrary-length chosen-ciphertext secure asymmetric encryption, thus addressing what is actually needed for a practical usage of strong public-key cryptography in the real world. We put forward two generic constructions, gem-1 and gem-2, which apply to explicit fixed-length weakly secure primitives and provide a strongly secure (IND-CCA2) public-key encryption scheme for messages of unfixed length (typically computer files). Our techniques optimally combine a single call to any one-way trapdoor function with repeated encryptions through some weak block-cipher (a simple xor is fine) and hash functions of fixed-length input so that a minimal number of calls to these functions is needed. Our encryption/decryption throughputs are comparable to the ones of standard methods (asymmetric encryption of a session key + symmetric encryption with multiple modes). In our case, however, we formally prove that our designs are secure in the strongest sense and provide complete security reductions holding in the random oracle model.

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.

2002

EPRINT

The Jacobi Model of an Elliptic Curve and Side-Channel Analysis
Abstract

A way for preventing SPA-like attacks on elliptic curve systems is to
use the same formula for the doubling and the general addition of
points on the curve. Various proposals have been made in this
direction with different results. This paper re-investigates the
Jacobi form suggested by Liardet and Smart (CHES 2001). Rather than
considering the Jacobi form as the intersection of two quadrics, the
addition law is directly derived from the underlying quartic. As a
result, this leads to substantial memory savings and produces the
fastest unified addition formula for curves of order a multiple of 2.

#### Program Committees

- CHES 2020
- Eurocrypt 2020
- CHES 2019
- PKC 2019
- CHES 2018
- CHES 2017
- CHES 2016
- CHES 2015
- Asiacrypt 2015
- Eurocrypt 2015
- Eurocrypt 2014
- Asiacrypt 2014
- CHES 2014
- CHES 2013
- CHES 2012
- CHES 2011
- CHES 2010
- Eurocrypt 2010
- Crypto 2009
- Asiacrypt 2009
- CHES 2009
- PKC 2009
- Eurocrypt 2008
- CHES 2008
- CHES 2007
- Asiacrypt 2007
- CHES 2006
- Eurocrypt 2005
- Asiacrypt 2004
- PKC 2004
- CHES 2004 (Program chair)
- CHES 2003
- PKC 2003
- Asiacrypt 2003

#### Coauthors

- Giuseppe Ateniese (2)
- Fabrice Benhamouda (1)
- Daniel J. Bernstein (1)
- Olivier Billet (1)
- Peter Birkner (1)
- Eric Brier (1)
- Jan Camenisch (2)
- Benoît Chevallier-Mames (2)
- Mathieu Ciet (3)
- Christophe Clavier (1)
- Jean-Sébastien Coron (5)
- Reza Rezaeian Farashahi (1)
- Raveen R. Goundar (2)
- Helena Handschuh (2)
- Javier Herranz (1)
- Tanja Lange (1)
- Kristin E. Lauter (1)
- Arjen K. Lenstra (1)
- Benoît Libert (9)
- Atsuko Miyaji (2)
- Peter L. Montgomery (1)
- David Naccache (4)
- Pascal Paillier (10)
- Thomas Peters (7)
- Christiane Peters (1)
- David Pointcheval (2)
- St\'ephanie Porte (1)
- Jean-Jacques Quisquater (2)
- Berry Schoenmakers (1)
- Mehdi Tibouchi (1)
- Gene Tsudik (2)
- Michael Tunstall (1)
- Christophe Tymen (4)
- Serge Vaudenay (1)
- Damien Vergnaud (1)
- Sung-Ming Yen (3)
- Moti Yung (7)