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
-
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},
url = {https://eprint.iacr.org/2016/192}
}