[Algorithmic Foundations] #3. differential privacy promises

Definition 2.4 (Differential Privacy)
Pr[M(x)∈S]≤exp(ε)Pr[M(y)∈S]+δ

– in detail: https://saraheee.com/2024/01/foundation-differential-privacy-definition/

2.3.1 What differential privacy promises

An Economic View. 개인이 데이터베이스에 포함되었을 때 additional harm으로부터 개인을 보호할 것을 약속한다.
why? database x에 대해, data가 x의 일부이기 때문에 문제에 직면할 수 있는 가능성의 문제가 생기기 때문이다.

differentially private mechanism M의 결과인 M(x)가 공개되더라도 개인이 실제로 피해를 입을 수는 있지만, 차등 프라이버시는 개인의 참여 선택으로 인해 피해의 확률이 크게 증가하지 않았다고 약속하고 있다.
why? 데이터베이스를 사용해 생성된 결과로 인해 개인에게 발생할 수 있는 피해의 확률이 유사하게 유지되기 때문이다.
why? 개인정보 보호와 데이터 유용성 사이의 균형을 이루는 방식으로 개인정보 보호를 강화하기 때문이다.
how? ε-differential privacy 보장으로 미래 유틸리티가 exp(ε) ≈ (1+ε)를 초과하여 해를 입지 않을 것을 보장한다.
ε이 매우 작을 때, 0에 가까울 때 적용 가능한 근사, 개인의 유틸리티가 그보다 많이 감소하지 않을 것임을 의미한다.
따라서 차등 프라이버시의 영향으로 인한 유틸리티의 변화가 제한적이다.

\(u_i: A \rightarrow \mathbb{R}_{\geq 0}\) 개인 i의 효용 함수, 특정 결과나 사건에서 얻는 만족이나 이익을 정량화
\(x \in \mathbb{N}^{|X|}\): 개인 i의 개인 private data를 포함한 데이터셋
M: ε-차등 프라이버시 알고리즘
y: i의 데이터를 제외하고 x와 동일한 데이터셋 (in particular, \(\parallel x-y \parallel_1 = 1\))
f: Range(M) →∆(A): M의 출력에 따라 미래 사건 A의 분포를 결정하는 함수

\(\mathbb{E}_{a \sim f(M(x))}[u_i(a)] = \sum_{a \in A}u_i(a) \cdot Pr_{f(M(x))}[a] \\ \leq \sum_{a \in A}u_i(a) \cdot exp(\epsilon) Pr_{f(M(y))}[a] \\ = exp(\epsilon) \mathbb{E}_{a \sim f(M(y))}[u_i(a)]\)

Similarly,

\(\mathbb{E}_{a \sim f(M(x))}[u_i(a)] \geq exp(-\epsilon) \mathbb{E}_{a \sim f(M(y))}[u_i(a)]\).

개인 i가 미래의 모든 사건들(A로 표시된 집합)에 대해 임의의 선호를 가지고 있음
\(\mathbb{E}\): 기대값(확률적 사건의 평균 또는 가장 가능성 있는 결과를 예측하는 역할), 가능한 모든 인스턴스(사례)에 대한 평균을 나타나는 예상 값
a ~ f(M(x)): dataset x에 작용하는 메커니즘 M의 출력에 함수 f를 적용, 이 정의된 분포에서 a가 추출됨

가능한 모든 결과와 각 확률을 고려해서 생성된 결과 a에서 개인 i가 기대할 수 있는 평균 효용 또는 이익

set A의 모든 가능한 결과 a에 대해 개인 i에 대한 기대 효용 \(u_i(a)\)을 확률에 의해 가중치를 적용하여 계산함
발생하는 각 결과의 \(Pr_{f(M(x))[a]}\)

\(Pr_{f(M(x))}[a]\): 모든 가능한 사건 a에 대해 \(u_i(a)\)와 그 사건이 발생할 확률

