Cryptology ePrint Archive: Report 2016/192

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

Douglas Miller and Adam Scrivener and 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.

Category / Keywords: foundations / monotone boolean circuits, negation complexity, one-way functions, collision-resistant hash-functions

Date: received 23 Feb 2016, last revised 19 Jun 2018

Contact author: muthuv at cs rochester edu

Available format(s): PDF | BibTeX Citation

Note: Incorporated missing acknowledgements

Version: 20180619:154552 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]