Paper 2024/003

Simple Soundness Proofs

Alex Kampa, Aragon ZK Research

We present a general method to simplify soundness proofs under certain conditions. Given an adversary $\mathcal{A}$ able to break a scheme $S$ with non-negligible probability $t$, we define the concept of $\textit{trace}$ of a $\textit{winning configuration}$, which is already implicitly used in soundness proofs. If a scheme can be constructed that (1) takes a random configuration $e$, being the inputs and execution environment of $\mathcal{A}$, (2) "guesses" a trace, (3) modifies $e$ based on its guess so that the modified configuration $e'$ is statistically indistinguishable from the original one, (4) is then able to execute $\mathcal{A}$ correctly under the condition that $e'$ is a winning configuration and that $B$'s guess of the trace was correct, and finally (5) that during its execution $\mathcal{A}$ is unable extract any information about $B$'s guess, then the probability of $B$ winning can be expressed as a simple function of $t$ and the bit-length of the trace, namely $\frac{t}{2^m}$. Soundness then results if $2^m$ is polynomial in the security parameter. To illustrate the concept, a concrete application of this method to a simple binary voting scheme is then described in detail.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere.
Soundness proofs
Contact author(s)
alex kampa @ azkr org
2024-01-05: approved
2024-01-01: received
See all versions
Short URL
Creative Commons Attribution-NonCommercial-NoDerivs


      author = {Alex Kampa},
      title = {Simple Soundness Proofs},
      howpublished = {Cryptology ePrint Archive, Paper 2024/003},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.