x에서 M을 적용한 예상 유틸리티는 y에서 M을 적용한 후 예상 유틸리티의 exp(ε)배 이상
데이터셋의 작은 변화가 유틸리티에 미치는 영향이 제한적임

메커니즘 M의 출력에 함수 f를 적용한 결과 a가 출력될 때 개별 i에 대한 예상 효용

ε-differential privacy의 보장을 약속하면서, 데이터 분석가는 개인에게 예상되는 미래 유틸리티가 exp(ε) ≈ (1+ε) 요인 이상으로 피해를 입지 않을 것이라고 약속할 수 있음

2.3.2 What differential privacy does not promise

Smoking Causes Cancer: ‘흡연이 암을 유발한다’와 같은 결론은, 개인에 대한 통계적 정보를 반영할 수 있음에도 불구하고, 차등 프라이버시 위반의 증거가 아니다. 개인이 설문 조사에 참여했는지 여부와 관계없이 유사한 확률로 이러한 결정적인 결과가 얻어지기 때문이다.(응답자의 존재 여부와 무관하게 거의 동일한 확률로 관찰되기 때문)

Qualitative Properties of Differential Privacy

1. Protection against arbitrary risks.

재식별에 대한 보호를 넘어서는 임의의 위험에 대한 보호
단순히 데이터셋에서 개인을 재식별하는 것을 방지하는 것 이상의 보호를 제공한다. 데이터 분석 과정에서 개인의 정보가 노출될 수 있는 모든 임의의 위험으로부터 보호함을 의미한다.
즉, 차등 프라이버시는 데이터의 사용이 개인에게 예상치 못한 해를 입힐 가능성을 최소화한다.

[다른 데이터 프라이버시 보호 방법들]

방법	설명	예시	DP 비교
익명화(Anonymization)	식별 정보를 제거하거나 변형	이름, 주소	데이터 잡음 추가
총계화(Aggregation)	데이터의 집계된 형태를 사용해 개인 정보를 보호	평균, 중앙값	개별 데이터 포인트
Perturbative Privacy	데이터에 임의의 잡음 추가 – 프라이버시의 정확한 수준을 보장하기 어려움		잡음의 양을 정량적으로 조절
Data Masking	데이터 값을 가려서 원본을 숨김 – 특정 상황에서 신속하게 적용 가능하나, 공격자가 마스킹된 부분을 우회할 가능성이 있음 – 차등 프라이버시는 데이터 유용성을 더 잘 유지할 수 있음		잡음을 추가
가명 처리(Pseudonymization)	식별 가능한 데이터를 가명(다른 식별자로 대체)으로 변환하여 원본 식별자와의 직접적인 연결을 끊음 – 원본 데이터와 연결될 수 있는 키를 별도로 관리함		데이터 잡음 추가

2. Automatic neutralization of linkage attacks.

과거, 현재 및 미래의 모든 데이터셋과 기타 형태 및 보조 정보 소스로 시도된 모든 것들을 포함한 연계 공격의 자동 중립화
차등 프라이버시는 다양한 데이터셋과 보조 정보를 결합하여 개인을 식별하려는 연결 공격(linkage attacks)에 자동으로 대응한다. 이는 분석가가 데이터를 처리할 때, 공격자가 다른 데이터셋이나 정보를 활용하여 특정 개인의 데이터를 추적하더라도, 개인의 프라이버시가 보호됨을 보장한다.
how? 데이터 처리 과정에서 자동으로 잡음을 추가한다.

