Implementation of a leakage-resilient ElGamal key encapsulation mechanism

Research output: Contribution to journalArticlepeer-review

Standard

Implementation of a leakage-resilient ElGamal key encapsulation mechanism. / Galindo, David; Großschädl, Johann; Liu, Zhe; Vadnala, Praveen Kumar; Vivek, Srinivas.

In: Journal of Cryptographic Engineering, Vol. 6, No. 3, 09.2016, p. 229–238.

Research output: Contribution to journalArticlepeer-review

Harvard

APA

Vancouver

Author

Galindo, David ; Großschädl, Johann ; Liu, Zhe ; Vadnala, Praveen Kumar ; Vivek, Srinivas. / Implementation of a leakage-resilient ElGamal key encapsulation mechanism. In: Journal of Cryptographic Engineering. 2016 ; Vol. 6, No. 3. pp. 229–238.

Bibtex

@article{4fef0ce8947247c58355ca6771da2b47,
title = "Implementation of a leakage-resilient ElGamal key encapsulation mechanism",
abstract = "Leakage-resilient cryptography aims to extend the rigorous guarantees achieved through the provable security paradigm to physical implementations. The constructions designed on basis of this new approach inevitably suffer from an Achilles heel: a bounded leakage assumption is needed. Currently, a huge gap exists between the theory of such designs and their implementation to confirm the leakage resilience in practice. The present work tries to narrow this gap for the leakage-resilient bilinear ElGamal key encapsulation mechanism (BEG-KEM) proposed by Kiltz and Pietrzak in 2010. Our first contribution is a variant of the bounded leakage and the only-computation-leaks model that is closer to practice. We weaken the restriction on the image size of the leakage functions in these models and only insist that the inputs to the leakage functions have sufficient min-entropy left, in spite of the leakage, with no limitation on the quantity of this leakage. We provide a novel security reduction for BEG-KEM in this relaxed leakage model using the generic bilinear group axiom. Secondly, we show that a naive implementation of the exponentiation in BEG-KEM makes it impossible to meet the leakage bound. Instead of trying to find an exponentiation algorithm that meets the leakage axiom (which is a non-trivial problem in practice), we propose an advanced scheme, BEG-KEM+, that avoids exponentiation by a secret value, but rather uses an encoding into the base group due to Fouque and Tibouchi. Thirdly, we present a software implementation of BEG-KEM+ based on the Miracl library and provide detailed experimental results. We also assess its (theoretical) resistance against power analysis attacks from a practical perspective, taking into account the state-of-the-art in side-channel cryptanalysis.",
keywords = "Secure implementation, Side-channel cryptanalysis, Leakage-resilient cryptography, Security proof, Public-key encryption, Pairings",
author = "David Galindo and Johann Gro{\ss}sch{\"a}dl and Zhe Liu and Vadnala, {Praveen Kumar} and Srinivas Vivek",
year = "2016",
month = sep,
doi = "10.1007/s13389-016-0121-x",
language = "English",
volume = "6",
pages = "229–238",
journal = "Journal of Cryptographic Engineering",
issn = "2190-8508",
publisher = "Springer",
number = "3",

}

RIS

TY - JOUR

T1 - Implementation of a leakage-resilient ElGamal key encapsulation mechanism

AU - Galindo, David

AU - Großschädl, Johann

AU - Liu, Zhe

AU - Vadnala, Praveen Kumar

AU - Vivek, Srinivas

PY - 2016/9

Y1 - 2016/9

N2 - Leakage-resilient cryptography aims to extend the rigorous guarantees achieved through the provable security paradigm to physical implementations. The constructions designed on basis of this new approach inevitably suffer from an Achilles heel: a bounded leakage assumption is needed. Currently, a huge gap exists between the theory of such designs and their implementation to confirm the leakage resilience in practice. The present work tries to narrow this gap for the leakage-resilient bilinear ElGamal key encapsulation mechanism (BEG-KEM) proposed by Kiltz and Pietrzak in 2010. Our first contribution is a variant of the bounded leakage and the only-computation-leaks model that is closer to practice. We weaken the restriction on the image size of the leakage functions in these models and only insist that the inputs to the leakage functions have sufficient min-entropy left, in spite of the leakage, with no limitation on the quantity of this leakage. We provide a novel security reduction for BEG-KEM in this relaxed leakage model using the generic bilinear group axiom. Secondly, we show that a naive implementation of the exponentiation in BEG-KEM makes it impossible to meet the leakage bound. Instead of trying to find an exponentiation algorithm that meets the leakage axiom (which is a non-trivial problem in practice), we propose an advanced scheme, BEG-KEM+, that avoids exponentiation by a secret value, but rather uses an encoding into the base group due to Fouque and Tibouchi. Thirdly, we present a software implementation of BEG-KEM+ based on the Miracl library and provide detailed experimental results. We also assess its (theoretical) resistance against power analysis attacks from a practical perspective, taking into account the state-of-the-art in side-channel cryptanalysis.

AB - Leakage-resilient cryptography aims to extend the rigorous guarantees achieved through the provable security paradigm to physical implementations. The constructions designed on basis of this new approach inevitably suffer from an Achilles heel: a bounded leakage assumption is needed. Currently, a huge gap exists between the theory of such designs and their implementation to confirm the leakage resilience in practice. The present work tries to narrow this gap for the leakage-resilient bilinear ElGamal key encapsulation mechanism (BEG-KEM) proposed by Kiltz and Pietrzak in 2010. Our first contribution is a variant of the bounded leakage and the only-computation-leaks model that is closer to practice. We weaken the restriction on the image size of the leakage functions in these models and only insist that the inputs to the leakage functions have sufficient min-entropy left, in spite of the leakage, with no limitation on the quantity of this leakage. We provide a novel security reduction for BEG-KEM in this relaxed leakage model using the generic bilinear group axiom. Secondly, we show that a naive implementation of the exponentiation in BEG-KEM makes it impossible to meet the leakage bound. Instead of trying to find an exponentiation algorithm that meets the leakage axiom (which is a non-trivial problem in practice), we propose an advanced scheme, BEG-KEM+, that avoids exponentiation by a secret value, but rather uses an encoding into the base group due to Fouque and Tibouchi. Thirdly, we present a software implementation of BEG-KEM+ based on the Miracl library and provide detailed experimental results. We also assess its (theoretical) resistance against power analysis attacks from a practical perspective, taking into account the state-of-the-art in side-channel cryptanalysis.

KW - Secure implementation

KW - Side-channel cryptanalysis

KW - Leakage-resilient cryptography

KW - Security proof

KW - Public-key encryption

KW - Pairings

U2 - 10.1007/s13389-016-0121-x

DO - 10.1007/s13389-016-0121-x

M3 - Article

VL - 6

SP - 229

EP - 238

JO - Journal of Cryptographic Engineering

JF - Journal of Cryptographic Engineering

SN - 2190-8508

IS - 3

ER -