4
$\begingroup$

I'm currently working on Ciphertext Policy Attribute-Based Encryption (CP-ABE). So far I'm only using it with a basic understanding how it actually works. Now I want to understand it a bit better, but I've never learned anything about bilinear groups or pairing-based cryptography.

To start with I would like to calculate a very simple example on my own. Therefore I'd like to use small numbers and very simple operations (although this definitely won't be secure).

I will just write what I tried to do for the first step (Setup) — would be great if someone could tell me whether it is completely wrong or if it goes in the right direction:

I chose a group generator of $g=7$ and an order of $p=13$. Therefore I got the group $G_0=\{1\ldots12\}$. (Correct so far?)

Then I defined $e(X,Y)=g^{XY}\bmod{}p$

Using this, I can now calculate the Public Key and the Master Key with two random integers $\alpha=3; \beta=4$:

$MK=\{\beta,g^\alpha\}=\{4,7^3\}=\{4,343\bmod13\}=\{4,5\}$

(Still correct?)

$PK=\{G_0,g,h=g^\beta,f=g^{1/\beta},e(g,g)^\alpha\}=\{G_0,7,7^4\bmod13,7^{1/4}\bmod13,7^{7*7*3}\bmod13\}=\{G_0,7,9,??,5\}$

(How can I calculate $7^{1/4}$?)

I hope to be able to do the rest on my own as soon as I understand this part.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Pairings are defined over special elliptic curve points, not integers. Im affraid there is no simple example if you want to see the actual numbers. Not sure if this will help at all, but here is some high level code for a cp-abe schemehttps://github.com/JHUISI/charm/blob/dev/charm/schemes/abenc/abenc_bsw07.py $\endgroup$
    – imichaelmiers
    Apr 29, 2013 at 6:40

1 Answer 1

Reset to default
4
$\begingroup$

I think you have a lack of knowledge on pairings and finite fields. Your definition of the pairing $e(X,Y)=g^{XY} \bmod p$ is not correct.

A pairing is defined as a map $e : \mathbb{G}_1 \times \mathbb{G}_2 \to \mathbb{G}_T$ with the property \begin{align}\text{for all }g_1 \in \mathbb{G}_1 \text{ and } g_2 \in \mathbb{G}_2: e(g_1^a,g_2^b) = e(g_1,g_2)^{ab}\text{.}\end{align} For cryptographic usage we also need the properties that the pairing is not degenerated and efficient computable. Your definition of the pairing does not hold all these properties.

Today, pairings are basically implemented with elliptic curves over finite fields ($\mathbb{G}_1$ and $\mathbb{G}_2$) and with an extended finite field ($\mathbb{G}_T$). All the three groups have prime order $p$ so that you can calculate the inverse in the exponent very easily: $g^{1/\beta} = g^{\beta^{-1} \pmod p}$.

I think it is not that easy to generate a toy example for pairing based cryptography, because you need special elliptic curves with known order, embedding degree and other parameters and an efficiently computable pairing function.

If you like to understand pairings better I can recommend the dissertation of Ben Lynn [1]. He also wrote the PBC Library [2] that implements pairings in C and is very easy to use.

[1] https://crypto.stanford.edu/pbc/thesis.html
[2] https://crypto.stanford.edu/pbc/

Improve this answer
$\endgroup$
7
  • $\begingroup$ I looked at the thesis from Ben Lynn now, but I still did not really understand what it means - think I have not enough basic knowledge in this area. Can you please point out which property it is that my pairing does not hold. $\endgroup$
    – Baertierchen
    Mar 3, 2013 at 22:54
  • 1
    $\begingroup$ Your definition of the pairing $e(X,Y)=g^{XY} \mod p$ with $p=13$ and $g=7$ does not hold the biliniarity property, because $e(7^2,7^3) \neq e(7,7^2)^3 \neq e(7,7^3)^2 \neq e(7,7^6) \neq e(7,7)^6$. All these expressions should be equal, but if you evaluate the first two expressions you get $e(7^2,7^3) = 7^{10\cdot5} = 10$ and $e(7,7^2)^3 = (7^{7\cdot10})^3 = 4^3 = 12$. To my knowledge, there are no pairings for finite fields and you need to use elliptic curves. $\endgroup$
    – Ekris
    Mar 4, 2013 at 8:59
  • $\begingroup$ It has been a while since I asked my question. I read up on ECC and think I got a basic understanding now (hopefully). In another post (crypto.stackexchange.com/questions/2367/…), a simple pairing - which is cryptographically insecure of course - has been suggested over $\mathbb{Z}_p$ additive: $e(a,b)=ab$, if I got it right. The definition property would then be $e(ag,bg)=e(g,g)ab$, right? Could this be applied to CP-ABE? $\endgroup$
    – Baertierchen
    Mar 18, 2013 at 16:51
  • 1
    $\begingroup$ Spontaneously, I would say that your pairing definition is correct, but cannot be applied to CP-ABE. The group $\mathbb{Z}_p$ has order $p-1$, but CP-ABE requires a group of prime order and I think a subgroup of prime order would not be sufficient. Of course, elliptic curves and Miller's algorithm are very difficult to calculate in a toy example, but I think you need to... $\endgroup$
    – Ekris
    Mar 18, 2013 at 21:04
  • $\begingroup$ OK, what if I use any $\mathbb{Z}_{p+1}$ instead? $\endgroup$
    – Baertierchen
    Mar 19, 2013 at 22:00

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