earticle

영어

This paper deals with the problem in which users require to compute a set which only have elements of which frequency is greater than or equal to a threshold value α while keeping their private multisets from other users secret. To this end, we use as a main cryptographic tool, commutative encryption to address the privacy issue in this problem. Commutative encryption allows to protect the elements of sets from being revealed to others while preserving its computational efficiency. Further, we apply the Bloom filter to improve the transmission amount between users during execution of the protocol.

한국어

본 논문은 사용자가 소유한 각자의 집합을 Xi 라 할 때, 모든 사용자 집합들의 합집합 Y = ∪Xi 에 대하여 Y 에 속하는 각 원소들의 빈도수가 임계값 (Threshold) α 보다 자주 나타나는 원소들로만 구성된 집합을 효율적으로 계산하는 방법을 설계하고 분석하는 것이다. 특히 각 사용자가 자신의 집 합을 공개하지 않은 상태에서 효율적으로 이러한 집합을 얻기 위한 것이다. 본 논문에서는 이러한 목 적을 달성하기 위해, 암호학적 도구로 가환암호를 사용하여 사용자가 자신의 집합의 원소를 외부에 공개하지 않은 상태에서 목적으로 하는 집합만 계산할 수 있는 Protocol을 설계한다. 추가로 제안하는 Protocol이 암호학적으로 안전하다는 것을 암호학적 가정을 기반으로 자세히 증명한다. 가환암호 는 안전성의 보장과 연산의 효율성을 동시에 제공해주며, 추가로 Protocol 수행하는 도중 전송 효율성을 개선하기 위하여 Bloom filter를 어떻게 적용할 수 있는지 제시한다.