bpsi

README

BPSI implementation

protocol

The bloomfilter private set intersection (BPSI) is another naive and insecure protocol, but it is highly efficient and has lower communication cost than NPSI. It is based on bloomfilter [1], a probablistic data structure that uses k independent hash functions to compactly represent a set of n elements with only m bits. It supports O(1) set insertion and provides O(1) set membership queries at the cost of a small and tunable false positive rate. This means that we can know for certain an element is not in the bloomfilter, and we know an element is in the bloomfilter except with a small false positive probability.

In the protocol, the sender P1 inserts all its elements X into a bloomfilter, and sends it to the receiver P2. To compute the intersection, P2 needs to simply check the set membership of each of his elements Y with the received bloomfilter.

data flow

Sender (P1)                                       Receiver (P2)
X                                                 Y

BF(X)         ------------------------------>     intersect(Y, BF(X))

BF(X): Bloomfilter bit set of inputs X

References

[1] Bloom, Burton H. "Space/time trade-offs in hash coding with allowable errors." Communications of the ACM 13.7 (1970): 422-426.

Documentation

Index

• Constants
• Variables
• func NewBloomfilter(t Bloomfilter, n int64) (bloomfilter, error)
• func ReadFrom(r io.Reader) (bloomfilter, int64, error)
• type Bloomfilter
• type Receiver
  • func NewReceiver(rw io.ReadWriter) *Receiver
  • func (r *Receiver) Intersect(ctx context.Context, n int64, identifiers <-chan []byte) (intersection [][]byte, err error)
• type Sender
  • func NewSender(rw io.ReadWriter) *Sender
  • func (s *Sender) Send(ctx context.Context, n int64, identifiers <-chan []byte) error

Constants

const (
	// FalsePositive is the fixed false positive rate parameter for the bloomfilter,
	// expressed in terms of 0-1 is 0% - 100%
	FalsePositive = 1e-6

	BloomfilterTypeBitsAndBloom = iota
)

Variables

var ErrReadingBloomfilter = fmt.Errorf("could not read a bloomfilter structure from the remote end")

ErrReadingBloomfilter is triggered if there's an IO problem reading the remote side bloomfilter structure

Functions

func NewBloomfilter

func NewBloomfilter(t Bloomfilter, n int64) (bloomfilter, error)

NewBloomfilter instantiates a bloomfilter with the given type and number of items to be inserted.

func ReadFrom

func ReadFrom(r io.Reader) (bloomfilter, int64, error)

ReadFrom r into a new bitsAndBloom bloomfilter

Types

type Bloomfilter

type Bloomfilter int

var BloomfilterBitsAndBloom Bloomfilter = BloomfilterTypeBitsAndBloom

type Receiver

type Receiver struct {
	// contains filtered or unexported fields
}

Receiver side of the BPSI protocol

func NewReceiver

func NewReceiver(rw io.ReadWriter) *Receiver

NewReceiver returns a bloomfilter receiver initialized to use rw as the communication layer

func (*Receiver) Intersect

func (r *Receiver) Intersect(ctx context.Context, n int64, identifiers <-chan []byte) (intersection [][]byte, err error)

Intersect on matchables read from the identifiers channel, returning the matching intersection, using the NPSI protocol. The format of an indentifier is

string

type Sender

type Sender struct {
	// contains filtered or unexported fields
}

Sender side of the BPSI protocol

func NewSender

func NewSender(rw io.ReadWriter) *Sender

NewSender returns a bloomfilter sender initialized to use rw as the communication layer

func (*Sender) Send

func (s *Sender) Send(ctx context.Context, n int64, identifiers <-chan []byte) error

Send initiates a BPSI exchange that are read from identifiers, until identifiers closes. The format of an indentifier is string example:

0e1f461bbefa6e07cc2ef06b9ee1ed25101e24d4345af266ed2f5a58bcd26c5e