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

Abstract

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.

Popular Abstract

There is a current challenge to develop new cryptographic standards that are secure against quantum algorithms. With the knowledge that a sufficiently powerful quantum computer can break current asymmetric cryptographic schemes, it is important to redesign such protocols. This thesis explores the practical implementation of a threshold-signature scheme that is secure even with access to a quantum computer.

Digital signatures are schemes utilizing asymmetric cryptography, allowing an entity to create a public/private key pair. The public key can then be distributed freely, while the private key can be used to sign messages, documents, software and more. Anyone with access to the public key can verify that the signature is legitimate, i.e. the signature was created by the holder of the private key. This scheme can be extended to a threshold scheme, where multiple participants are required to create a valid signature. Threshold-signature schemes are typically called t-out-of-n signature schemes, where t denotes the number of participants required to create a valid signature, and n denotes the total number of participants.

This is achieved in our scheme with two underlying homomorphic schemes for commitments and encryption. The homomorphic property allows for mathematical operations such as addition of encrypted data, e.g. ciphertexts, where adding multiple ciphertexts is equivalent to the sum of the encrypted corresponding plaintext.

Lattices are a popular candidate going forward for constructing quantum-safe algorithms. Additionally, homomorphic schemes were first realized in lattice-based cryptography. A lattice is a set of points in a multi-dimensional space, created by taking the linear combinations of a set of basis vectors.

There exists various theoretical implementations of lattice-based t-out-of-n schemes, but publicly available practical implementations are lacking. Our implementation serves as a first prototype to demonstrate the feasibility of implementing these schemes. We evaluate execution time, sizes of messages sent, and number of mathematical operations in the protocol for different values of (t, n). We found that our system scaled exponentially, with Shamir's Secret Sharing method requiring the most time out of all algorithms. We also discovered that key generation, which was the most expensive algorithm, was the most expensive for each participant when t was equal to (n+1)/2.

• author: Gustafsson, Max and Petersson, Mattias
• supervisor: Paul Stankovski; Denis Nabokov
• organization: Department of Electrical and Information Technology
• course: EITM01 20241
• year: 2024
• type: H2 - Master's Degree (Two Years)
• subject: Technology and Engineering
• keywords: Lattices, Threshold Signatures, Homomorphic Encryption, Threshold Encryption
• report number: LU/LTH-EIT 2024-986
• language: English
• id: 9157457
• date added to LUP: 2024-06-17 15:31:33
• date last changed: 2024-06-17 15:31:33