Cryptography Reference
In-Depth Information
The Twin Bilinear Die-Hellman Inversion
Problem and Applications
Yu Chen 1 and Liqun Chen 2
1 School of Electronics Engineering and Computer Science, Peking University, China
Key Laboratory of High Confidence Software Technologies, Ministry of Education
chenyu@infosec.pku.edu.cn
2 Hewlett-Packard Laboratories, Bristol, United Kingdom
liqun.chen@hp.com
Abstract. We propose a new computational problem and call it the
twin bilinear Di e-Hellman inversion (BDHI) problem . Inspired by the
technique proposed by Cash, Kiltz and Shoup, we have developed a new
trapdoor test which enables us to prove that the twin BDHI problem
is at least as hard as the ordinary BDHI problem even in the presence
of a decision oracle that recognizes a solution to the problem. The rela-
tion between the two problems implies that many of the cryptographic
constructions based on ordinary BDHI problem can be improved with
a tighter security reduction. As one such application, we present a new
variant of Sakai-Kasahara Identity-Based Encryption (SK-IBE) with a
simple and ecient security proof in the random oracle model, under
the computational BDHI problem. We also present a new Identity-Based
Key Encapsulation Mechanism (ID-KEM) based on SK-IBE, which has
a better security analysis than previous results.
Keywords: bilinear Die-Hellman inversion problem, twin bilinear
Die-Hellman inversion problem, trapdoor test, identity-based encryp-
tion, identity-based key encapsulation.
1
Introduction
The bilinear Di e-Hellman inversion (BDHI) problem has found its applica-
tions in many cryptographic constructions, such as identity-based encryption
(IBE) [6, 11, 22], identity-based key encapsulation mechanism [12], identity-
based signatures (IBS) [2], identity-based signcryption [2], identity-based key
agreement (IBKA) [14, 21], and verifiable random function [18] etc.
In this paper, we introduce a new problem based on the original BDHI prob-
lem, named the twin bilinear Die-Hellman inversion problem , which has the
following properties:
- The twin BDHI problem can easily be employed in many cryptographic
constructions where one would usually use the ordinary BDHI problem; as
a result, it will improve the security analysis of these constructions.
- The twin BDHI problem is hard, even given access to the corresponding
decision oracle, assuming the ordinary BDHI problem is hard.
 
Search WWH ::




Custom Search