CDLS: Proving Knowledge of Committed Discrete Logarithms with Soundness

Sofia Celi; Shai Levin; Joe Rowell

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

Abstract

$Σ$ -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 $Σ$ -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 -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.

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: Preprint.
Keywords: Sigma-protocols Zero-Knowledge PoK Elliptic-Curves
Contact author(s): cherenkov @ riseup net
shai levin @ auckland ac nz
Joe Rowell 2015 @ live rhul ac uk
History: 2024-01-05: revised; 2023-10-14: received; See all versions
Short URL: https://ia.cr/2023/1595
License: CC BY

BibTeX

@misc{cryptoeprint:2023/1595,
      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},
      url = {https://eprint.iacr.org/2023/1595}
}