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.


Published in:
Proceedings of the 4th International Conference, ProvSec 2010, 6402, 144-165
Presented at:
4th International Conference, ProvSec 2010, Malacca, Malaysia, October 13-15, 2010
Year:
2010
Publisher:
Springer
Keywords:
Laboratories:




 Record created 2010-10-16, last modified 2018-09-13

n/a:
Download fulltext
PDF

Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)