[다른 프라이버시 보호 기술들]
1) k-anonymity: 데이터셋 내에서 어떤 개인도 적어도 k-1명의 다른 개인과 구분할 수 없도록 만드는 데이터 익명화 기법, 개인을 직접적으로 식별할 수 있는 속성(예: 이름, 주소)을 수정하거나 일반화한다.
– advantages: 재식별 위험 감소, 구현이 용이
– disadvantages: 동질성 공격이나 배경 지식을 활용한 공격
2) l-diversity: 익명화된 그룹 내의 민감한 속성이 최소 l개의 다양한 값을 포함하도록 보장하는 k-익명성의 확장 기법
– advantages: 동질성 공격에 대한 보호, 민감 정보의 다양성 보장
– disadvantages: 구현 복잡도 증가
3) t-closeness: 익명화된 그룹 내의 민감한 속성의 분포가 전체 데이터셋 내의 해당 분포와 t 이내로 근접하도록 하는 기법
– advantages: 민감 속성의 분포 왜곡 감소
– disadv: 분석의 복잡도 및 계산 비용 증가, 데이터 유용성 감소 가능성

3. Quantification of privacy loss.

손실을 이진 개념(binary concept)으로 다루지 않고, 개인 정보 보호 손실의 정도를 정량화할 수 있는 척도를 제공한다. 따라서 다른 기술 간의 비교가 가능하다.
예: 개인 정보 보호 손실에 대한 한계가 고정되어 있을 때, 어떤 기술이 더 나은 정확성을 제공하는지 비교할 수 있다.
반대로 정확도가 고정되어 있을 때(for a fixed accuracy), 어떤 기술이 더 나은 프라이버시를 제공하는지 비교할 수 있다.

[the others]
1) 최소 엔트로피(Min-Entropy): 데이터의 불확실성 또는 무작위성을 측정
엔트로피가 높을수록 더 높은 프라이버시를 의미한다.
데이터셋 간의 불확실성을 비교하여 프라이버시 보호 수준을 평가한다.
2) 상호 정보량(Mutual Information): 원본 데이터셋과 익명화된 데이터셋 간 공유하는 정보의 양을 측정
상호 정보량이 낮을수록 더 높은 프라이버시를 의미한다.

4. Composition.

조합성, 여러 계산에 대한 누적된 개인 정보 보호 손실의 분석과 통제를 허용한다.
손실의 정량화가 여러 계산에 걸쳐 누적된 프라이버시 손실을 분석하고 제어할 수 있게 해준다.
차등 프라이버시 메커니즘의 조합 아래에서의 행동을 이해함으로써, 더 간단한 차등 프라이버시 빌딩 블록으로부터 복잡한 차등 프라이버시 알고리즘을 설계하고 분석할 수 있다.

[the others]
1) Sequential Composition
여러 차례의 데이터 처리 작업이 순차적으로 이루어질 때, 각 작업에서의 프라이버시 손실을 합산하여 전체 프라이버시 손실을 계산
예: 차등 프라이버시 알고리즘을 여러 번 적용할 경우, 각 단계에서의 ε 값을 더함으로써 전체 작업의 프라이버시 손실을 추정
2) Parallel Composition
서로 다른 데이터 집합에 대해 독립적으로 수행되는 데이터 처리 작업에서의 프라이버시 손실을 계산, 전체 프라이버시 손실은 개별 작업에서의 최대 프라이버시 손실로 결정된다.
예: 별도의 데이터 서브넷에 차등 프라이버시 알고리즘을 적용할 때, 전체 프라이버시 손실은 가장 높은 단일 알고리즘의 ε 값으로 측정
3) Secure Multi-party Computation (SMC)
여러 참여자가 각자의 비밀 정보를 공개하지 않으면서 공동의 계산 문제를 해결할 수 있도록 하는 암호학적 기법
참여자들 각 입력 데이터를 암호화, 암호화된 형태로 계산 수행 및 최종 결과만을 공유
예: 참여자들 사이의 프라이버시를 보호하면서 데이터 분석이나 기계 학습 작업을 수행할 수 있게 함
방법: 평균 급여를 구하기 위해, 본인의 급여가 되는 수치를 n개로 나눠 n명의 사람에게 각각 전달, 전체 (n개의 값)^2/n 하여 평균 급여 계산
4) Homomorphic Encryption (HE)
암호화된 데이터에 대해 직접 계산을 수행할 수 있는 암호화 기법, 복호화하면 원래 데이터에 동일한 계산을 수행한 결과와 같음
예: 데이터를 직접 노출시키지 않고도 클라우드 환경에서 복잡한 데이터 처리 및 분석 작업을 수행할 수 있음, 데이터의 누적된 프라이버시 손실을 방지하는 데 도움이 됨
방법: 가산적 동형성을 지원하는 경우, 두 암호문을 더하고 결과를 복호화하면 두 원래 평문을 더한 결과와 같은 값을 가짐
– D(E(a) ⊕ E(b)) = a + b

