Abstract: Lattice-based zero-knowledge proofs are now efficient enough for practical use, and they are enabling several post-quantum privacy-enhancing primitives such as anonymous credentials. However, most current instantiations are tailored to a single prover, i.e., one trusted party holds the witness and generates the proof, which represents a single point of failure. In the threshold setting, where the witness is distributed among n>t provers such that no fewer than t of them are required to recover it, threshold lattice-based zero-knowledge proofs are well understood for Σ-protocols (protocols that require three rounds between a prover and a verifier where the prover speaks first and last) that certify shortness only approximately. However, proving shortness exactly, which is required by applications such as anonymous credentials, requires protocols of more than three rounds and the application of rejection sampling, both of which are problematic in the threshold setting. In this talk, I will explain how we thresholdize the exact lattice-based zero-knowledge proofs of Attema, Lyubashevsky, and Seiler (CRYPTO 2020) and Esgin, Nguyen, and Seiler (ASIACRYPT 2020). We make them rejection-free using the work of Kim, Lee, Seo, and Song (CRYPTO 2023), and non-interactive using the work of Aardal, Aranha, Boudgoust, Kolby, and Takahashi (CRYPTO 2024), and also split the witness using the homomorphic encryption framework of Gur, Katz, and Silde (PQCrypto 2024).
Joint work: Scott Griffy, Victor Youdom Kemmoe, Ngoc Khanh Nguyen, Tjerand Silde.
Suggested readings
