Paper 2013/213

On (Destructive) Impacts of Mathematical Realizations over the Security of Leakage Resilient Cryptographic Construction

Guangjun Fan and Yongbin Zhou and F.-X. Standaert and Dengguo Feng

Abstract

Leakage resilient cryptography aims to address the issue of inadvertent and unexpected information leakages from physical cryptographic implementations at algorithmic level in a provable manner. In real world, for an abstract mathematical construction to be an actual physical implementation, it usually undergoes two phases: mathematical realization at algorithmic level and physical realization at implementation level. In the former process, an abstract and generic cryptographic construction is being transformed into an exact and specified mathematical scheme, while in the latter process the output of mathematical realization is being transformed into a physical cryptographic module that runs as a piece of software, or hardware, or combination of both. It turns out that physical realization bears negatively and directly on the security of any cryptographic implementations, which means that the theoretical security of any mathematical cryptographic scheme in leakage free setting (a.k.a. black-box model) does not hold any more when it is implemented and running at physical realization level in leaky setting (e.g. in the context of side-channel attacks). However, it is not clear that whether or not the theoretical security of one leakage resilient cryptographic scheme will still remain secure with considering any details of mathematical realizations. In other words, whether or not the theoretical leakage resilience of one leakage resilient cryptographic construction will still keep unchanged and/or slightly changed, if this scheme is instantiated with cryptographic components that meet their claimed security properties. In this paper, we try to answer this question of important theoretical values, by presenting attacks on three mathematical realizations of the leakage resilient ElGamal encryption scheme EG^* in the paper of E. Kiltz et al. at Asiacrypt2010. Our results convincingly indicate that mathematical realizations of EG^* really have significant destructive impact on its theoretical leakage resilience. This important discovery is not considered or neglected in previous work. Our results suggest that a leakage resilient scheme without considering the mathematical realization may not be secure any more.