🧬 biology

Quantum Private Intersection Based on Single Qubits

본 논문은 단일 큐비트 상태와 연산을 활용하여 준정직한 제3자(semi-honest third party) 하에서 작동하는 자원 효율적인 2자 간 양자 사적 교집합 프로토콜을 제안하고 검증하며, 기존 솔루션들과 비교하여 우수한 공정성과 실용적 타당성을 입증한다.

원저자: Cai Zhang, Zhuoxuan Zhan, Zhiwei Sun

게시일 2026-07-09

📖 6 분 읽기🧠 심층 분석

CC BY 4.0

원저자: Cai Zhang, Zhuoxuan Zhan, Zhiwei Sun

원본 논문은 CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ⚕️ 이것은 동료 심사를 거치지 않은 프리프린트의 AI 생성 설명입니다. 의학적 조언이 아닙니다. 이 내용을 바탕으로 건강 관련 결정을 내리지 마세요. 전체 면책 조항 읽기

큰 그림: "비밀 클럽" 문제

**앨리스(Alice)**와 **밥(Bob)**이라는 두 사람이 각각 자신이 좋아하는 취미 목록을 가지고 있다고 상상해 보세요.

앨리스의 목록: {하이킹, 요리, 체스, 가드닝}
밥의 목록: {체스, 수영, 가드닝, 페인팅}

그들은 알고 싶습니다: "우리 둘 다 좋아하는 취미는 무엇인가?" (정답은 체스와 가드닝입니다).

하지만 그들에게는 문제가 있습니다:

서로의 전체 목록을 보여주고 싶지 않습니다 (앨리스는 밥이 자신이 요리를 좋아한다는 것을 알기를 원치 않고, 밥은 앨리스가 수영을 좋아한다는 것을 알기를 원치 않습니다).
인터넷을 통해 서로의 목록을 그냥 보내기에는 서로를 충분히 신뢰할 수 없습니다. 왜냐하면 해커(**이브(Eve)**라고 부릅시다)가 데이터를 훔칠 수도 있기 때문입니다.
또한, 속임수를 쓰거나 몰래 훔쳐볼 수 있는 "중간 관리자"에게 의존하고 싶지도 않습니다.

이것이 바로 프라이빗 셋 인터섹션(Private Set Intersection, PSI) 문제입니다. 이 논문은 완전한 프라이버시와 공정성을 보장하기 위해 양자 물리학(구체적으로는 "큐비트"라고 불리는 단일 광자 입자)을 사용하여 이 문제를 해결하는 새로운 방법을 제안합니다.

등장인물

앨리스 & 밥: 비밀 목록을 가진 두 사람.
찰리(Charlie): "준정직한(Semi-Honest)" 제3자 (심판 같은 역할). 그는 규칙을 엄격히 따르지만, 가능하다면 데이터를 훔쳐보려고 시도할 수도 있습니다. 그는 두 사람이 직접 대화하지 않고도 답을 계산할 수 있도록 돕기 위해 필요합니다.
이브(Eve): 비밀을 훔치려는 도청자.

마법의 도구: "양자 동전"

목록을 종이에 적는 대신, 앨리스와 밥은 **양자 동전(단일 큐비트)**을 사용합니다.

일반 동전은 앞면 또는 뒷면을 가집니다.
"양자 동전"은 앞면, 뒷면, 또는 그 둘의 중첩 상태를 가질 수 있습니다.
양자 물리학의 황금 법칙: 양자 동전이 무엇인지 확인하기 위해 관찰하면, 그 상태를 변화시킵니다. 만약 잘못된 방식으로 관찰하면, 그것은 무작위 노이즈가 되어 버립니다.

이 논문은 이 동전들에 사용하는 두 가지 특별한 "동작"(유니터리 연산자)을 사용합니다:

동작 U1: 동전을 뒤집습니다 (앞면은 뒷면으로, 뒷면은 앞면으로).
동작 U2: 더 복잡한 뒤집기로, 이 동작을 두 번 수행하면 동작 U1을 한 번 수행한 것과 같습니다.

