Limitations on Provable Security, and Beyond

In this talk, I ask the question of how to bypass impossibility results. The focus in this talk is on my own the impossibility result that rules out a large class of three-move blind signatures in the standard model (EUROCRYPT '10). The result shows that finding security proofs for the well-known blind signature schemes by Chaum, and by Pointcheval and Stern in the standard model via black-box reductions is hard. Then, I show how to bypass this impossibility result presenting the first round-optimal, i.e., two-move, blind signature scheme in the standard model. This positive result (CRYPTO '11) proves not only the existence of round optimal blind signatures, but it is also a positive example of a scenario in which known impossibility results for concurrently-secure two-party computation (Lindell, STOC '03, TCC '04) can be avoided to achieve meaningful game-based security definitions.