5. Group Privacy.

그룹에 의해 발생하는 프라이버시 손실을 분석하고 제어할 수 있게 해준다. (such as families)
[another]
1) 연합 학습(Federated Learning): 머신러닝 연합 학습은 로컬 데이터 샘플을 보유한 여러 분산된 장치나 서버에서 모델을 학습할 수 있게 함
데이터 자체를 교환하지 않고 모델 또는 그래디언트만을 집계함으로써 그룹의 프라이버시를 보호함
분산 시스템에서 사용, 지속적인 학습

6. Closure Under Post-Processing.

데이터 분석가는 개인 데이터베이스에 대한 추가 지식 없이 차등 프라이버시 알고리즘 M의 출력 함수를 계산하고 그것을 덜 차등 프라이버시 적으로 만들 수 없다. 데이터 분석가는 알고리즘의 출력에 대해 생각하고, 어떤 보조 정보가 가능하더라도 형식적 정의나 직관적인 의미에서 프라이버시 손실을 증가시킬 수 없다. 차등 프라이버시 알고리즘의 결과에 대해 어떠한 추가 분석이나 처리가 이루어지더라도, 그 결과의 프라이버시 보호 수준이 유지되거나 악화되지 않음을 보장한다.
예: 차등 프라이버시 알고리즘을 사용해 얻은 데이터셋에서 통계적 분석을 수행하거나, 그 결과를 기반으로 예측 모델을 만들더라도 이러한 후처리 작업은 원본 데이터셋의 개인 정보를 추가로 노출시키지 않는다.
데이터 처리 과정에 잡음을 추가함으로써 개인정보를 보호하고, 후처리는 이미 잡음이 추가된 데이터를 기반으로 이루어지기 때문에 이 과정에서 새로운 개인정보가 노출될 위험은 없다.
[the others]
1) 제로 지식 증명(Zero-Knowledge Proofs): 한 당사자가 다른 당사자에게 특정 진술이 참임을 증명할 수 있게 해주는 암호화 기술
어떤 추가 정보도 공개하지 않고 후처리 과정에서도 원본 데이터에 대한 정보가 노출되지 않도록 보장
2) 프라이버시 보존 학습(Privacy-Preserving Machine Learning): 머신러닝 모델을 훈련시키면서 개인 데이터의 프라이버시를 보호하는 기법, 모델의 학습 과정이나 결과 해석 단계에서 개인정보가 노출되지 않도록 보장
3) 블록체인과 스마트 컨트랙트(Blockchain and Smart Contracts): 블록체인 상에서 실행되는 스마트 컨트랙트는 코드에 따라 자동으로 실행되므로, 한 번 배포된 후에는 외부에서 임의로 수정할 수 없음

2.3.3 Final remarks on the definition

The Granularity of Privacy.
프라이버시의 세밀함, 데이터 단위(단일 항목)에 대해 프라이버시 보호를 약속하는지를 정의(알고리즘의 동작이 얼마나 변하는지)
데이터베이스의 단일 항목을 구성하는 것이 무엇인가? (But what constitutes a single entry in the database?) 알고리즘이 항목의 변경에 어떻게 반응해야 하는지에 대한 기준을 제시한다.

