cc-set-intersection

README

cc-set-intersection

Confidential computing example - Set-Intersection

@ref - research gate

Kissner L , Song D . Private and threshold set-intersection[J]. Advances in Cryptology – Crypto ’, 2004.

problem

Alice has Set A (S_A)

Bob has Set B (S_B)

Alice and Bob want to compute the set-intersection of S_A and S_B, but they do not want to leak any information about their set.

This protocol is used for confidential computing.

Alice and Bob both run this protocol with their set's as input, at the end of this protocol, they both have the intersection of their sets.

In this protocol, Set is defined as a collection of big numbers. For other type of elements, we can map them to big numbers.

base knowledge

Additively Homomorphic Cryptosystem

Paillier’s cryptosystem

TODO:: 找 golang 的 Paillier 库, 或者自行实现(推荐)

the encryption function with public key pk:

• E_pk(·)

The cryptosystem supports the following two operations, which can be performed without knowledge of the private key:

• E_pk(a + b) := E_pk(a) +_h E_pk(b)

  • Given the encryptions of a and b, E_pk(a) and E_pk(b), we can efficiently compute the encryption of a + b

  • 加同态

• E_pk(c · a) := c ×_h E_pk(a)

  • Given a constant c and the encryption of a, E_pk(a), we can efficiently compute the encryption of c · a,

  • 标量乘同态

We also require that the homomorphic public-key cryptosystem support secure (n, n)- threshold decryption.

Polynomials Over Rings

TODO:: 需要一人确定是否用到此部分

Commitment

TODO:: 需要具体方案

Hash Function

SHA

TODO:: 需要确定使用哪种hash

• h(·)

  • a hash function from {0, 1}^* to {0, 1}^l ( l = lg(1 / ε) ), where ε is a probability parameter chosen to be negligable)

Zero-Knowledge Proofs

TODO:: 确定是否均为标准 ZKP 流程

• POPK{C = E_pk(x)}

  • V: 拥有数字 x 的密文 C = E_pk(x)
  • P: 证明知道秘密 x

• ZKPK{f | p' = f ∗_h E_pk(p)}

  • V: 拥有多项式 p 的密文 p' = f ∗_h E_pk(p)
  • P: 证明知道多项式 p

• ZKPK{f | (p' = f ∗_h E_pk(p)) ∧ (y = E_pk (f))}

  • V: 拥有多项式 p 的密文 p' = f ∗_h E_pk(p)
  • V: 拥有乘法系数 f 的密文 y = E_pk (f))
  • P: 证明知道多项式 p 和 乘法系数 f

protocol

TODO:: 理清流程, 将上方的内容对号入座

The protocol is based on section 6.2 of Private and threshold set-intersection, named Intersection-Mal.

input