PhD Proposal: Practical(ish) Multiparty Protocols from Lattice Assumptions
Kamil Doruk Gur
Tuesday, April 9, 2024, 10:00 am-12:00 pm 
Abstract
The ever-looming threat of quantum computers has motivated the study of cryptographic primitives that remain secure even in the presence of a quantum adversary. Cryptologic community conducted an immense amount of work on many different methodologies for efficient key encapsulation and digital signature protocols. However, modern communication requires more advanced functionality than simple encryption and signing. In particular, many protocols are built on the idea of having multiple participants with their own secret material contribute to their execution. Out of many different multiparty protocols, threshold signatures and verifiable oblivious pseudorandom functions(VOPRFs) are of particular interest due to their applications to cryptocurrency and private authentication mechanisms.
While both threshold signatures and VOPRFs have been studied extensively in the classical setting, there is little to no progress achieved for their post-quantum counterparts as quantum resistant algorithms rely on primitives that do not translate into the distributed setting easily. In particular, one of the leading paradigms for post-quantum cryptography is based on lattices which requires the secret key material to be out of a specific distribution. Furthermore, many lattice-based algorithms require subprotocols that do not have a clear way of achieving over multiple parties. These reasons limit the currently available solutions for lattice problems, as most of the solutions either rely on generic evaluation of the protocol over secure multiparty computation or serve as feasibility results with non-practical communication costs. This raises the question of whether efficient multiparty lattice protocols without the need of generic framework applications are possible.
In this work I present two somewhat practical lattice multiparty protocols: the first lattice based threshold signature for arbitrary thresholds that allows distributed key generation and the first practical lattice based VOPRF that can be extended to first known t-out-of-n and n-out-of-n lattice VOPRF constructions. I will also discuss my proposed work which focuses on improving practicality of both lattice based threshold signatures and VOPRFs. With recent improvements in zero-knowledge proofs, homomorphic encryption, and blind signatures, it is possible to relax some of the assumptions we make in favor of smaller key and communication sizes. I will also discuss potential ways to apply these techniques to build other threshold lattice based protocols.
While both threshold signatures and VOPRFs have been studied extensively in the classical setting, there is little to no progress achieved for their post-quantum counterparts as quantum resistant algorithms rely on primitives that do not translate into the distributed setting easily. In particular, one of the leading paradigms for post-quantum cryptography is based on lattices which requires the secret key material to be out of a specific distribution. Furthermore, many lattice-based algorithms require subprotocols that do not have a clear way of achieving over multiple parties. These reasons limit the currently available solutions for lattice problems, as most of the solutions either rely on generic evaluation of the protocol over secure multiparty computation or serve as feasibility results with non-practical communication costs. This raises the question of whether efficient multiparty lattice protocols without the need of generic framework applications are possible.
In this work I present two somewhat practical lattice multiparty protocols: the first lattice based threshold signature for arbitrary thresholds that allows distributed key generation and the first practical lattice based VOPRF that can be extended to first known t-out-of-n and n-out-of-n lattice VOPRF constructions. I will also discuss my proposed work which focuses on improving practicality of both lattice based threshold signatures and VOPRFs. With recent improvements in zero-knowledge proofs, homomorphic encryption, and blind signatures, it is possible to relax some of the assumptions we make in favor of smaller key and communication sizes. I will also discuss potential ways to apply these techniques to build other threshold lattice based protocols.
Bio
Kamil Doruk Gur is a PhD student in the Department of Computer Science at the University of Maryland, College Park, advised by Dr. Jonathan Katz. Although he is interested in a variety of both practical and applied topics, his research focuses on building lattice protocols with interacting parties.
This talk is organized by Migo Gui