# ECKS-PS algorithm: searching in encrypted data; bilinear maps

I have found an encryption algorithm named ECKS-PS (published in the paper Efficient conjunctive keyword search on encrypted data storage system) that allows an user to search in encrypted data. All the steps are described here:

And I have written them a little bit more clear here:

I have tried to find a calculation example of finding two words multiple times:

but I never get a match.

Can anybody tell me what I am doing wrong and/or provide me with an example where you get a match (based on the ECKS-PS algorithm)? I know there may be other algorithms to search in encrypted data but I would like to know how to do it with this algorithm.

EDIT: with some advice from Barack and Gilles

$e(i,j) = 53 ^ {i*j} \mod 59$

$g=53$, $\alpha = 7$, $r= 16$, $\theta = 3$, $a_i = 6$, $Hash(W_1) = 53 ^ {23}$, $Hash(W_2) = 53 ^ {18}$,

$e(g^{a_i \theta}, g ^r ) = 53 ^ { 53 ^ {6*3} * 53 ^{16}} \mod 59 = 53 ^ { 53 ^{34}} = 9$

$e(g^{a_i }, (Hash(W_1) * Hash(W_2))^{\alpha} * g^{\theta * r} ) = 53^ {{({53 ^ {23} * {53 ^ {18} }}) ^ {7} * 53 ^{16*3} }} \mod 59 = 9$

$e(g^{\alpha}, Hash(W_1)^{a_i}) = 53 ^ {{53^7}*{{53^{23}}^6}} \mod 59 = 19$ $e(g^{\alpha}, Hash(W_2)^{a_i}) = 53 ^ {{53^7}*{{53^{18}}^6}} \mod 59 = 27$

$\frac 9{19*7} =>$ multiplicative inverse of $19*27 \mod 59 = 36$ => $29 \mod 59 \ne 9 \mod 59$

-
Looking through your first page of notes (which I don't find easy to read) I notice that you appear to have e(i,j)=53^(i*j) mod 59 where I would normally read e to be some suitable paring computation on an elliptic curve. I presume you believe you're allowed to make this substitution to make thing simpler but it's not clear to me that it's actually going to work. Is this something you can justify? –  Barack Obama Apr 9 '13 at 22:19
Hi @BarackObama thank you for your answer. I based my e function on stackoverflow.com/questions/5293873/… this post. Perhaps what I did was wrong, but I have no idea how to solve this algorithm otherwise –  user71797 Apr 10 '13 at 7:24
Please type your notes into your questions, your handwritten calculations are hard to follow. Use MathJax (quickstart). –  Gilles Apr 10 '13 at 9:52

Note I have changed the value of $H(W_2)$ to make intermediate caclulation results unique. $e(g^i,g^j) =g^{i*j}\mod 59,g=53,\alpha=7,r=16,\theta=3,a_i=6,H(W_1)=53^{23},H(W_2)=53^{19}$

$e(g^{a_i \theta},g^r)=53^{6*3 * 16} \mod 59=53^{27}=41$

$A=(H(W_1)*H(W_2))^\alpha . g^{\theta r}=53^{(23+19)*7+3*16 \mod 29}=53^{23}$

$e(g^{a_i},A) = 53 ^ {6*23} \mod 59 = 28$

$e(g^{\alpha}, H(W_1)^{a_i}) = 53^{7 * 23*6} \mod 59 = 53^9 \mod 59 = 35$

$e(g^{\alpha}, H(W_2)^{a_i}) = 53^{7 * 19*6} \mod 59 = 53^{15} \mod 59 = 17$

$\frac {28}{35*17} \mod 59= 41$ QED

-
@Gilles, Barack Obama thank you for your response. I have tried your advice (see edit in original question), but didn't succeed. However, I don't understand why everything has to be mod 59, I thought that two groups needed to be mod 29, and one group mod 59? –  user71797 Apr 11 '13 at 9:07
When you're dealing with powers of 53 then you reduce mod 29. So the above calculation now works because both sides are equal to 41 in this instance. –  Barack Obama Apr 11 '13 at 13:27
Thank you very much! –  user71797 Apr 11 '13 at 13:40