An implementation of private contact search by George Tankersley and Filippo Valsorda https://blog.gtank.cc/private-contact-search/

main.go

package main

import (
	"crypto/rand"
	"crypto/sha512"
	"fmt"
	"time"

	"github.com/gtank/ristretto255"
	"github.com/thetannerryan/ring"
)

var (
	// server's static secret value
	k *ristretto255.Scalar
	bloom *ring.Ring //a bloom filter to hold all "encrypted" contacts
)


func AddToBloom(contact []byte){
	x := HashToElement(contact)
	x.ScalarMult(k, x)
	bloom.Add(x.Encode(nil))
}

func main() {
	var err error

	buf := make([]byte, 64)
	rand.Read(buf)
	k = ristretto255.NewScalar().FromUniformBytes(buf) //init server key

	//init bloom filter with 1m capacity and 0.01% chance of false positive
	bloom, err = ring.Init(1000000, 0.0001)
	if err != nil {
		// error will only occur if parameters are set incorrectly
		panic(err)
	}

	fmt.Println("adding 100 000 contacts to filter")
	t := time.Now()
	var contacts [][]byte
	for i := 0; i < 100000; i++{
		contact := make([]byte, 10)
		rand.Read(contact)
		contacts = append(contacts, contact)
		AddToBloom(contact)
	}
	fmt.Println("Done in",time.Since(t), "Now client checks for 3 existing and 1 non existing contacts")
	//client part
	rand.Read(buf)
	r := ristretto255.NewScalar().FromUniformBytes(buf) //random blinding value
	rInv := ristretto255.NewScalar().Invert(r) // r ^ -1

	clientContacts := [][]byte{contacts[0], contacts[1000], contacts[10101], contacts[10102]}
	clientContacts[3][0] ^=3 //modify one contact and see what happens
	for _, contact := range clientContacts{
		x := HashToElement(contact)
		//multiply contact by blinding value
		x.ScalarMult(r, x)
		//send blinded contact to server and multiply by k (this is where rate limiting, etc occurs)
		x.ScalarMult(k, x)
		//return protected contact and deblind
		x.ScalarMult(rInv, x)
		//check
		fmt.Println(bloom.Test(x.Encode(nil)))
	}
}

func HashToElement(data []byte) *ristretto255.Element{
	hash := sha512.Sum512(data)
	return ristretto255.NewElement().FromUniformBytes(hash[:])
}