Crypto

[Crypto][theory]Private Set Intersection

kwon76 2025. 2. 20. 00:51

 

최근 동형 암호를 공부하면서 관련된 응용 주제 중 Private Set Intersection에 대해 논문을 읽고 이를 Linux 환경에서 구현해보고 있다.

오늘은 PSI에 대한 개념을 가볍게 알아보자.

 

 

 

 

Private Set Intersection(PSI)

  • Alice와 Bob이 있다. Alice는 {1, 2, 3}을 가지고 있고, Bob은 {1, 3, 4, 5, 9}를 가지고 있다.
  • Alice는 자신과 Bob의 교집합에는 어떤 원소가 있는지, 즉 공통으로 가지고 있는 원소가 무엇인지 알고 싶다. 그럴러면 Bob의 원소에는 무엇이 있는지 Alice가 직접 확인해야 할 것이다. 그렇게 되면 Bob의 정보가 Alice에게 유출되는 것으로 볼 수 있다.
  • Private Set Intersection은 위의 상황을 방지하면서도 Alice가 자신과 Bob의 공통 원소가 무엇이 있는지를 알 수 있게 한다. 즉, Bob의 모든 원소가 Alice에게 공개되지 않은 채 공통 원소만을 Alice에게 알려주는 것이다. 중요한 것은 이때 Bob은 Alice에게 어떤 원소가 있는지 알 수 없게 하는 것이 PSI의 보안성이다.

PSI의 기본 개념도.

 

 

 

Basic Protocol

  • 이 PSI를 구현할 때 동형 암호 기술이 중요하게 적용이 된다. 기본적인 Protocol은 다음과 같다.

 

1. 송신자(Sender) 집합 X와 수신자(Receiver) 집합 Y가 있다. 각각의 원소를 {x1, x2, x3 ... , xn}, {y1, y2, y3, ... , ym}이라 하자.

2. 집합 Y의 원소들을 전부 Encrypt 한다. 암호화된 원소들을 {Enc(y1), Enc(y2), ... , Enc(ym)} = {c1, c2, ... , cm} 이라 하자.

3. 수신자는 {c1, c2, ... , cm}을 송신자에게 보낸다. 송신자는 수신자의 원소가 암호화 되어있기 때문에 무엇인지 알 수 없다.

4. 송신자는 암호화된 각각의 c에 대해 (c-x1)(c-x2)...(c-xn)를 계산한 값들을 수신자에게 보내준다.

5. 수신자는 이 값들을 Decrypt한다. 이때 Decrypt한 값이 0이라면, 그 원소를 공통 원소로 결정한다.

 

 

 

 

Reference