Paper 2024/003

Simple Soundness Proofs

Abstract

We present a general method to simplify soundness proofs under certain conditions. Given an adversary $$ able to break a scheme $$ with non-negligible probability $$, we define the concept of $$ of a $$, which is already implicitly used in soundness proofs. If a scheme can be constructed that (1) takes a random configuration $$, being the inputs and execution environment of $$, (2) "guesses" a trace, (3) modifies $$ based on its guess so that the modified configuration $$ is statistically indistinguishable from the original one, (4) is then able to execute $$ correctly under the condition that $$ is a winning configuration and that $$'s guess of the trace was correct, and finally (5) that during its execution $$ is unable extract any information about $$'s guess, then the probability of $$ 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.