International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 31 October 2014

Siyao Guo, Tal Malkin, Igor C. Oliveira, Alon Rosen
ePrint Report ePrint Report
The study of monotonicity and negation complexity for Boolean

functions has been prevalent in complexity theory as well as in computational learning theory, but little attention has been given to

it in the cryptographic context. Recently, Goldreich and

Izsak (2012) have initiated a study of whether cryptographic

primitives can be monotone, and showed that one-way functions can be

monotone (assuming they exist), but a pseudorandom generator cannot.

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.

Expand

Additional news items may be found on the IACR news page.