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

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

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},
     publisher = {mathdoc},
     volume = {399},
     year = {2012},
     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
PB  - mathdoc
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
%I mathdoc
%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/