1) 정점(vertex) – 데이터페이스의 단일 항목
데이터베이스에 대한 수정이 한 번에 영향을 미칠 수 있는 최소한의 데이터 단위
– 정점 수준의 세밀함: 차등 프라이버시 알고리즘이 그래프에서 정점의 추가 또는 삭제에 둔감해야 함
그래프에서 단일 정점의 추가나 제거가 그래프에서 최대 n개의 엣지를 추가하거나 제거할 수 있음
+ 단일 정점의 추가나 제거가 가능한 엣지의 최대 수가 n임을 의미한다. 그래프가 n개의 정점을 가지고 있다면, 새로운 정점을 추가하는 것은 이론적으로 최대 n개의 새로운 엣지를 생성할 수 있다.

2) 간선(edge) – 그래프 데이터베이스
각 개인이 정점으로 표현되고, 개인 간의 관계가 간선(edge)으로 나타남
– 간선 수준의 세밀함: 단일 엣지에 대한 ϵ-차등 프라이버시를 약속한다면, 데이터 분석가는 그래프 내에서 어떠한 1/ϵ 간선의 집합의 존재에 대해서도 결론을 내릴 수 없어야 한다.
+ ϵ = 0.01이라면, 분석가는 데이터베이스의 특정 엣지 집합에 대해 알아낼 수 있는 정보의 양이 줄어들며, 데이터베이스 내 100개의 엣지(1/0.01 = 100) 중 어느 것도 특정할 수 없음을 의미한다.
– 대규모의 사회적 연락처 그룹이 민감한 정보로 간주되지 않는 상황에서 유용

세분화 수준 확인, 데이터베이스의 단일 항목이 수정되더라도 알고리즘의 동작이 거의 변하지 않을 것
(e.g., 그래프 형태의 데이터베이스 – 소셜 네트워크에서의 데이터 레코드에서,
(1) 각 개인이 그래프에서의 한 정점(vertex), (2) 개인 간의 친구 관계가 엣지(edge)로 표현
– 각 개인 i ∈ [n]은 그래프에서 정점으로 표현됨)

All Small Epsilons Are Alike.
ε가 작을 때, (ε, 0)-differential privacy는 인접한 데이터베이스 x, y 및 모든 출력 o의 모든 쌍에 대해, adversary는 어느 것이 진정한 데이터베이스인지 구별할 수 없다고 주장한다. 즉, ε 값이 작다면 비록 서로 다른 ε 값들이라 할지라도, 그것들이 제공하는 프라이버시 보호의 정도는 유사하다는 것이다.
ε가 작을 때, (ε, 0)-differentially private와 메커니즘 (2ε, 0)-differentially private에 대해, 엡실론은 다르지만 작은 프라이버시 속성은 매우 비슷하다.
ε가 클 때, (15, 0)-differentially private가 되지 않는 이유는 단지 이웃 데이터베이스가 존재하고 데이터베이스에 따라 관찰할 확률의 비율이 각각 x 또는 y인 출력 o가 크다.

A Few Additional Formalisms.

1) 프라이버시 메커니즘의 보조 매개변수 w
메커니즘 M은 종종 데이터베이스 x 외에도 몇 가지 보조 매개 변수 w를 입력으로 사용한다.
w는 데이터베이스 x의 쿼리 \(q_w\) 또는 쿼리 \(Q_w\) 컬렉션을 지정할 수 있다.
M: privacy mechanism, 데이터베이스 x의 데이터를 처리하는 기능 또는 알고리즘, 개별 데이터 항목이 공개될 위험을 최소화하면서 데이터 분석 또는 쿼리를 허용
w: 보조 매개변수
\(q_w\): 쿼리 지정, 보조 매개변수(w)가 데이터베이스(x)에서 실행될 특정 쿼리(\(q_w\))를 지정한다.
– \(q_w(x)\)는 데이터베이스 x에 적용될 때 w 매개변수를 사용하는 쿼리의 결과를 나타내어, 데이터베이스 내 특정 정보를 추출하거나 분석하는 데 사용될 수 있다.
(e.g., 사용자들의 정보, \(q_w\): 30세 이상의 사용자 수는 몇 명인가?(개별 쿼리))
\(Q_w\): 쿼리 컬렉션을 정의(여러 쿼리)
– 여러 개의 쿼리 \(q_w\)를 포함한다.
(e.g., 나이, 지역, 직업 등 다양한 기준에 따른 사용자 수를 묻는 여러 쿼리들의 집합)

