암호화된 데이터에 대한 범위 쿼리
1.1 소개
1.1.1 배경과 동기
1 ], Microsoft Azure [ 2 ] 및 Google App Engine [ 3 ] 과 같은 클라우드로 점점 더 아웃소싱되었습니다 . 그러나 개인 정보 보호는 클라우드 컴퓨팅의 주요 장애물이었습니다. 한편으로는 클라우드가 제공하는 컴퓨팅 및 스토리지 기능을 활용하려면 클라우드에 데이터를 저장해야 합니다. 반면에, 여러 가지 이유로 인해 우리는 데이터 개인정보 보호에 있어서 클라우드를 완전히 신뢰하지 못할 수도 있습니다. 첫째, 클라우드는 데이터 개인 정보 보호 정책을 따르지 않는 직원을 부패시켰을 수 있습니다. 예를 들어, 2010년에 Google 엔지니어가 여러 어린이의 Gmail 및 Google Voice 계정에 침입했습니다.
둘째, 클라우드 컴퓨팅 시스템은 외부의 악의적인 공격에 취약할 수 있으며, 침입이 발생할 경우 클라우드 고객은 데이터 개인 정보 보호에 대한 잠재적인 영향에 대해 완전히 알지 못할 수 있습니다. 셋째, 클라우드는 개인 정보 보호 규정을 시행하기 어려운 일부 해외 시설을 기반으로 서비스를 제공할 수 있습니다.
이 장에서는 다음과 같은 널리 사용되는 클라우드 컴퓨팅 패러다임을 고려합니다. 데이터 소유자는 클라우드에 데이터를 저장하고 여러 데이터 사용자는 데이터를 쿼리합니다. 간단한 예로 사용자는 클라우드에 자신의 데이터를 저장하고 자신의 데이터를 쿼리합니다. 또 다른 예로, 병원의 여러 의사가 환자의 의료 기록을 클라우드에 저장하고 쿼리합니다. 그림 1.1 은 우리 모델의 세 당사자, 즉 데이터 소유자, 클라우드 및 여러 데이터 사용자를 보여줍니다. 세 당사자 중 데이터 소유자와 데이터 사용자는 신뢰할 수 있지만 클라우드는 완전히 신뢰할 수 없습니다.
이 장에서 다루는 문제는 개인 정보를 보호하면서도 확장 가능한 방식으로 클라우드에서 범위 쿼리를 처리하는 것입니다. 모든 레코드가 숫자 값을 가지거나 숫자 값으로 표시될 수 있는 동일한 속성 A 를 갖는 레코드 집합의 경우 간격 [ a,b ] 로 지정된 범위 쿼리가 주어지면 쿼리 결과는 A 를 갖는 레코드 집합입니다. . 범위 쿼리는 데이터베이스 SQL 쿼리 및 빅데이터 분석을 위한 기본 작업입니다.
데이터베이스 SQL 쿼리에서 where 절에는 범위로 지정된 조건자가 포함되는 경우가 많습니다. 예를 들어, SQL 쿼리 select * from Patients where 20 <= age 및 age <= 30은 연령이 [ 20,30 ] 범위에 있는 환자의 모든 기록을 찾는 것을 의미합니다 . 빅 데이터 분석에서 많은 분석에는 시간, 인간 나이 등의 차원에 따른 범위 쿼리가 포함됩니다.
데이터 항목 d 1 ,…,d n 이 주어지면 데이터 소유자는 데이터 소유자와 데이터 사용자 간에 공유되는 대칭 키 K를 사용하여 이러한 데이터를 암호화하고 인덱스 를 생성한 다음 표시된 암호화된 데이터(d)를 모두 보냅니다. 1 ) k ,…,(d n ) k 및 클라우드에 대한 인덱스입니다. 쿼리가 주어지면 데이터 사용자는 트랩도어 를 생성 한 후 클라우드로 보냅니다. 인덱스와 트랩도어를 통해 클라우드는 어떤 데이터 항목이 쿼리를 만족하는지 결정할 수 있어야 합니다.
하지만 이 과정에서 클라우드는 데이터와 쿼리에 대한 유용한 정보를 추론할 수 없어야 합니다 . 이 맥락에서 유용한 정보에는 데이터 항목의 값, 쿼리 내용, 데이터 항목의 통계 속성이 포함됩니다. 클라우드에는 암호화된 데이터 및 쿼리 외에 쿼리 결과와 함께 데이터에 대한 도메인 지식(예: 연령 분포)과 같은 다른 채널에서 얻은 정보가 있을 수 있습니다. 그러나 이러한 정보가 있더라도 개인 정보 보호 범위 쿼리 방식은 클라우드가 과거 쿼리 결과를 기반으로 데이터에 대한 추가 정보를 추론하는 것을 허용해서는 안 됩니다.
프라이버시 보장 외에도, 프라이버시 보호 범위 쿼리 방식은 쿼리 처리 시간, 저장 오버헤드, 통신 오버헤드 측면에서 효율적이어야 합니다. 많은 애플리케이션이 실시간 쿼리를 요구하므로 쿼리 처리 시간이 짧아야 합니다. 스토리지 오버헤드는 암호화된 데이터 항목 외에 클라우드가 저장해야 하는 데이터를 의미합니다. 클라우드에 저장되는 데이터의 양은 일반적으로 크기 때문에 작아야 합니다. 통신 오버헤드는 암호화된 데이터 항목 외에 데이터 소유자와 클라우드 간에 전송되는 데이터, 정확한 질의 결과 외에 데이터 사용자와 클라우드 간에 전송되는 데이터를 의미한다. 대역폭 제한과 업로드 및 다운로드에 소요되는 추가 시간으로 인해 크기가 작아야 합니다.
1.1.2 위협 모델
클라우드의 경우 Canetti et al이 제안한 클라우드가 반정직 ( 정직하지만 호기심이 많음 이라고도 함)이라고 가정합니다. [ 5 ] 에서는 사전 개인 정보 보호 범위 및 키워드 쿼리 작업을 포함하여 널리 채택되었습니다 [ 6 – 18 ]. 클라우드가 반정직하다는 것은 필요한 통신 프로토콜을 따르고 필요한 알고리즘을 올바르게 실행하지만 데이터 항목 및 쿼리에 대한 도메인 지식의 도움을 받아 데이터 항목 및 사용자 쿼리 내용에 대한 정보를 얻으려고 시도할 수 있음을 의미합니다( 데이터 항목 및 쿼리의 분포 등). 데이터 소유자와 데이터 사용자에 대해서는 신뢰할 수 있다고 가정합니다.
1.1.3 보안 모델
이전의 개인 정보 보호 키워드 쿼리 작업에서 널리 수용되었던 [ 13 ] 에서 제안된 IND-CKA 보안 모델을 채택합니다 . 이 모델에는 IND(색인 구별 불가능성) 와 CKA(선택한 키워드 공격 시 보안) 라는 두 가지 주요 요구 사항이 있습니다 . 비공식적으로, 범위 쿼리 방식은 공격자 A가 데이터 항목의 두 개의 서로 다른 세트 S 1 및 S 2 를 선택하는 경우 IND-CKA 모델에서 안전합니다 . 여기서 두 세트는 동일한 수의 데이터 항목을 가지며 중복되거나 중복되지 않을 수 있습니다.
Oracle이 데이터 소유자를 시뮬레이션하여 S 1 및 S 2 에 대한 인덱스를 구축할 수 있지만 A는 어떤 인덱스가 어떤 데이터 세트에 대한 것인지 구별할 수 없습니다. 문제가 S 1 과 S 2 에 대한 인덱스를 구별하는 것이 어렵다면 S 1 과 S 2 가 공통으로 갖지 않는 적어도 하나의 데이터 항목을 추론하는 것도 어려울 것이라는 이론적 근거가 있습니다.
즉, A가 어떤 데이터 항목이 1/2와 무시할 수 없을 정도로 다른 확률로 인덱스에 인코딩되어 있는지 결정할 수 없는 경우 인덱스는 데이터 항목에 대해 아무 것도 나타내지 않습니다. 이러한 인덱스를 보안 인덱스 라고 합니다 . IND-CKA 모델은 공격자 A 가 이전 쿼리 결과나 다른 채널에서 이미 알고 있는 것 외에 인덱스에서 데이터 항목의 일반 텍스트 값을 추론하지 못하도록 방지하는 것을 목표로 합니다. 보안 인덱스는 데이터 항목 수와 같은 정보를 숨기지 않습니다.
데이터 항목 번호의 개인정보 보호를 요구하는 애플리케이션의 경우 더미 데이터 항목을 작은 데이터 세트에 주입하여 모든 데이터 세트의 크기를 동일하게 만들 수 있습니다. 또한 검색 패턴을 숨기는 데는 관심이 없습니다. 여기서 검색 패턴은 다양한 사용자 쿼리에 해당하는 트랩도어 집합으로 정의됩니다. 트랩도어는 결정론적으로 생성되기 때문에(즉, 동일한 키워드에 대해 항상 동일한 트랩도어가 생성됨).
1.1.4 선행기술의 요약 및 제한
기존의 개인 정보 보호 질의 방식은 질의 유형에 따라 주어진 범위에 속하는 모든 데이터 항목을 질의하는 범위 질의와 특정 키워드를 포함하는 모든 텍스트 문서를 질의하는 키워드 질의로 구분된다. 프라이버시 보호 범위 질의 방식은 범위 검색 가능 대칭 암호화 방식 이라고도 하며 , 프라이버시 보호 키워드 질의 방식은 키워드 검색 가능 대칭 암호화 방식 이라고도 합니다 . 단일 데이터 소유자 다중 데이터 사용자 클라우드 패러다임에 대한 이전의 개인 정보 보호 범위 쿼리 체계는 버킷팅 체계[ 6 – 8 ]와 순서 보존 체계[ 9 – 11 ]의 두 가지 범주로 분류됩니다. 버킷팅 방식에서 데이터 소유자는 전체 데이터 도메인(예: 인간 연령의 [ 0,150 ] )을 다양한 크기의 여러 버킷(예: [ 0,12 ] , [ 13,22 ] , [ 23,60 의 4개 버킷)으로 분할합니다. ] , [ 61,150 ] ).
인덱스는 버킷 ID와 버킷의 암호화된 데이터 항목 쌍으로 구성됩니다. 범위 쿼리(예: [ 10,20 ] )의 트랩도어는 범위와 겹치는 버킷의 ID(예: 버킷 ID 1 및 2)로 구성됩니다. 버킷이 쿼리와 겹치는 한 버킷의 모든 데이터 항목은 쿼리 결과에 포함됩니다. 버킷팅 방식에는 약한 개인 정보 보호와 높은 통신 비용이라는 두 가지 주요 제한 사항이 있습니다. [ 7 ] 에서 지적한 바와 같이, 클라우드는 도메인 지식과 과거 쿼리 결과를 사용하여 데이터 항목과 쿼리 모두의 실제 가치를 통계적으로 추정할 수 있기 때문에 개인 정보 보호가 취약합니다 .
쿼리 결과에 포함된 많은 데이터 항목이 쿼리를 만족하지 못하기 때문에 통신 비용이 높습니다. 버킷 크기를 줄이면 통신 비용을 줄이는 데 도움이 되지만, 버킷 수가 데이터 항목 수에 가까워지기 때문에 개인 정보 보호가 악화됩니다.
순서 보존 체계는 암호화 후에도 데이터 항목의 상대적 순서를 유지하는 암호화 기능을 사용합니다. 임의의 두 데이터 항목 a와 b 및 순서 보존 암호화 함수 f에 대해 f(a) ≤ f(b) 인 경우에만 a ≤ b 입니다 . 체계를 보존하기 위해 데이터 항목 d 1 ,…,d n 에 대한 인덱스 는 f(d 1 ),…,f(d n )이고 쿼리 [ a,b ] 에 대한 트랩도어 는 [ f( a),f(b) ] . 순서 보존 체계는 클라우드가 데이터 항목과 쿼리 모두의 실제 값을 통계적으로 추정할 수 있도록 하기 때문에 개인 정보 보호가 약합니다[ 19 ].
위의 기존 방식이 제공하는 개인 정보 보호가 취약한 근본적인 이유는 동일한 수의 데이터 항목에 대해 인덱스를 구별할 수 있지만 분포가 다르기 때문입니다. 버킷팅 방식에서는 동일한 수의 데이터 항목에 대해 데이터 값의 분포가 다르면 버킷 간에 항목 수의 균형을 유지해야 하기 때문에 버킷의 크기 분포가 달라집니다. 체계를 보존하기 위해 동일한 수의 데이터 항목에 대해 데이터 값의 분포가 다르면 암호문이 투영된 공간에서 다른 분포를 갖게 됩니다. 버킷팅 체계와 순서 보존 체계 모두 데이터 배포에 대한 도메인 지식을 활용하여 클라우드는 데이터와 쿼리의 값을 통계적으로 추정할 수 있습니다.
1.1.5 제안된 접근법
본 장에서는 인덱스 구별 불가능성을 달성하는 최초의 프라이버시 보호 범위 쿼리 기법을 제안한다. 인덱스 구별 불가능성을 달성하기 위한 핵심 아이디어는 각 노드가 PB트리 (여기서 “P”는 개인 정보 보호 를 나타내고 “B”는 블룸 필터를 나타냄)라고 하는 Bloom 필터를 사용하여 표현되는 완전한 이진 트리에서 모든 인덱싱 요소를 구성하는 것입니다. . PBtree에는 두 가지 중요한 속성이 있기 때문에 인덱스 구별 불가능성을 달성할 수 있습니다 .
첫째, PBtree는 구조 구별 불가능 성의 특성을 갖습니다 . 즉, 두 세트의 데이터 항목이 동일한 수의 데이터 항목을 갖는 경우에만 두 세트의 데이터 항목이 동일한 PBtree 구조를 갖습니다. 데이터 항목 집합의 PBtree 구조는 데이터 항목의 값이 아닌 집합 카디널리티에 의해서만 결정됩니다. 둘째, PBtree는 노드 구별 불가능성( node indistinguishability) 의 속성을 가지고 있습니다.
즉, 동일한 구조를 갖는 동일한 카디널리티의 데이터 세트로 구성된 임의의 두 PBtree와 두 PBtree의 해당 노드에 대해 두 노드의 값 구별이 되지 않습니다. 따라서 우리의 방식은 클라우드가 도메인 지식이 있어도 인덱스에 대한 통계 분석을 수행하는 것을 방지합니다.
1.1.6 기술적 과제 및 솔루션
두 가지 주요 기술적 과제가 있습니다. 첫 번째 과제는 데이터 소유자가 PBtree를 구축하는 것입니다. 우리는 먼저 보다 작음 및 보다 큼 비교를 집합 멤버십 테스트(즉, 숫자가 집합에 있는지 테스트)로 변환하여 이 문제를 해결합니다. 이 테스트에는 같음 비교만 포함되며 그런 다음 모든 집합을 PB트리에서 계층적으로 구성합니다. . PBtree 노드 간의 관계가 더 이상 통계적으로 의미가 없기 때문에 이 변환은 노드 구별 불가능성을 달성하는 데 도움이 됩니다. 두 번째 과제는 클라우드에서 빠른 쿼리 처리를 위해 PBtree를 최적화하는 것입니다.
우리는 PBtree 순회 너비 최소화 와 PBtree 순회 깊이 최소화 라는 두 가지 아이디어로 이 문제를 해결합니다 . PBtree 순회 폭 최소화 의 개념은 클라우드가 쿼리를 처리하기 위해 통과해야 하는 경로 수를 최소화하는 것입니다. 우리는 PBtree 순회 폭 최소화 문제가 NP-hard임을 증명하고 효율적인 근사 알고리즘을 제안합니다. PBtree 탐색 깊이 최소화 의 아이디어는 클라우드가 쿼리를 처리하기 위해 통과해야 하는 경로의 탐색 깊이를 최소화하는 것입니다. 즉, 우리는 많은 경로의 순회가 가능한 한 빨리 종료되기를 원합니다.
1.1.7 주요 기여
우리는 세 가지 주요 기여를 합니다. 첫째, 우리는 최초의 프라이버시 보호 범위 쿼리 방식을 제안하고 그것이 널리 채택된 IND-CKA 모델 하에서 안전하다는 것을 증명합니다. 둘째, PBtree, 기본 PBtree 구성 및 질의 처리 알고리즘, 그리고 두 가지 PBtree 최적화 알고리즘을 제안한다. 셋째, 우리는 500만 개의 데이터 항목이 포함된 대규모 실제 데이터 세트에 대한 계획을 구현하고 평가했습니다. 실험 결과는 우리의 계획이 빠르고 확장 가능하다는 것을 보여줍니다. 예를 들어 결과에 10개의 데이터 항목이 포함된 쿼리의 경우 0.17ms만 소요됩니다.