Geodesic
Feebly secure cryptographic primitives
Zapiski Nauchnykh Seminarov POMI, Computational complexity theory. Part X, Tome 399 (2012), pp. 32-64 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

In 1992, A. Hiltgen [9] provided first constructions of provably (slightly) secure cryptographic primitives, namely feebly one-way functions. These functions are provably harder to invert than to compute, but the complexity (viewed as the circuit complexity over circuits with arbitrary binary gates) is amplified only by a constant factor (in Hiltgen's works, the factor approaches $2$). In traditional cryptography, one-way functions are the basic primitive of private-key schemes, while public-key schemes are constructed using trapdoor functions. We continue Hiltgen's work by providing examples of feebly secure trapdoor functions where the adversary is guaranteed to spend more time than honest participants (also by a constant factor). We give both a (simpler) linear and a (better) non-linear construction. 
@article{ZNSL_2012_399_a2,
     author = {E. A. Hirsch and O. Melanich and S. I. Nikolenko},
     title = {Feebly secure cryptographic primitives},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {32--64},
     year = {2012},
     volume = {399},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2012_399_a2/}
}
TY  - JOUR
AU  - E. A. Hirsch
AU  - O. Melanich
AU  - S. I. Nikolenko
TI  - Feebly secure cryptographic primitives
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2012
SP  - 32
EP  - 64
VL  - 399
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2012_399_a2/
LA  - en
ID  - ZNSL_2012_399_a2
ER  - 
%0 Journal Article
%A E. A. Hirsch
%A O. Melanich
%A S. I. Nikolenko
%T Feebly secure cryptographic primitives
%J Zapiski Nauchnykh Seminarov POMI
%D 2012
%P 32-64
%V 399
%U http://geodesic.mathdoc.fr/item/ZNSL_2012_399_a2/
%G en
%F ZNSL_2012_399_a2
E. A. Hirsch; O. Melanich; S. I. Nikolenko. Feebly secure cryptographic primitives. Zapiski Nauchnykh Seminarov POMI, Computational complexity theory. Part X, Tome 399 (2012), pp. 32-64. http://geodesic.mathdoc.fr/item/ZNSL_2012_399_a2/

[1] 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

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

[3] A. Davydow, S. I. Nikolenko, “Gate elimination for linear runctions and new feebly secure constructions”, Proceedings of the 6th Computer science symposium in Russia, Lecture Notes in Computer Science, 6651, 2001, 148–161 | DOI | MR

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

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

[6] D. Grigoriev, E. A. Hirsch, K. Pervyshev, “A complete public-key cryptosystem”, Groups, Complexity, and Cryptology, 1:1 (2009), 1–12 | DOI | MR | Zbl

[7] 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

[8] J. Hastad, Computational Limitations for Small Depth Circuits, MIT Press, Cambridge, MA, 1987 | MR

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

[10] A. P. Hiltgen, Cryptographically relevant contributions to combinatorial complexity theory, ETH Series in Information Processing, 3, eds. J. L. Massey, Hartung–Gorre, Konstanz, 1994

[11] A. P. Hiltgen, “Towards a better understanding of one-wayness: facing linear permutations”, Proceedings of EuroCrypt' 98, Lecture Notes in Computer Science, 1233, 1998, 319–333 | DOI | MR

[12] 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

[13] K. Iwama O. Lachish, H. Morizumi, R. Raz, “An explicit lower bound of $5n-o(n)$ for boolean circuits”, Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, 2001, 399–408 | MR

[14] 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

[15] L. A. Levin, “One-way functions and pseudorandom generators”, Combinatorica, 7:4 (1987), 357–363 | DOI | MR | Zbl

[16] J. Massey, The difficulty with difficulty, A guide to the transparencies from the EUROCRYPT' 96 IACR distinguished lecture, 1996

[17] O. Melanich, Nonlinear feebly secure cryptographic primitives, PDMI preprint, 12/2009

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

[19] A. A. Razborov, “Bounded arithmetic and lower bounds”, Feasible Mathematics, v. II, Progress in Computer Science and Applied Logic, 13, eds. P. Clote, J. Remmel, Birkhäuser, 1995, 344–386 | MR | Zbl

[20] R. L. Rivest, A. Shamir, L. Adleman, “A method for obtaining digital signatures and public-key cryptosystems”, Communications of the ACM, 21:2 (1978), 120–126 | DOI | MR | Zbl

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

[22] C. E. Shannon, “Communication theory of secrecy systems”, Bell System Technical Journal, 28:4 (1949), 656–717 | DOI | MR

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

[24] G. S. Vernam, “Cipher printing telegraph systems for secret wire and radio telegraphic communications”, Journal of the IEEE, 55 (1926), 109–115

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