Paper 2022/1144

On the Higher bit Version of Approximate Inhomogeneous Short Integer Solution Problem

Anaëlle Le Dévéhat, Tohoku University
Hiroki Shizuya, Tohoku University
Shingo Hasegawa, Tohoku University
Abstract

We explore a bitwise modification in Ajtai's one-way function. Our main contribution is to define the higher-bit approximate inhomogeneous short integer solution (ISIS) problem and prove its reduction to the ISIS problem. In this new instance, our main idea is to discard low-weighted bits to gain compactness. As an application, we construct a bitwise version of a hash-and-sign signature in the random oracle model whose security relies on the (Ring)-LWE and (Ring)-ISIS assumptions. Our scheme is built from the hash-and-sign digital signature scheme based on the relaxed notion of approximate trapdoors introduced by Chen, Genise and Mukherjee (2019). Their work can be interpreted as a bitwise optimization of the work of Micciancio and Peikert (2012). We extend this idea and apply our technique to the scheme by discarding low-weighted bits in the public key. Our modification brings improvement in the public key size but also in the signature size when used in the right setting. However, constructions based on the higher-bit approximate ISIS save memory space at the expense of loosening security. Parameters must be set in regards with this trade-off.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. CANS2021
DOI
10.1007/978-3-030-92548-2_14
Keywords
Lattice cryptography Approximate trapdoorHash-and-sign signature
Contact author(s)
anaelle le devehat s8 @ alumni tohoku ac jp
History
2022-09-05: approved
2022-09-02: received
See all versions
Short URL
https://ia.cr/2022/1144
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/1144,
      author = {Anaëlle Le Dévéhat and Hiroki Shizuya and Shingo Hasegawa},
      title = {On the Higher bit Version of Approximate Inhomogeneous Short Integer Solution Problem},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/1144},
      year = {2022},
      doi = {10.1007/978-3-030-92548-2_14},
      url = {https://eprint.iacr.org/2022/1144}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.