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