In this paper, we start by filling in the picture and proving that many other basic cryptographic primitives cannot be monotone. We then initiate a quantitative study of the power of negations, asking how many negations are required. We provide several lower bounds, some of them tight, for various cryptographic primitives and building blocks including one-way permutations, pseudorandom functions, small-bias generators, hard-core predicates, error-correcting codes, and randomness extractors. Among our results, we highlight the following.
i) Pseudorandom functions can only be computed by circuits containing at least log n - O(1) negations (which is optimal up to the additive term). ii) We prove that error-correcting codes with optimal distance parameters require log n - O(1) negations (again, optimal up to the additive term). iii) Unlike one-way functions, one-way permutations cannot be monotone. iv) We prove a general result for monotone functions, showing a lower bound on the depth of any circuit with t negations on the bottom that computes a monotone function f in terms of the monotone circuit depth of f. This result addresses a question posed by Koroth and Sarma (2014) in the context of the circuit complexity of the Clique problem.
Our results lead to a few intriguing open problems, and to interesting directions for further research.
Category / Keywords: foundations / cryptographic primitives, Boolean circuits, negation complexity Original Publication (with minor differences): IACR-TCC-2015 Date: received 31 Oct 2014, last revised 14 Jan 2015 Contact author: gsy014 at gmail com Available format(s): PDF | BibTeX Citation Version: 20150114:181544 (All versions of this report) Discussion forum: Show discussion | Start new discussion