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
ASIACRYPT
2014
EUROCRYPT
2014
ASIACRYPT
Program Committees
- CHES 2022
- PKC 2021
- Eurocrypt 2021
- CHES 2020
- Eurocrypt 2020
- PKC 2019
- CHES 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 (1)
- Fabrice Benhamouda (1)
- Eric Brier (1)
- Jan Camenisch (1)
- Benoît Chevallier-Mames (1)
- Christophe Clavier (1)
- Jean-Sébastien Coron (3)
- Reza Rezaeian Farashahi (1)
- Raveen R. Goundar (1)
- Helena Handschuh (1)
- Javier Herranz (1)
- Arjen K. Lenstra (1)
- Benoît Libert (8)
- Atsuko Miyaji (1)
- David Naccache (2)
- Pascal Paillier (8)
- Thomas Peters (6)
- David Pointcheval (1)
- Jean-Jacques Quisquater (2)
- Berry Schoenmakers (1)
- Gene Tsudik (1)
- Michael Tunstall (1)
- Christophe Tymen (3)
- Serge Vaudenay (1)
- Sung-Ming Yen (3)
- Moti Yung (6)