Paper 2014/902

The Power of Negations in Cryptography

Siyao Guo, Tal Malkin, Igor C. Oliveira, and Alon Rosen

Abstract

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) Unlike one-way functions, one-way permutations cannot be monotone. ii) We prove that pseudorandom functions require log n - O(1) negations (which is optimal up to the additive term). iii) Error-correcting codes with optimal distance parameters require log n - O(1) negations (again, optimal up to the additive term). 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.

Note: The new version includes a simpler proof of Proposition 5.9 which fixed a minor issue in the previous argument.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A minor revision of an IACR publication in TCC 2015
Keywords
cryptographic primitivesBoolean circuitsnegation complexity
Contact author(s)
gsy014 @ gmail com
History
2018-08-25: last of 5 revisions
2014-10-31: received
See all versions
Short URL
https://ia.cr/2014/902
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/902,
      author = {Siyao Guo and Tal Malkin and Igor C.  Oliveira and Alon Rosen},
      title = {The Power of Negations in Cryptography},
      howpublished = {Cryptology ePrint Archive, Paper 2014/902},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/902}},
      url = {https://eprint.iacr.org/2014/902}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.