The Complexity of Distinguishing Distributions

Cryptography often meets the problem of distinguishing distributions. In this paper we review techniques from hypothesis testing to express the advantage of the best distinguisher limited to a given number of samples. We link it with the Chernoff information and provide a useful approximation based on the squared Euclidean distance. We use it to extend linear cryptanalysis to groups with order larger than 2.


Published in:
Information Theoretic Security, Third International, 210-222
Presented at:
ICITS 2008, Calgary, Canada, August 10-13, 2008
Year:
2008
Publisher:
Springer
Laboratories:




 Record created 2008-09-02, last modified 2018-03-17

n/a:
Download fulltext
PDF

Rate this document:

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