Cryptology ePrint Archive: Report 2007/074

A Cramer-Shoup Encryption Scheme from the Linear Assumption and from Progressively Weaker Linear Variants

Hovav Shacham

Abstract: We describe a CCA-secure public-key encryption scheme, in the Cramer-Shoup paradigm, based on the Linear assumption of Boneh, Boyen, and Shacham. Through a comparison to the Kiltz tag-encryption scheme from TCC 2006, our scheme gives evidence that the Cramer-Shoup paradigm yields CCA encryption with shorter ciphertexts than the Canetti-Halevi-Katz paradigm.

We present a generalization of the Linear assumption into a family of progressively weaker assumptions and show how to instantiate our Linear Cramer-Shoup encryption using the progressively weaker members of this family.

Category / Keywords: public-key cryptography / Cramer-Shoup, Canetti-Halevi-Katz, CCA encryption, bilinear groups, generic groups

Date: received 25 Feb 2007, last revised 22 Apr 2009

Contact author: hovav shacham at weizmann ac il

Available format(s): PDF | BibTeX Citation

Version: 20090423:010226 (All versions of this report)

Short URL: ia.cr/2007/074