Post-quantum signatures from secure computation

Jonathan Katz
University of Maryland


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.