Быстрый алгоритм статистического оценивания максимальной несбалансированности билинейных аппроксимаций булевых отображений | Прикладная дискретная математика. 2011. № 3(13).

Предложен вероятностный алгоритм, позволяющий оценивать сверху максимальную несбалансированность (в заданном классе) билинейных аппросимаций булевых отображений п переменных за время, линейно зависящее от n.
  • Title Быстрый алгоритм статистического оценивания максимальной несбалансированности билинейных аппроксимаций булевых отображений
  • Headline Быстрый алгоритм статистического оценивания максимальной несбалансированности билинейных аппроксимаций булевых отображений
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 3(13)
  • Date:
  • DOI
Ключевые слова
probabilistic algorithm, bilinear approximation, Boolean mapping, bilinear cryptanalysis, block cipher, вероятностный алгоритм, билинейная аппроксимация, булево отображение, билинейный криптоанализ, блочный шифр
Авторы
Ссылки
Ростовцев А. Г., Маховенко Е. Б. Введение в теорию итерированых шифров. СПб.: НПО «Мир и Семья», 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.
 Быстрый алгоритм статистического оценивания максимальной несбалансированности билинейных аппроксимаций булевых отображений | Прикладная дискретная математика. 2011. № 3(13).
Быстрый алгоритм статистического оценивания максимальной несбалансированности билинейных аппроксимаций булевых отображений | Прикладная дискретная математика. 2011. № 3(13).