Coder Social home page Coder Social logo

sdiehl / oblivious-transfer Goto Github PK

View Code? Open in Web Editor NEW
36.0 13.0 6.0 32 KB

Oblivious transfer for multiparty computation

Home Page: https://www.adjoint.io

License: BSD 3-Clause "New" or "Revised" License

Haskell 100.00%
cryptography multiparty-computation oblivious-transfer elliptic-curves

oblivious-transfer's Introduction

Adjoint Logo

CircleCI Hackage

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, m0 and m1; 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 Mc, 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(Fq). The set of points E(Fq) 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

  1. Alice derives two keys:
    • K0 = aB
    • K1 = a(B - A)

It's easy to check that Bob can derive the key Kc 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 (M0, ..., Mn-1). 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 ∈ Zp 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 ∈ Zn, samples b ∈ Zp and replies R = cA + bG. Alice aborts if R is not a valid point in the curve.

Key derivation

  1. For all e ∈ Zn, Alice computes ke = aR - eT. She now has a vector of keys (k0, ..., kn-1).

  2. Bob computes kR = bA.

We can see that the key ke = aR - eT = abG + (c - e)T. If e = c, then kc = abG = bA = kR. Therefore, kR = kc if both parties are honest.

{-# LANGUAGE ScopedTypeVariables #-}
import Protolude
import Data.Curve.Weierstrass.SECP256K1
import qualified OT

testOT :: Integer -> IO Bool
testOT n = do

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

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

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

  -- Bob only gets to know one out of n keys. Alice doesn't know which one
  let receiverKey = OT.deriveReceiverKey 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 ∈ Zp 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 ci ∈ Zn, samples bi ∈ Zp and replies Ri = ciA + biG. Alice aborts if Ri is not a valid point in the curve.

Key derivation

  1. For all ei ∈ Zn, Alice computes kei = aRi - eiT. She now has a vector of vectors of keys (k0i, ..., kn-1i).

  2. Bob computes kRi = biA.

We can see that the key kei = aRi - eiT = abiG + (ci - ei)T. If e = c, then kci = abiG = biA = kRi. Therefore, kRi = kci 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.
P: Upper-case letters are points in an elliptic curve.
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-2020 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.

oblivious-transfer's People

Contributors

24jkeen avatar acentelles avatar sdiehl avatar

Stargazers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

Watchers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.