HomeIssuesFast algorithm for statistical estimation of the maximal imbalance of bilinear approximations of Boolean mappings

Fast algorithm for statistical estimation of the maximal imbalance of bilinear approximations of Boolean mappings | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2011. № 3(13).

We propose a probabilistic algorithm fordetermining the upper bounds of the maximal imbalance (in a given class) of bilinear approximationsof Boolean mappings of N variables for a time linearly dependent on N.
Download file
Counter downloads: 65
  • Title Fast algorithm for statistical estimation of the maximal imbalance of bilinear approximations of Boolean mappings
  • Headline Fast algorithm for statistical estimation of the maximal imbalance of bilinear approximations of Boolean mappings
  • Publesher Tomask State UniversityTomsk State University
  • Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 3(13)
  • Date:
  • DOI
Keywords
probabilistic algorithm, bilinear approximation, Boolean mapping, bilinear cryptanalysis, block cipher, вероятностный алгоритм, билинейная аппроксимация, булево отображение, билинейный криптоанализ, блочный шифр
Authors
References
Ростовцев А. Г., Маховенко Е. Б. Введение в теорию итерированых шифров. СПб.: НПО «Мир и Семья», 2003. 302 с.
ГОСТ 28147-89. Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования. М.: Госстандарт СССР, 1989.
Логачев О. А., Сальников А. А., Ященко В. В. Булевы функции в теории кодирования и криптологии. М.: МЦНМО, 2004. 470 с.
Fourquet R., Loidreau P., and Tavernier C. Finding good linear approximations of block ciphers and its application to cryptanalysis of redused round DES // Proc. of the WCC 2009: ced.tavernier.free.fr/publications.
Trevisan L. Some applications of coding theory in computational complexity // http:// eprint.arXiv:cs./0409044v1. 24 Sept., 2004.
Kabatiansky G. and Tavernier C. List decoding of Reed-Muller codes // Proc. Ninth Int. Workshop on Algebraic and Comb. Coding Theory. Kranevo, Bulgaria, 2004. P. 230-235.
Goldreich O., Rubinfeld R., and Sudan M. Learning polynomials with queries: the highly noisy case // SIAM J. Discrete Math. 2000. V. 13. No. 4. P. 535-570. Extended version: http:// people.csail.mit.edu/madhu/papers.html.
Bshouty N., Jackson J., and Tamon C. More efficient PAC-learning of DNF with membership queries under the uniform distribution // Proc. 12th Annual Conf. on Comput. Learning Theory. NY, USA: ACM, 1999. P. 286-295.
Levin L. A. Randomness and non-determinism / / J . Symbolic Logic. 1993. V. 58. No. 3. P. 1102-1103.
Goldreich O. and Levin L. A. A hard core predicate for all one-way functions // Proc. of the 21th ACM Sympos. of Theory of Computing. NY, USA: ACM, 1989. P. 25-32.
Алексейчук А. Н., Шевцов А. С. Верхние оценки несбалансированности билинейных аппроксимаций раундовых функций блочных шифров // Кибернетика и системный анализ. 2010. №4. С. 42-51.
Courtois N. T. Feistel schemes and bi-linear cryptanalysis // Advances in Cryptology - CRYPTO'04. Springer Verlag, 2004. P. 23-40.
Алексейчук А. Н., Шевцов А. С. Показатели и оценки стойкости блочных шифров относительно статистических атак первого порядка // Реестращя, збертання i обробка даних. 2006. Т. 8. №4. С. 53-63.
Fast algorithm for statistical estimation of the maximal imbalance of bilinear approximations of Boolean mappings | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2011. № 3(13).
Fast algorithm for statistical estimation of the maximal imbalance of bilinear approximations of Boolean mappings | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2011. № 3(13).
Download full-text version
Counter downloads: 248
Download file