Paper 2024/003

Simple Soundness Proofs

Alex Kampa, Aragon ZK Research
Abstract

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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. https://research.aragon.org/
Keywords
Soundness proofs
Contact author(s)
alex kampa @ azkr org
History
2024-01-05: approved
2024-01-01: received
See all versions
Short URL
https://ia.cr/2024/003
License
Creative Commons Attribution-NonCommercial-NoDerivs
CC BY-NC-ND

BibTeX

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