비공개 정보 검색
TL;DR
- 비공개 정보 검색, 즉 PIR은 서버가 어떤 항목이 요청되었는지 알지 못한 채 기기가 서버 데이터베이스에서 하나의 항목을 가져올 수 있게 해줍니다
- Zcash에는 이것이 필요합니다. 프라이버시 지갑은 어떤 거래가 자기 것인지 서버에 물어보는 순간 정체가 드러나기 때문입니다
- 현재 지갑은 필요한 것보다 훨씬 더 많은 데이터를 다운로드하고 스캔하며, 이것이 동기화가 느린 주된 이유 중 하나입니다
- PIR을 사용하면 지갑이 자기 데이터만 비공개로 가져올 수 있어, 프라이버시를 유지하면서 그 병목을 제거할 수 있습니다
- 이것은 Zcash에서 활발히 연구 중인 분야로, 이론적으로는 매우 강력하며 실제 지갑에 적용 가능하도록 실용화가 진행되고 있습니다
이 문서는 누구를 위한 것인가
- 프라이버시 지갑이 어떤 코인이 자기 것인지 어떻게 유출 없이 찾아내는지 궁금했던 모든 사람
- Zcash 확장성 작업과 함께 PIR이 언급되는 것을 계속 보게 되는 입문자
- 먼저 개념을 이해하고 그다음에 그 아래의 암호학을 알고 싶은 독자
PIR이 Zcash에서 해결하는 문제
Zcash는 거래의 수신자가 누구인지 숨깁니다. 그런데 그 프라이버시는 난처한 질문을 만들어냅니다. 네트워크가 어떤 거래가 당신의 것인지 볼 수 없다면, 당신의 지갑은 그것들을 어떻게 찾아낼까요?
오늘날의 답은 단순합니다. 지갑은 어떤 거래가 내 것인지 서버에 물어볼 수 없습니다. 그런 질문 자체가 Zcash가 숨기려는 것을 정확히 드러내기 때문입니다. 그래서 대신 지갑은 많은 양의 데이터를 다운로드한 뒤, 각 항목을 로컬에서 검사해 무엇이 자기 것인지 판별합니다. 이 방식은 작동하고 프라이버시도 지켜주지만, 느리고 무겁습니다. 이런 스캐닝은 지갑 동기화가 답답하게 느껴지는 주된 이유 중 하나입니다.
이상적인 방식은 지갑이 서버에 정확히 자기 데이터만 요청하고, 서버는 무엇이 요청되었는지 전혀 모른 채 그것을 돌려주는 것입니다. 바로 그것이 비공개 정보 검색이 제공하는 기능입니다.
PIR이란 무엇인가
비공개 정보 검색은 클라이언트가 서버 데이터베이스에서 하나의 항목을 읽으면서도, 서버에는 어떤 항목을 읽었는지 드러내지 않는 암호학적 방법입니다.
원하는 책을 정확히 받아 가지만, 사서는 어떤 책을 건넸는지 전혀 모르는 도서관을 상상해 보세요. 당신은 원하는 항목을 받고, 당신의 관심사는 비공개로 남습니다. PIR은 이 아이디어를 수학적으로 구현해 어떤 데이터베이스에든 적용한 것입니다.
이 개념은 수십 년 동안 암호학에서 연구되어 왔습니다. 1995년에 Chor, Goldreich, Kushilevitz, Sudan이 처음 제안했으며, 이들은 다중 서버 접근법을 설명했습니다. 그리고 최초의 단일 서버 버전은 1997년에 Kushilevitz와 Ostrovsky가 뒤이어 발표했습니다. 이것은 Zcash가 발명한 것이 아니라, Zcash가 이제 현실적이고 까다로운 문제에 적용하고 있는 이미 확립된 분야입니다.
첫 단계에서 보는 PIR의 작동 방식
PIR을 구축하는 방법은 크게 두 가지이며, 그 차이는 중요합니다.
첫 번째는 여러 서버를 사용하는 방식입니다. 클라이언트는 여러 서버 각각에 질의의 일부를 보내고, 그 응답을 로컬에서 결합합니다. 어느 하나의 서버도 요청된 항목이 무엇인지 알 수 있을 만큼 충분한 정보를 보지 못합니다. 이 방식은 효율적이지만, 서버들끼리 서로 공모하지 않는다는 전제가 필요하며, 현실에서는 이를 보장하기 어렵습니다.
두 번째는 여러 참여자 대신 정교한 암호학을 사용하는 단일 서버 방식입니다. 여기서 클라이언트는 동형암호라는 특별한 도구에 의존하며, 여러 개의 비공모 서버가 필요하지 않기 때문에 실제 배포에 가장 유용한 방향이기도 합니다.
메커니즘: 동형암호
동형암호는 데이터가 암호화된 상태를 유지한 채 서버가 그 데이터 위에서 계산할 수 있게 해주는 암호 방식입니다. 서버는 실제 값을 전혀 보지 않고도 올바른 암호화된 답을 만들어냅니다.
이 방식으로 구축된 단일 서버 PIR의 핵심 아이디어는 이렇습니다. 클라이언트가 목록에서 3번 항목을 원한다고 합시다. 그러면 사실상 3번 위치에는 암호화된 yes, 나머지 모든 위치에는 암호화된 no가 들어 있는 질의를 만듭니다. 서버가 보기에는 이 질의가 그저 의미 없는 잡음일 뿐이라, 어느 위치에 yes가 들어 있는지 알 수 없습니다.
그다음 서버는 동형암호의 특수한 성질을 이용해 데이터베이스와 이 암호화된 질의를 결합합니다. 즉, 저장된 각 항목에 대응하는 암호화된 yes 또는 no를 곱하고, 그 결과를 모두 더합니다. 그러면 최종적으로 클라이언트가 원한 항목만 정확히 담긴 하나의 암호화된 패키지가 나오며, 어느 항목이 선택되었는지는 전혀 드러나지 않습니다. 클라이언트는 그 패키지를 복호화해 원하는 항목을 읽습니다. 서버는 질문이 무엇인지 전혀 모른 채 그 질문에 답한 셈입니다.
대칭 PIR이라고 불리는 더 강한 버전은 두 번째 보장도 추가합니다. 즉, 클라이언트는 자신이 요청한 항목만 알 수 있고, 데이터베이스의 다른 어떤 항목에 대해서도 아무것도 알 수 없습니다. 이는 클라이언트뿐 아니라 데이터베이스 자체도 보호합니다.
기술 독자를 위한 좀 더 자세한 설명
현대의 단일 서버 방식은 격자 기반 암호학 위에 구축되며, 가장 흔한 가정은 learning with errors입니다. 클라이언트의 질의는 암호문 벡터로 구성되며, 목표 인덱스에는 1, 그 외의 위치에는 0이 암호화됩니다. 이 암호화는 가법 동형성을 가지므로, 서버는 복호화 없이 암호문들을 더하고 이를 평문 데이터베이스 항목과 곱할 수 있습니다.
서버는 데이터베이스를 행렬로 다루고, 암호화된 선택 벡터를 적용한 뒤, 원하는 행으로 복호화되는 하나의 암호문을 반환합니다. 질의는 무작위 잡음과 구별할 수 없기 때문에, 서버는 인덱스에 대한 어떤 정보도 얻지 못합니다.
역사적으로 늘 걸림돌이 된 것은 비용입니다. 가장 단순한 방식에서는 서버가 질의마다 데이터베이스의 모든 항목을 건드려야 하므로 계산 비용이 큽니다. 또한 암호문 크기도 커서 대역폭 비용도 큽니다. 최근 연구는 이를 사전 처리로 해결하려고 합니다. SimplePIR나 FrodoPIR 같은 방식은 서버가 데이터베이스를 미리 준비하고 각 클라이언트에 작은 힌트를 제공할 수 있게 하여, 작업의 상당 부분을 오프라인 단계로 밀어 넣고 실제 질의는 빠르게 처리되도록 만듭니다. 또 하나의 유용한 부수 효과는, 격자 기반 구성은 양자 공격에도 저항성이 있는 것으로 여겨진다는 점이며, 이는 Zcash가 전반적으로 포스트 양자 프라이버시로 나아가는 방향과도 맞아떨어집니다.
Zcash에서의 PIR
PIR은 Zcash를 프라이버시를 유지하면서도 대규모로 빠르게 만들기 위한 노력의 일부입니다.
앞서 설명한 지갑 스캐닝 병목이 바로 목표입니다. Valar Group의 작업은 지갑이 서버에 어떤 항목을 요청했는지 서버가 알지 못한 채 자기 데이터를 가져올 수 있도록 비공개 정보 검색 기법을 개발하고 있습니다. 한 가지 구체적인 적용 사례는 nullifier를 비공개로 확인하는 것입니다. nullifier는 노트가 사용될 때 공개되는 고유한 표시자로, 동일한 자금이 두 번 사용되는 것을 막습니다. 지갑은 주어진 nullifier가 이미 등장했는지, 다시 말해 해당 노트가 아직 미사용 상태인지 자주 확인해야 하는데, 오늘날 이 작업을 서버를 통해 수행하면 어떤 노트에 대해 묻고 있는지가 유출될 수 있습니다. 비공개 정보 검색은 지갑이 어떤 nullifier에 관심이 있는지 드러내지 않고도 이 질문을 할 수 있게 해줍니다. 이는 Project Tachyon과 새로운 노드 소프트웨어를 포함한 다른 확장성 작업과 함께 진행되며, 오늘날 프라이버시 지갑을 가로막는 성능 한계를 제거하는 것을 목표로 합니다.
현재 단계에 대해서는 솔직할 필요가 있습니다. 이것은 완성되어 배포된 기능이 아니라, 활발한 연구와 엔지니어링 작업입니다. 개념은 잘 확립되어 있고 방향도 정해져 있지만, PIR을 일반적인 기기에서 일상적으로 사용하는 지갑에 충분히 효율적으로 만드는 일이 바로 지금 해결 중인 어려운 부분입니다.
흔한 오해
- PIR은 당신이 어떤 항목을 요청했는지는 숨기지만, 반드시 당신이 서버에 접속했다는 사실 자체까지 숨기지는 않습니다. 네트워크 수준 메타데이터는 별개의 문제입니다
- PIR은 Zcash만의 고유한 기술이 아닙니다. 이것은 Zcash가 지갑 프라이버시에 적용하고 있는 범용 암호학 도구입니다
- PIR로 더 빠른 동기화를 구현하는 것은 진행 중인 목표이지, 이미 지갑에 존재하는 기능이 아닙니다
- 모든 것을 다운로드해 로컬에서 스캔하는 현재 방식은 프라이버시는 지켜주지만 느립니다. PIR은 그 프라이버시를 유지하면서 느림을 제거하는 것을 목표로 합니다
관련 페이지
