Skip to main content
placeholder image

Using Freivalds¿ Algorithm to Accelerate Lattice-Based Signature Verifications

Chapter


Abstract


  • We present a novel computational technique to check whether a matrix-vector product is correct with a relatively high probability. While the idea could be related to verifiable delegated computations, most of the literature in this line of work focuses on provably secure functional aspects and do not provide clear computational techniques to verify whether a product $$xA = y$$ is correct where x, A and y are not given nor computed by the party which requires validity checking: this is typically the case for some cryptographic lattice-based signature schemes. This paper focuses on the computational aspects and the improvement on both speed and memory when implementing such a verifier, and use a practical example: the Diagonal Reduction Signature (DRS) scheme as it was one of the candidates in the recent National Institute of Standards and Technology Post-Quantum Cryptography Standardization Calls for Proposals competition. We show that in the case of DRS, we can gain a factor of 20 in verification speed.

Publication Date


  • 2019

Citation


  • Sipasseuth, A., Plantard, T., & Susilo, W. (2019). Using Freivalds¿ Algorithm to Accelerate Lattice-Based Signature Verifications. In Unknown Book (Vol. 11879 LNCS, pp. 401-412). doi:10.1007/978-3-030-34339-2_22

International Standard Book Number (isbn) 13


  • 9783030343385

Scopus Eid


  • 2-s2.0-85076669056

Book Title


  • Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Start Page


  • 401

End Page


  • 412

Abstract


  • We present a novel computational technique to check whether a matrix-vector product is correct with a relatively high probability. While the idea could be related to verifiable delegated computations, most of the literature in this line of work focuses on provably secure functional aspects and do not provide clear computational techniques to verify whether a product $$xA = y$$ is correct where x, A and y are not given nor computed by the party which requires validity checking: this is typically the case for some cryptographic lattice-based signature schemes. This paper focuses on the computational aspects and the improvement on both speed and memory when implementing such a verifier, and use a practical example: the Diagonal Reduction Signature (DRS) scheme as it was one of the candidates in the recent National Institute of Standards and Technology Post-Quantum Cryptography Standardization Calls for Proposals competition. We show that in the case of DRS, we can gain a factor of 20 in verification speed.

Publication Date


  • 2019

Citation


  • Sipasseuth, A., Plantard, T., & Susilo, W. (2019). Using Freivalds¿ Algorithm to Accelerate Lattice-Based Signature Verifications. In Unknown Book (Vol. 11879 LNCS, pp. 401-412). doi:10.1007/978-3-030-34339-2_22

International Standard Book Number (isbn) 13


  • 9783030343385

Scopus Eid


  • 2-s2.0-85076669056

Book Title


  • Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Start Page


  • 401

End Page


  • 412