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 Contact author: muthuv at cs rochester edu, jesseastern@gmail com, ascriven@u rochester edu Available format(s): PDF | BibTeX Citation Version: 20160223:163213 (All versions of this report) Short URL: ia.cr/2016/192 Discussion forum: Show discussion | Start new discussion