The Library
The power of negations in cryptography
Tools
Guo, Siyao, Malkin, Tal, Oliveira, Igor C. and Rosen, Alon (2015) The power of negations in cryptography. In: Dodis, Yevgeniy and Nielsen, Jesper Buus, (eds.) Theory of Cryptography : 12th International Conference, TCC 2015, Warsaw, Poland, March 23-25, 2015, Proceedings, Part I. Lecture Notes in Computer Science, 9014 . Springer-Verlag Berlin Heidelberg, pp. 36-65. ISBN 9783662464939
|
PDF
WRAP-power-negations-cryptography-Oliveira-2019.pdf - Accepted Version - Requires a PDF viewer. Download (987Kb) | Preview |
Official URL: http://dx.doi.org/10.1007/978-3-662-46494-6_3
Abstract
The study of monotonicity and negation complexity for Bool-ean 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.
Unlike one-way functions, one-way permutations cannot be monotone.
We prove that pseudorandom functions require logn − O(1) negations (which is optimal up to the additive term).
We prove that error-correcting codes with optimal distance parameters require logn − O(1) negations (again, optimal up to the additive term).
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.
Item Type: | Book Item | |||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | |||||||||||||||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | |||||||||||||||||||||
Library of Congress Subject Headings (LCSH): | Algebra, Boolean, Cryptography, Negation (Logic), Monotonic functions, Computational complexity | |||||||||||||||||||||
Series Name: | Lecture Notes in Computer Science | |||||||||||||||||||||
Publisher: | Springer-Verlag Berlin Heidelberg | |||||||||||||||||||||
ISBN: | 9783662464939 | |||||||||||||||||||||
ISSN: | 0302-9743 | |||||||||||||||||||||
Book Title: | Theory of Cryptography : 12th International Conference, TCC 2015, Warsaw, Poland, March 23-25, 2015, Proceedings, Part I | |||||||||||||||||||||
Editor: | Dodis, Yevgeniy and Nielsen, Jesper Buus | |||||||||||||||||||||
Official Date: | 2015 | |||||||||||||||||||||
Dates: |
|
|||||||||||||||||||||
Volume: | 9014 | |||||||||||||||||||||
Page Range: | pp. 36-65 | |||||||||||||||||||||
DOI: | 10.1007/978-3-662-46494-6_3 | |||||||||||||||||||||
Status: | Peer Reviewed | |||||||||||||||||||||
Publication Status: | Published | |||||||||||||||||||||
Access rights to Published version: | Restricted or Subscription Access | |||||||||||||||||||||
Date of first compliant deposit: | 7 November 2019 | |||||||||||||||||||||
Date of first compliant Open Access: | 7 November 2019 | |||||||||||||||||||||
RIOXX Funder/Project Grant: |
|
|||||||||||||||||||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year