R-LWE-Based Distributed Key Generation and Threshold Decryption

Published in Special Issue "Recent Advances in Security, Privacy, and Applied Cryptography", Mathematics, MDPI, 2022

Recommended citation: Alborch, F.; Martínez, R.; Morillo, P. R-LWE-Based Distributed Key Generation and Threshold Decryption. Mathematics 2022, 10, 728.

Ever since the appearance of quantum computers, prime factoring and discrete logarithm-based cryptography have been questioned, giving birth to the so-called post-quantum cryptography. The most prominent field in post-quantum cryptography is lattice-based cryptography, protocols that are proved to be as difficult to break as certain hard lattice problems like Learning with Errors (LWE) or Ring Learning with Errors ($$R$$-LWE). Furthermore, the application of cryptographic techniques to different areas, like electronic voting, has also nourished a great interest in distributed cryptography.

In this work, we will give two original threshold protocols based in the lattice problem $$R$$-LWE: one for key generation and one for decryption. We will prove them both correct and secure under the assumption of hardness of some well-known lattice problems. Finally, we will give a rough implementation of the protocols in C to give some tentative results about their viability, in particular our model generates keys in the order of $$10^3$$ ms and decrypts and encrypts in the order of $$10^2$$ ms.