閾值PSI

若交集數量超過某個給定閾值時，允許分散式的各個參與方在自己集合中找到交集，且除了交集外，得不到其他額外資訊。

實現論文： Multi-Party Threshold Private Set Intersection with Sublinear Communication

原始碼地址：https://github.com/ontanj/tpsi

其中\(F_{TPSI-int}\)做出部分修改，因為基於TFHE無法實現自舉（bootstrapping）技術。

用到的加密演演算法：

\(TAHE\)：Paillier-https://github.com/niclabs/tcpaillier

\(TFHE\)：BFV-https://github.com/ldsec/lattigo

介面：

（1）AHE_Cryptosystem和FHE_Cryptosystem實現同態運算

type AHE_Cryptosystem interface {

    // 密文+密文
    Add(Ciphertext, Ciphertext) (sum Ciphertext, err error)

    // 密文^{明文}
    Scale(cipher Ciphertext, factor *big.Int) (product Ciphertext, err error)
    
    // 加密
    Encrypt(*big.Int) (Ciphertext, error)

    // 聚合明文
    CombinePartials([]Partial_decryption) (*big.Int, error)

    // 計算加密矩陣
    EvaluationSpace() gm.Space

    // 明文空間大小
    N() *big.Int
}
type FHE_Cryptosystem interface {
    AHE_Cryptosystem

    // 密文*密文
    Multiply(Ciphertext, Ciphertext) (Ciphertext, error)
}

（2）AHE_setting和FHE_setting包含參與方數量、閾值大小和通訊方式

type AHE_setting interface {
	// 閾值
	Threshold() int

	// 參與方
	Parties() int

	// AHE
	AHE_cryptosystem() AHE_Cryptosystem

	// central方釋出訊息給其他方
	Distribute(interface{})

	// 其他方給central方傳遞訊息
	Send(interface{})

	// central方給指定方傳送訊息
	SendTo(int, interface{})

	// central方等待來其他方的訊息，並將其（按順序）分組
	ReceiveAll() []interface{}

	// 接手central方的訊息
	Receive() interface{}

	// 判斷是否為central方
	IsCentral() bool
}
type FHE_setting interface {
	AHE_setting

	// FHE
	FHE_cryptosystem() FHE_Cryptosystem
}

本實驗是在一臺機器上模擬多方通訊，通過goroutine實現。

goroutine：在go語言中，每一個並行的執行單元叫做goroutine，如果一個程式中包含多個goroutine，對兩個函數的呼叫則可能發生在同一時刻。

執行：

go run main/main.go diff dj 7 main/elements

其中FTPSI-diff使用的是TAHE，閾值為7。

功能：

（1）TPSIdiffWorker，在交集測試下求交集和差集

（2）TPSIintWorker：在差集測試下求交集和差集

測試：

P1：0,3,6,9,13,16
P2：0,3,6,9,14,17
P3：0,3,6,9,14,15
P4：0,3,6,9,12,17
P5：0,3,6,9,13,15

T=7

//交集大時用TFHE求
go run main/main.go int bfv 7 main/elements
//差集小時用TAHE求
go run main/main.go diff dj 7 main/elements
//差集小時用TFHE求
go run main/main.go diff bfv 7 main/elements

總結：
用FHE實現，效率是顯而易見的！