Identification Schemes from Key Encapsulation Mechanisms

Hiroaki ANADA  Seiko ARITA  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E95-A   No.7   pp.1136-1155
Publication Date: 2012/07/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E95.A.1136
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Cryptography and Information Security
identification scheme,  key encapsulation mechanism,  one-way-CCA2 security,  concurrent man-in-the-middle attack,  the computational Diffie-Hellman assumption,  

Full Text: PDF(410.8KB)>>
Buy this Article

We propose a generic conversion from a key encapsulation mechanism (KEM) to an identification (ID) scheme. The conversion derives the security for ID schemes against concurrent man-in-the-middle (cMiM) attacks from the security for KEMs against adaptive chosen ciphertext attacks on one-wayness (one-way-CCA2). Then, regarding the derivation as a design principle of ID schemes, we develop a series of concrete one-way-CCA2 secure KEMs. We start with El Gamal KEM and prove it secure against non-adaptive chosen ciphertext attacks on one-wayness (one-way-CCA1) in the standard model. Then, we apply a tag framework with the algebraic trick of Boneh and Boyen to make it one-way-CCA2 secure based on the Gap-CDH assumption. Next, we apply the CHK transformation or a target collision resistant hash function to exit the tag framework. And finally, as it is better to rely on the CDH assumption rather than the Gap-CDH assumption, we apply the Twin DH technique of Cash, Kiltz and Shoup. The application is not “black box” and we do it by making the Twin DH technique compatible with the algebraic trick. The ID schemes obtained from our KEMs show the highest performance in both computational amount and message length compared with previously known ID schemes secure against concurrent man-in-the-middle attacks.