Private Set Intersection
왜 중요한가 회사들은 공동 혜택이나 광고 효과를 재려고 어떤 고객을 공유하는지 알고 싶어 하는 일이 잦아요. 쉬운 방법은 고객 목록을 주고받는 건데, 그러면 여러분의 이메일이 다른 회사의 데이터베이스에 들어가요. Private Set Intersection은 어느 쪽도 목록을 넘기지 않고 겹치는 부분을 찾게 해 줘요. 어떻게 작동하는지 알면 진짜 프라이버시와 "해시된 이메일만 공유했어요"를 구별할 수 있어요.
교육용 암호이지 안전하지 않아요: 이 모듈 실습의 숫자는 읽을 수 있을 만큼 작고 무작위성은 채점을 되풀이할 수 있도록 시드가 고정돼 있어요. 실제 시스템은 검증된 라이브러리와 훨씬 큰 숫자를 써요. 교육용 코드를 제품에 절대 복사하지 마세요.
문제
가게와 앱이 각각 고객 이메일 목록을 가져요. 두 목록 모두에 있는 이메일을 원하고, 그 밖엔 아무것도 원하지 않아요: 가게는 앱의 다른 사용자를 알면 안 되고, 앱은 가게의 다른 고객을 알면 안 돼요.
집합 교집합: 두 목록이 공통으로 가진 항목. Private Set Intersection(PSI): 두 당사자가 목록에 대해 다른 건 아무것도 드러내지 않고 그걸 계산하는 방법.
"그냥 해시하라"가 실패하는 이유
해시: 글을 고정 길이로 뒤섞은 것으로 바꾸는 함수(SHA-256이 흔한 것이에요). 같은 입력은 언제나 같은 출력을 주고, 직접 거꾸로 돌릴 수는 없어요.
"해시된 이메일을 주고받으니 아무도 진짜를 못 본다"는 안전하게 들려요. 하지만 이메일은 짐작할 수 있어요. 그럴듯한 이메일 목록을 가진 누구든 짐작마다 해시하고 맞는 걸 찾을 수 있어요. 큰 열쇠 꾸러미의 모든 열쇠를 시도해 보는 것처럼요. 여러분의 naive_reverse 함수가 연습 세계의 합성 이메일 200개로 바로 그걸 할 거예요. 해싱은 입력을 짐작할 수 없을 때만 데이터를 숨기고, 이메일, 전화번호, 이름은 짐작할 수 있어요.
자물쇠 둘 요령
수학 레슨에서 기억하세요: 비밀 a를 걸고, 그다음 비밀 b를 걸면 b 그다음 a와 같아요. 각 이메일을 상자로 그려 보세요. Alice는 자기 상자마다 자기 자물쇠를 걸어 Bob에게 보내요. Bob은 자기 자물쇠를 더해 돌려보내요. Bob도 자기 상자를 잠가 Alice에게 보내고, Alice가 자기 자물쇠를 더해요. 이제 모든 상자에 자물쇠가 둘 있고, 안에 같은 이메일이 든 두 상자는 어느 자물쇠를 먼저 걸었든 똑같아 보여요.
숫자로는, watched.leg7a_privacy의 연습 군(P, hash_to_group, random_secret)으로:
- Alice가
blind(alice_items, a)를 보내요: 각 항목을 군으로 해시한 다음a로 거듭제곱한 것. - Bob이 그것들을
b로 거듭제곱하고(reblind) 같은 순서로 돌려보내요. - Bob이
blind(bob_items, b)를 보내요. - Alice가 Bob의 값을
a로 거듭제곱해요. 자물쇠를 두 번 건 그녀의 값 중 Bob의 이중 잠금 집합에 나타나는 건 공유 항목이에요. 순서를 지켰으니, 각각이 그녀의 어느 항목인지 알아요.
해싱이 실패한 곳에서 이건 왜 안전할까요? 짐작을 시험하려면 두 비밀이 모두 필요하고, 각자 자기 것을 지녀요. Bob은 Alice의 비밀이 걸린 그녀의 값만 보고, 그건 무작위 숫자처럼 보여요.
Diffie-Hellman PSI: 이 프로토콜의 이름으로, 빌려 온 1976년 키 교환 생각(두 당사자가 비밀 지수를 합치기)에서 왔어요. 실제 버전은 타원 곡선(같은 "순서는 상관없다" 성질이 있고 숫자가 훨씬 짧은 다른 종류의 군)과 신중한 해싱을 써요.
답 자체가 공개예요
완벽한 PSI도 Alice에게 특정한 사람이 Bob의 고객이라는 걸 알려 줘요. Bob이 병원이나 부채 상담사라면 그건 민감해요. 회사에 흔히 필요한 건 공유 고객이 몇 명인지뿐이에요. PSI 카디널리티에서는 Bob이 2단계에서 답을 섞어서, Alice는 맞는 걸 셀 수 있지만 그게 그녀의 어느 항목인지는 알 수 없어요. 질문에 답하는 가장 적은 것을 요청하세요.
다른 언어로
BigInt로 하는 JavaScript의 가리기 단계(수학 레슨의 것 같은 powMod 도우미 사용):
const blind = (items, secret) => items.map(x => powMod(hashToGroup(x), secret, P));
const reblind = (values, secret) => values.map(v => powMod(v, secret, P));그리고 math/big을 쓴 Go로:
func reblind(values []*big.Int, secret, p *big.Int) []*big.Int {
out := make([]*big.Int, len(values))
for i, v := range values {
out[i] = new(big.Int).Exp(v, secret, p)
}
return out
}실제 제품에는 직접 쓰지 말고 감사받은 PSI 라이브러리를 쓰세요.
요약
- 해시된 이메일은 짐작 목록으로 쉽게 되돌릴 수 있으니, "해시만 공유했다"는 프라이버시가 아니에요.
- Diffie-Hellman PSI는 순서가 상관없는 두 비밀로 모든 항목을 이중으로 잠가서, 어느 목록도 드러나지 않고 맞는 게 나타나요.
- 순서를 지키면 어떤 항목이 맞는지 드러나고, 섞으면(PSI 카디널리티) 몇 개인지만 드러나요.
- 교집합 자체가 개인 데이터이니, 질문에 답하는 가장 적은 것을 요청하세요.
함수 다섯을 쓰세요. naive_reverse(hashes, candidates)는 SHA-256 16진수 다이제스트(hashlib.sha256(c.encode()).hexdigest())가 hashes에 있는 후보의 정렬된 리스트를 반환해요. blind(items, secret)는 [pow(hash_to_group(x), secret, P) for x in items]를 반환해요. reblind(values, secret)는 순서를 지키며 각 값을 모듈로 P로 secret 제곱해요. psi(alice_items, bob_items, a_secret, b_secret)는 blind와 reblind로 레슨의 네 단계를 따르고, Bob도 가진 Alice 항목의 정렬된 리스트를 반환해요. psi_cardinality(alice_items, bob_items, a_secret, b_secret, rng)는 같은 일을 하되 rng.shuffle로 Bob의 답을 섞고 공유 항목의 수만 반환해요.
이 연습은 곧 열려요
앞의 레슨을 마치면 이 레슨이 열려요. 강좌 전체가 무료이고 계정도 필요 없으며, 이 레슨은 지금 바로 읽을 수 있어요.
이 브라우저가 learn.floati.life의 쿠키를 막고 있어서, 여기서 마친 레슨들이 순서대로 열리지 않아요. 이 사이트의 쿠키를 허용하고 새로고침하세요.