Variable-Length Coding with Zero and Non-Zero Privacy Leakage

Area of Science:

• Information Theory
• Data Compression
• Cybersecurity

Background:

• Addresses private compression where data Y is correlated with private attribute X.
• Encoder uses a private compression mechanism to create an encoded message C.
• An adversary attempts to estimate X from the encoded message C.

Purpose of the Study:

• To design an encoded message C with minimum average length under privacy constraints.
• To investigate scenarios with zero (perfect) and non-zero (non-perfect) privacy leakage.
• To improve existing bounds on data compression with privacy.

Main Methods:

• Linear programming to find upper bounds on optimizer entropy for perfect privacy.
• Two-part construction coding for achieving upper bounds in specific cases.
• Minimum entropy coupling and greedy entropy-based algorithms to strengthen bounds.
• Analysis of upper and lower bounds using different privacy metrics for non-perfect privacy.

Main Results:

• Strengthened existing bounds for private compression, particularly when |X|≥|Y| or for specific joint distributions.
• Achieved upper bounds using two-part construction coding, improving upon prior results.
• Derived and analyzed bounds for non-perfect privacy scenarios, demonstrating asymptotic tightness in examples.

Conclusions:

• Developed novel private compression techniques balancing data compression efficiency and privacy.
• Established new theoretical bounds and practical coding strategies for secure data transmission.
• The proposed methods offer improved performance over existing approaches for private information retrieval.