Geodesic
Fast algorithm for statistical estimation of the maximal imbalance of bilinear approximations of Boolean mappings
Prikladnaâ diskretnaâ matematika, no. 3 (2011), pp. 5-11.

Voir la notice de l'article provenant de la source Math-Net.Ru

We propose a probabilistic algorithm for determining the upper bounds of the maximal imbalance (in a given class) of bilinear approximations of Boolean mappings of $n$ variables for a time linearly dependent on $n$.
Keywords: block cipher, bilinear cryptanalysis, Boolean mapping, bilinear approximation, probabilistic algorithm. 
@article{PDM_2011_3_a0,
     author = {A. N. Alekseychuk and A. S. Shevtsov},
     title = {Fast algorithm for statistical estimation of the maximal imbalance of bilinear approximations of {Boolean} mappings},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {5--11},
     publisher = {mathdoc},
     number = {3},
     year = {2011},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2011_3_a0/}
}
TY  - JOUR
AU  - A. N. Alekseychuk
AU  - A. S. Shevtsov
TI  - Fast algorithm for statistical estimation of the maximal imbalance of bilinear approximations of Boolean mappings
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2011
SP  - 5
EP  - 11
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2011_3_a0/
LA  - ru
ID  - PDM_2011_3_a0
ER  - 
%0 Journal Article
%A A. N. Alekseychuk
%A A. S. Shevtsov
%T Fast algorithm for statistical estimation of the maximal imbalance of bilinear approximations of Boolean mappings
%J Prikladnaâ diskretnaâ matematika
%D 2011
%P 5-11
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2011_3_a0/
%G ru
%F PDM_2011_3_a0
A. N. Alekseychuk; A. S. Shevtsov. Fast algorithm for statistical estimation of the maximal imbalance of bilinear approximations of Boolean mappings. Prikladnaâ diskretnaâ matematika, no. 3 (2011), pp. 5-11. http://geodesic.mathdoc.fr/item/PDM_2011_3_a0/

[1] Courtois N. T., “Feistel schemes and bi-linear cryptanalysis”, Advances in Cryptology – CRYPTO' 04, Springer Verlag, 2004, 23–40 | MR | Zbl

[2] Alekseichuk A. N., Shevtsov A. S., “Pokazateli i otsenki stoikosti blochnykh shifrov otnositelno statisticheskikh atak pervogo poryadka”, Reєstratsiya, zberigannya i obrobka danikh, 8:4 (2006), 53–63

[3] Alekseichuk A. N., Shevtsov A. S., “Verkhnie otsenki nesbalansirovannosti bilineinykh approksimatsii raundovykh funktsii blochnykh shifrov”, Kibernetika i sistemnyi analiz, 2010, no. 4, 42–51

[4] Goldreich O., Levin L. A., “A hard core predicate for all one-way functions”, Proc. of the 21th ACM Sympos. of Theory of Computing, ACM, NY, USA, 1989, 25–32

[5] Levin L. A., “Randomness and non-determinism”, J. Symbolic Logic, 58:3 (1993), 1102–1103

[6] Bshouty N., Jackson J., Tamon C., “More efficient PAC-learning of DNF with membership queries under the uniform distribution”, Proc. 12th Annual Conf. on Comput. Learning Theory, ACM, NY, USA, 1999, 286–295 | MR

[7] Goldreich O., Rubinfeld R., Sudan M., “Learning polynomials with queries: the highly noisy case”, SIAM J. Discrete Math., 13:4 (2000), 535–570 ; \nofrills Extended version: http://people.csail.mit.edu/madhu/papers.html | DOI | MR | Zbl

[8] Kabatiansky G., Tavernier C., “List decoding of Reed-Muller codes”, Proc. Ninth Int. Workshop on Algebraic and Comb. Coding Theory, Kranevo, Bulgaria, 2004, 230–235

[9] Trevisan L., Some applications of coding theory in computational complexity, 24 Sept. 2004, arXiv: cs/0409044v1 | MR

[10] Fourquet R., Loidreau P., Tavernier C., Finding good linear approximations of block ciphers and its application to cryptanalysis of redused round DES, Proc. of the WCC 2009 http://ced.tavernier.free.fr/index_fichiers/Articles/Linear_Approximations.pdf

[11] Logachev O. A., Salnikov A. A., Yaschenko V. V., Bulevy funktsii v teorii kodirovaniya i kriptologii, MTsNMO, M., 2004, 470 pp. | MR

[12] GOST 28147-89. Sistemy obrabotki informatsii. Zaschita kriptograficheskaya. Algoritm kriptograficheskogo preobrazovaniya, Gosstandart SSSR, M., 1989

[13] Rostovtsev A. G., Makhovenko E. B., Vvedenie v teoriyu iterirovanykh shifrov, NPO “Mir i Semya”, SPb., 2003, 302 pp.