프로토콜 작동 방식 (게임)

게임은 공통 취미를 찾기 위해 두 단계(Phase)로 진행됩니다.

1단계: "누가 가지고 있는가?" 라운드

목표: 적어도 한 명의 목록에 포함된 항목이 무엇인지 알아냅니다 (합집합).

찰리는 무작위 상태(앞면, 뒷면, 또는 회전하는 상태 등)의 양자 동전들을 길게 늘어놓습니다. 그는 스파이를 잡기 위해 줄 사이에 몇 개의 "디코이(decoy, 미끼)" 동전들을 숨겨둡니다.
찰리는 이 줄을 앨리스에게 보냅니다.
앨리스는 스이가 있는지 확인하기 위해 디코이를 체크합니다. 안전하다면, 그녀는 자신의 비밀 목록을 확인합니다.
- 만약 그녀의 목록에 해당 취미가 있다면, 그녀는 해당 특정 동전에 대해 동작 U1(뒤집기)을 수행합니다.
- 만약 없다면, 동전을 그대로 둡니다.
앨리스는 동전의 순서를 섞습니다 (찰리가 어떤 동전이 어떤 취미에 해당하는지 알 수 없도록 합니다). 그리고 밥에게 보냅니다.
밥은 디코이를 체크합니다. 안전하다면, 그는 자신의 목록을 확인합니다.
- 만약 그에게 해당 취미가 있다면, 그는 해당 동전에 대해 동작 U1(뒤집기)을 수행합니다.
- 만약 없다면, 동전을 그대로 둡니다.
밥은 동전들을 다시 찰리에게 보냅니다.

결과:

둘 다 해당 취미를 가지고 있지 않다면: 동전은 뒤집히지 않았습니다. (상태: 원래 상태)
한 명만 가지고 있다면: 동전이 한 번 뒤집혔습니다. (상태: 뒤집힘)
둘 다 가지고 있다면: 동전이 두 번 뒤집혔습니다. (상태: 다시 원래대로 돌아옴, 두 번 뒤집으면 상쇄되기 때문입니다).

찰리는 동전들을 측정합니다. 그는 이제 어떤 취미가 적어도 한 명의 목록에 있는지(뒤집힌 것들)와 어떤 것이 둘 다 혹은 둘 다 없는지(원래 상태인 것들)를 알 수 있습니다. 그는 후보 목록을 만들지만, 아직 누가 그것을 소유했는지는 모릅け습니다.

2단계: "누가 소유하고 있는가?" 라운드

목표: 후보 목록을 필터링하여 정확한 일치 항목을 찾습니다 (교집합).

찰리는 "후보" 동전들을 가져와 다시 앨리스에게 보냅니다.
앨리스는 자신이 소유한 동전에 대해 다른 동작인 동작 U2를 사용합니다.
밥은 동전들을 전달받아 자신이 소유한 동전에 대해 동작 U2를 사용합니다.
찰리는 동전들을 돌려받아 다시 측정합니다.

마법의 논리:

1단계에서 둘 다 소유하지 않았다면, 2단계에서 아무것도 하지 않습니다. 동전은 그대로 유지됩니다.
1단계에서 둘 다 소유했다면, 2단계에서 둘 다 동작 U2를 수행합니다. 동작 U2를 두 번 하는 것은 수학적으로 동작 U1을 한 번 하는 것과 같습니다. 이 동작은 동전을 뒤집습니다!
찰리는 뒤집힘을 목격합니다. 그는 "이 동전은 2단계에서 뒤집혔다, 즉 앨리스와 밥이 모두 이 동전을 건드렸다"는 것을 알게 됩니다.

최종 답변:
찰리는 앨리스와 밥에게 말합니다: "이 뒤집힌 동전에 해당하는 취미들이 바로 여러분이 공통으로 공유하는 것입니다."

이것이 왜 안전한가? (스파이 증명)

이 논문은 두 가지 유형의 악의적인 행위자에 대해 안전하다고 주장합니다.

