💻 computer science

Gyokuro: Source-assisted Private Membership Testing using Trusted Execution Environments

이 논문은 신뢰 실행 환경 (TEE) 을 활용하여 데이터베이스 크기에 무관한 통신 및 계산 비용으로 강력한 프라이버시 보장과 높은 효율성을 실현하는 새로운 소스 지원 개인 멤버십 테스트 프로토콜 'Gyokuro'를 제안합니다.

원저자: Yoshimichi Nakatsuka, Nicolas Dutly, Kari Kostiainen, Srdjan Capkun

게시일 2026-03-25

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Yoshimichi Nakatsuka, Nicolas Dutly, Kari Kostiainen, Srdjan Capkun

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

🌱 '교요쿠루 (Gyokuro)': 당신의 비밀을 지키며 "내 물건이 여기에 있나요?"를 확인하는 새로운 방법

이 논문은 **"내 물건이 정말로 그 곳에 저장되었는지 확인하면서도, 내 물건이 무엇인지는 절대 들키지 않게 하는 방법"**을 소개합니다. 이를 위해 연구자들은 '신뢰할 수 있는 블랙박스 (TEE)'와 '감시자 (Monitor)'를 활용하는 독특한 시스템을 만들었습니다.

이 복잡한 기술을 일상적인 비유로 쉽게 설명해 드릴게요.

1. 문제 상황: "내 약이 진짜로 기록되었나요?" (하지만 약 이름은 말하고 싶지 않아요)

가상의 상황을 상상해 보세요.
당신은 병원에서 비싼 약을 샀습니다. 약 포장지에는 QR 코드가 붙어 있는데, 이 QR 코드는 "이 약이 합법적인 공장에서 왔고, 공인된 기록장에 저장되었다"는 증서입니다.

하지만 당신은 두 가지 걱정이 있습니다.

기록장 (서버) 이 거짓말을 하지 않았을까? (약이 기록장에 진짜로 저장되었는지 확인하고 싶어요.)
기록장 주인이 내 약 이름을 훔쳐보지 않았을까? (약 이름은 비밀인데, "내 약이 저장되었는지 확인해 주세요"라고 말하면 약 이름을 알려주는 꼴이 되죠.)

기존의 방법들은 이 두 가지를 동시에 해결하기 어려웠습니다. "내 약이 저장되었나요?"라고 물어보면, 서버는 "어떤 약을 물어보는 거죠?"라고 알 수 있게 됩니다.

2. 해결책: '교요쿠루 (Gyokuro)' 시스템의 등장

연구자들은 이 문제를 해결하기 위해 세 명의 등장인물이 협력하는 방식을 고안했습니다.

약국 (데이터 소스): 약을 만들고 QR 코드 (증명서) 를 줍니다.
블랙박스 (TEE, 신뢰할 수 있는 컴퓨터): 서버 안에 있는 '신뢰할 수 있는 금고' 같은 곳입니다. 외부에서는 안을 볼 수 없지만, 정해진 규칙만은 꼭 지키는 기계입니다.
감시관 (Monitor): 기록장을 매일 복사해서 감시하는 독립적인 기관입니다.

🎭 비유: "시간의 흐름"을 이용한 마법

기존 방식은 서버에게 "내 물건이 있어요?"라고 직접 물어보느라 문제가 생겼다면, 교요쿠루는 **"시간이 흘렀으니, 내 물건이 들어갔을 거야"**라고 추론합니다.

작동 원리 (일상 비유):

