How to Play Mental Solitaire under Continuous Side-Channels: A Completeness Theorem using Secure Hardware by Guy Rothblum, IAS

Abstract: 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.
Joanne Talbot Hanley
Last modified: Mon Aug 16 11:09:38 EDT 2010