README.md

[toc]

Introdcution

Useful tools for local differential privacy, which mainly consists of several parts:

• basis
  • ldplib: local differential privacy library
  • kvlib: key-value library
  • mdlib: missing data library
• heavy_hitters
  • hadamard_response
  • k_random_response
  • k_subset
  • rappor
• mean_solutions
  • duchi
  • piecewise

ldplib

The ldplib provides basic randomized functions.

• eps2p: turn the privacy budget to the probability by coin flipping
• discretization: used to discretize a continuous value
• RR: Randomized Response: A Survey Technique for Eliminating Evasive Answer Bias
• Unary Encoding: from paper Locally Differentially Private Protocols for Frequency Estimation
• SUE: symmetric unary encoding from paper Locally Differentially Private Protocols for Frequency Estimation
• OUE: optimized unary encodingfrom paper Locally Differentially Private Protocols for Frequency Estimation

kvlib

Some basic encoding terms:

• kv: a kv pair denoted as $\langle k, v\rangle$, where $k\in {0,1}, v\in[-1,1]$.
• kvl: a list of key-value pairs, denoted by $[\langle k_1, v_1\rangle,\langle k_2, v_2\rangle...]$. The kvl is used to represent the $i-$th key-value or to represent a list of key-value pairs of one user.
• kvt: a $n\times d$ key-value table. A kvt is used to represent the kvl from $n$ users.

The kvlib main contains the following perturbation and analysis algorithms:

• PrivBV: PrivKV: Key-Value Data Collection with Local Differential Privacy
• BiSample: BiSample: Bidirectional Sampling for Handling Missing Data with Local Differential Privacy.
• SE: from paper Conditional Analysis for Key-Value Data with Local Differential Privacy

heavy_hitters

• Hadamard Repsonse: Hadamard Response: Estimating Distributions Privately, Efficiently, and with Little Communication
• k-RR: the k-randomized response
• k-subset:
• RAPPOR: RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response

mean_solutions

• duchi: also known as the 1Bit Mechanism (noted that the input domain of 1Bit is [1,m], while the input domain of duchi is [-1,1]).
• PM: Collecting and Analyzing Multidimensional Data with Local Differential Privacy