[Crypto][theory]Private Set Intersection

 

최근 동형 암호를 공부하면서 관련된 응용 주제 중 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의 기본 개념도.

 

• PSI는 개인 정보를 중요시하는 여러 분야에 적용된다. 코로나 유행 때 동선안심이 어플에도 PSI가 적용되었다. 애플은 암호 모니터링$Password Monitoring$에서 PSI를 적용한다. (https://support.apple.com/ko-kr/guide/security/sec78e79fc3b/web)

 

 

---

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

• Chen, Hao; Laine, Kim; Rindal, Peter $2018-05-16$. Fast Private Set Intersection from Homomorphic Encryption. Association for Computing Machinery. ISBN 9781450349468.