We just finished implementing Falcon-512 PQ digital signature verification algorithm in #Polygon #Miden VM assembly
Falcon signature verification costs ~337K -cycles
secp256k1 scalar multiplication costs ~3M -cycles
github.com/maticnetwork/m
Conversation
Replying to
Falcon-512 digital signature verification requires us to perform two NTTs and one iNTT for degree-511 polynomial multiplication
NTT costs ~64.9K -cycles
iNTT costs ~69.9K -cycles
Future improvements in NTT implementation should yield better performance
1
Note, while verifying a Falcon-512 signature, signature decompression and hash-to-point ( involves SHAKE256 XOF ) are computed outside of the VM.
If interested in our secp256k1 implementation in Miden assembly, see
1
While implementing Falcon-512 PQ DSA inside Miden VM, we've collected motivation from ia.cr/2022/1041, which comes with reference implementation