약국에서 QR 코드 받기 (Upload 단계):
- 약국 (데이터 소스) 이 약을 블랙박스 (TEE) 에 넣습니다.
- 블랙박스는 약을 받으면 **"이 약을 받았습니다. 지금 시계는 10 시 00 분입니다"**라고 적힌 **수령증 (POR)**을 줍니다.
- 블랙박스는 약을 모아서 기록장에 넣습니다. 기록장이 꽉 차면 시계를 10 시 01 분으로 바꿉니다.
내가 확인하기 (Testing 단계):
- 며칠 뒤, 당신이 약을 샀습니다. QR 코드 (수령증) 가 있습니다.
- 당신은 기록장 주인에게 **"지금 블랙박스 시계는 몇 시인가요?"**라고 묻습니다. (약 이름은 말하지 않음!)
- 블랙박스는 **"지금 시계는 10 시 30 분입니다"**라고 답합니다.
- 추론: "어? 내가 받은 수령증은 10 시 00 분인데, 지금 시계는 10 시 30 분이네? 시간이 30 분이나 흘렀으니, 내 약은 분명히 기록장에 들어갔을 거야!"라고 결론 내립니다.
감시관의 확인 (일관성 확인):
- 만약 기록장 주인이 "내 약은 들어갔는데, 다른 약은 빼먹었어"라고 거짓말을 한다면 어떨까요?
- 이때 감시관이 나옵니다. 감시관은 기록장을 복사해서 "내 시계도 10 시 30 분이고, 기록 내용도 똑같아"라고 확인해 줍니다.
- 블랙박스와 감시관의 시계가 일치하면, **"약이 진짜로 안전하게 저장되었다"**는 것을 100% 확신할 수 있습니다.

3. 왜 이 방법이 특별한가요?

비밀 유지 (Privacy): 당신은 블랙박스에게 "내 약 이름"을 말한 적이 없습니다. 오직 "시간이 흘렀는지"만 확인했을 뿐입니다. 서버 주인은 당신이 어떤 약을 확인하려는지 전혀 알 수 없습니다.
빠른 속도 (Speed): 서버는 매번 복잡한 계산을 할 필요가 없습니다. 그냥 "지금 시계는 몇 시야?"라고 물어보면 되니까, 0.007 초 (7 밀리초) 만에 답을 줍니다. (초당 1,400 건 이상 처리 가능!)
확장성 (Scalability): 기록장에 약이 10 개든, 100 억 개든 확인하는 시간은 똑같습니다. 기록장이 커져도 속도가 느려지지 않습니다.

4. 실생활 적용 예시

이 기술은 다음과 같은 곳에 쓰일 수 있습니다.

인터넷 보안 (SSL 인증서): 웹사이트를 방문할 때, "이 사이트의 인증서가 진짜로 기록장에 있나?"를 확인하면서도, 내가 어떤 사이트를 방문하는지 (검색 기록) 는 숨길 수 있습니다.
의약품 안전: 약을 살 때, "이 약이 합법적인 경로로 왔나?"를 확인하되, 내가 어떤 병으로 어떤 약을 사는지 (개인 건강 정보) 는 공개하지 않아도 됩니다.
가짜 뉴스 방지: 사진이나 영상이 "진짜로 기록장에 저장되어 검증된 것"인지 확인하되, 내가 어떤 사진을 의심하는지 공개하지 않아도 됩니다.

📝 요약

**교요쿠루 (Gyokuro)**는 **"내 물건이 저장되었는지 확인하기 위해 내 물건의 정체를 밝힐 필요는 없다"**는 아이디어를 실현한 시스템입니다.

신뢰할 수 있는 **블랙박스 (TEE)**가 시간을 재고, 감시관이 기록을 대조함으로써, 우리는 비밀을 지키면서도 데이터의 진위를 확실하게 확인할 수 있게 되었습니다. 마치 **"내 편지함이 비어있는지 확인하기 위해, 편지 내용을 읽지 않고도 우편배달부의 출근 시간을 확인하는 것"**과 같은 원리입니다.

이 기술은 앞으로 우리가 디지털 세상에서 프라이버시를 지키며 안전하게 정보를 검증하는 데 큰 역할을 할 것으로 기대됩니다.

1. 연구 배경 및 문제 정의 (Problem Statement)

Private Membership Testing (PMT, 개인 구성원성 테스트) 은 클라이언트가 특정 데이터 항목이 데이터베이스에 포함되어 있는지 확인하되, 데이터베이스 운영자나 외부 당사자에게 확인하려는 항목 자체를 노출하지 않는 프로토콜입니다.

