Practical Multiparty Protocols From Lattice Assumptions: Threshold Signatures, Oblivious Pseudorandom Functions, And More

Abstract

Lattice-based cryptography has emerged as the most dominant replacement candidate for the next generation of post-quantum cryptographic tools. With their operational simplicity while allowing advanced functionality, these protocols lead the majority of post-quantum standardization efforts and motivate a great chunk of current research to realize advanced trusted communication models. However, lattices' greatest asset is also their greatest curse. The applicability of advanced functionality motivates protocols with multiple computing parties while the assumptions that make lattice protocols secure in the first place hate settings where secrets are distributed. In this work we try to alleviate this issue by building practical lattice-based multiparty protocols. First we propose the first known concrete lattice-based threshold signature scheme with distributed key generation to demonstrate practicality. Second, we look at a different type of protocol, namely verifiable oblivious pseudorandom functions, and propose a practical version of an existing protocol through different analysis techniques while also giving the first lattice-based threshold versions of such protocols. Using these techniques, we then rebuild our threshold signature scheme and show a concretely efficient threshold signature that simultaneously provides additional desirable properties like identifiability and non-interactivity. Finally, we look at the possibility of asymmetric outsourced computation and formalize the classic notion of augmented password-protected threshold signatures in a more practicality friendly manner and construct the first lattice-based augmented password-protected threshold signature scheme. All of these works act as building blocks for more complicated protocols and share similar analysis techniques and solutions to problems specific to the distributed setting. This commonality indicates that it is not only the assumptions that we need to revisit but also how we think about security in general as part of preparing cryptography for its post-quantum era.