Factoring-Based Signatures with Fiat-Shamir … for a Post-Quantum World

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 signature, he computes:

Z=zG

eS′=(−e)S

e′=Hash((Z+eS′)||M)

if e′ is the same as e, the signature is valid. This works because:

e′=Hash((Z+eS′)||M)=Hash((zG+(−e)sG)||M)=Hash((se+y)G+(−e)sG)||M)=Hash(yG||M)=Hash(Y||M)

The following is the code using the secp256k1 curve [here]:

import random
import hashlib
from secp256k1 import curve,scalar_mult,point_add
import sys

# Alice's secret key
s = random.randint(0, curve.n-1)

# Alice random value for signature
y = random.randint(0, curve.n-1)

G= curve.g
Y = scalar_mult(y,G)
S = scalar_mult(s,G)

M="hello"
if (len(sys.argv)>1):
	M=str(sys.argv[1])

M=M.encode()
Y_x,Y_y = Y
S_x,S_y = S

e=hashlib.sha256(Y_x.to_bytes(32,'big')+Y_y.to_bytes(32,'big')+M)

digest = e.hexdigest()
e = int(digest, 16)

z=(s*e+y) % curve.n

print (f"Message: {M.decode()}")
print (f"Alice secret key (s)={s}")
print (f"Alice public key (S)={S}\n")
print (f"Alice random (y)={y}\n\n")

Z = scalar_mult(z,G)
S_ = scalar_mult(-e,S)

Res=point_add(Z,S_)
Res_x,Res_y = Res

Res_=int(hashlib.sha256(Res_x.to_bytes(32,'big')+Res_y.to_bytes(32,'big')+M).hexdigest(),16)

print (f"\nSignature:\ne={e}\nz={z}")

print ("\n== To check, Bob uses z, e and S ==")
print (f"\nResult={Res_}")

if (e==Res_): print("They match!!!")

A sample run gives the proof [here]:

Message: hello
Alice secret key (s)=79372360234784491245802153557901650538712864544231990695104256261465725042050
Alice public key (S)=(60289430997947944525018523511685181848106621025118324003397786578563820448554, 53656803965313566209050975602646185993844184973675069576770742185561736825970)

Alice random (y)=43367599150729727169188786487222261280236438204793945195805121335812876009495

Signature:
e=58006645943275619189249399530845873697163578902032125665999993987578678122821
z=98076753675682586563161462099149764381360471242026070999961932942775127739388

== To check, Bob uses z, e and S ==

Result=58006645943275619189249399530845873697163578902032125665999993987578678122821
They match!!!

Here is the running code:

Conclusions

The Fiat-Shamir method is wonderful. It is currently helping to build privacy-preserving methods and is now supporting Post-Quantum digital signatures. For quantum-robust signatures, its core form is converted into a lattice-based approach, and with polynomials replacing the message and the elliptic curve points.

Reference

[1] Lyubashevsky, V. (2009, December). Fiat-Shamir with aborts: Applications to lattice and factoring-based signatures. In International Conference on the Theory and Application of Cryptology and Information Security (pp. 598–616). Springer, Berlin, Heidelberg [paper].