README
¶
ECDH PSI implementation
protocol
The Diffie-Hellman private set intersection (DHPSI) [1] is one of the first PSI protocols and is communication efficient, but requires expensive computations from both parties: a sender and a receiver. We implement DHPSI using elliptic curve (specifically ristretto255 [2]) instead of finite field exponentiation for performance reasons. The point operation of kP is the multiplication of a ristretto point P with a scalar k over an ellipic curve (Curve25519).
- the receiver and the sender agree on a preset elliptic curve E (Curve25519).
- the sender generates his private key (scalar) a, and hashes each identifier from his input audience list to obtains points xi ∈ X on E. (Derive)
- for each of the derived points xi, the sender computes point multiplication: axi, and obtains the set of multiplied points aX. (Multiply)
- the sender permutes aX and sends them to the receiver. (ShuffleWrite)
- the receiver receives aX from the sender. The receiver generates his private key (scalar) b and multiplies each element axi ∈ aX with private key b: b(axi) to obtain the set of multiplied points baX and index it. (ReadMultiply)
- the receiver hashes each identifier from his input audience list to obtain points yi ∈ Y on E. (Derive)
- for each of the derived points yi, the receiver computes point multiplication: byi, and obtains the set of multiplied points bY. (Multiply)
- the receiver permutes bY and sends them to the sender. (ShuffleWrite)
- The sender receives bY, and multiplies each element byi ∈ bY with his private key a: a(byi) to obtain the set of multiplied points abY, and sends them back to the receiver. (ReadMultiply)
- the receiver receives abY, and finds the intersecting identifiers from the set baX and abY. (Intersect)
data flow
Sender Receiver
X, a Y, b
Stage 1 DM/Shuffle --------------aX-------------> M -> baX Stage 1
Stage 2 M -> abY +-------------bY-------------- DM/Shuffle Stage 2.1
|
+-------------abY------------> intersect(baX, abY) Stage 2.2
DM: ristretto255 derive/multiply
M: ristretto255 multiply
Shuffle: cryptographic quality shuffle
References
[1] C. Meadows. A more efficient cryptographic matchmaking protocol for use in the absence of a continuously available third party. In IEEE S&P’86, pages 134–137. IEEE, 1986.
[2] https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-ristretto255-decaf448
Documentation
¶
Index ¶
Constants ¶
const ( // EncodedLen is the length of an encoded ristretto point EncodedLen = 32 // EmailPrefixedLen is the length of a prefixed email identifier EmailPrefixedLen = 66 )
const ( RistrettoTypeGR = iota RistrettoTypeR255 RistrettoNil )
Variables ¶
var (
ErrUnexpectedPoint = fmt.Errorf("received a point to encode past the configured encoder size")
)
Functions ¶
This section is empty.
Types ¶
type DeriveMultiplyParallelShuffler ¶
type DeriveMultiplyParallelShuffler struct {
// contains filtered or unexported fields
}
DeriveMultiplyParallelShuffler contains the necessary machineries to derive identifiers into ristretto point multiply them with secret key and permute them, all in a parallel fashion.
func NewDeriveMultiplyParallelShuffler ¶
func NewDeriveMultiplyParallelShuffler(w io.Writer, n int64, gr Ristretto) (*DeriveMultiplyParallelShuffler, error)
NewDeriveMultiplyParallelShuffler returns a dhpsi encoder that hashes, encrypts and shuffles matchable values on n sequences of bytes to be sent out. It first computes a permutation table and subsequently sends out sequences ordered by the precomputed permutation table. This is the first stage of doing a DH exchange.
This version operates on multiple cores in parallel
func (*DeriveMultiplyParallelShuffler) Permutations ¶
func (enc *DeriveMultiplyParallelShuffler) Permutations() permutations.Permutations
Permutations returns the permutation matrix that was computed on initialization
func (*DeriveMultiplyParallelShuffler) Shuffle ¶
func (enc *DeriveMultiplyParallelShuffler) Shuffle(identifier []byte) (err error)
Shuffle shuffles one prefixed ID. First derive and then multiply by the precomputed scaler, written out to the underlying writer while following the order of permutations created at NewDeriveMultiplyShuffler. Returns ErrUnexpectedEncodeByte when the whole expected sequence has been sent.
type DeriveMultiplyShuffler ¶
type DeriveMultiplyShuffler struct {
// contains filtered or unexported fields
}
DeriveMultiplyShuffler contains the necessary machineries to derive identifiers into ristretto point, multiply them with secret key and permute them.
func NewDeriveMultiplyShuffler ¶
NewDeriveMultiplyShuffler returns a dhpsi encoder that hashes, encrypts and shuffles matchable values on n sequences of bytes to be sent out. It first computes a permutation table and subsequently sends out sequences ordered by the precomputed permutation table. This is the first stage of doing a DH exchange.
func (*DeriveMultiplyShuffler) Permutations ¶
func (enc *DeriveMultiplyShuffler) Permutations() permutations.Permutations
Permutations returns the permutation matrix that was computed on initialization
func (*DeriveMultiplyShuffler) Shuffle ¶
func (enc *DeriveMultiplyShuffler) Shuffle(identifier []byte) (err error)
Shuffle shuffles one identifier. First derive and then multiply by the precomputed scalar, then write out to the underlying writer while following the order of permutations created at NewDeriveMultiplyShuffler. Returns ErrUnexpectedPoint when the whole expected sequence has been sent.
type GR ¶
type GR struct {
// contains filtered or unexported fields
}
GR uses ristretto implementation from "github.com/bwesterb/go-ristretto"
func (GR) DeriveMultiply ¶
func (g GR) DeriveMultiply(dst *[EncodedLen]byte, src []byte)
DeriveMultiply derives src to a ristretto point and multiplies it with the private key and stores it into dst.
func (GR) Multiply ¶
func (g GR) Multiply(dst *[EncodedLen]byte, src [EncodedLen]byte)
Multiply multiplies src with private key and stores it into dst.
type MultiplyParallelReader ¶
type MultiplyParallelReader struct {
// contains filtered or unexported fields
}
A MultiplyParallelReader is a reader that sits on the other end of a DeriveMultiplyShuffler or a Writer and reads encoded ristretto hashes and multiplies them using gr.
func NewMultiplyParallelReader ¶
func NewMultiplyParallelReader(r io.Reader, gr Ristretto) (*MultiplyParallelReader, error)
NewMultiplyParallelReader makes a ristretto multiplier reader that sits on the other end of the DeriveMultiplyShuffler or the Writer and reads encoded ristretto hashes and multiplies them using gr.
This version operates on multiple cores in parallel
func (*MultiplyParallelReader) Max ¶
func (dec *MultiplyParallelReader) Max() int64
Max returns the expected number of matchable this decoder will receive
func (*MultiplyParallelReader) Read ¶
func (dec *MultiplyParallelReader) Read(point *[EncodedLen]byte) (err error)
Read reads a point from the underlying reader, multiplies it with ristretto and writes it into point. Returns io.EOF when the sequence has been completely read.
type MultiplyReader ¶
type MultiplyReader struct {
// contains filtered or unexported fields
}
func NewMultiplyReader ¶
func NewMultiplyReader(r io.Reader, gr Ristretto) (*MultiplyReader, error)
NewMultiplyReader makes a ristretto multiplier reader that sits on the other end of the DeriveMultiplyShuffler or the Writer and reads encoded ristretto hashes and multiplies them using gr.
func (*MultiplyReader) Max ¶
func (r *MultiplyReader) Max() int64
Max returns the expected number of matchable this decoder will receive
func (*MultiplyReader) Read ¶
func (r *MultiplyReader) Read(point *[EncodedLen]byte) (err error)
Read reads a point from the underlying reader, multiplies it with ristretto and writes it into point. Returns io.EOF when the sequence has been completely read.
type R255 ¶
type R255 struct {
// contains filtered or unexported fields
}
R255 uses ristretto implementation from "github.com/gtank/ristretto255"
func (R255) DeriveMultiply ¶
func (r R255) DeriveMultiply(dst *[EncodedLen]byte, src []byte)
DeriveMultiply derives src to a ristretto point and multiplies it with the private key and stores it into dst.
func (R255) Multiply ¶
func (r R255) Multiply(dst *[EncodedLen]byte, src [EncodedLen]byte)
Multiply multiplies src with private key and stores it into dst.
type Reader ¶
type Reader struct {
// contains filtered or unexported fields
}
func NewReader ¶
NewReader makes a simple reader that sits on the other end of the DeriveMultiplyShuffler or the Writer and reads encoded ristretto points
type Receiver ¶
type Receiver struct {
// contains filtered or unexported fields
}
Receiver represents the receiver in a DHPSI operation, often the publisher. The receiver learns the intersection of matchable between its set and the set of the sender
func NewReceiver ¶
func NewReceiver(rw io.ReadWriter) *Receiver
NewReceiver returns a receiver initialized to use rw as the communication layer
type Ristretto ¶
type Ristretto interface {
DeriveMultiply(dst *[EncodedLen]byte, src []byte)
Multiply(dst *[EncodedLen]byte, src [EncodedLen]byte)
}
Ristretto represents a ristretto point on an edward2559 curve.
The method DeriveMultiply converts an identifier to a ristretto point and multiply it with the secret key. Multiply operates on ristretto point directly and multiply it with the secret key.
func NewRistretto ¶
NewRistretto returns a new Ristretto of a given ristretto implementation.
type Sender ¶
type Sender struct {
// contains filtered or unexported fields
}
Sender represents the sender in a DHPSI operation, often the advertiser. The sender initiates the transfer and in the case of DHPSI, it learns nothing.
func NewSender ¶
func NewSender(rw io.ReadWriter) *Sender
NewSender returns a sender initialized to use rw as the communication layer
func (*Sender) Send ¶
Send initiates a DHPSI exchange with n identifiers that are read from the identifiers channel, until identifiers closes or n is reached. The format of an indentifier is string example:
0e1f461bbefa6e07cc2ef06b9ee1ed25101e24d4345af266ed2f5a58bcd26c5e
func (*Sender) SendFromReader ¶
SendFromReader initiates a DHPSI exchange with n identifiers that are read from r. The format of an indentifier is
string\n
example:
0e1f461bbefa6e07cc2ef06b9ee1ed25101e24d4345af266ed2f5a58bcd26c5e\r\n
Source Files