이 논문은 오블리비어스 키-값 저장소(OKVS) 구조인 Peelable Garbled Bloom Filter(PGBF)를 제안한다. 카운팅 블룸 필터로 키-값 집합을 양파처럼 겹겹의 부분집합으로 나눠 인코딩·디코딩하되, 확장률이 작을 때 발생하는 비어있지 않은 코어 문제를 해결하기 위해 여러 PGBF를 재귀적으로 결합한 Multi-PGBF와, 대규모 집합을 클러스터링해 속도를 높인 C-Multi-PGBF를 함께 제시한다. 실험 결과 Multi-PGBF는 기존 RR(CCS'22) 대비 인코딩 시간을 65.1~77.6%, 디코딩 시간을 최대 96.3% 단축했다. 최신 2자·다자간 프라이빗 셋 교집합(PSI) 프로토콜에 적용했을 때도 기존 OKVS 구조보다 대부분의 설정에서 더 빠른 성능을 보였다.
- •카운팅 블룸 필터로 키-값 집합을 겹겹이 벗기고 씌우는 방식의 새 OKVS 구조 PGBF를 제안했다.
- •여러 PGBF를 재귀적으로 결합한 Multi-PGBF로 작은 확장률에서 발생하는 비어있지 않은 코어 문제를 해결했다.
- •Multi-PGBF는 RR(CCS'22) 대비 인코딩 65.1~77.6%, 디코딩 28.6~62.4% 더 빠르고, RB-OKVS(Usenix'23) 대비 디코딩이 최대 96.3% 빠르다.
- •클러스터링 변형 C-Multi-PGBF는 대규모 집합에서 더 빠른 인코딩 효율을 달성한다.
- •최신 프라이빗 셋 교집합(PSI) 프로토콜(Eurocrypt'21, Usenix'24)에 적용해 기존 OKVS 대비 더 빠른 프로토콜을 구현했다.
0단 자동
AI가 규칙대로 쓰고 그대로 게시했습니다. 사람이 따로 보지 않았습니다.
- 규칙 판
- 규칙 판 도입 이전 기사입니다.
- 남기는 것
- 규칙 판 · 모델 · 시각
- 판 기록
- 아직 없습니다.
Multi-PGBF: Efficient Oblivious Key-Value Store and Application to Private Set Intersection
- 1.onion peeling 방식의 새 데이터구조 'Peelable Garbled Bloom Filter(PGBF)' 제안
- 2.Multi-PGBF가 RR(CCS'22) 대비 인코딩 시간 65.1~77.6% 단축
- 3.디코딩 속도는 RR 대비 28.6~62.4%, RB-OKVS(Usenix'23) 대비 89.7~96.3% 향상
- 4.2자·다자간 최신 PSI 프로토콜(Eurocrypt'21, Usenix'24)에 적용해 기존 OKVS보다 빠른 성능 확인
왜 중요한가?
오블리비어스 키-값 저장소(OKVS)의 인코딩·디코딩 효율을 크게 높여, 프라이빗 집합 교집합(PSI) 등 실사용 프라이버시 프로토콜의 성능 병목을 완화한다.
본 연구는 개인 정보 보호에 필수적인 '무지 키-값 저장소'를 효율적으로 구현하고, 이를 '프라이빗 집합 교차(PSI)'에 적용하는 방안을 제시합니다. 국내에서 개인정보보호법 강화와 함께 민감 데이터의 안전한 교환 및 분석 수요가 증가하는 가운데, 이 기술은 금융기관 간 정보 공유, 의료 데이터 분석 등 다양한 산업 분야에서 프라이버시를 보장하며 데이터를 활용하는 핵심 솔루션이 될 수 있습니다.
본문 미리보기
An oblivious key-value store is a data structure that can encode and decode $n$ key-value pairs in a table of size $m$ obliviously. After encoding, one cannot distinguish the encoded key-value pairs from other key-value pairs in the input domain. In this paper, we first propose a data structure called Peelable Garbled Bloom Filter (PGBF), which encodes the key-value pairs in a similar way to peeling and unpeeling an \emph{onion}. Specifically, it can divide the key-value pair set (i.e., onion) a
전체 내용이 궁금하다면?
원문을 직접 읽어보세요
이 글이 만들어진 과정
- 11:24AI 초안
