Charles River Crypto Day – The Power of Negations in Cryptography

The study of monotonicity and negation complexity for Boolean 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 work, 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. i) Unlike one-way functions, one-way permutations cannot be monotone. ii) We prove that pseudorandom functions require log n−O(1) negations (which is optimal up to the additive term). iii) Error-correcting codes with optimal distance parameters require log n−O(1) negations (again, optimal up to the additive term). iv) 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. Joint work with Siyao Guo, Igor Carboni Oliveira, and Alon Rosen.

Speaker Details

Tal Malkin is an associate professor of Computer Science at Columbia University, where she directs the Cryptography Lab. She received her Ph.D. in Computer Science from the Massachusetts Institute of Technology in 2000, and joined Columbia after three years as a research scientist in the Secure Systems Research Department at AT&T Labs – Research. Her research interests are in cryptography, security, complexity theory, and related areas. She has served on program committees and steering committees for over twenty international conferences on cryptography, theoretical computer science, and security. She chaired the CT-RSA conference, and is on the editorial board for the Theory of Computing Journal. Prof. Malkin is the recipient an NSF CAREER award, an IBM faculty partnership award, Google Faculty Research award, and a research fellowship of the Columbia University Diversity Initiative. Her research has been funded by NSF, NSA, NYSIA, DHS, IARPA, and gifts from Google, IBM, Mitsubishi, and NEC.

Date:
Speakers:
Tal Malkin
Affiliation:
Columbia University