Geodesic
Circuit complexity of linear functions: gate elimination and feeble security
Zapiski Nauchnykh Seminarov POMI, Computational complexity theory. Part X, Tome 399 (2012), pp. 65-87 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

In this work, we consider provably secure cryptographic constructions in the context of circuit complexity. Based on the ideas of provably secure trapdoor functions previously developed in (Hirsch, Nikolenko, 2009; Melanich, 2009), we present a new linear construction of a provably secure trapdoor function with order of security $5/4$. Besides, we present an in-depth general study of the gate elimination method for the case of linear functions. We also give a non-constructive proof of nonlinear lower bounds on the circuit complexity of linear Boolean functions and upper bounds on circuit implementations of linear Boolean functions, obtaining specific constants. 
@article{ZNSL_2012_399_a3,
     author = {A. P. Davydow and S. I. Nikolenko},
     title = {Circuit complexity of linear functions: gate elimination and feeble security},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {65--87},
     year = {2012},
     volume = {399},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2012_399_a3/}
}
TY  - JOUR
AU  - A. P. Davydow
AU  - S. I. Nikolenko
TI  - Circuit complexity of linear functions: gate elimination and feeble security
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2012
SP  - 65
EP  - 87
VL  - 399
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2012_399_a3/
LA  - ru
ID  - ZNSL_2012_399_a3
ER  - 
%0 Journal Article
%A A. P. Davydow
%A S. I. Nikolenko
%T Circuit complexity of linear functions: gate elimination and feeble security
%J Zapiski Nauchnykh Seminarov POMI
%D 2012
%P 65-87
%V 399
%U http://geodesic.mathdoc.fr/item/ZNSL_2012_399_a3/
%G ru
%F ZNSL_2012_399_a3
A. P. Davydow; S. I. Nikolenko. Circuit complexity of linear functions: gate elimination and feeble security. Zapiski Nauchnykh Seminarov POMI, Computational complexity theory. Part X, Tome 399 (2012), pp. 65-87. http://geodesic.mathdoc.fr/item/ZNSL_2012_399_a3/

[1] M. Ajtai, “$\Sigma_1^1$-formulae on finite structures”, Annals Pure Appl. Logic, 24 (1983), 1–48 | DOI | MR | Zbl

[2] M. Ajtai, C. Dwork, “A public-key cryptosystem with worst-case/average-case equivalence”, Proceedings of the 29th Annual ACM Symposium on Theory of Computing, 1997, 284–293 | MR

[3] E. Allender, “Circuit complexity before the dawn of the new millennium”, Proceedings of the 16th Conference on Foundations of Software Technology and Theoretical Computer Science, 1996, 1–18 | DOI | MR

[4] N. Alon, M. Karchmer, A. Wigderson, “Linear circuits over $\mathrm{GF}(2)$”, SIAM J. Comput., 19:6 (1990), 1064–1067 | DOI | MR | Zbl

[5] N. Blum, “A boolean function requiring $3n$ network size”, Theor. Computer Sci., 28 (1984), 337–345 | DOI | MR | Zbl

[6] R. B. Boppana, M. Sipser, “The Complexity of Finite Functions”, Handbook Theor. Computer Sci., v. A, Algorithms and Complexity, ed. J. van Leeuwen, The MIT Press/Elsevier, 1990 | MR | Zbl

[7] A. Davydow, S. I. Nikolenko, “Gate elimination for linear functions and new feebly secure constructions”, Proceedings of the 6th Computer Science Symposium in Russia, Lecture Notes in Computer Science, 6651, 2011, 148–161 | DOI | MR | Zbl

[8] W. Diffie, M. Hellman, “New directions in cryptography”, IEEE Transact. Inform. Theory, IT-22 (1976), 644–654 | DOI | MR | Zbl

[9] C. Dwork, “Positive Applications of Lattices to Cryptography”, Proceedings of the 22nd International Symposium on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science, 1295, 1997, 44–51 | DOI | MR | Zbl

[10] M. Furst, J. Saxe, M. Sipser, “Parity, circuits, and the polynomial-time hierarchy”, Math. Systems Theory, 17 (1984), 13–27 | DOI | MR | Zbl

