Relaxed two-to-one recoding schemes

Omkant Pandey, Kim Ramchen, Brent Waters

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearch

2 Citations (Scopus)


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 TORschemes called correlationrelaxed 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.

Original languageEnglish
Title of host publicationSecurity and Cryptography for Networks
Subtitle of host publication9th International Conference, SCN 2014 Amalfi, Italy, September 3-5, 2014 Proceedings
EditorsMichel Abdalla, Roberto de Prisco
Place of PublicationCham Switzerland
Number of pages20
ISBN (Electronic)9783319108797
ISBN (Print)9783319108780
Publication statusPublished - 2014
Externally publishedYes
EventConference on Security and Cryptography for Networks 2014 - Amalfi, Italy
Duration: 3 Sept 20145 Sept 2014
Conference number: 9th

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


ConferenceConference on Security and Cryptography for Networks 2014
Abbreviated titleSCN 2014
Internet address

Cite this