Factoring-Based Signatures with Fiat-Shamir … for a Post-Quantum World
For the love of public key and digital signatures!
The CRYSTALS Dilithium method for quantum robust digital signatures uses a factoring-based signature based on the Fiat-Shamir method [1]. It was first outlined by Lyubashevsky in 2009 and has since been converted into a method that is a finalist for the NIST PCQ competition for digital signatures. In the article, we will implement the method defined in [1], but use elliptic curve methods instead of discrete log methods:
For elliptic curve methods, Alice generates a random private key (s), and then computes her public key:
S=sG
and where G is the base point on the curve. For each signature, Alice generates a random value (y) and computes:
Y=yG
Now Alice takes the message (M) and computes:
e=Hash(Y||M)
and where “||” is a concatenation operation. Next, she computes:
z=se+y
The signature for the message is then (z,e). Bob then wants to check the…
