New proof techniques for adaptive security – Zahra Jafargholi – 8.25.16

Master’s Thesis Defense

Abstract

Selective security refers to the case where the attacker decides on some parameters of the attack before the attack even begins. In contrast, adaptive security refers to the case where the attacker can make decisions throughout the course of the attack. Therefore these decisions can depend on the information the attacker receives during the attack. One can use complexity-leveraging to reduce the problem of proving adaptive security to proving selective security. This technique which involves guessing the decisions the attacker makes during the attack, leads to an exponential loss in security reduction. Here we look at two settings, where we prove adaptive security from scratch – without reducing to selective security. The first problem, Generalized Selective Decryption (GSD) Game, captures security requirements of Broadcast and Multicast Encryption protocols. We give an analysis of the system that proves GSDG is adaptively secure with only a quasi-polynomial loss in the secur ity reduction. In study of the second problem, Adaptively Secure Garbling Schemes, we devise a new garbling scheme that has Yao’s garbling scheme at heart. Our adaptively secure garbling scheme has a garbled input of length proportional to the circuit’s width. This is a considerable improvement over the previous schemes where the garbled input grew with the size of the entire circuit. Finally, we use the new techniques to analyze adaptive security of Yao’s garbling scheme. We show that that Yao’s garbling scheme is adaptively secure for NC1 circuits.

Committee

Daniel Wichs (Advisor)
Rajmohan Rajaraman
Jonathan Ullman
Vinod Vaikuntanathan (MIT)