TY - GEN
T1 - On the Higher-Bit Version of Approximate Inhomogeneous Short Integer Solution Problem
AU - Le Dévéhat, Anaëlle
AU - Shizuya, Hiroki
AU - Hasegawa, Shingo
N1 - Funding Information:
We would like to thank Yilei Chen, Nicholas Genise and Pratyay Mukherjee for kindly sharing with us their implementation of Hash-and-Sign signature based on F-trapdoors. We are especially grateful to Yilei Chen for his invaluable advice to our work.
Publisher Copyright:
© 2021, Springer Nature Switzerland AG.
PY - 2021
Y1 - 2021
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85121901462&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85121901462&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-92548-2_14
DO - 10.1007/978-3-030-92548-2_14
M3 - Conference contribution
AN - SCOPUS:85121901462
SN - 9783030925475
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 253
EP - 272
BT - Cryptology and Network Security - 20th International Conference, CANS 2021, Proceedings
A2 - Conti, Mauro
A2 - Stevens, Marc
A2 - Krenn, Stephan
PB - Springer Science and Business Media Deutschland GmbH
T2 - 20th International Conference on Cryptology and Network Security, CANS 2021
Y2 - 13 December 2021 through 15 December 2021
ER -