Skip to main content
placeholder image

Using Freivalds’ Algorithm to Accelerate Lattice-Based Signature Verifications

Journal Article


Abstract


  • © Springer Nature Switzerland AG, 2019. 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. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 11879 LNCS 401-412. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Scopus Eid


  • 2-s2.0-85076669056

Number Of Pages


  • 11

Start Page


  • 401

End Page


  • 412

Volume


  • 11879 LNCS

Place Of Publication


  • Germany

Abstract


  • © Springer Nature Switzerland AG, 2019. 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. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 11879 LNCS 401-412. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Scopus Eid


  • 2-s2.0-85076669056

Number Of Pages


  • 11

Start Page


  • 401

End Page


  • 412

Volume


  • 11879 LNCS

Place Of Publication


  • Germany