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

Baodong Qin, Shengli Liu, Shifeng Sun, Robert H. Deng, Dawu Gu

Research output: Contribution to journalArticleResearchpeer-review

Abstract

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.

Original languageEnglish
Pages (from-to)1-11
Number of pages11
JournalInformation Sciences
Volume406-407
DOIs
Publication statusPublished - 1 Sep 2017
Externally publishedYes

Keywords

  • BDH
  • Key-encapsulation mechanism
  • Related-key attacks

Cite this

Qin, Baodong ; Liu, Shengli ; Sun, Shifeng ; Deng, Robert H. ; Gu, Dawu. / Related-key secure key encapsulation from extended computational bilinear Diffie–Hellman. In: Information Sciences. 2017 ; Vol. 406-407. pp. 1-11.
@article{61de1b5e827b45e588dd2147bb454acd,
title = "Related-key secure key encapsulation from extended computational bilinear Diffie–Hellman",
abstract = "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.",
keywords = "BDH, Key-encapsulation mechanism, Related-key attacks",
author = "Baodong Qin and Shengli Liu and Shifeng Sun and Deng, {Robert H.} and Dawu Gu",
year = "2017",
month = "9",
day = "1",
doi = "10.1016/j.ins.2017.04.018",
language = "English",
volume = "406-407",
pages = "1--11",
journal = "Information Sciences",
issn = "0020-0255",
publisher = "Elsevier",

}

Related-key secure key encapsulation from extended computational bilinear Diffie–Hellman. / Qin, Baodong; Liu, Shengli; Sun, Shifeng; Deng, Robert H.; Gu, Dawu.

In: Information Sciences, Vol. 406-407, 01.09.2017, p. 1-11.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

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

AU - Qin, Baodong

AU - Liu, Shengli

AU - Sun, Shifeng

AU - Deng, Robert H.

AU - Gu, Dawu

PY - 2017/9/1

Y1 - 2017/9/1

N2 - 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.

AB - 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.

KW - BDH

KW - Key-encapsulation mechanism

KW - Related-key attacks

UR - http://www.scopus.com/inward/record.url?scp=85017589756&partnerID=8YFLogxK

U2 - 10.1016/j.ins.2017.04.018

DO - 10.1016/j.ins.2017.04.018

M3 - Article

VL - 406-407

SP - 1

EP - 11

JO - Information Sciences

JF - Information Sciences

SN - 0020-0255

ER -