Paper 2024/003
Simple Soundness Proofs
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 nonnegligible 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 bitlength 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)
 Category
 Cryptographic protocols
 Publication info
 Published elsewhere. https://research.aragon.org/
 Keywords
 Soundness proofs
 Contact author(s)
 alex kampa @ azkr org
 History
 20240105: approved
 20240101: received
 See all versions
 Short URL
 https://ia.cr/2024/003
 License

CC BYNCND
BibTeX
@misc{cryptoeprint:2024/003, author = {Alex Kampa}, title = {Simple Soundness Proofs}, howpublished = {Cryptology ePrint Archive, Paper 2024/003}, year = {2024}, note = {\url{https://eprint.iacr.org/2024/003}}, url = {https://eprint.iacr.org/2024/003} }