Hoeteck Wee

Efficient Chosen-Ciphertext Security via Extractable Hash Proofs

Hoeteck Wee

We introduce the notion of an extractable hash proof system. Essentially, 
this is a special kind of non-interactive zero-knowledge proof of knowledge 
system where the secret keys may be generated in one of two modes to 
allow for either simulation or extraction. 
-- We show how to derive efficient CCA-secure encryption schemes via 
extractable hash proofs in a simple and modular fashion. Our construction 
clarifies and generalizes the recent factoring-based cryptosystem of 
Hofheinz and Kiltz (Eurocrypt 09), and is reminiscent of an approach 
proposed by Rackoff and Simon (Crypto 91). We show how to instantiate 
extractable hash proof system for hard search problems, notably factoring 
and computational Diffie-Hellman. Using our framework, we obtain the first 
CCA-secure encryption scheme based on CDH where the public key is a constant 
number of group elements and a more modular and conceptually simpler variant 
of the Hofheinz-Kiltz cryptosystem (though less efficient). 
-- We introduce adaptive weakly trapdoor functions, a relaxation of the 
adaptive trapdoor functions considered by Kiltz, Mohassel and O'Neil 
(Eurocrypt '10), but nonetheless imply CCA-secure encryption schemes. We 
show how to construct such functions using extractable hash proofs, which 
in turn yields realizations from hardness of factoring and CDH. This is the 
first general assumption that implies CCA-secure encryption while 
simultaneously admitting instantations from hardness of factoring, CDH and 
lattice-based assumptions.