[11] O. Goldreich, Foundations of Cryptography. Basic Tools, Cambridge University Press, 2001 | MR | Zbl

[12] D. Grigoriev, E. A. Hirsch, K. Pervyshev, “A Complete Public-Key Cryptosystem”, Groups, Complexity, and Cryptology, 1 (2009), 1–12 | DOI | MR | Zbl

[13] D. Harnik, J. Kilian, M. Naor, O. Reingold, A. Rosen, “On robust combiners for oblivious transfers and other primitives”, Proceedings of EuroCrypt 05, Lecture Notes in Computer Science, 3494, 2005, 96–113 | DOI | MR | Zbl

[14] J. Håstad, Computational Limitations for Small Depth Circuits, MIT Press, Cambridge, MA, 1987 | MR

[15] A. P. Hiltgen, “Constructions of Feebly-One-Way Families of Permutations”, Proc. of AsiaCrypt' 92, 1992, 422–434 | MR

[16] A. P. Hiltgen, Cryptographically Relevant Contributions to Combinatorial Complexity Theory, ETH Series in Information Processing, 3, ed. J. L. Massey, Hartung-Gorre, Konstanz, 1994

[17] A. P. Hiltgen, “Towards a Better Understanding of One-Wayness: Facing Linear Permutations”, Proceedings of EuroCrypt' 98, Lect Notes Computer Science, 1233, 1998, 319–333 | DOI | MR

[18] E. A. Hirsch, S. I. Nikolenko, “A feebly secure trapdoor function”, Proceedings of the 4th Computer Science Symposium in Russia, Lecture Notes in Computer Science, 5675, 2009, 129–142 | DOI | Zbl

[19] N. Koblitz, “The uneasy relationship between mathematics and cryptography”, Notices Amer. Math. Soc., 54 (2007), 972–979 | MR | Zbl

[20] N. Koblitz, A. Menezes, “Another Look at “Provable Security” II”, Proceedings of the Progress in Cryptology – Indocrypt 2006, Lecture Notes in Computer Science, 4329, 2006, 148–175 | DOI | MR | Zbl

[21] N. Koblitz, A. Menezes, “Another Look at “Provable Security””, J. Cryptology, 20:1 (2007), 3–37 | DOI | MR | Zbl

[22] E. A. Lamagna, J. E. Savage, On the logical complexity of symmetric switching functions in monotone and complete bases, Tech. Rep., Brown University, Rhode Island, July 1973

[23] L. A. Levin, “One-Way Functions and Pseudorandom Generators”, Combinatorica, 7:4 (1987), 357–363 | DOI | MR | Zbl

[24] W. J. Paul, “A $2.5n$ lower bound on the combinational complexity of Boolean functions”, SIAM J. Comput., 6 (1977), 427–443 | DOI | MR | Zbl

[25] O. Regev, “On lattices, learning with errors, random linear codes, and cryptography”, Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005, 84–93 | MR | Zbl

[26] O. Regev, “Lattice-Based Cryptography”, Proceedings of the 26th Annual International Cryptology Conference, CRYPTO' 06, Lect. Notes Computer Science, 4117, 2006, 131–141 | DOI | MR | Zbl

[27] R. L. Rivest, A. Shamir, L. Adleman, “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems”, Communications ACM, 21:2 (1978), 120–126 | DOI | MR | Zbl

[28] J. E. Savage, The Complexity of Computing, Wiley, New York, 1976 | MR | Zbl

[29] C. E. Shannon, “Communication Theory of Secrecy Systems”, Bell System Technical J., 28:4 (1949), 656–717 | DOI | MR

[30] R. Smolensky, “Algebraic methods in the theory of lower bounds for Boolean circuit complexity”, Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987, 77–82

[31] L. Stockmeyer, The complexity of decision problems in automata theory and logic, Ph. D. thesis, Massachusetts Institute of Technology, 1974

[32] L. Stockmeyer, “On the combinational complexity of certain symmetric Boolean functions”, Math. Systems Theory, 10 (1977), 323–326 | DOI | MR

