TY - GEN
T1 - Untangling the Security of Kilian’s Protocol
T2 - 22nd Theory of Cryptography Conference, TCC 2024
AU - Chiesa, Alessandro
AU - Dall’Agnol, Marcel
AU - Guan, Ziyi
AU - Spooner, Nicholas
AU - Yogev, Eylon
N1 - Publisher Copyright:
© International Association for Cryptologic Research 2025.
PY - 2025
Y1 - 2025
N2 - 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.
AB - 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.
KW - succinct interactive arguments
KW - vector commitment schemes
UR - http://www.scopus.com/inward/record.url?scp=85211931236&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85211931236&partnerID=8YFLogxK
U2 - 10.1007/978-3-031-78011-0_6
DO - 10.1007/978-3-031-78011-0_6
M3 - Conference contribution
AN - SCOPUS:85211931236
SN - 9783031780103
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 158
EP - 188
BT - Theory of Cryptography - 22nd International Conference, TCC 2024, Proceedings
A2 - Boyle, Elette
A2 - Boyle, Elette
A2 - Mahmoody, Mohammad
PB - Springer Science and Business Media Deutschland GmbH
Y2 - 2 December 2024 through 6 December 2024
ER -