Theory Seminar - Concrete Security Bounds in Cryptography: Advancing the Meta-Reduction Paradigm

Concrete Security Bounds in Cryptography: Advancing the Meta-Reduction Paradigm

Abstract: A central aspect of research in theoretical cryptography is defining the boundaries of what can be proven secure, both via positive results, which take the form of security reductions, and negative (impossibility) results which prove the non-existence of such reductions. In this talk, we focus on one of the key methods for proving impossibility results, known as the meta-reduction paradigm. Roughly speaking, given a reduction which uses an adversary for some primitive to break the security of an underlying assumption (thus demonstrating that the primitive is secure as long as the assumption is), if we create a "meta-reduction" which efficiently simulates the interaction between this reduction and an "ideal" but inefficient adversary, then we can show that the meta-reduction itself efficiently breaks the assumption, and so either such a reduction cannot exist or the underlying assumption is inherently insecure.

 In this talk, I will present two of my recent works, produced jointly with Rafael Pass and Elaine Shi, which leverage the meta-reduction paradigm to prove strong bounds on the "efficiency", or concrete security loss, of reductions that are not impossible. Notably, these constitute the first "complete" concrete security bounds, as, prior to ours, all such results have required significant restrictions on the class of reductions for which they provide bounds. Our first result (presented at TCC '18) removes these restrictions from a classical result by Jean-Sebastien Coron (Eurocrypt '02), ruling out any "efficient" (linear-preserving) reduction from unique or rerandomizable digital signature schemes to arbitrary assumptions. The second provides a similar, yet more technically intricate, impossibility result for reductions from multi-user security of families of pseudorandom functions. Using these works as a starting point, I hope to work towards investigating the full extent and limitations of what we can prove via meta-reductions