MESS는 신뢰할 수 없는 클라우드에서 운영되는 시맨틱 검색 시스템에서 프라이버시·정확도·효율성을 동시에 달성하는 새로운 방식이다. 벡터를 이진 코드로 매핑한 뒤 지역성 민감 해싱(LSH)과 무작위 응답 기법으로 값을 교란하고, 이 교란된 코드 위에 다중 그래프 HNSW 인덱스를 구축해 데이터·질의·접근 패턴 프라이버시를 보장한다. 2단계 질의 교란 메커니즘으로 검색 패턴 프라이버시까지 확보하면서도, 동형암호나 ORAM 없이 교란된 코드 위에서 직접 검색을 수행해 기존 최고 성능 대비 최대 15.08배 낮은 지연시간을 달성했다. 프라이버시 보장 근접 이웃 검색을 실용적 속도로 구현했다는 점에서 클라우드 기반 RAG나 벡터DB 서비스에 실질적 적용 가능성을 제시한다.

• •벡터를 이진 코드로 변환 후 LSH와 무작위 응답으로 교란, 다중 그래프 HNSW 인덱스 구축
• •데이터·질의·접근 패턴 프라이버시에 더해 2단계 질의 교란으로 검색 패턴 프라이버시까지 보장
• •동형암호(HE)나 ORAM 없이 교란된 코드 위에서 직접 검색해 오버헤드 최소화
• •기존 최신 기법 대비 최대 15.08배 낮은 지연시간 달성
• •다중 그래프 구조로 교란에 따른 검색 정확도 저하를 완화