암호학자들은 전체 검색 개인 정보 보호를 위한 접근 방식을 고안합니다. 콴타 매거진

우리 모두는 온라인에서 공유하는 세부사항에 주의해야 한다는 것을 알고 있지만, 우리가 찾는 정보는 공개될 수도 있습니다. 운전 경로를 검색하면 우리의 위치를 ​​훨씬 쉽게 추측할 수 있습니다. 손상된 데이터 저장소에서 비밀번호를 확인하면 비밀번호가 유출될 위험이 있습니다.

이러한 상황은 암호화에 대한 핵심 질문을 촉발시킵니다. 액세스한 내용에 대해 아무것도 공개하지 않고 공개 데이터베이스에서 정보를 어떻게 가져올 수 있습니까? 이는 사서가 어떤 책인지 알지 못한 채 도서관에서 책을 대출하는 것과 같습니다.

개인 정보 검색으로 알려진 이 문제를 해결하는 전략을 고안하는 것은 "다양한 개인 정보 보호 애플리케이션에서 매우 유용한 구성 요소"라고 말했습니다. 데이비드 우, 텍사스 대학교 오스틴 캠퍼스의 암호학자. 1990년대부터 연구자들은 데이터베이스에 개인적으로 접근하기 위한 전략을 개선하면서 이 문제를 해결해 왔습니다. 대규모 데이터베이스에서는 여전히 불가능한 주요 목표 중 하나는 과도한 계산 작업을 수행하지 않고도 익명으로 많은 데이터를 선별할 수 있는 비공개 Google 검색과 같습니다.

이제 세 명의 연구자가 만들어진 오랫동안 추구해 온 개인 정보 검색 버전을 확장하여 보다 일반적인 개인 정보 보호 전략을 구축했습니다. 상을 받은 작품 최고의 논문상 XNUMX월 연례행사에서 컴퓨팅 이론 심포지엄, 진정한 사적인 검색으로가는 길에 주요 이론적 장벽을 무너 뜨립니다.

"[이것은] 우리 모두가 원했지만 그것이 존재한다고 믿지 않았던 암호화의 무언가입니다."라고 말했습니다. 비 노드 바이 쿠툰 타나 단, 논문에 참여하지 않은 MIT의 암호학자입니다. “획기적인 결과입니다.”

개인 데이터베이스 액세스 문제는 1990년대에 구체화되었습니다. 처음에 연구자들은 검색할 때마다 전체 데이터베이스를 스캔하는 것이 유일한 해결책이라고 생각했습니다. 이는 사서가 책을 반납하기 전에 모든 책장을 샅샅이 뒤지는 것과 같습니다. 결국, 검색에서 어떤 섹션을 건너뛴 경우 사서는 귀하의 책이 도서관의 해당 부분에 없다는 것을 알게 될 것입니다.

이 접근 방식은 소규모에서는 충분히 효과적이지만 데이터베이스가 커짐에 따라 데이터베이스를 검색하는 데 필요한 시간도 그에 비례하여 늘어납니다. 더 큰 데이터베이스에서 읽을 때(인터넷은 꽤 큰 데이터베이스임) 프로세스가 엄청나게 비효율적이 됩니다.

2000년대 초반, 연구자들은 데이터베이스를 "전처리"함으로써 전체 스캔 장벽을 피할 수 있다고 의심하기 시작했습니다. 대략적으로 이는 전체 데이터베이스를 특수 구조로 인코딩하여 서버가 해당 구조의 작은 부분만 읽어 쿼리에 응답할 수 있음을 의미합니다. 이론적으로 충분히 신중한 전처리는 정보를 호스팅하는 단일 서버가 자체적으로 프로세스를 한 번만 거치므로 미래의 모든 사용자가 더 이상 노력하지 않고도 개인적으로 정보를 얻을 수 있음을 의미할 수 있습니다.

럭셔리 다니엘 위치스Northeastern University의 암호학자이자 새 논문의 공동 저자인 , 그것은 사실이 되기에는 너무 좋아 보였습니다. 2011년쯤부터 그는 이런 계획이 불가능하다는 것을 증명하기 시작했다. “나는 이것이 이루어질 수 있는 방법이 없다고 확신했다”고 그는 말했다.

하지만 2017년에는 두 그룹의 연구자들이 출판 결과 그것이 그의 마음을 바꾸었다. 그들은 이런 종류의 개인정보 검색을 할 수 있는 최초의 프로그램을 만들었지만 그 프로그램이 안전하다는 것을 보여주지는 못했습니다. (암호학자들은 시스템을 깨는 것이 어려운 문제를 해결하는 것만큼 어렵다는 것을 보여줌으로써 시스템의 보안을 입증합니다. 연구원들은 이를 표준적인 어려운 문제와 비교할 수 없었습니다.)

그래서 그의 희망이 새로워졌음에도 불구하고 Wichs는 이러한 프로그램의 안전한 버전이 아직 멀었다고 생각했습니다. 대신 그와 그의 공동 저자들은 — 웨이카이 린, 현재는 버지니아 대학교에 있으며, 에단 묵, 또한 Northeastern에서 — 여러 서버가 데이터베이스를 호스팅하는 경우와 관련하여 더 쉬울 것이라고 생각한 문제를 해결했습니다.