→ 모든 δ ≥ 0에 대해, 모든 w, M(w,·)에 대해 (ε, δ)-differential privacy를 만족한다면 메커니즘 M(·,·)이 (ε, δ)-differential privacy을 만족시킨다고 말한다.

2) 보안 매개변수 κ 및 무시할 수 있는 기능 δ
w에 포함될 수 있는 매개 변수의 또 다른 예는 δ = δ(κ)가 얼마나 작아야 하는지를 제어하는 security parameter κ이다.
κ: 알고리즘의 보안성과 직접적으로 관련된 매개변수, 알고리즘의 복잡성 조절
– κ가 증가하면 더 높은 보안 수준을 제공하지만 더 많은 계산 리소스가 필요하다.
– 보안성 평가: κ는 알고리즘의 보안성을 평가하는 데 중요한 역할을 한다.
δ: ε-차등 프라이버시를 완벽하게 만족하지 않더라도 매우 낮은 확률로 이를 위반할 수 있도록 허용하는 매개변수
(1) 프라이버시 보호의 확률적 확장: δ는 알고리즘이 ε-차등 프라이버시 조건을 어기는 경우 확률의 상한을 나타낸다. 알고리즘이 이론적으로는 ε-차등 프라이버시를 위반할 수 있으나, 그 확률이 δ 이하로 낮다는 것을 의미한다.
(2) 미세 조정 가능: δ는 보통 매우 작은 값으로 설정되며, 이 값은 알고리즘이 얼마나 ‘너그러울’ 수 있는지 결정한다. (δ가 0에 가까울수록, 알고리즘은 더 엄격한 프라이버시 보호를 제공한다.)
(3) 무시할 만한(negligible) 함수: δ의 값은 보안 매개변수 κ에 따라 결정되고, κ가 증가함에 따라 δ는 기하급수적으로 감소하여, 프라이버시 위반의 가능성을 극히 낮게 유지한다.

M(κ, ·)은 모든 κ에 대해 (ε, δ(κ))-differentially private해야 한다. 논문 전반에 걸쳐 δ가 δ = \(κ^{−ω(1)}\)에서 무시할 수 있는 기능일 것을 요구한다. (δ = \(κ^{−ω(1)}\)에서 ω(1)는 점근적 표기법의 일부로 사용, 매우 천천히 증가하는 함수이지만 결국 모든 상수값보다 크게 되는, 무한대로 증가하는 함수를 나타낸다.)
– δ를 암호학적으로 작은 것으로 생각하는 반면, ε는 일반적으로 적당히 작은 상수로 여겨진다.

3) 시놉시스 생성기
원본 데이터를 바탕으로 데이터의 통계적 특성을 유지하면서도 개인 정보를 보호할 수 있는 요약된 정보나 가공된 데이터 집합을 생성한다.
시놉시스 생성기의 작동 원리
(1) 데이터 요약: 원본 데이터베이스로부터 추출할 수 있는 통계적 특성 계산, 유사한 통계적 특성을 가진 합성 데이터나 요약 정보를 생성
(2) 노이즈 추가: 데이터의 통계적 특성을 계산하거나 합성 데이터를 생성할 때 노이즈를 추가
(3) 프라이버시와 유용성의 균형: 너무 많은 노이즈를 추가하면 데이터의 유용성 저하