1. 외부 스파이 (이브):
이브가 동전을 가로채려 합니다.

함정: 찰리는 "디코이" 동전을 숨겨둡니다. 이브는 어떤 것이 진짜이고 어떤 것이 미끼인지 알 수 없습니다.
실수: 이브가 동전을 읽으려면 어떻게 관찰할지 추측해야 합니다. 만약 추측이 틀리면, 그녀는 동전의 상태를 변화시킵니다.
포착: 앨리스와 밥이 디코이를 확인할 때, 그들은 동전이 변했다는 것을 알게 됩니다. 그들은 이브가 있었다는 것을 알게 되고, 전체 게임을 폐기하고 처음부터 다시 시작합니다. 논문은 충분한 디코이가 있다면 이브가 들키지 않고 빠져나갈 확률은 사실상 제로에 가깝다고 계산합니다.

2. 참여자 중의 부정행위자 (찰리, 앨리스, 또는 밥):

찰리 (심판): 그는 동전을 보지만, 앨리스와 밥이 섞어 놓았기 때문에 순서를 알 수 없습니다. 그는 누가 동전을 뒤집었는지는 알 수 없고, 오직 "뒤집혔다"는 사실만 알 수 있습니다. 그는 전체 목록을 훔칠 수 없습니다.
앨리스 & 밥: 그들은 상대방의 목록을 볼 수 없습니다. 왜냐Net 그들은 찰리가 준비한 원래의 상태를 모르기 때문입니다. 만약 그들이 미리 측정하려고 시도한다면, 그저 무작위 노이즈를 얻게 될 뿐입니다.

이 논문이 특별한 이유는 무엇인가? (효율성 주장)

이전의 양자 솔루션들은 거대하고 복잡한 크레인을 사용하여 집을 짓는 것과 같았습니다 (무거운 얽힘과 복잡한 수학을 사용). 그것들은 만들기 어렵고 비용이 많이 들었습니다.

이 논문은 단일 큐비트 연산(단순한 뒤집기)을 사용하는 것을 제안합니다.

비유: 거대한 크레인 대신, 단순한 손 도구를 사용하는 것입니다.
이점: 이는 더 적은 "자원"(더 적은 입자)을 사용하며, 더 단순한 장비를 필요로 하고, 현재 기술로 훨씬 더 쉽게 구축할 수 있습니다.
공정성: 한 사람만 답을 얻는 기존 방식과 달리, 이 방법은 앨리스와 밥 모두가 최종적인 공통 목록을 동시에 얻을 수 있도록 보장합니다.

"실험실 테스트" (시뮬레이션)

저자들은 이론만 제시한 것이 아니라, IBM의 Qiskit(양자 컴퓨터 시뮬레이터)을 사용하여 이 게임의 가상 버전을 구축했습니다.

그들은 0부터 7까지의 숫자로 작은 예시를 시뮬레이션했습니다.
앨리스는 {1, 3, 5, 7}을 가졌습니다.
밥은 {2, 3, 4, 7}을 가졌습니다.
컴퓨터는 "뒤집기"와 "섞기" 단계를 실행했습니다.
결과: 컴퓨터는 공통 항목인 {3, 7}을 정확하게 식별해 냈으며, 이는 수학적 원리가 실제로 작동함을 입증했습니다.

요약

이 논문은 두 사람이 양자 물리학을 사용하여 자신들의 비밀을 찾는 더 단순하고 공정한 새로운 방법을 제시합니다. 이는 단일 입자에 대한 단순한 "동전 뒤집기"를 사용하며, 스파이를 잡기 위해 "디코이 함정"으로 데이터를 숨기고, 심판조차 속일 수 없도록 보장합니다. 이는 컴퓨터 시뮬레이터에서 테스트되었으며 완벽하게 작동합니다.

기술 요약: 단일 큐비트에 기반한 양자 개인 정보 교집합 (Quantum Private Intersection Based on Single Qubits)

