1-out-of-2 Oblivious Transfer
1-out-of-2 Oblivious Transfer
by Jose Manuel Rodriguez Caballero
Abstract. We develop the 1-out-of-2 oblivious transfer protocol from the field of secure computation. The goal is to send one of two messages from one agent to another without revealing any other information.
Statement of the problem
Statement of the problem
Problem (1-out-of-2 Oblivious Transfer). Alice has two messages m[[1]] and m[[2]]. Bob has chosen a number b ∈ {1, 2}. Bob wants to receive m[[b]] from Alice without letting her know the value of b. Alice wants to send m[[b]] to Bob, without letting him know the value of the other message.
Example
Example
Alice has two messages m[[1]] and m[[2]].
In[]:=
m={1729,137}
Out[]=
{1729,137}
Null
Bob has chosen a number b ∈ {1, 2}.
In[]:=
b=1
Out[]=
1
Solution
Solution
We will implement the solution developed in [1].
RSA module
RSA module
Generating RSA module n, where n is the product of two prime numbers p and q.
Random prime p.
In[]:=
p=Prime[RandomInteger[{Max[m],10000*Max[m]}]]
Out[]=
220771597
Random prime q.
In[]:=
q=Prime[RandomInteger[{Max[m],10000*Max[m]}]]
Out[]=
110859451
RSA module.
In[]:=
n=p*q
Out[]=
24474618039813247
RSA keys
RSA keys
Alice generates an RSA pair key.
Private exponent: d; Public exponent: e
Private exponent: d; Public exponent: e
Carmichael's totient function λ(n) evaluated at the RSA module.
In[]:=
λ=LCM[p-1,q-1]
Out[]=
4079102951363700
Public exponent.
In[]:=
e = NestWhile[RandomInteger[{2,λ-1}]&,RandomInteger[{2,λ-1}],GCD[#,λ]≠1&]
Out[]=
1773775395199591
Private exponent.
In[]:=
d = ModularInverse[e,λ]
Out[]=
935053266453511
Alice to Bob
Alice to Bob
Alice generates two random numbers.
In[]:=
x={RandomInteger[{1,n}],RandomInteger[{1,n}]}
Out[]=
{16874658342456873,5656699756448064}
Alice's information.
In[]:=
Alice =<|"RSA module" n,"lambda"λ,"public exp" e, "private exp" d, "messages"m,"x-numbers"x|>
Out[]=
RSA module24474618039813247,lambda4079102951363700,public exp1773775395199591,private exp935053266453511,messages{1729,137},x-numbers{16874658342456873,5656699756448064}
In[]:=
Clear[n,λ,e,d,m,x,p,q]
Alice sends (n, e, x) to Bob.
Bob's information.
In[]:=
Bob=<| "RSA module"Alice[["RSA module"]], "public exp"Alice[["public exp"]], "x-numbers" Alice[["x-numbers"]], "choice" b |>
Out[]=
RSA module24474618039813247,public exp1773775395199591,x-numbers{16874658342456873,5656699756448064},choice1
In[]:=
Clear[b]
Bob to Alice
Bob to Alice
Bob generates a random number k.
In[]:=
k=RandomInteger[{2,Bob[["RSA module"]]}]
Out[]=
133952696227886
In[]:=
Bob=Bob ~Join~ <|"v-number" Bob["x-numbers"][[ Bob["choice"] ]] +PowerMod[k,Bob["public exp"],Bob[["RSA module"]]] ,"k-number"k |>
Out[]=
RSA module24474618039813247,public exp1773775395199591,x-numbers{16874658342456873,5656699756448064},choice1,v-number29936250246858515,k-number133952696227886
In[]:=
Clear[k]
Bob sends v to Alice
In[]:=
Alice = Alice~Join~<|"v-number"Bob[["v-number"]]|>
Out[]=
RSA module24474618039813247,lambda4079102951363700,public exp1773775395199591,private exp935053266453511,messages{1729,137},x-numbers{16874658342456873,5656699756448064},v-number29936250246858515
Alice to Bob
Alice to Bob
Alice estimates the value of k. There are two possibilities.
In[]:=
Alice=Alice~Join~<|"k-estimations"{ PowerMod[Alice[["v-number"]] -Alice[["x-numbers"]][[1]] ,Alice[["private exp"]],Alice[["RSA module"]]], PowerMod[Alice[["v-number"]] -Alice[["x-numbers"]][[2]] ,Alice[["private exp"]],Alice[["RSA module"]]] }|>
Out[]=
RSA module24474618039813247,lambda4079102951363700,public exp1773775395199591,private exp935053266453511,messages{1729,137},x-numbers{16874658342456873,5656699756448064},v-number29936250246858515,k-estimations{133952696227886,18004012245639507}
Alice encrypt the messages with the estimations of k and send this information to Bob
In[]:=
Bob=Bob~Join~<| "encrypted messages"{Alice[["messages"]][[1]] +Alice[["k-estimations"]][[1]],Alice[["messages"]][[2]] +Alice[["k-estimations"]][[2]]} |>
Out[]=
RSA module24474618039813247,public exp1773775395199591,x-numbers{16874658342456873,5656699756448064},choice1,v-number29936250246858515,k-number133952696227886,encrypted messages{133952696229615,18004012245639644}
Bob knows that the encrypted message Bob[["choice"]] is the one that he can decrypt. Therefore, the message m[[b]] is as follows.
In[]:=
Bob[["encrypted messages"]][[ Bob[["choice"]] ]] - Bob[[ "k-number" ]]
Out[]=
1729
Main Reference
Main Reference
[1] S. Even, O. Goldreich, and A. Lempel, "A Randomized Protocol for Signing Contracts", Communications of the ACM, Volume 28, Issue 6, pg. 637–647, 1985.