A: 시놉시스 생성기의 출력(synopsis generator outputs), 분석 목적으로 데이터의 유용성을 유지하면서 개별 데이터베이스 항목에 대한 정보가 차등 개인 정보 보호 표준에 따라 보호되도록 설계된 원본 데이터베이스의 압축 또는 합성 표현
M: 메커니즘, 원본 데이터베이스에서 시놉시스를 생성하는 프로세스 또는 알고리즘, 공격자가 데이터베이스에 있는 개인의 특정 정보를 추론하는 것을 허용하지 않도록 차등 개인 정보 보호 원칙이 통합되어 있음, 예산과 매개변수를 고려하여 개인정보 보호-데이터 유용성 간 균형을 맞춤
– 분석 도구 A를 사용하여 원본 데이터로부터 시놉시스 A를 생성해야 한다.
R: 재구성 절차, 특정 쿼리에 대한 답변을 도출하는 데 사용되는 방법
– A와 v를 입력으로 받아 실수 \(\mathbb{R}\)에 속하는 결과 R(A, v)를 출력해야 한다.

→ 개인 정보를 엄격하게 보호하면서 민감한 데이터 세트를 분석할 수 있는 정교한 도구, 데이터에 표시된 개인의 기밀성을 손상시키지 않으면서 분석 및 의사 결정을 위한 데이터 활용을 가능하게 한다.

쿼리 \(Q_w = \{q : X^n → \mathbb{R}\}\)
: \(Q_w\)는 데이터베이스 \(X^n\)에서 실수 집합 \(\mathbb{R}\)로 매핑하는 쿼리들의 집합을 나타낸다.
쿼리 \(q_v \in Q_w\)를 지정하는 각 input v에 대해 R(A,v) ∈ \(\mathbb{R}\)을 출력하도록 하는 재구성 절차 R이 존재해야 한다. (e.g., 사람들의 정보를 포함하는 데이터베이스에 대해 특정 연산(예: 평균 연산)을 수행하고 실수 결과(예: 평균 나이)를 출력하는 함수들의 모음)
일반적으로 높은 확률로 M이 A를 사용하여 재구성 절차가 정확한 답을 계산할 수 있도록 시놉시스 A를 생성하도록 요구할 것이다. 즉, 쿼리 \(q_v \in Q_w\)의 전부 또는 대부분(일부 분포에 의해 가중치)의 경우, 오류 |R(A, v) − \(q_v(x)\)|가 제한될 것이다.
때때로 표기법을 남용하고 실제 쿼리 q(일부 표현 v가 아닌)를 입력하고 R(A, q)를 출력하는 재구성 절차를 참조할 것이다.

4) 합성 데이터베이스(synthetic database)
시놉시스 생성기의 출력
분석가가 원래 데이터베이스에서 사용하는 것과 동일한 소프트웨어를 사용하여 분석(원본 데이터를 모방하여 데이터 분석), 특별한 재구성 절차 없이 R의 필요성을 없애는 것

5) 부동 소수점(floating point) 연산 주의
노이즈를 추가하는 메커니즘을 구현할 때 플로팅 포인트 연산이 정확도에 미치는 영향을 고려해야 한다.
데이터베이스 x에서 0이 아닌 확률을 가진 출력이 반올림으로 인해 인접한 데이터베이스 y에서 0의 확률을 가질 수 있으므로 프라이버시가 파괴될 수 있다.
– 정밀도 손실, 누적 오차, 수치적 안정성
→ 고정 소수점 연산 사용, 오차를 고려한 알고리즘 설계, 추가적인 오차 분석 수행

Reference

• Cynthia Dwork and Aaron Roth, The Algorithmic Foundations of Differential Privacy, 2.3.1. What differential privacy promises
• Cynthia Dwork and Aaron Roth, The Algorithmic Foundations of Differential Privacy, 2.3.2. What differential privacy does not promise
• Cynthia Dwork and Aaron Roth, The Algorithmic Foundations of Differential Privacy, 2.3.3. Final remarks on the definition