기존 기술의 한계: 기존 PMT 는 PIR(개인 정보 검색), PSI(개인 집합 교차), ORAM(무관심 RAM), 동형 암호화 등 복잡한 암호학적 원리를 사용하거나, 모든 레코드를 스캔하는 방식을 취합니다. 이는 통신 오버헤드가 크고, 계산 비용이 높으며, 대규모 데이터베이스에서 확장성 (Scalability) 을 보장하기 어렵다는 문제가 있습니다.
Source-assisted PMT (SPMT) 의 필요성: 데이터 소스 (Data Source) 가 클라이언트에게 데이터 항목과 함께 '소스 지원 정보 (Source-assisted information, 예: QR 코드, 디지털 서명 등)'를 제공하는 시나리오를 가정합니다. 이는 인증서 투명성 (CT) 로깅, 공급망 감사, 데이터 출처 검증 등 다양한 분야에서 유용합니다.
핵심 과제: 기존 SPMT 방식은 서버가 포함 증명 (Proof of Inclusion) 을 즉시 생성해야 하거나, 클라이언트가 데이터베이스 전체를 다운로드해야 하는 등 비효율적이었습니다. 또한, 서버가 악의적으로 데이터를 삭제하거나 지연시킬 경우 이를 검증하기 어렵습니다.

2. 제안된 방법론: Gyokuro

이 논문은 신뢰 실행 환경 (Trusted Execution Environments, TEE) 을 활용하여 기존 접근법과 다른 새로운 방식을 제안합니다. 핵심 아이디어는 "데이터가 존재함을 증명하는 것" 대신 "서버가 데이터를 처리하고 저장하는 데 충분한 진척 (Progress) 을 이루었음을 증명하는 것" 으로 전환하는 것입니다.

2.1 시스템 구성 요소

데이터 소스 (Data Source): 데이터를 생성하고 TEE 에 제출합니다.
서버/TEE: 데이터를 수신하고 외부 데이터베이스에 저장하는 역할을 수행합니다.
모니터 (Monitor): 데이터베이스의 일관성을 확인하는 제 3 자 (정직한 호기심, Honest-but-curious).
클라이언트: 데이터 소스로부터 정보를 받아 TEE 와 상호작용하여 구성원성을 검증합니다.

2.2 핵심 프로토콜

Gyokuro 는 두 가지 주요 프로토콜로 구성됩니다.

업로드 프로토콜 (Upload Protocol):
- 데이터 소스가 TEE 에 데이터를 제출하면, TEE 는 데이터를 버퍼에 저장하고 수신 증명 (Proof of Reception, POR) 을 생성하여 반환합니다.
- POR 는 데이터와 TEE 내부의 단조 증가 카운터 (Monotonic Counter) 값을 서명한 것입니다.
- 버퍼가 가득 차면 TEE 는 데이터를 외부 데이터베이스에 저장하고, 해시 체인 (Hash Chain) 또는 어큐뮬레이터를 업데이트한 후 카운터를 증가시킵니다.
테스트 프로토콜 (Testing Protocol):
- 클라이언트는 관심 있는 데이터 항목과 해당 POR 를 TEE 에게 요청합니다.
- TEE 는 현재 카운터 값을 서명한 처리 증명 (Proof of Processing, POP) 을 반환합니다.
- 검증 로직: 클라이언트는 POR 의 카운터 값 ( $cnt_{POR}$ ) 이 POP 의 카운터 값 ( $cnt_{POP}$ ) 보다 작으면, 해당 데이터가 TEE 에 의해 처리되어 데이터베이스에 저장되었음을 추론합니다.
- 일관성 확인: 클라이언트는 TEE 와 모니터로부터 어큐뮬레이터 값을 받아 비교합니다. 두 값이 일치하면 데이터베이스에서 데이터가 삭제되지 않았음을 보장받습니다.

2.3 기술적 특징

