Differential Privacy over Hamming Codes
This work provides a method to enhance privacy in communication systems without sacrificing utility, relevant for privacy-preserving data transmission.
The authors show that by optimally arranging codewords in Hamming codes, differential privacy guarantees can be improved without adding noise or increasing error probability, achieving a strict privacy gain for free.
We consider the transmission of the outputs of counting queries over a binary symmetric channel (BSC), where Hamming codes are employed as the channel encoder. Since the channel is inherently noisy, this transmission already provides a degree of privacy protection ``for free'', albeit at the cost of reduced utility in the form of decoding errors. A natural question is whether this privacy can be further improved (i) without any additional real-time obfuscation of the data, such as injecting artificial noise prior to transmission, and (ii) without increasing the end-to-end error probability. In this work, we answer this question in the affirmative by deriving an optimal codeword arrangement that strictly improves differential privacy guarantees while incurring no real-time computational overhead and no degradation in utility.