Post-quantum Signatures from Secure Computation

Speaker:

Dr. Jonathan Katz
University of Maryland, College Park

Abstract:

Recent progress in secure computation has shown that many ideas previously viewed as purely theoretical can, in fact, lead to amazingly efficient instantiations. With this motivation in mind, we explore applications of the "MPC-in-the-head" approach due to Ishai et al. for constructing zero-knowledge (ZK) proofs from protocols for secure multi-party computation (MPC). We show how to instantiate that approach with MPC protocols in the preprocessing model; along with several optimizations, this yields a ZK proof with comparable computation as in prior work but less communication for circuits containing roughly 300-100,000 AND gates.

Our ZK proof can, in turn, be used to construct a digital signature scheme based only on symmetric-key primitives believed to be quantum secure. We show (surprisingly) that the resulting scheme has shorter signatures than other leading candidates for "post-quantum" signatures while still offering excellent running times. Extensions of our scheme yield efficient ring/group signatures, also based on symmetric-key primitives alone. We believe our schemes are thus competitive for standardization as part of NIST's ongoing standardization efforts for post-quantum cryptosystems.

Bio:

Jonathan Katz is a professor of computer science at the University of Maryland, where he is also director of the Maryland Cybersecurity Center. His research interests lie broadly in the fields of cryptography, privacy, and the science of cybersecurity, and he is a co-author of the widely used textbook "Introduction to Modern Cryptography," now in its second edition. Katz was a member of the DARPA Computer Science Study Group in 2009-2010 and, since then, has worked with a number of government agencies on topics relating to cryptography, cybersecurity, and privacy- preserving technologies. He currently serves on the steering committee for the IEEE Cybersecurity Initiative as well as on the State of Maryland Cybersecurity Council. Katz received a Humboldt Award in 2015, and the University of Maryland Distinguished Scholar-Teacher Award in 2017.