Black-Box Construction of Partial Key Exposure Resilient Symmetric-Key Encryption Scheme

In a TLS session, the user is granted access solely to the encryption and decryption oracles, ℰ ( K , · ) and 𝒟 ( K , · ) , of a symmetric-key encryption scheme, which are treated as black boxes. Here, ℰ denotes the encryption algorithm, 𝒟 the decryption algorithm, and K the secret key. In this paper, by utilizing any secure symmetric-key encryption scheme as a black-box primitive, we demonstrate a method for constructing a symmetric-key encryption scheme that remains secure even in the presence of partial key leakage. This approach can, for example, enhance the security of TLS sessions.

Our construction employs the All-Or-Nothing Transform (AONT) in the pre-processing phase. Therefore we provide a tighter security analysis of existing AONT constructions, and establish a lower bound on their security. Finally we propose a new AONT construction that achieves security beyond this lower bound.