Bit Security Estimation for Leakage-Prone Key Establishment Schemes

The security guarantees of cryptographic primitives are subject to the assumption that established keys are known only by the legitimate users and no information about the key bits is known by illegitimate users. Unfortunately, this assumption may not be applicable in leakage-prone key establishment schemes. Namely, information leakage about an established key (defined as a bit inference rate of an adversary that is strictly greater than 50%) reduces its computational effort required in an exhaustive key search. In this paper, we present a methodology and a polynomial-time algorithm that determines the exact impact of information leakage on a generated bit sequence and expressed these findings in terms of the achieved level of bit security. Additional simulation results enable us to determine the achieved level of bit security of a leakage-prone bit sequence or, conversely, enable us to determine the length of a bit sequence necessary to achieve a selected level of bit security.