Paper 2023/1595

CDLS: Proving Knowledge of Committed Discrete Logarithms with Soundness

Sofia Celi, Brave Software
Shai Levin, University of Auckland
Joe Rowell, Royal Holloway, University of London

$\Sigma$-protocols, a class of interactive two-party protocols, which are used as a framework to instantiate many other authentication schemes, are automatically a proof of knowledge (PoK) given that they satisfy the "special-soundness" property. This fact provides a convenient method to compose $\Sigma$-protocols and PoKs for complex relations. However, composing in this manner can be error-prone. While they must satisfy special-soundness, this is unfortunately not the case for many recently proposed composed practical schemes. Here we explore two schemes: ZKAttest from Faz-Hernández et al. and the ones from Agrawal et al., and show that their $\Sigma$-protocol's suffer from several security misdesigns which invalidate their security proofs, and state a practical cheap attack on ZKAttest's implementation. By exploring and resolving their misdesigns, we propose CDLS, a sound and secure variant of their protocols.

Note: We resolve an error discovered in the reviews process with respect to the soundness of the proof of sum.

Available format(s)
Attacks and cryptanalysis
Publication info
Contact author(s)
cherenkov @ riseup net
shai levin @ auckland ac nz
Joe Rowell 2015 @ live rhul ac uk
2024-01-05: revised
2023-10-14: received
See all versions
Short URL
Creative Commons Attribution


      author = {Sofia Celi and Shai Levin and Joe Rowell},
      title = {CDLS: Proving Knowledge of Committed Discrete Logarithms with Soundness},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1595},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.