Efficient Homomorphic String Search via TFHE

출처:IACR ePrint (암호학)

AI 인사이트

개발자

1.TFHE 기반 암호문 검색법 제안, 정수 입력 TFHE의 두 연산 모드를 활용해 완전 보안 이진 탐색 구현
2.기존 BGV 기반 Bonte&Iliashenko(CCSW'20) 방식의 O(|P||T|) 비교 횟수를 O(|P|log|T|)로 감소
3.길이 100 패턴을 100만 자 유전체 암호텍스트에서 5분 이내에 찾음, 기존 방식은 약 5일 소요

왜 중요한가?

유전체 등 민감한 데이터를 복호화 없이 검색할 수 있게 하면서 처리 시간을 하루 단위에서 분 단위로 줄여, TFHE 기반 완전동형암호 문자열 검색의 실용화 가능성을 크게 높였다.

본문 미리보기

We present a method for secure pattern matching over encrypted texts using TFHE. Our approach realizes a fully secure binary search algorithm by leveraging two operational modes of integer-input TFHE. While the BGV-based method of Bonte and Iliashenko (CCSW '20) requires $O(|P| \cdot |T|)$ secure character comparisons to find a pattern $P$ in a text $T$, our method reduces this to $O(|P|\log |T|)$ comparisons, achieving improved scalability for large texts. As a result, our method can find

전체 내용이 궁금하다면?

원문을 직접 읽어보세요

원문 보기