Paper 2021/1161

Balanced Non-Adjacent Forms

Marc Joye

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.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published by the IACR in Asiacrypt 2021
Contact author(s)
marc @ zama ai
History
2021-09-14: received
Short URL
https://ia.cr/2021/1161
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1161,
      author = {Marc Joye},
      title = {Balanced Non-Adjacent Forms},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1161},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/1161}},
      url = {https://eprint.iacr.org/2021/1161}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.