Paper 2008/452

Injective Trapdoor Functions are Necessary and Sufficient for CCA2 Secure Public-Key Cryptosystems

Rui Xue and Dengguo Feng

Abstract

We make the following contributions in this paper: 1. We show that the existence of semantically secure public-key cryptosystems implies the existence of injective one-way trapdoor functions. This resolves one of long-standing open problems in cryptography. Moreover, the black-box way of construction to injective trapdoor functions from any semantically secure cryptosystem disproves a conclusion at FOCS'01. 2. We further show that the injective trapdoor functions constructed are secure correlated products under uniform, repetitional distribution. This shows that the existence of semantically secure public-key cryptosystems implies the existence of CCA2 secure cryptosystems by a result of Rosen and Segev. This settles another intensive investigated long-standing and fundamental open problem in cryptography. It also indicates that the secure correlated products under uniform, repetitional distribution exist if and only if injective trapdoor functions exist. That in turn answers the motivating question by Rosen and Segev. Combining them with prior results, we achieve a somewhat surprising result: injective trapdoor functions exist if and only if CCA2 secure cryptosystems exist. Considering CCA2 security is the strongest among securities for public-key cryptosystems, this makes security hierarchy for public-key cryptosystems, in the sense of existence, collapses into one level. The conclusions of this work have many consequences: for example, the trapdoor functions with poly-bounded pre-image size exist if and only if injective trapdoor functions exist; There exists a collection of efficient trapdoor functions from Ajtai-Dwork lattice based cryptosystems, and several others.