Concrete implementation of t-out-of-n threshold lattice signatures

Sammanfattning

In preparation for quantum attacks on current cryptographic primitives, efforts are being made to find ways to construct new primitives. While quantum computers are not yet capable of breaking the keys used in modern parameter selection, efforts are still being made to establish new primitives not vulnerable to any known quantum attacks. These newly proposed solutions range from theoretical constructions to concrete implementations. In this paper, we implement a lattice-based linearly homomorphic t-out-of-n threshold signature scheme based on lattices in an effort to verify its functionality and gather detailed performance data. We do this using fully homomorphic encryption schemes and Shamir’s Secret Sharing method. Our work proves that both the proposed passive and active security constructions in the paper works in practice using our implementation. We provide insights to the communication between participants and the number of messages being sent, as well as the size of each message during an actively secure run of our scheme. We also show some results on key sizes and total execution time for different parameters, as well as computations for the number of mathematical operations used in the algorithms. We further used our implementation to determine how runtime scales for key generation and signature generation for increasing values of (t, n). The main bottleneck was determined to be the Shamir’s Secret Sharing component of the algorithm. Our results also show that key generation, which was the most expensive algorithm overall, achieves maximum time-cost per participant when t is equal to (n+1)/2.