2
$\begingroup$

How can I calculate the real size of key in a CP-ABE scheme. For example, I have this GSWV scheme:

Fuchun Guo, Willy Susilo, Duncan Wong, Vijay Varadharajan: CP-ABE with constant-size keys for lightweight devices.

In both papers I have that $\mathbb{G}_1=160$ bits and $\mathbb{G}_2=512$ bits, and length of decryption key is: $2\mathbb{G}$.

In this paper, the size of key is: $|S_K|=|\mathbb{G}_1|+|\mathbb{G}_2|=2\cdot 160+2\cdot 512=1344$ bits for $80$-bit security. ($\mathbb{G}_1$ and $\mathbb{G}_2$ are elliptic curve bilinear groups).

In this paper (original paper), the same key is: $|S_{K_\mathbb{A}}|=|\mathbb{G}_1|+|\mathbb{G}_2|=672$ bits.

I'm confused.

I don't understand, how can I calculate the size of key correctly if I only have $\mathbb{G}_1$ and $\mathbb{G}_2$ ?

How can I calculate the size of key in this case: $n\mathbb{G}$ ?

I'm confused if I must calculate $n\mathbb{G}=|\mathbb{G}_1|+|\mathbb{G}_2|$ or $n\mathbb{G}=n\cdot|\mathbb{G}_1|+n\cdot|\mathbb{G}_2|$.

$\endgroup$
2
  • $\begingroup$ There is no such thing as $\mathbb{G}_x$ with $x>2$. $n \mathbb{G}$ obviously means $n \cdot |\mathbb{G}|$ $\endgroup$
    – Artjom B.
    Commented Feb 18, 2016 at 21:41
  • $\begingroup$ @ArtjomB. I have modified my question. I suppose that have only $\mathbb{G}_1$ and $\mathbb{G}_2$. For example, if have that the size of decryption key is $3\mathbb{G}$, then $|S_k|$=$3\mathbb{G}_1$+$3\mathbb{G}_2$ ? or $|S_k|$=$\mathbb{G}_1$+$\mathbb{G}_2$. Sorry but i'm confused. $\endgroup$
    – Ellipticat
    Commented Feb 19, 2016 at 8:51

1 Answer 1

2
$\begingroup$

Different researchers use different notations for elliptic curve bilinear pairing groups. For symmetric pairing this can look like:

  • $e: \; \mathbb{G} \times \mathbb{G} \rightarrow \mathbb{G}_T$
  • $e: \; \mathbb{G}_1 \times \mathbb{G}_1 \rightarrow \mathbb{G}_T$
  • $e: \; \mathbb{G}_1 \times \mathbb{G}_1 \rightarrow \mathbb{G}_2$
  • $e: \; \mathbb{G}_1 \times \mathbb{G}_2 \rightarrow \mathbb{G}_T$ (with $\mathbb{G}_1 = \mathbb{G}_2$ for symmetric and $\mathbb{G}_1 \neq \mathbb{G}_2$ for asymmetric)

All of the symmetric variants mean the exact same thing and only differ notationally.

Now, if a scheme is constructed from asymmetric pairing, there is nothing holding you back from instantiating the scheme with a symmetric pairing, other than possible security concerns and enabling attacks on it. So, theoretically we can calculate the size of the user secret key as $|SK| = 2|\mathbb{G}| = |\mathbb{G}|+|\mathbb{G}|$ instead of $|SK| = |\mathbb{G}_1|+|\mathbb{G}_2|$. Now you only need to use one group instead of two, which is a more compact notation, but not entirely true.

The authors of both papers that you referenced probably chose this notation in order to include everything in a single table, because the page width is limited and they can't severely change the font size, because they need to follow the template of the conference/journal.


Now, your question is why the authors of the ODG scheme calculated the size of the secret keys of the GSWV scheme differently than the authors of the GSWV scheme themselves.

Let's recap elliptic curve groups. We have an elliptic curve, such as $y^2 = x^3+a\cdot x+b$ where $a$ and $b$ are curve parameters, that is defined in two-dimensional space over some (prime) field. Each point on the curve, where the above equation holds, is represented by two elements, $x$ and $y$, from the underlying field.

If the field is a 160-bit prime-order field, then elements of $\mathbb{G}_1$ can be serialized to 320-bit as a concatenation of $x$ and $y$. But we don't necessarily have to store $y$, because if we know the curve, then we can simply calculate $y$ from $x$:

$$y = \sqrt{(x^2+a)\cdot x + b}$$

Example in code from jPBC:

protected void setPointFromX() {
    infFlag = 0;
    y.set(x.duplicate().square().add(field.a).mul(x).add(field.b).sqrt());
}

So, you can reduce the size of the serialized curve element by half, but then you would need to do additional calculations in order to reconstruct the curve element from $x$ in order to use it. It's a compromise. The authors of GPSW chose to optimize for size and the authors of ODG chose to optimize for speed (or simply to let their scheme look good).

$\endgroup$
2
  • $\begingroup$ Sorry, but in the square root, is x elevated at cube ? $\endgroup$
    – Ellipticat
    Commented Mar 7, 2016 at 15:44
  • $\begingroup$ Yes, because $(x^2 + a)\cdot x + b = x^3 + a\cdot x + b$. It's usually implemented as shown on the left side of the equation, because there is one multiplication less than on the right side. $\endgroup$
    – Artjom B.
    Commented Mar 7, 2016 at 18:41

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.