PhD Defense: Practical Multiparty Protocols from Lattice Assumptions: Signatures, Pseudorandom Functions, and More

Decades of "arms race'' against post-quantum adversaries seem to slow down as lattice-based cryptography emerges as the most dominant replacement candidate for the new generation of cryptographic tools. With their operational simplicity and advanced functionality, these protocols lead the post-quantum standardization efforts and motivate a significant chunk of current research to realize advanced, trusted communication models. However, lattices' greatest asset is also their greatest curse. Their affinity for advanced functionality motivates protocols with multiple computing parties, while the assumptions that make lattice protocols secure in the first place hate settings with distributed secrets.
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 efficient 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.
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 we need to revisit not only the assumptions but also how we define security in general as part of preparing cryptography for its post-quantum era.