Oblivious transfer (OT) protocol that transfers points on an elliptic curve, instead of binary strings.

Elliptic Curve Oblivious Transfer.md

We propose an elliptic curve-version of oblivious transfer (ECOT) protocol which transfers points on an elliptic curve, instead of binary strings.

Oblivious transfer (OT)

Oblivious transfer (OT) is an important cryptographic primitive used in many cryptographic protocols as a building block. In the oblivious transfer protocols, the sender has messages m₀ and m₁ and the receiver wishes to retrieve one of the two messages without showing the sender which message was actually retrieved. OTs usually transfer binary strings, but in our protocol points on an elliptic curve are transfered.

For more details, please refer to Wikipedia article.

Protocol

Let G be the basepoint of the elliptic curve. Let M₀ and M₁ be messages the sender wishes to send. Let b be the index that receiver wishes to fetch (in the final step of or protocol, receiver will get M_b without disclosing the index b to the sender).

• Sender (S)
  • Pick random numbers x₀ and x₁. Send X₀ := x₀G and X₁ := x₁G to the receiver.
• Receirver (R)
  • Pick a random number k and send K := kX_b to the sender.
• Sender (S)
  • Send the following two points to the receiver.
    • M₀' := M₀ + x₀^-1 K
    • M₁' := M₁ + x₁^-1 K
• Receiver (R)
  • Compute M_b' - kG to get M_b.

Discussion

Correctness

M_b' - kG = M_b + x_b^-1・kx_bG = M_b

Indistinguishability for the sender

The only variable the sender receives from the receiver is K, which is uniformly random because it is multiplied by a random k.

Infeasibility for computing M_1-b for the receiver

M_1-b' = M_1-b + kx_bx_1-b^-1G

Since x_bx_1-b^-1G is not known to the reciever, it is impossible to extract M_1-b (within a probabilistic polynomial time).

Is it possible to convert to a modular arithmetic-version?

We only use a group addition, it is an easy exercise to convert the protocol to work with (Z/pZ)^☓. We note that the element inversion (x → x^-1) should be computed in Z/φ(p-1)Z, which requires the factorization of p-1.

Is it possible to extend to 1-out-of-n OT?

Yes. To do so, the sender should send {x_iG}_i at the first step and {M_i + x_i^-1 K}_i at the third step. The communication cost is thus linear in the number of messages, which is comparably inefficient to the context of private information retrieval (PIR).

Connection between binary OTs and ECOTs

Any point on an elliptic curve can be serialized to a binary string (the most straightforward way is to concatenate the binary expression of x- and y-coordinates), which can be transfered by binary OTs.

On the other hand, a binary string can be converted into a point on an elliptic curve by identifying the binary string to the x-coordinate of the point on an elliptic curve. In this case, the final binary message can be extracted from the x-coordinate of the EC-point message. There are two possible candidates of y for a single x because if (x, y) is on a curve, (x, -y) is also on a curve. You can choose either points arbitrary since y-coordinate will be discarded at the final step of this protocol.