BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:The Power of Negations in Cryptography  - Siyao Guo\, The Chinese 
 University of Hong Kong
DTSTART:20150909T100000Z
DTEND:20150909T110000Z
UID:TALK60685@talks.cam.ac.uk
CONTACT:Microsoft Research Cambridge Talks Admins
DESCRIPTION:The study of monotonicity and negation complexity for Boolean 
 functions has been prevalent in complexity theory as well as in computatio
 nal learning theory\, but little attention has been given to it in the cry
 ptographic context. Recently\, Goldreich and Izsak (2012) have initiated a
  study of whether cryptographic primitives can be monotone\, and showed th
 at one-way functions can be monotone (assuming they exist)\, but a pseudor
 andom generator cannot. \nIn this paper\, we start by filling in the pictu
 re and proving that many other basic cryptographic primitives cannot be mo
 notone. 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 blo
 cks including one-way permutations\, pseudorandom functions\, small-bias g
 enerators\, hard-core predicates\, error-correcting codes\, and randomness
  extractors. Among our results\, we highlight the following. \n•	Unlike 
 one-way functions\, one-way permutations cannot be monotone. 
\n•	We p
 rove that pseudorandom functions require log n − O(1) negations (which i
 s optimal 
up to the additive term). 
\n•	Error-correcting codes wit
 h optimal distance parameters require log n − O(1) negations (again\, op
 timal up to the additive term). 
\n•	We prove a general result for mon
 otone 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 t
 he monotone circuit depth of f. 
\nJoint work with Tal Malkin\, Igor Car
 boni Oliveira and Alon Rosen. \n
LOCATION:Small Lecture Theatre\, Microsoft Research Ltd\, 21 Station Road\
 , Cambridge\, CB1 2FB
END:VEVENT
END:VCALENDAR