Cryptology ePrint Archive: Report 2019/1045

Predicate Encryption from Bilinear Maps and One-Sided Probabilistic Rank

Josh Alman and Robin Hui

Abstract: In predicate encryption for a function $f$, an authority can create ciphertexts and secret keys which are associated with `attributes'. A user with decryption key $K_y$ corresponding to attribute $y$ can decrypt a ciphertext $CT_x$ corresponding to a message $m$ and attribute $x$ if and only if $f(x,y)=0$. Furthermore, the attribute $x$ remains hidden to the user if $f(x,y) \neq 0$.

We construct predicate encryption from assumptions on bilinear maps for a large class of new functions, including sparse set disjointness, Hamming distance at most $k$, inner product mod 2, and any function with an efficient Arthur-Merlin communication protocol. Our construction uses a new probabilistic representation of Boolean functions we call `one-sided probabilistic rank,' and combines it with known constructions of inner product encryption in a novel way.

Category / Keywords: public-key cryptography / Predicate Encryption, Bilinear Maps, Probabilistic Rank

Original Publication (with minor differences): IACR-TCC-2019

Date: received 13 Sep 2019, last revised 29 Oct 2019

Contact author: jalman at mit edu, ctunoku at mit edu

Available format(s): PDF | BibTeX Citation

Version: 20191029:170701 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]