Oblivious Transfer

The base OT and correlated OT extension underneath threshold ECDSA — simplest (Verified Simplest OT) and kos (KOS15 cOT extension).

What oblivious transfer is, and why ECDSA needs it

In 1-out-of-2 OT the sender holds two strings m_0, m_1; the receiver holds a choice bit b. After the protocol the receiver knows m_b and nothing about m_{1-b}, and the sender learns nothing about b.

ECDSA needs this because signing requires computing k^{-1}(H(m) + r·sk) where k and sk are both split across two parties. Adding shares is free; multiplying them is not. The standard two-party trick is to expand one party’s secret into bits, have the other party offer a correlated pair per bit, and let OT select. Sum the selections and you have an additive sharing of the product, with neither side having learned a factor. That is precisely what sign.MultiplySender / MultiplyReceiver do, and kos is the OT engine they drive.

Two layers, one reason

Base OT costs public-key operations — a Schnorr proof, a scalar multiplication per instance. A single ECDSA signature needs thousands of OTs. Running thousands of base OTs would be intolerably slow.

OT extension fixes this. You run a small fixed number of base OTs once — kos.Kappa = 256 of them, the computational security parameter — and then stretch that seed material into arbitrarily many OTs using nothing but hashing and binary-field arithmetic. In kos each extension produces L = 2·Kappa + 2·s = 672 correlated OTs (with s = 80, the statistical security parameter) from that one seed set.

So the pipeline is: simplest once → kos many times.

ot/base/simplest — Verified Simplest OT

The package doc names its lineage precisely: “Verified Simplest OT” as defined in “protocol 7” of DKLs18, with the original Simplest OT from CC15. Multiple choice bits run in parallel, and it is implemented as a Random OT — the sender does not choose its messages; both are random pads produced by the protocol.

Security model, from the source

• The “Verified” prefix is the point: rounds 4–6 are a challenge/response/opening phase that lets the receiver detect a cheating sender. This is the maliciously secure variant of Simplest OT, not the semi-honest one.
• Ideal functionalities are instantiated concretely, and the package says which: ZKP Schnorr realizes the F^{R_{DL}}_{ZK} zero-knowledge functionality, and “We have used HMAC for realizing the Random Oracle Hash function, the key for HMAC is received as input to the protocol.” The HMAC key is the uniqueSessionId.
• Session binding uses a Merlin transcript, initialised with the domain string "Coinbase_DKLs_SeedOT" and immediately absorbing uniqueSessionId.

Construction

import (
	"crypto/rand"

	"github.com/sonr-io/crypto/core/curves"
	"github.com/sonr-io/crypto/ot/base/simplest"
)

curve := curves.K256()

// Fresh, unpredictable, and identical on both sides. See the danger callout.
uniqueSessionId := [simplest.DigestSize]byte{}
if _, err := rand.Read(uniqueSessionId[:]); err != nil {
	return err
}

const batchSize = 256 // must be a multiple of 8

sender, err := simplest.NewSender(curve, batchSize, uniqueSessionId)
if err != nil {
	return err
}
receiver, err := simplest.NewReceiver(curve, batchSize, uniqueSessionId)
if err != nil {
	return err
}

DigestSize = 32 — the hash length, and also the plaintext/ciphertext size for the optional encryption steps.

The eight interleaved rounds

As in tECDSA, the numbers form one global sequence across both parties; the sender owns the odd rounds and the receiver the even ones. ot/ottest.RunSimplestOT wires all of it up:

import "github.com/sonr-io/crypto/ot/ottest"

// Creates both parties, runs rounds 1–6, and returns their outputs.
senderOutput, receiverOutput, err := ottest.RunSimplestOT(curve, batchSize, uniqueSessionId)

Its own doc says it is “a utility function used only during various tests”. The sequence it performs, which is the canonical call order:

Outputs

The correctness invariant, which the tests assert directly:

The optional message layer is SenderOutput.Encrypt(plaintexts) (protocol step 9) and ReceiverOutput.Decrypt(ciphertexts) (step 10); the round wrappers above just call these. ExtractBitFromByteVector(vector []byte, index int) byte reads the index-th bit of a packed vector, little-endian both across and within bytes — needed to interpret PackedRandomChoiceBits by hand.

