packages feed

oblivious-transfer (empty) → 0.1.0

raw patch · 8 files changed

+416/−0 lines, 8 filesdep +QuickCheckdep +basedep +bytestringsetup-changed

Dependencies added: QuickCheck, base, bytestring, cryptonite, memory, oblivious-transfer, protolude, random, tasty, tasty-discover, tasty-hunit, tasty-quickcheck

Files

+ ChangeLog.md view
@@ -0,0 +1,3 @@+# Changelog for oblivious-transfer++## Unreleased changes
+ LICENSE view
@@ -0,0 +1,30 @@+Copyright Author name here (c) 2018++All rights reserved.++Redistribution and use in source and binary forms, with or without+modification, are permitted provided that the following conditions are met:++    * Redistributions of source code must retain the above copyright+      notice, this list of conditions and the following disclaimer.++    * Redistributions in binary form must reproduce the above+      copyright notice, this list of conditions and the following+      disclaimer in the documentation and/or other materials provided+      with the distribution.++    * Neither the name of Author name here nor the names of other+      contributors may be used to endorse or promote products derived+      from this software without specific prior written permission.++THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS+"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT+LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR+A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT+OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,+SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT+LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,+DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY+THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT+(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE+OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ README.md view
@@ -0,0 +1,130 @@+<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](https://circleci.com/gh/adjoint-io/oblivious-transfer.svg?style=svg)](https://circleci.com/gh/adjoint-io/oblivious-transfer)++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.++```haskell+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.+```
+ Setup.hs view
@@ -0,0 +1,2 @@+import Distribution.Simple+main = defaultMain
+ oblivious-transfer.cabal view
@@ -0,0 +1,68 @@+-- This file has been generated from package.yaml by hpack version 0.28.2.+--+-- see: https://github.com/sol/hpack+--+-- hash: 0274e8d72c54fc39e8449ddd6257b2d6346b35128509a08618044668a67cb578++name:           oblivious-transfer+version:        0.1.0+synopsis:       An implementation of the Oblivious Transfer protocol in Haskell+description:    Please see the README on GitHub at <https://github.com/githubuser/oblivious-transfer#readme>+category:       Cryptography+homepage:       https://github.com/adjoint-io/oblivious-transfer#readme+bug-reports:    https://github.com/adjoint-io/oblivious-transfer/issues+maintainer:     Adjoint Inc (info@adjoint.io)+license:        Apache+license-file:   LICENSE+build-type:     Simple+cabal-version:  >= 1.10+extra-source-files:+    ChangeLog.md+    README.md++source-repository head+  type: git+  location: https://github.com/adjoint-io/oblivious-transfer++library+  exposed-modules:+      OT+  other-modules:+      Paths_oblivious_transfer+  hs-source-dirs:+      src+  default-extensions: LambdaCase RecordWildCards OverloadedStrings NoImplicitPrelude FlexibleInstances+  ghc-options: -fwarn-tabs -fwarn-incomplete-patterns -fwarn-incomplete-record-updates -fwarn-redundant-constraints -fwarn-implicit-prelude -fwarn-overflowed-literals -fwarn-orphans -fwarn-identities -fwarn-dodgy-exports -fwarn-dodgy-imports -fwarn-duplicate-exports -fwarn-overlapping-patterns -fwarn-missing-fields -fwarn-missing-methods -fwarn-missing-signatures -fwarn-noncanonical-monad-instances -fwarn-unused-pattern-binds -fwarn-unused-type-patterns -fwarn-unrecognised-pragmas -fwarn-wrong-do-bind -fno-warn-name-shadowing -fno-warn-unused-binds -fno-warn-unused-matches -fno-warn-unused-do-bind+  build-depends:+      base >=4.7 && <5+    , bytestring+    , cryptonite+    , memory+    , protolude >=0.2+    , random+  default-language: Haskell2010++test-suite oblivious-transfer-test+  type: exitcode-stdio-1.0+  main-is: Driver.hs+  other-modules:+      TestOT+      Paths_oblivious_transfer+  hs-source-dirs:+      test+  default-extensions: LambdaCase RecordWildCards OverloadedStrings NoImplicitPrelude FlexibleInstances+  ghc-options: -threaded -rtsopts -with-rtsopts=-N+  build-depends:+      QuickCheck+    , base >=4.7 && <5+    , bytestring+    , cryptonite+    , memory+    , oblivious-transfer+    , protolude >=0.2+    , random+    , tasty+    , tasty-discover+    , tasty-hunit+    , tasty-quickcheck+  default-language: Haskell2010
+ src/OT.hs view
@@ -0,0 +1,128 @@+module OT+( setup+, choose+, deriveSenderKeys+, deriveReceiverKey+, mDeriveSenderKeys+, mDeriveReceiverKeys+--, unzip3+, mChoose+) where++import Protolude hiding (hash)++import           Crypto.Hash+import           Crypto.Random.Types (MonadRandom)+import qualified Crypto.PubKey.ECC.Prim     as ECC+import qualified Crypto.PubKey.ECC.Types    as ECC+import qualified Crypto.PubKey.ECC.Generate as ECC+import           Crypto.Number.Generate     (generateMax)+import qualified Crypto.PubKey.ECC.ECDSA    as ECDSA+import           Crypto.Number.Serialize    (os2ip)+import qualified Data.ByteArray             as BA+import qualified Data.ByteString            as BS+import Control.Monad.Fail+import           Data.List  ((!!))  +++-- | Setup: Only once, independently of the number of OT messages *m*.+setup :: (MonadRandom m, MonadFail m) => ECC.Curve -> m (Integer, ECC.Point, ECC.Point)+setup curve = do+  -- 1. Sender samples y <- Zp and computes S = yB and T = yS+  (sPubKey, sPrivKey) <- bimap ECDSA.public_q ECDSA.private_d <$> ECC.generate curve+  let t = ECC.pointMul curve sPrivKey sPubKey++  -- 2. S sends S to R, who aborts if S doesn't belong to G+  unless (ECC.isPointValid curve sPubKey) $+    fail "Invalid sPubKey from sender"++  pure (sPrivKey, sPubKey, t)+++-- | Choose: In parallel for all OT messages.+choose :: (MonadRandom m, MonadFail m) => ECC.Curve -> Integer -> ECC.Point -> m (Integer, ECC.Point, Integer)+choose curve n sPubKey = do+  -- 1. Receiver samples x <- Zp and computes Response+  c <- generateMax (n - 1)+  rPrivKey <- ECDSA.private_d . snd <$> ECC.generate curve++  let cS = ECC.pointMul curve c sPubKey+  let xB = ECC.pointBaseMul curve rPrivKey+  let response = ECC.pointAdd curve cS xB++  -- 2. Fail if the response is not a valid point in the curve+  unless (ECC.isPointValid curve response) $+    fail "Invalid response from verifier"++  pure (rPrivKey, response, c)+++mChoose+  :: (Eq t, Num t, MonadRandom m, MonadFail m) =>+     ECC.Curve+     -> Integer+     -> ECC.Point+     -> t+     -> [(Integer, ECC.Point, Integer)]+     -> m [(Integer, ECC.Point, Integer)]++-- | Call 'choose' 'm' times to create a list of three lists +-- | Return lists of private keys, responses and choice bit+mChoose curve n sPubKey 0 accum = return accum+mChoose curve n sPubKey m accum = do +  a <- choose curve n sPubKey+  b <- mChoose curve (n) sPubKey (m-1) accum+  let accum = a : b +  return (accum)++-- | Sender's key derivation from his private key and receiver's response+-- In parallel for all OT messages+deriveSenderKeys :: ECC.Curve -> Integer -> Integer -> ECC.Point -> ECC.Point -> [Integer]+deriveSenderKeys curve n sPrivKey response t = deriveSenderKey <$> [0..n-1]+ where+    deriveSenderKey j = hashPoint curve (ECC.pointAdd curve yR (ECC.pointNegate curve (jT j)))+    yR = ECC.pointMul curve sPrivKey response+    jT j = ECC.pointMul curve j t++mDeriveSenderKeys+  :: ECC.Curve+  -> Integer +  -> Integer +  -> [ECC.Point] +  -> ECC.Point  +  -> [[Integer]]++-- | Fold together 'm' calls of 'deriveSenderKeys'  +mDeriveSenderKeys curve n sPrivKey responses t = mDeriveSenderKeys' <$> responses+  where mDeriveSenderKeys' response = deriveSenderKeys curve n sPrivKey response t +++-- | Receiver's key derivation from his private key and sender's public key+-- In parallel for all OT messages+deriveReceiverKey :: ECC.Curve -> Integer -> ECC.Point -> Integer+deriveReceiverKey curve rPrivKey sPubKey = hashPoint curve (ECC.pointMul curve rPrivKey sPubKey)++mDeriveReceiverKeys+  :: ECC.Curve+  -> [Integer] +  -> ECC.Point  +  -> [Integer]++-- | Fold together 'm' calls of 'deriveReceiverKeys'+mDeriveReceiverKeys curve rPrivKeys sPubKey = deriveReceiverKey'  <$> rPrivKeys+  where deriveReceiverKey' rPrivKey = deriveReceiverKey curve rPrivKey sPubKey++hashPoint :: ECC.Curve -> ECC.Point -> Integer+hashPoint curve ECC.PointO      = oracle curve ""+hashPoint curve (ECC.Point x y) = oracle curve (show x <> show y)++-- | Outputs unpredictable but deterministic random values+oracle :: ECC.Curve -> BS.ByteString -> Integer+oracle curve x = os2ip (sha256 x) `mod` ecc_n+  where+    ecc_n = ECC.ecc_n (ECC.common_curve curve)++-- | Secure cryptographic hash function+sha256 :: BS.ByteString -> BS.ByteString+sha256 bs = BA.convert (hash bs :: Digest SHA3_256)+
+ test/Driver.hs view
@@ -0,0 +1,1 @@+{-# OPTIONS_GHC -F -pgmF tasty-discover -optF --tree-display #-}
+ test/TestOT.hs view
@@ -0,0 +1,54 @@+module TestOT where++import           Protolude+import           Data.List +import qualified Test.QuickCheck.Monadic as QCM+import           Test.Tasty+import           Test.Tasty.HUnit+import           Test.Tasty.QuickCheck+import qualified Crypto.PubKey.ECC.Prim     as ECC+import qualified Crypto.PubKey.ECC.Types    as ECC+import qualified Crypto.PubKey.ECC.Generate as ECC++import qualified OT++secp256k1Curve :: ECC.Curve+secp256k1Curve = ECC.getCurveByName ECC.SEC_p256k1++test_OT :: TestTree+test_OT = testGroup "1-out-of-N oblivious transfer"+  [ localOption (QuickCheckTests 10) $ testProperty+      "Verify that the receiver key is one of the sender keys"+      (forAll (choose (3, 20) )(testOT secp256k1Curve))++  +   ,   localOption (QuickCheckTests 10) $ testProperty+      "Verify m 1-out-of-n receiver keys match with sender keys"+      (forAll (choose (3, 20)) (testMOT secp256k1Curve))+   ]++--test m 1-out-of-n OT protocol+testMOT:: ECC.Curve -> Integer -> Property+testMOT curve n = QCM.monadicIO $ do+  let m = 20+  (sPrivKey, sPubKey, t) <- liftIO $ OT.setup curve+  choices <- liftIO $OT.mChoose curve n sPubKey m []+  let (rPrivKeys, responses, cs) = unzip3 choices+  let senderKeys = OT.mDeriveSenderKeys curve n sPrivKey responses t+  let recieverKeys = OT.mDeriveReceiverKeys curve rPrivKeys sPubKey+  QCM.assert True++-- test 1 out of n OT protocol+testOT :: ECC.Curve -> Integer -> Property+testOT curve n = QCM.monadicIO $ do++  (sPrivKey, sPubKey, t) <- liftIO $ OT.setup curve++  (rPrivKey, response, c) <- liftIO $ OT.choose curve n sPubKey++  let senderKeys = OT.deriveSenderKeys curve n sPrivKey response t++  -- Receiver only gets to know one out of n values. Sender doesn't know which one+  let receiverKey = OT.deriveReceiverKey curve rPrivKey sPubKey++  QCM.assert $ receiverKey == (senderKeys !! fromInteger c)