oblivious-transfer: An implementation of the Oblivious Transfer protocol in Haskell

[ cryptography, library ] [ Propose Tags ]

Please see the README on GitHub at https://github.com/adjoint-io/oblivious-transfer#readme


[Skip to Readme]
Versions [faq] 0.1.0
Change log ChangeLog.md
Dependencies base (>=4.7 && <5), bytestring, cryptonite, memory, protolude (>=0.2), random [details]
License LicenseRef-Apache
Author
Maintainer Adjoint Inc (info@adjoint.io)
Revised Revision 1 made by sdiehl at Fri Nov 30 15:11:05 UTC 2018
Category Cryptography
Home page https://github.com/adjoint-io/oblivious-transfer#readme
Bug tracker https://github.com/adjoint-io/oblivious-transfer/issues
Source repo head: git clone https://github.com/adjoint-io/oblivious-transfer
Uploaded by sdiehl at Wed Nov 21 12:53:22 UTC 2018
Distributions LTSHaskell:0.1.0, NixOS:0.1.0, Stackage:0.1.0
Downloads 201 total (18 in the last 30 days)
Rating (no votes yet) [estimated by rule of succession]
Your Rating
  • λ
  • λ
  • λ
Status Hackage Matrix CI
Docs available [build log]
Last success reported on 2018-11-21 [all 1 reports]

Modules

[Index] [Quick Jump]

Downloads

Note: This package has metadata revisions in the cabal description newer than included in the tarball. To unpack the package including the revisions, use 'cabal get'.

Maintainer's Corner

For package maintainers and hackage trustees


Readme for oblivious-transfer-0.1.0

[back to package description]
<p align="center"> <a href="http://www.adjoint.io"><img src="https://www.adjoint.io/assets/img/adjoint-logo@2x.png" width="250"/></a> </p>

CircleCI

Oblivious Transfer (OT) is a cryptographic primitive in which a sender transfers some of potentially many pieces of information to a receiver. The sender doesn't know which pieces of information have been transferred.

1-out-of-2 OT

Oblivious transfer is central to many of the constructions for secure multiparty computation. In its most basic form, the sender has two secret messages as inputs, m<sub>0</sub> and m<sub>1</sub>; the receiver has a choice bit c as input. At the end of the 1-out-of-2 OT protocol, the receiver should only learn message M<sub>c</sub>, while the sender should not learn the value of the receiver's input c.

The protocol is defined for elliptic curves over finite fields E(F<sub>q</sub>). The set of points E(F<sub>q</sub>) is a finite abelian group. It works as follows:

  1. Alice samples a random a and computes A = aG. Sends A to Bob

  2. Bob has a choice c. He samples a random b.

    • If c is 0, then he computes B = bG.
    • If c is 1, then he computes B = A + bG.

    Sends B to Alice

  3. Alice derives two keys:

    • K<sub>0</sub> = aB
    • K<sub>1</sub> = a(B - A)

    It's easy to check that Bob can derive the key K<sub>c</sub> corresponding to his choice bit, but cannot compute the other one.

1-out-of-N OT

The 1-out-of-N oblivious transfer protocol is a natural generalization of the 1-out-of-2 OT protocol, in which the sender has a vector of messages (M<sub>0</sub>, ..., M<sub>n-1</sub>). The receiver only has a choice c.

We implement a protocol for random OT, where the sender, Alice, outputs n random keys and the receiver, Bob, only learns one of them. It consists on three parts:

Setup

Alice samples a ∈ Z<sub>p</sub> and computes A = aG and T = aA, where G and p are the generator and the order of the curve, respectively. She sends A to Bob, who aborts if A is not a valid point in the curve.

Choose

Bob takes his choice c ∈ Z<sub>n</sub>, samples b ∈ Z<sub>p</sub> and replies R = cA + bG. Alice aborts if R is not a valid point in the curve.

Key derivation

  1. For all e ∈ Z<sub>n</sub>, Alice computes k<sub>e</sub> = aR - eT. She now has a vector of keys (k<sub>0</sub>, ..., k<sub>n-1</sub>).

  2. Bob computes k<sub>R</sub> = bA.

We can see that the key k<sub>e</sub> = aR - eT = abG + (c - e)T. If e = c, then k<sub>c</sub> = abG = bA = k<sub>R</sub>. Therefore, k<sub>R</sub> = k<sub>c</sub> if both parties are honest.

testOT :: ECC.Curve -> Integer -> IO Bool
testOT curve n = do

  -- Alice sets up the procotol
  (sPrivKey, sPubKey, t) <- OT.setup curve

  -- Bob picks a choice bit 'c'
  (rPrivKey, response, c) <- OT.choose curve n sPubKey

  -- Alice computes a set of n keys
  let senderKeys = OT.deriveSenderKeys curve n sPrivKey response t

  -- Bob only gets to know one out of n keys. Alice doesn't know which one
  let receiverKey = OT.deriveReceiverKey curve rPrivKey sPubKey

  pure $ receiverKey == (senderKeys !! fromInteger c)

k-out-of-N OT

1-out-of-N oblivious transfer can be generalised one step further into k-out-of-N. This is very similar in structure to the methods above comprising the same 3 parts:

Setup As above, Alice samples a ∈ Z<sub>p</sub> and computes A = aG and T = aA, where G and p are the generator and the order of the curve, respectively. She sends A to Bob, who aborts if A is not a valid point in the curve.

Choose Bob takes his choices c<sup>i</sup> ∈ Z<sub>n</sub>, samples b<sup>i</sup> ∈ Z<sub>p</sub> and replies R<sup>i</sup> = c<sup>i</sup>A + b<sup>i</sup>G. Alice aborts if R<sup>i</sup> is not a valid point in the curve.

Key derivation

  1. For all e<sup>i</sup> ∈ Z<sub>n</sub>, Alice computes k<sub>e</sub><sup>i</sup> = aR<sup>i</sup> - e<sup>i</sup>T. She now has a vector of vectors of keys (k<sub>0</sub><sup>i</sup>, ..., k<sub>n-1</sub><sup>i</sup>).

  2. Bob computes k<sub>R</sub><sup>i</sup> = b<sup>i</sup>A.

We can see that the key k<sub>e</sub><sup>i</sup> = aR<sup>i</sup> - e<sup>i</sup>T = ab<sup>i</sup>G + (c<sup>i</sup> - e<sup>i</sup>)T. If e = c, then k<sub>c</sub><sup>i</sup> = ab<sup>i</sup>G = b<sup>i</sup>A = k<sub>R</sub><sup>i</sup>. Therefore, k<sub>R</sub><sup>i</sup> = k<sub>c</sub><sup>i</sup> if both parties are honest.

References:

  1. Chou, T. and Orlandi, C. "The Simplest Protocol for Oblivious Transfer" Technische Universiteit Eindhoven and Aarhus University

Notation:

k: Lower-case letters are scalars. <br /> P: Upper-case letters are points in an elliptic curve. <br /> kP: Multiplication of a point P with a scalar k over an elliptic curve defined over a finite field modulo a prime number.

License

Copyright 2018 Adjoint Inc

Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at

    http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.