Advanced

An Optimal Sampling Technique for Distinguishing Random S-boxes

Stankovski, Paul LU and Hell, Martin LU (2012) ISIT 2012 In Information Theory Proceedings (ISIT), 2012 IEEE International Symposium on p.846-850
Abstract
The nonrandom behavior of the outputs of a random S-box can be exploited when constructing distinguishers for cryptographic primitives. Different methods of constructing samples from the outputs have been used in the literature. However, it has been unclear exactly how these methods differ and which method is optimal. We analyze four different sampling techniques. We prove that two of these sampling techniques result in dependent samples. We further show one sampling technique that is optimal in terms of error probabilities in the resulting distinguisher. However, this sampling technique is quite impractical as it requires very large storage. We further show a fourth sampling technique that is much more practical, and we prove that it is... (More)
The nonrandom behavior of the outputs of a random S-box can be exploited when constructing distinguishers for cryptographic primitives. Different methods of constructing samples from the outputs have been used in the literature. However, it has been unclear exactly how these methods differ and which method is optimal. We analyze four different sampling techniques. We prove that two of these sampling techniques result in dependent samples. We further show one sampling technique that is optimal in terms of error probabilities in the resulting distinguisher. However, this sampling technique is quite impractical as it requires very large storage. We further show a fourth sampling technique that is much more practical, and we prove that it is equivalent to the optimal one. We also show an improved algorithm for calculating the associated probability distributions that are required for the attack. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
in
Information Theory Proceedings (ISIT), 2012 IEEE International Symposium on
editor
Viswanath, Pramod and
pages
5 pages
conference name
ISIT 2012
external identifiers
  • wos:000312544300172
  • scopus:84867528737
ISSN
2157-8117
2157-8095
ISBN
978-1-4673-2580-6 (Print)
978-1-4673-2578-3 (Online)
DOI
10.1109/ISIT.2012.6284680
language
English
LU publication?
yes
id
41f77893-ea42-4ead-b830-c442319d72ba (old id 2701859)
date added to LUP
2012-06-07 14:17:01
date last changed
2017-01-01 07:29:19
@inproceedings{41f77893-ea42-4ead-b830-c442319d72ba,
  abstract     = {The nonrandom behavior of the outputs of a random S-box can be exploited when constructing distinguishers for cryptographic primitives. Different methods of constructing samples from the outputs have been used in the literature. However, it has been unclear exactly how these methods differ and which method is optimal. We analyze four different sampling techniques. We prove that two of these sampling techniques result in dependent samples. We further show one sampling technique that is optimal in terms of error probabilities in the resulting distinguisher. However, this sampling technique is quite impractical as it requires very large storage. We further show a fourth sampling technique that is much more practical, and we prove that it is equivalent to the optimal one. We also show an improved algorithm for calculating the associated probability distributions that are required for the attack.},
  author       = {Stankovski, Paul and Hell, Martin},
  booktitle    = {Information Theory Proceedings (ISIT), 2012 IEEE International Symposium on},
  editor       = {Viswanath, Pramod},
  isbn         = {978-1-4673-2580-6 (Print)},
  issn         = {2157-8117},
  language     = {eng},
  pages        = {846--850},
  title        = {An Optimal Sampling Technique for Distinguishing Random S-boxes},
  url          = {http://dx.doi.org/10.1109/ISIT.2012.6284680},
  year         = {2012},
}