Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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:

definitions

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

handwritten notes

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

calculation page 1

calculation page 2

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$

share|improve this question
1  
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
1  
Please type your notes into your questions, your handwritten calculations are hard to follow. Use MathJax (quickstart). –  Gilles Apr 10 '13 at 9:52

1 Answer 1

up vote 2 down vote accepted

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

share|improve this answer
    
@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

Your Answer

 
discard

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

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