Untangling the Security of Kilian’s Protocol: Upper and Lower Bounds

Alessandro Chiesa, Marcel Dall’Agnol, Ziyi Guan, Nicholas Spooner, Eylon Yogev

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Sigma protocols are elegant cryptographic proofs that have become a cornerstone of modern cryptography. A notable example is Schnorr’s protocol, a zero-knowledge proof-of-knowledge of a discrete logarithm. Despite extensive research, the security of Schnorr’s protocol in the standard model is not fully understood. In this paper we study Kilian’s protocol, an influential public-coin interactive protocol that, while not a sigma protocol, shares striking similarities with sigma protocols. The first example of a succinct argument, Kilian’s protocol is proved secure via rewinding, the same idea used to prove sigma protocols secure. In this paper we show how, similar to Schnorr’s protocol, a precise understanding of the security of Kilian’s protocol remains elusive. We contribute new insights via upper bounds and lower bounds. Upper bounds. We establish the tightest known bounds on the security of Kilian’s protocol in the standard model, via strict-time reductions and via expected-time reductions. Prior analyses are strict-time reductions that incur large overheads or assume restrictive properties of the PCP underlying Kilian’s protocol.Lower bounds. We prove that significantly improving on the bounds that we establish for Kilian’s protocol would imply improving the security analysis of Schnorr’s protocol beyond the current state-of-the-art (an open problem). This partly explains the difficulties in obtaining tight bounds for Kilian’s protocol. Upper bounds. We establish the tightest known bounds on the security of Kilian’s protocol in the standard model, via strict-time reductions and via expected-time reductions. Prior analyses are strict-time reductions that incur large overheads or assume restrictive properties of the PCP underlying Kilian’s protocol. Lower bounds. We prove that significantly improving on the bounds that we establish for Kilian’s protocol would imply improving the security analysis of Schnorr’s protocol beyond the current state-of-the-art (an open problem). This partly explains the difficulties in obtaining tight bounds for Kilian’s protocol.

Original languageEnglish (US)
Title of host publicationTheory of Cryptography - 22nd International Conference, TCC 2024, Proceedings
EditorsElette Boyle, Elette Boyle, Mohammad Mahmoody
PublisherSpringer Science and Business Media Deutschland GmbH
Pages158-188
Number of pages31
ISBN (Print)9783031780103
DOIs
StatePublished - 2025
Event22nd Theory of Cryptography Conference, TCC 2024 - Milan, Italy
Duration: Dec 2 2024Dec 6 2024

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume15364 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference22nd Theory of Cryptography Conference, TCC 2024
Country/TerritoryItaly
CityMilan
Period12/2/2412/6/24

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Keywords

  • succinct interactive arguments
  • vector commitment schemes

Fingerprint

Dive into the research topics of 'Untangling the Security of Kilian’s Protocol: Upper and Lower Bounds'. Together they form a unique fingerprint.

Cite this