In a paper about predicate encryption or attribute based encryption, the setup function is mentioned with the $setup(1^n)$ or $setup(1^l)$. I want to know what is meant here.

Is it multiples of ones or representing something else? Also, why is this used here?


1 Answer 1


If you got an expression that resembles $\{1\}^n$ (or $1^n$) at a place in a surrounding expression where you would expect an $n$-bit bit string to be, the $\{1\}^n$ expression means a string of $n$ bits each with the bit value $1$.

Conversely, $\{0\}^n$ means a string of $n$ zero valued bits, and $\{0,1\}^n$ just means any bit string of length $n$.

In the paper you mentioned, it looks like $n$ plays double duty: it both determines the set of attributes/predicates, and it is the security parameter. In this case the authors don't seem to use this notation to indicate that the setup is polynomial in the binary logarithm of the key space, but rather that it is polynomial in the maximum number of independent predicates.

The concepts Predicate and Attribute are related in such way that each entity $k$ (that might or might not have rights to decrypt a given cipher text) is associated with some set of predicates $F_k = \{f_i\}$ and the cipher text is associated with an Attribute $I$, and entity $k$ will be able to decrypt the cipher text if and only if $f_i(I)=1$ for some predicate $f_i \in F_k$ the entity has been assigned. The attribute was set as parameter when the plain text was encrypted to produce the cipher text.

The $Setup$ function defined in the referenced paper generates a master public key $PK$ and a master secret key $SK$. The master secret key is then passed to the $GenKey$ function that generates a secret key $SK_f$ for each predicate $f$

Although not written out explicitly, I suppose the argument of the Setup function could be interpreted as the union of the unhidden attributes of the cipher texts that the master secret key (generated by setup), will decrypt. With $n$ predicates, there are $2^n$ possible valid attribute value classes (there might be more than one value that instantiates each attribute), meaning that the set of attributes is isomorphic to $\{0,1\}^n$. One might in such case define the isomorphism $\phi$ such that the master attribute $I_M = \phi(1^n)$ equals the attribute such that $f_k(I_M) = 1$ for all predicates $f_k, 0 \le k \lt n$.

So how does this relate to the specific definitions in the referenced paper?

For starters, the set of attributes $\Sigma = \mathbb Z^n_N$ is a vector set with $N^n$ different values. However, the difference between $N^n$ and $2^n$ is due to there being $(N-1)^{n-k}$ different values in $\Sigma$ that all correspond to the same selection of $k$ predicates. Think of it like this:

Let $X$ be an $n\times n$ matrix over $\mathbb Z_N$, where each row corresponds to a predicate vector. Let $Y$ be an $n$ element column matrix corresponding to an attribute $I$. Let $XY = Z$. Now, since matrix multiplication of a row on the left with a column on the right corresponds to a dot vector multiplication, for each element $z_i$ in the $Z$ column matrix, $f_i(I) = 0 \iff z_i = 0$. On the other hand, if $f_i(I) \neq 0$, then $z_i$ might be any non-zero value in $\mathbb Z_N$, and there are $N-1$ such values.

  • $\begingroup$ I added some clarification on why this is used. Feel free to revert if you think it doesn't fit your answer, then I'll post it as a separate answer. $\endgroup$ Mar 28, 2013 at 22:17
  • $\begingroup$ @PaŭloEbermann: Thanks, the link wasn't available when I wrote my first reply. FWIW the definitions only mention that the same security parameter is also an implicit parameter of the set of attributes and set of predicates. On what page did you find the reference to polynomial time setup? $\endgroup$ Mar 29, 2013 at 0:38
  • $\begingroup$ Actually, I didn't read the paper at all (being a bit on limited time), I just remember that usage convention from other papers. All "normal" (not brute-force) algorithms used in Cryptography are somehow supposed to be polynomial-time (or probabilistic polynomial). $\endgroup$ Apr 2, 2013 at 15:12
  • $\begingroup$ Henrick, your answer sounds plausible on the surface, but when I read the paper, it's pretty clear that it is not correct. The real story is that $1^n$ is a security parameter (as the paper states in Definition 1), not some representation of hidden predicates, and the real explanation is the one given at crypto.stackexchange.com/q/8174/351 $\endgroup$
    – D.W.
    May 1, 2013 at 20:11
  • $\begingroup$ @D.W.: There is more to it. The parameter $n$ is not just an empty place holder that only exists in the security parameter $1^n$, but represents the number of dimensions in the formal attribute set $\mathbb Z_N^n$. Confer page 3. $\endgroup$ May 1, 2013 at 20:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.