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 $\mathit{\text{trace}}$ of a $\mathit{\text{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^{\prime }$ is statistically indistinguishable from the original one, (4) is then able to execute $\mathcal{A}$ correctly under the condition that $e^{\prime }$ 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 $$ and the bit-length of the trace, namely $$. Soundness then results if $$ 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.