Private Information Retrieval with Information Leakage under KL Divergence and JS Divergence

Abstract

In this dissertation, two main contributions are given as; Private information retrieval with information leakage under the Kullback-Leibler divergence is formulated and solved. Private information retrieval with information leakage under the Jensen-Shannon divergence is formulated and solved.

First, the private information retrieval (PIR) problem with information leakage is proposed with the Kullback-Leibler (KL) divergence. The amount of information leakage is measured by the KL divergence. The divergence is from the given reference probability distribution causing no information leakage in the PIR system to an arbitrary probability distribution of user's choice. Information leakage can be helpful in terms of the performance of the PIR system, that is, the download cost. In other words, allowing information leakage enables us to reduce the download cost of the PIR problem. We want to restrict the problem as efficiently as possible, and thus, the optimal tradeoff between the information leakage and the download cost is being considered. The problem is formulated as an optimization problem and solved using convex optimization. Furthermore, we propose an alternative PIR scheme with less message length that shows a better tradeoff than the existing PIR scheme in some tradeoff intervals.

Second, the same private information retrieval problem with information leakage is proposed but with the Jensen-Shannon (JS) divergence. The JS divergence is based on the KL divergence. The divergence occurs from the difference in probability distributions among the user's desired messages. Similar to the KL divergence, it captures the dissimilarity among the probability distributions but with some desirable features. One of the advantages it gives is that it can measure the dissimilarity of more than two probability distributions, which makes the problem more general. More specifically, the problem formulated with JS divergence does not need the given reference probability distribution causing no information leakage in the PIR system. The tradeoff between the information leakage measured by the JS divergence and the download cost is formulated as a convex optimization problem and solved with numerical solutions.

이 논문에서의 두 가지 주요 공헌은 다음과 같다. Kullback-Leibler 발산으로 측정한 정보 누출이 존재하는 개인 정보 검색 문제를 만들고 해결하였다. Jensen-Shannon 발산으로 측정한 정보 누출이 존재하는 개인 정보 검색 문제를 만들고 해결하였다.

첫째로, Kullback-Leibler 발산을 사용하여 정보 누출이 존재하는 개인 정보 검색 문제를 제안한다. 정보 누출량은 Kullback-Leibler 발산으로 측정된다. 발산이 가지는 의미는 개인 정보 검색 시스템에 누출이 없게 되는 기준이 되는 특정 분포로부터 사용자가 선택할 수 있는 임의 분포로의 차이를 측정한 것이다. 정보 누출은 개인 정보 검색 시스템의 성능인 다운로드 비용 측면에서 도움을 줄 수 있다. 가능한 한 효율적으로 정보 누출을 이용하는 방법을 찾고자 하였으며 정보 누출과 다운로드 비용 간의 최적의 균형 지점을 찾는 문제를 제시하였다. 이 문제는 컨벡스 최적화 문제로 만들어 해결하였다. 또한, 일부 트레이드 오프 구간에서 기존의 개인 정보 검색 방식보다 더 나은 성능을 보여주는 메시지 길이가 더 짧은 개인 정보 검색 방식을 제안하였다.

둘째로, Jensen-Shannon 발산을 사용하여 정보 누출이 존재하는 개인 정보 검색 문제를 제안한다. Jensen-Shannon 발산은 Kullback-Leibler 발산을 기반으로 하는 확률 분포 사이의 비유사성을 나타내는 값이다. 사용자가 원하는 메시지가 무엇이냐에 따라 사용자가 선택할 수 있는 확률 분포의 차이가 발생하고 그 확률 분포들 간의 발산을 측정한다. Jensen-Shannon 발산에는 몇 가지 적절한 특징이 있는데 그 중 하나는 3 개 이상의 확률 분포 간의 비유사성을 측정할 수 있다는 것이다. 이를 이용하여 Jensen-Shannon 발산으로 공식화 된 문제에는 개인 정보 검색 시스템에 누출이 없게 되는 기준이 되는 특정 분포가 필요하지 않다. Jensen-Shannon 발산으로 측정된 정보 누출과 다운로드 비용 간의 균형 지점은 컨벡스 최적화 문제로 만들 수 있으며, 시뮬레이션을 통한 솔루션이 제시되었다.