그들이 연구한 방법에서 데이터베이스의 정보는 수학적 표현으로 변환될 수 있으며, 서버는 이를 평가하여 정보를 추출할 수 있습니다. 저자는 평가 프로세스를 보다 효율적으로 만드는 것이 가능할 것이라고 생각했습니다. 그들은 2011년에 다른 연구자들이 일반적인 평가 단계를 건너뛸 수 있는 특별하고 컴팩트한 값 테이블을 생성하여 전처리를 통해 그러한 표현식을 신속하게 평가하는 방법을 찾았을 때 아이디어를 가지고 놀았습니다.

이 방법은 아무런 개선도 가져오지 못했고 그룹은 포기할 뻔했습니다. 그러다가 이 도구가 탐나는 단일 서버 사례에서 실제로 작동할 수 있을지 궁금해졌습니다. 충분히 신중하게 다항식을 선택하면 단일 서버가 2011년 결과를 기반으로 이를 전처리할 수 있어 Wichs가 수년 동안 고민해 왔던 안전하고 효율적인 조회 체계를 얻을 수 있었습니다. 갑자기 그들은 결국 더 어려운 문제를 해결했습니다.

처음에 저자들은 그것을 믿지 않았습니다. Wichs는 "이게 무슨 문제인지 알아내자"고 생각했던 것을 기억했습니다. "우리는 그것이 어디에서 고장나는지 알아내려고 계속 노력했습니다."

그러나 해결책은 그대로 유지되었습니다. 그들은 누구나 비밀리에 정보를 가져올 수 있도록 단일 서버 데이터베이스를 전처리하는 안전한 방법을 실제로 발견했습니다. “정말로 우리가 기대했던 모든 것 이상입니다.”라고 말했습니다. 유발 이샤이, 이 작업에는 참여하지 않은 이스라엘 Technion의 암호학자입니다. 그는 “우리는 요구할 만큼 용감하지도 못한 결과”라고 말했다.

비밀 조회 체계를 구축한 후 저자들은 데이터베이스에서 정보를 가져오는 것보다 더 복잡한 개인 인터넷 검색이라는 실제 목표로 전환했다고 Wichs는 말했습니다. 비공개 조회 체계 자체는 Google과 유사한 비공개 검색 버전을 허용하지만 매우 노동 집약적입니다. Google의 알고리즘을 직접 실행하고 필요할 때 비밀리에 인터넷에서 데이터를 가져옵니다. Wichs는 요청을 보내고 서버가 결과를 수집하는 동안 가만히 앉아 있는 진정한 검색은 실제로 다른 사람이 데이터에 대해 전혀 알지 못한 채 데이터를 조작할 수 있도록 데이터를 위장하는 동형암호라고 알려진 더 광범위한 접근 방식의 목표라고 말했습니다. .

일반적인 동형암호 전략은 검색할 때마다 인터넷의 모든 콘텐츠를 샅샅이 뒤져 개인 정보 검색과 같은 난관에 부딪힐 것입니다. 그러나 저자는 비공개 조회 방법을 발판으로 사용하여 우리가 매일 사용하는 프로그램과 더 유사한 계산을 실행하고 전체 인터넷을 휩쓸지 않고 은밀하게 정보를 가져오는 새로운 체계를 구축했습니다. 이는 인터넷 검색과 데이터에 대한 빠른 액세스가 필요한 모든 프로그램의 효율성을 향상시킬 것입니다.

동형 암호화는 개인 조회 체계의 유용한 확장이지만 개인 정보 검색이 더 근본적인 문제라고 Ishai는 말했습니다. 저자의 솔루션은 "마법의 빌딩 블록"이며 동형 암호화 전략은 자연스러운 후속 조치입니다.

현재로서는 두 체계 모두 실질적으로 유용하지 않습니다. 현재 전처리는 데이터베이스 크기가 무한대로 커지는 극단적인 상황에서 도움이 됩니다. 그러나 실제로 배포하면 이러한 절감 효과가 실현될 수 없으며 프로세스에 너무 많은 시간과 저장 공간이 소모됩니다.

다행히도, Vaikuntanathan은 암호학자들이 처음에는 비실용적이었던 결과를 최적화해 온 오랜 역사를 가지고 있다고 말했습니다. 향후 작업을 통해 접근 방식을 간소화할 수 있다면 대규모 데이터베이스의 개인 조회도 가능해질 것이라고 그는 믿습니다. “우리 모두는 우리가 거기에 갇혀 있다고 생각했습니다.”라고 그는 말했습니다. “다니엘의 결과가 주는 것은 희망입니다.”

콴타 에서는 청중에게 더 나은 서비스를 제공하기 위해 일련의 설문조사를 실시하고 있습니다. 우리의 컴퓨터 과학 독자 설문조사 그러면 당신은 무료로 승리할 수 있는 자격을 얻게 될 것입니다 콴타 상품.