Cryptology ePrint Archive: Report 2014/477
Relaxed Two-to-one Recoding Schemes
Omkant Pandey and Kim Ramchen and Brent Waters
Abstract: A two-to-one recoding (TOR) scheme is a new cryptographic primitive, proposed in the recent work of Gorbunov, Vaikuntanathan, and Wee (GVW), as a means to construct attribute-based encryption
(ABE) schemes for all boolean circuits. GVW show that TOR schemes can be constructed assuming the hardness of the learning-with-errors (LWE) problem.
We propose a slightly weaker variant of TOR schemes called correlation-relaxed two-to-one recoding (CR-TOR). Unlike the TOR schemes, our weaker variant does not require an encoding function to
be pseudorandom on correlated inputs. We instead replace it with an indistinguishability property that states a ciphertext is hard to decrypt without access to a certain encoding. The primary benefit of this relaxation is that it allows the construction of ABE for circuits using the TOR paradigm from a broader class of cryptographic assumptions.
We show how to construct a CR-TOR scheme from the noisy cryptographic multilinear maps of Garg, Gentry, and Halevi as well as those of Coron, Lepoint, and Tibouchi. Our framework leads to an instantiation of ABE for circuits that is conceptually different from the existing constructions.
Category / Keywords: public-key cryptography /
Date: received 17 Jun 2014, last revised 23 Jul 2014
Contact author: kramchen at cs utexas edu
Available format(s): PDF | BibTeX Citation
Version: 20140723:212748 (All versions of this report)
Short URL: ia.cr/2014/477
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]