General Construction of Chameleon All-But-One Trapdoor Functions

Shengli Liu¹, Junzuo Lai², and Robert H. Deng²

¹Department of Computer Science and Engineering

Shanghai Jiao Tong University

Shanghai 200240, China

slliu@sjtu.edu.cn

²School of Information Systems,

Singapore Management University

Singapore 178902

{junzuolai,robertdeng}@smu.edu.sg

Abstract

Lossy trapdoor functions enable black-box construction of public key encryption (PKE) schemes

secure against chosen-ciphertext attack [18]. Recently, a more efficient black-box construction of

public key encryption was given in [13] with the help of chameleon all-but-one trapdoor functions

(ABO-TDFs). In this paper, we propose a black-box construction for transforming any ABO-TDFs

into chameleon ABO-TDFs with the help of chameleon hash functions. Instantiating the proposed

general black-box construction of chameleon ABO-TDFs, we obtain the first chameleon ABO-TDFs

based on the Decisional Diffie-Hellman (DDH) assumption.

Keywords: Lossy trapdoor functions, chameleon ABO-TDFs, Decisional Diffie-Hellman (DDH) assumption