## Abstract

We study zero-knowledge arguments where proofs are: of knowledge, short, publicly-verifiable and produced without interaction. While zkSNARKs satisfy these requirements, we build such proofs in a constrained theoretical setting: in the standard-model—i.e., without a random oracle—and without assuming public-verifiable SNARKs (or even NIZKs, for some of our constructions) or primitives currently known to imply them. We model and construct a new primitive, SPuC (Succinct Publicly-Certifiable System), where: a party can prove knowledge of a witness w by publishing a proof π
_{0} ; the latter can then be certified non-interactively by a committee sharing a secret; any party in the system can now verify the proof through its certificates; the total communication complexity should be sublinear in | w|. We construct SPuCs generally from (leveled) FHE, homomorphic signatures and linear-only encryption, all instantiatable from lattices and thus plausibly quantum-resistant. We also construct them in the two-party case replacing FHE with the simpler primitive of homomorphic secret-sharing. Our model has practical applications in blockchains and in other protocols where there exist committees sharing a secret and it is necessary for parties to prove knowledge of a solution to some puzzle. Our constructions can be seen as a way to compile a designated-verifier SNARK into a proof system with a flavor of public-verifiability with similar efficiency features of the starting dvSNARK (e.g., proving time). We show that one can construct a version of SPuCs with robust proactive security from similar assumptions. In a proactively secure model the committee reshares its secret from time to time. Such a model is robust if the committee members can prove they performed this resharing step correctly. Along the way to our goal we define and build Proactive Universal Thresholdizers, a proactive version of the Universal Thresholdizer defined in Boneh et al. [Crypto 2018].

Original language | English |
---|---|

Title of host publication | Progress in Cryptology – INDOCRYPT 2021 - 22nd International Conference on Cryptology in India, 2021, Proceedings : 22nd International Conference on Cryptology in India, Jaipur, India, December 12-15, 2021, Proceedings |

Editors | Avishek Adhikari, Ralf Küsters, Bart Preneel |

Number of pages | 25 |

Publisher | Springer |

Publication date | 2021 |

Pages | 607-631 |

ISBN (Print) | 978-3-030-92517-8 |

DOIs | |

Publication status | Published - 2021 |

Event | 22nd International Conference on Cryptology in India - The LNM Institute of Information Technology, Jaipur, India Duration: 13 Dec 2021 → 15 Dec 2021 Conference number: 22 https://indocrypt2021.lnmiit.ac.in |

### Conference

Conference | 22nd International Conference on Cryptology in India |
---|---|

Number | 22 |

Location | The LNM Institute of Information Technology |

Country/Territory | India |

City | Jaipur |

Period | 13/12/2021 → 15/12/2021 |

Internet address |

Series | Lecture Notes in Computer Science |
---|---|

Volume | 13143 |

ISSN | 0302-9743 |