Implementation av ett latticebaserat t-av-n-tröskelsignatursschema

Mattias Petersson () och Max Gustafsson ()

Sammanfattning

Due to the potential upheaval in cryptographic practices in the wake of practical quantum computers, much work is being put in to formulating cryptographic schemes that are not easily broken by quantum algorithms. Solutions to many basic use-cases are being developed and standardized, however certain less common algorithms are still in the process of being solved with theoretical schemes. Theoretical constructions of cryptographic schemes can be analyzed for security and certain comparative values, but since many cryptographic schemes end up calling other schemes in the background, obtaining a full analysis of a composite scheme’s runtime performance can be challenging without a concrete implementation. In this paper, we implement a linearly homomorphic t-out-of-n threshold signature scheme based on lattices. 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 work 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 results on 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.

Handledare: Denis Nabokov (EIT) och Paul Stankovski Wagner (EIT)
Examinator: Thomas Johansson (EIT)