Distinguishing Distributions Using Chernoff Information
In this paper, we study the soundness amplification by repetition of cryptographic protocols. As a tool, we use the Chernoff Information. We specify the number of attempts or samples required to distinguish two distributions efficiently in various protocols. This includes weakly verifiable puzzles such as CAPTCHA-like challenge-response protocols, interactive arguments in sequential composition scenario and cryptanalysis of block ciphers. As our main contribution, we revisit computational soundness amplification by sequential repetition in the threshold case, i.e when completeness is not perfect. Moreover, we outline applications to the Leftover Hash Lemma and iterative attacks on block ciphers.
Provsec_2010.pdf
openaccess
291.28 KB
Adobe PDF
ac514d75b0aeb32f9a5a8d9006a1367b