How to Play Mental Solitaire under Continuous Side-Channels: A Completeness Theorem using Secure Hardware
Speaker: Guy Rothblum , IAS
Date: April 23 2010
Time: 10:30AM to 12:00PM
Location: 32-G449 Patil/Kiva
Host: Yael Tauman Kalai, Microsoft, NE
Contact: Be Blackburn , 3-6098, imbe@mit.edu
Relevant URL: We present a general method to compile any cryptographic algorithm
into one which resists side channel attacks of the only computation
leaks information variety for an unbounded number of executions. Our
method uses as a building block a semantically secure bit encryption
scheme with the following additional operations: key refreshing,
oblivious generation of cipher texts,cipher-text re-generation, and
blinded homomorphic evaluation of one single complete gate
(e.g. NAND). Furthermore, the security properties of the encryption
scheme should withstand bounded leakage incurred while performing each
of the above operations.
We show how to implement such an encryption scheme under the DDH
intractability assumption and the existence of a simple secure
hardware component. The hardware component is independent of the
encryption scheme secret key. The encryption scheme resists leakage
attacks which are polynomial time computable function, whose output
size is bounded by a constant fraction of the security parameter.
Our technical contributions include showing that the BHHO/Naor-Segev
cryptosystem is resilient to leakage on both keys and ciphertexts
(each separately), a method for refreshing secret keys and
ciphertexts, homomorphic evaluation procedure for NANDs on encrypted
values, which can be blinded even in the presence of side-channels
(using simple secure hardware), and a framework for composable
security under side-channel attacks.
Joint work with Shafi Goldwasser.
See other events that are part of CIS/Microsoft Seminars 2009/2010
See other events happening in April 2010
