Paper 2016/192

On Negation Complexity of Injections, Surjections and Collision-Resistance in Cryptography

Douglas Miller, Adam Scrivener, Jesse Stern, and Muthuramakrishnan Venkitasubramaniam

Abstract

Goldreich and Izsak (Theory of Computing, 2012) initiated the research on understanding the role of negations in circuits implementing cryptographic primitives, notably, considering one-way functions and pseudo-random generators. More recently, Guo, Malkin, Oliveira and Rosen (TCC, 2014) determined tight bounds on the minimum number of negations gates (i.e., negation complexity) of a wide variety of cryptographic primitives including pseudo-random functions, error-correcting codes, hardcore-predicates and randomness extractors. We continue this line of work to establish the following results: 1. First, we determine tight lower bounds on the negation complexity of collision-resistant and target collision-resistant hash-function families. 2. Next, we examine the role of injectivity and surjectivity on the negation complexity of one-way functions. Here we show that, a) Assuming the existence of one-way injections, there exists a monotone one-way injection. Furthermore, we complement our result by showing that, even in the worst-case, there cannot exist a monotone one-way injection with constant stretch. b) Assuming the existence of one-way permutations, there exists a monotone one-way surjection. 3. Finally, we show that there exists list-decodable codes with monotone decoders. In addition, we observe some interesting corollaries to our results.

Note: Incorporated missing acknowledgements

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
monotone boolean circuitsnegation complexityone-way functionscollision-resistant hash-functions
Contact author(s)
muthuv @ cs rochester edu
History
2018-06-19: revised
2016-02-23: received
See all versions
Short URL
https://ia.cr/2016/192
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/192,
      author = {Douglas Miller and Adam Scrivener and Jesse Stern and Muthuramakrishnan Venkitasubramaniam},
      title = {On Negation Complexity of Injections, Surjections and Collision-Resistance in Cryptography},
      howpublished = {Cryptology ePrint Archive, Paper 2016/192},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/192}},
      url = {https://eprint.iacr.org/2016/192}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.