Circuit complexity of linear functions: gate elimination and feeble security

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.