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 ¶
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.
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
Source Files