Streaming helpers

senderPipe, receiverPipe := simplest.NewPipeWrappers()
errorsChannel := make(chan error, 2)

go func() { errorsChannel <- simplest.SenderStreamOTRun(sender, senderPipe) }()
go func() { errorsChannel <- simplest.ReceiverStreamOTRun(receiver, receiverPipe) }()

for i := 0; i < 2; i++ {
	if err := <-errorsChannel; err != nil {
		return err
	}
}

SenderStreamOTRun(sender *Sender, rw io.ReadWriter) error and ReceiverStreamOTRun(receiver *Receiver, rw io.ReadWriter) error run the whole six-round process over one io.ReadWriter — a websocket in practice — handling all encoding and decoding. The docs frame the purpose as “conveniently bundling up the entire seed OT process, for use in tests”. NewPipeWrappers() returns a connected in-memory pair for driving both sides in one process.

ot/extension/kos — correlated OT extension

Maliciously secure OT extension, “Protocol 9” of DKLs18, originally KOS15 — both cited in the package doc.

This is correlated OT: the receiver supplies a choice vector, the sender supplies input scalars alpha_j, and the two outputs add to alpha_j where the choice bit is 1 and to zero where it is 0. That additive-sharing-of-a-selected-value shape is exactly what the multiplication protocol consumes.

Constants

Three rounds

import (
	"crypto/rand"

	"github.com/sonr-io/crypto/core/curves"
	"github.com/sonr-io/crypto/ot/base/simplest"
	"github.com/sonr-io/crypto/ot/extension/kos"
	"github.com/sonr-io/crypto/ot/ottest"
)

func runCOt(curve *curves.Curve) error {
	uniqueSessionId := [simplest.DigestSize]byte{}
	if _, err := rand.Read(uniqueSessionId[:]); err != nil {
		return err
	}

	// Seed OT: exactly Kappa base OTs.
	baseSenderOutput, baseReceiverOutput, err := ottest.RunSimplestOT(curve, kos.Kappa, uniqueSessionId)
	if err != nil {
		return err
	}

	// Note the crossed roles.
	sender := kos.NewCOtSender(baseReceiverOutput, curve)
	receiver := kos.NewCOtReceiver(baseSenderOutput, curve)

	// Receiver's input: the packed choice vector.
	choice := [kos.COtBlockSizeBytes]byte{}
	if _, err = rand.Read(choice[:]); err != nil {
		return err
	}

	// Sender's input: the correlations alpha_j.
	input := [kos.L][kos.OtWidth]curves.Scalar{}
	for i := 0; i < kos.L; i++ {
		for j := 0; j < kos.OtWidth; j++ {
			input[i][j] = curve.Scalar.Random(rand.Reader)
		}
	}

	round1Output, err := receiver.Round1Initialize(uniqueSessionId, choice)
	if err != nil {
		return err
	}
	round2Output, err := sender.Round2Transfer(uniqueSessionId, input, round1Output)
	if err != nil {
		return err
	}
	if err = receiver.Round3Transfer(round2Output); err != nil {
		return err
	}

	// Invariant: for every slot j and every k < OtWidth,
	//   sender.OutputAdditiveShares[j][k] + receiver.OutputAdditiveShares[j][k]
	//     == input[j][k]   if choice bit j is 1
	//     == 0             if choice bit j is 0
	return nil
}

Both parties read their result from the exported field OutputAdditiveShares [L][OtWidth]curves.Scalar.

Streaming equivalents mirror the base layer: SenderStreamCOtRun(sender *Sender, hashKeySeed [simplest.DigestSize]byte, input [L][OtWidth]curves.Scalar, rw io.ReadWriter) error and ReceiverStreamCOtRun(receiver *Receiver, hashKeySeed [simplest.DigestSize]byte, choice [COtBlockSizeBytes]byte, rw io.ReadWriter) error. Both take the inputs plus a ReadWriter and handle every round and every encode/decode.

Caveats

Next