Related-key secure key encapsulation from extended computational bilinear Diffie–Hellman

• Main Authors: QIN, Brandon, LIU, Shengli, SUN, Shifeng, DENG, Robert H., GU, Dawu
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2017
• Subjects: Key-encapsulation mechanism; Related-key attacks; BDH; Hardware Systems; Software Engineering
• Online Access: https://ink.library.smu.edu.sg/sis_research/3678; https://ink.library.smu.edu.sg/context/sis_research/article/4680/viewcontent/1_s20_S0020025517306667_main.pdf
• Institution: Singapore Management University

As a special type of fault injection attacks, Related-Key Attacks (RKAs) allow an adversary to manipulate a cryptographic key and subsequently observe the outcomes of the cryptographic scheme under these modified keys. In the real life, related-key attacks are already practical enough to be implemented on cryptographic devices. To avoid cryptographic devices suffering from related-key attacks, it is necessary to design a cryptographic scheme that resists against such attacks. This paper proposes an efficient RKA-secure Key Encapsulation Mechanism (KEM), in which the adversary can modify the secret key sk to any value f(sk), as long as, f is a polynomial function of a bounded degree d. Especially, the polynomial-RKA security can be reduced to a hard search problem, namely d-extended computational Bilinear Diffie-Hellman (BDH) problem, in the standard model. Our construction essentially refines the security of Haralambiev et al.’s BDH-based KEM scheme from chosen-ciphertext security to related-key security. The main technique applied in our scheme is the re-computation of the public key in the decryption algorithm so that any (non-trivial) modification to the secret key can be detected.