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 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)
- 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
-
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} }