×

zbMATH — the first resource for mathematics

Digital signatures from the middle-product LWE. (English) Zbl 1421.94057
Baek, Joonsang (ed.) et al., Provable security. 12th international conference, ProvSec 2018, Jeju, South Korea, October 25–28, 2018. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11192, 239-257 (2018).
Summary: We construct digital signatures secure in the quantum random oracle model (QROM) under the middle-product Learning with Errors problem, which is recently proposed by M. Roşca et al. [Crypto 2017, Lect. Notes Comput. Sci. 10403, 283–297 (2017; Zbl 1406.94078)] and shown by M. Roşca et al. [Eurocrypt 2018, Lect. Notes Comput. Sci. 10820, 146–173 (2018; Zbl 1421.94069)] that it can be reduced from the worst-case hardness of ideal lattice problems for a large class of polynomial rings. The previous signatures secure under the lattice problems not specified in a certain ring is based on the Short Integer Solution (SIS) problems for bounded-degree polynomials [V. Lyubashevsky, Asiacrypt 2016, Lect. Notes Comput. Sci. 10032, 196–214 (2016; Zbl 1407.94141)]. The standard path to construct efficient signatures secure in the QROM [E. Kiltz et al., Eurocrypt 2018, Lect. Notes Comput. Sci. 10822, 552–586 (2018; Zbl 1415.94448)] requires hardness of a decision problem, but the SIS problems for polynomial rings are not known to have search-to-decision reductions. Our signatures are the first efficient signatures secure in the QROM under the worst-case hardness of ideal lattice problems for many rings.
For the entire collection see [Zbl 1398.94007].
MSC:
94A60 Cryptography
PDF BibTeX XML Cite
Full Text: DOI