문제 정의
개인 정보 교집합(Private Set Intersection, PSI)은 참여자들이 자신의 비공개 집합에 포함되지 않은 요소들을 드러내지 않으면서도 교집합을 계산할 수 있게 해주는 근본적인 안전한 다자간 계산(SMPC) 프리미티브이다. 기존의 고전적 PSI 프로토콜은 정수 인수분해와 같은 계산 복잡도 가정에 의존하지만, 이는 쇼어(Shor) 및 그로버(Grover) 알고리즘과 같은 양자 알고리즘에 취약하다. 기존의 양자 개인 정보 교집합(QPSI) 솔루션들은 이를 해결하기 위해 양자 역학적 원리를 활용하는 것을 목표로 한다. 그러나 현재의 QPSI 솔루션들은 다입자 얽힘, 복잡한 고차원 양자 게이트를 필요로 하거나, 한 당사자가 결과를 조작하거나 결과를 받지 못하는 공정성 문제를 겪는 등 구현 장벽이 높은 경우가 많다.

방법론
저자들은 앨리스(Alice), 밥(Bob), 그리고 준-정직한 제3자 찰리(Charlie)가 참여하는 2자간 QPSI 프로토콜을 제안한다. 이 프로토콜은 단일 큐비트 상태와 단일 큐비트 유니터리 연산만을 사용하여 작동하도록 설계되었으며, 얽힘이나 고차원 시스템을 필요로 하지 않는다.

핵심 메커니즘은 두 가지 특정 유니터리 연산자에 기반한다:

$U_1 = -iY$ : 계산 기저( $|0\rangle, |1\rangle$ )와 하다마르( $|+\rangle, |-\rangle$ ) 기저 모두에서 스와핑(swapping) 연산으로 작용한다.
$U_2 = \frac{1}{\sqrt{2}}(I - iY)$ : $U_2^2 = U_1$ 이라는 성질을 만족한다.

프로토콜은 두 단계로 진행된다:

단계 I (교집합과 합집합의 합집합 결정):
- 찰리는 무작위 기저( $Z$ 또는 $X$ )로 준비된 $n$ 개의 단일 입자 시퀀스를 준비하고, 도청 탐지를 위한 디코이(decoy) 입자를 삽입한다.
- 앨리스와 밥은 자신의 비공개 집합에 해당하는 요소들(비트 문자열 $m_A$ 및 $m_B$ 로 인코딩됨)에 대해 순차적으로 $U_1$ 을 적용한다. 만약 요소가 자신의 집합에 없다면 항등 연산( $I$ )을 적용한다.
- 참여자들은 전송 전 입자의 순서를 재배열하기 위해 치환(permutation)을 적용하며, 이는 제3자가 특정 인덱스에 연산을 연결하는 것을 방지한다.
- 찰리는 최종 시퀀스를 측정한다. 만약 입자의 상태가 초기 준비 상태에 비해 반전되었다면, 이는 해당 요소가 정확히 하나의 집합( $A \cap \bar{B}$ 또는 $\bar{A} \cap B$ )에 속함을 나타낸다. 만약 상태가 변하지 않았다면, 이는 해당 요소가 두 집합 모두에 있거나( $A \cap B$ ) 둘 다 없는 경우( $\bar{A} \cap \bar{B}$ )를 나타낸다. 이를 통해 집합 $(A \cap B) \cup (A \cup B)$ 를 얻는다.
단계 II (교집합 추출):
- 찰리는 측정한 입자들을 앨리스와 밥에게 다시 보낸다.
- 앨리스와 밥은 이제 자신의 비공개 집합에 해당하는 입자들에 $U_2$ 를 적용한다.
- $U_2^2 = U_1$ 이라는 성질 덕분에, 교집합( $A \cap B$ )에 있는 입자들은 $U_2$ 를 두 번 거치게 되어( $U_1$ 과 동일) 상태가 반전된다. 합집합에는 속하지만 교집합에는 속하지 않는 요소들( $A \cup B$ 이지만 $A \cap B$ 는 아닌 경우)은 $U_2$ 를 한 번 또는 zero 번 적용받아, 프로토콜의 논리적 맥락 내에서 단계 I의 베이스라인 대비 순수 변화가 발생하지 않는다.
- 찰리는 관련 입자들을 다시 측정한다. 그는 새로운 결과와 단계 I의 베이스라인을 비교함으로써, 상태가 반전된 요소, 즉 엄격하게 $A \cap B$ 에 해당하는 요소를 식별한다.

