Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am not sure if I missed some subtlety in the definition of Attribute Hiding found in this paper on Predicate Encryption, but isn't it possible to construct a scheme for Predicate Encryption supporting disjunctions that is both a lot less convoluted, and still supports Attribute Hiding?

(I realize that "convoluted" is a matter of opinion, but I think this falls within the scope of admissible subjective questions as laid out in the FAQ.)

Let $\mathbb G$ be a multiplicative group of prime order $q$ and with generator $g$ such that Computational Diffie-Hellman is hard in $\mathbb G$. Let $F$ be a set of $n$ predicates and let $\Sigma$ be the corresponding set of attributes (which is the power set of $F$).

$KeyGen:$ A trusted party performs the following operation: For each predicate $f_i \in F$, select two uniform values $x_{f_i},s_{f_i} \in \mathbb Z_q$. Let $w_{f_i} = g^{s_{f_i}}$. Let the Public Key $PK_i$ corresponding to predicate $f_i$ be $(x_{f_i},w_{f_i})$ and the private key be $(s_{f_i})$.

$KeyDist:$ Each entity $k$ is assigned a set of predicates $F_k \subset F$. For each $f \in F_k$, the trusted party distributes the corresponding private key $(s_f)$ to $k$.

$Enc:$ Generate a secret value $w \in \mathbb G$ (which might be used for deriving a symmetric key for authenticated key encryption) for the attribute $I \in \Sigma$ as follows:

  1. Select $s \leftarrow_{uniform} \mathbb Z_q$.
  2. For $i = 1$ to $n$:
    1. If $f_i \in I$ then $u_i = x_{f_i}$ and $v_i = w_{f_i}^s$, else $u_i \leftarrow_{uniform} \mathbb Z_q$ and $v_i \leftarrow_{uniform} \mathbb G$.
  3. Let $(l_i(x))_{i=1}^n$ be the Lagrange basis polynomials corresponding to the ordered set $(u_i)_{i=1}^n$.
  4. Let $p(x) = \Pi_{i=1}^nv_i^{l_i(x)}$.
  5. Calculate $w = p(0)$, $t = g^s$, and for each $1 \le i \le n-1, r_i = p(i)$.
  6. Output $(r_i)_{i=1}^{n-1}, t$, the key encrypted key and the payload cipher text.


  1. For each $f \in F_k$ do:
    1. Let $(l_i^\prime(x))_{i=1}^n$ be the Lagrange basis polynomials corresponding to $(1,..,n-1,x_f)$.
    2. Let $r_n = t^{s_f}$.
    3. Let $p^\prime(x) = \Pi_{i=1}^nr_i^{l_i^\prime(x)}$.
    4. Calculate $w_f = p^\prime(0)$. If $w_f$ decrypts the key encrypted key, let $w = w_f$.
  2. Use $w$ for decrypting the key encrypted key and payload cipher text.

Now, the difference between the above scheme and the one in the referenced paper, is that in the latter the decrypting entities get secret keys that are blinded with respect to which predicates that are included in the secret key. However, from what I can tell the definition of Attribute Hiding (Definition 2 on page 5) does not require such blinding. The adversary chooses two attributes $I_0, I_1$ and adaptively requests secret keys for any predicates $f_i$ subject to the restriction that $f_i(I_0) = f_i(I_1)$ for all $i$. Let $f_j$ be such that $f_j(I_0) \ne f_j(I_1)$. Clearly, an adversary $A$, attacking the scheme above, can't tell from $(r_i)_{i=1}^{n-1}, t$ if the encryptor used $v_j = w_{f_j}^s$ or $v_j \leftarrow_{uniform} \mathbb G$ without at least solving DDH in $\mathbb G$. Am I missing something?

share|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.