[33] L. Stockmeyer, “Classifying the computational complexity of problems”, J. Symbolic Logic, 52 (1987), 1–43 | DOI | MR | Zbl

[34] G. S. Vernam, “Cipher Printing Telegraph Systems For Secret Wire and Radio Telegraphic Communications”, J. IEEE, 55 (1926), 109–115

[35] H. Vollmer, Introduction to Circuit Complexity: a Uniform Approach, Springer Verlag, 1999 | MR

[36] I. Wegener, The Complexity of Boolean Functions, B. G. Teubner; John Wiley Sons, 1987 | MR | Zbl

[37] R. Williams, “Non-Uniform ACC Circuit Lower Bounds”, Proceedings of the 26nd Annual IEEE Conference on Computational Complexity, 2011, 115–125 | MR

[38] A. C.-C. Yao, “On ACC and threshold circuits”, Proceedings of the 31st Annual IEEE Symposium on the Foundations of Computer Science, 1990, 619–627 | MR

[39] A. Kozhevnikov, S. I. Nikolenko, “O polnykh odnostoronnikh funktsiyakh”, Problemy peredachi informatsii, 45:2 (2009), 101–118 | MR | Zbl

[40] L. A. Levin, “Odnostoronnie funktsii”, Problemy peredachi informatsii, 39:1 (2003), 103–117 | MR | Zbl

[41] O. B. Lupanov, “Ob odnom podkhode k sintezu upravlyayuschikh sistem – printsipe lokalnogo kodirovaniya”, Problemy kibernetiki, 14, 1965, 31–110 | MR | Zbl

[42] A. A. Markov, “O minimalnykh kontaktno-ventilnykh dvukhpolyusnikakh dlya monotonnykh simmetricheskikh funktsii”, Problemy kibernetiki, 8, 1962, 117–121 | MR | Zbl

[43] O. Melanich, Nelineinye nadezhnye v slabom smysle kriptograficheskie primitivy, Preprint No 12, POMI, 2009 | MR

[44] E. I. Nechiporuk, “Ob odnoi bulevskoi funktsii”, Dokl. Akad. Nauk SSSR, 169:4 (1966), 765–766 | MR | Zbl

[45] R. G. Nigmatullin, Slozhnost bulevykh funktsii, Nauka, M., 1991 | MR | Zbl

[46] A. A. Razborov, “Nizhnie otsenki monotonnoi slozhnosti logicheskogo permanenta”, Matem. zametki, 37:6 (1985), 887–900 | MR | Zbl

[47] A. A. Razborov, “Nizhnie otsenki razmera skhem ogranichennoi glubiny v polnom bazise, soderzhaschem funktsiyu logicheskogo slozheniya”, Matem. zametki, 41:4 (1987), 598–607 | MR | Zbl

[48] A. A. Razborov, “Nizhnie otsenki slozhnosti realizatsii simmetricheskikh bulevykh funktsii kontaktno-ventilnymi skhemami”, Matem. zametki, 48:6 (1990), 79–90 | MR | Zbl

[49] B. A. Subbotovskaya, “O realizatsii lineinykh funktsii formulami v bazise $\lor,\,\lnot$”, Dokl. Akad. Nauk SSSR, 136:3 (1961), 553–555 | Zbl

[50] B. A. Subbotovskaya, “O sravnenii bazisov pri realizatsii funktsii algebry logiki formulami”, Dokl. Akad. Nauk SSSR, 149:4 (1963), 784–787 | Zbl

[51] V. M. Khrapchenko, “O slozhnosti realizatsii lineinoi funktsii v klasse $\pi$-skhem”, Matem. zametki, 9:1 (1971), 36–40 | MR | Zbl

[52] L. A. Sholomov, “O realizatsii nedoopredelënnykh bulevykh funktsii skhemami iz funktsionalnykh elementov”, Problemy kibernetiki, 21, 1969, 215–226 | Zbl

[53] S. V. Yablonskii, “O klassakh funktsii algebry logiki, dopuskayuschikh prostuyu skhemnuyu realizatsiyu”, Uspekhi mat. nauk, 12:6 (1957), 189–196 | MR | Zbl