주요 기여

자원 효율성: 본 프로토콜은 단일 큐비트 상태와 단일 큐비트 유니터리 연산( $U_1$ 및 $U_2$ )만을 활용하여, 얽힘(벨 상태)이나 고차원 양자 상태를 요구하는 프로토콜에 비해 기술적 복잡성을 크게 줄였다.
공정성: 서버나 한 명의 클라이언트가 결과를 조작하거나 독점적으로 수령할 수 있는 기존 연구들과 달리, 본 프로토콜은 제3자를 통해 두 참여자가 최종 교집합 결과를 동시에 수령하도록 보장한다.
보안성: 프로토콜은 도청 탐지를 위한 디코이 상태와, 제3자가 중간 결과로부터 특정 인덱스를 추론하는 것을 방지하기 위한 치환 전략을 포함한다.
실험적 검증: 저자들은 IBM Qiskit 시뮬레이터 상에서 프로토콜을 구현하여, 상태 변환 및 측정 결과의 이론적 정확성을 확인하였다.

결과

정확성: 이론적 분석과 시뮬레이션 결과는 프로토콜이 $A \cap B$ 를 올바르게 계산함을 확인시켜 준다. 시뮬레이션에서 유니버설 집합 $\{0, \dots, 7\}$ , 앨리스의 집합 $\{1, 3, 5, 7\}$ , 밥의 집합 $\{2, 3, 4, 7\}$ 을 사용했을 때, 프로토콜은 교집합 $\{3, 7\}$ 을 성공적으로 식별하였다.
보안 분석: 논문은 다음과 같은 공격에 대한 저항성을 입증한다:
- 외부 공격: 디코이 상태 메커니즘을 통해 가로채기-재전송(Intercept-resend) 및 얽힘-측정(Entanglement-measurement) 공격을 높은 확률로 탐지한다. 트로이 목마 공격은 광학 필터를 통해 완화된다.
- 내부 공격: 준-정직한 제3자(찰리)는 치환 단계와 $U_1$ 연산의 특성(누가 적용하든 상태를 반전시킴)으로 인해 어떤 참여자가 특정 요소를 교집합에 기여했는지 알 수 없다. 부정직한 참여자(앨리 혹은 밥)는 초기 준비 기저와 상대방이 적용한 치환에 대한 지식이 없기 때문에 상대방의 집합을 추론할 수 없다.
비교 분석: 저자들은 자신들의 프로토콜을 기존 QPSI 프로토콜들(참조 [14], [17], [18], [20], [24], [25], [26])과 비교한다. 그들은 자신들의 프로토콜이 벨 상태( $6n + 5d$ )나 고차원 상태를 사용하는 프로토콜에 비해 더 적은 양자 자원( $n + 6d$ 입자)을 필요로 하면서도 공정성과 보안성을 유지한다고 주장한다.

의의 및 주장
본 논문은 제안된 프로토콜이 기존 QPSI 방식에 대한 실용적이고 실행 가능한 대안을 제공한다고 주장한다. 단일 큐비트 연산과 상태에만 의존함으로써, 이 프로토콜은 현재의 양자 기술 역량과 더 잘 부합하며 구현 장벽을 낮춘다. 저자들은 자신들의 접근 방식이 보안, 공정성, 그리고 양자 자원 효율성 사이의 균형을 성공적으로 맞추었으며, 공정성이 결여되었거나 구현하기 어려운 복잡한 양자 자원을 요구했던 이전 프로토콜들의 한계를 해결했다고 단언한다. 이 연구는 현실적인 시나리오에서 보안성이 강화된 양자 내성 개인 정보 교집합을 실현하기 위한 단계로 제시된다.