TY - GEN
T1 - Practical signatures from the partial fourier recovery problem revisited: A provably-secure and gaussian-distributed construction
AU - Lu, Xingye
AU - Zhang, Zhenfei
AU - Au, Man Ho
N1 - Funding Information:
Acknowledgement. We appreciate the anonymous reviewers for their valuable suggestions. Part of this work was supported by the National Natural Science Foundation of China (Grant No. 61602396, U1636205), and from the Research Grants Council of Hong Kong (Grant No. 25206317).
Publisher Copyright:
© Springer International Publishing AG, part of Springer Nature 2018.
PY - 2018
Y1 - 2018
N2 - In this paper, we present a new lattice-based signature scheme, PASSG, based on signatures from the partial Fourier recovery problem PASSRS introduced by Hoffstein et al. in 2014. Same as PASSRS, security of our construction relies on the average-case hardness of a special kind of Short Integer Solution (SIS) problem and the hardness of partial Fourier recovery problem. PASSG improves PASSRS in two aspects. Firstly, unlike PASSRS, PASSG comes with a reduction proof and is thus provably secure. Secondly, we adopt rejection sampling technique introduced by Lyubashevsky in 2008 to reduce the signature size and improve the efficiency. More concretely, signatures of PASSG are Gaussian-distributed and is more space efficient. We also present another security parameter set based on best known attack using BKZ 2.0 algorithm introduced by Chen and Nguyen in 2011.
AB - In this paper, we present a new lattice-based signature scheme, PASSG, based on signatures from the partial Fourier recovery problem PASSRS introduced by Hoffstein et al. in 2014. Same as PASSRS, security of our construction relies on the average-case hardness of a special kind of Short Integer Solution (SIS) problem and the hardness of partial Fourier recovery problem. PASSG improves PASSRS in two aspects. Firstly, unlike PASSRS, PASSG comes with a reduction proof and is thus provably secure. Secondly, we adopt rejection sampling technique introduced by Lyubashevsky in 2008 to reduce the signature size and improve the efficiency. More concretely, signatures of PASSG are Gaussian-distributed and is more space efficient. We also present another security parameter set based on best known attack using BKZ 2.0 algorithm introduced by Chen and Nguyen in 2011.
KW - Digital signature
KW - Lattice-based cryptography
KW - Partial fourier recovery problem
UR - http://www.scopus.com/inward/record.url?scp=85049796816&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-93638-3_50
DO - 10.1007/978-3-319-93638-3_50
M3 - Conference article published in proceeding or book
AN - SCOPUS:85049796816
SN - 9783319936376
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 813
EP - 820
BT - Information Security and Privacy - 23rd Australasian Conference, ACISP 2018, Proceedings
A2 - Susilo, Willy
A2 - Yang, Guomin
PB - Springer Verlag
T2 - 23rd Australasian Conference on Information Security and Privacy, ACISP 2018
Y2 - 11 July 2018 through 13 July 2018
ER -