비상호적 (Non-interactive) 성향: 클라이언트는 데이터베이스 운영자에게 자신이 어떤 데이터를 찾고 있는지 알리지 않습니다. TEE 에도 데이터 항목 자체를 보내지 않고, 오직 카운터 값 비교만 수행합니다.
시간 기반 진척 검증: TEE 가 데이터를 처리하는 데 걸리는 시간을 보장할 수는 없지만 (악성 서버가 지연시킬 수 있음), TEE 가 데이터를 처리하는 '진척도'를 카운터로 추적하여 검증합니다.
사이드 채널 공격 방어: 클라이언트의 관심 데이터가 TEE 내부로 전달되지 않으므로, TEE 내부의 메모리 접근 패턴이나 사이드 채널 공격으로부터 클라이언트 프라이버시가 보호됩니다.

3. 주요 기여 (Key Contributions)

문제 식별: 인증서 투명성 (CT) 및 공급망 감사 등 실제 응용 분야에서 중요한 SPMT 문제가 연구되지 않았음을 규명했습니다.
새로운 솔루션 (Gyokuro): 클라이언트가 제 3 자나 데이터베이스 운영자에게 개인 정보를 노출하지 않고도, TEE 의 실행 무결성과 모니터의 감시를 통해 데이터 존재 여부를 검증하는 새로운 TEE 기반 SPMT 방식을 제안했습니다.
성능 최적화: 데이터베이스 크기에 의존하지 않는 상수 시간 (Constant-time) 의 통신 및 계산 복잡도를 달성했습니다.
보안 분석: 클라이언트 프라이버시와 구성원성 테스트의 정확성을 수학적으로 증명했습니다.

4. 성능 평가 결과 (Performance Results)

연구진은 Azure 클라우드 환경 (AMD-SEV 기반 TEE) 에서 프로토타입을 구현하고 평가했습니다.

지연 시간 (Latency):
- 데이터 제출 (Upload): 약 6.5 ms
- 구성원성 테스트 (Membership Testing): 약 7 ms
- 이는 기존 암호학적 방식에 비해 매우 낮은 지연 시간입니다.
처리량 (Throughput):
- 데이터 제출: 코어당 초당 1,021 건 (1021 requests/sec/core)
- 테스트: 코어당 초당 1,432 건 (1432 requests/sec/core)
- 이는 대규모 시스템 (예: 수백만 개의 인증서를 저장하는 CT 로그) 을 처리하기에 충분한 성능입니다.
확장성: 통신 및 계산 비용이 데이터베이스 크기와 무관하므로, 데이터베이스가 수억 개로 커져도 성능 저하가 없습니다.

5. 의의 및 의의 (Significance)

프라이버시와 효율성의 균형: 기존 TEE 기반 PMT 는 ORAM 등을 사용하여 성능 저하를 겪거나, TEE 내부에 평문 쿼리가 존재해 사이드 채널 공격에 취약했습니다. Gyokuro 는 TEE 내부에 클라이언트의 관심 데이터를 노출하지 않으면서도, ORAM 없이도 높은 성능을 달성했습니다.
실용성: 7ms 미만의 지연 시간과 높은 처리량은 실시간 웹 브라우저 (CT 로그 검증) 나 모바일 애플리케이션 (공급망 추적) 에 직접 적용 가능한 수준입니다.
새로운 패러다임: "데이터의 존재 증명"에서 "처리 과정의 진척 증명"으로의 패러다임 전환은 신뢰할 수 있는 하드웨어 (TEE) 와 외부 감시자 (Monitor) 를 결합한 새로운 보안 설계 패턴을 제시합니다.

6. 결론 및 한계

Gyokuro 는 TEE 의 실행 무결성을 활용하여 효율적이고 확장 가능하며 프라이버시를 보호하는 SPMT 를 실현했습니다. 다만, 이 솔루션은 TEE 의 신뢰성에 의존하므로, 미래에 TEE 의 무결성이 침해될 경우 보안이 약화될 수 있다는 한계가 있습니다. 향후 연구 방향으로는 TEE 가 필요 없는 설계, 검색 기능 확장, 기존 애플리케이션 통합 등이 제시되었습니다.