Paper 2014/477

Relaxed Two-to-one Recoding Schemes

Omkant Pandey, Kim Ramchen, and Brent Waters


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.

Available format(s)
Public-key cryptography
Publication info
Preprint. MINOR revision.
Contact author(s)
kramchen @ cs utexas edu
2014-07-23: revised
2014-06-21: received
See all versions
Short URL
Creative Commons Attribution


      author = {Omkant Pandey and Kim Ramchen and Brent Waters},
      title = {Relaxed Two-to-one Recoding Schemes},
      howpublished = {Cryptology ePrint Archive, Paper 2014/477},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.