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

Abstract

In a TLS session, the user is granted access solely to the encryption and decryption oracles, <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>ℰ</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>K</mml:mi> <mml:mo>,</mml:mo> <mml:mi>·</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> </mml:math> and <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>𝒟</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>K</mml:mi> <mml:mo>,</mml:mo> <mml:mi>·</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> </mml:math> , of a symmetric-key encryption scheme, which are treated as black boxes. Here, <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>ℰ</mml:mi> </mml:mrow> </mml:math> denotes the encryption algorithm, <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>𝒟</mml:mi> </mml:mrow> </mml:math> the decryption algorithm, and <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>K</mml:mi> </mml:mrow> </mml:math> 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.