基於同代像加密法秘密計算富翁問題

Abstract

我們提出了一個可以秘密計算富翁問題的協定, 而這個協定可以在semi-honest 假設下被證明是安全的。我們的協定可以透過加法或者乘法的同代像加密法(homomorphic encryption schemes)來建構。在以前提出的協定中,都是以加法或者XOR特性的同代像加密法來建構。在計算量與傳輸量上, 我們的協定與之前的協定是在同樣的漸近等級(asymptotic order)。然而因為乘法同代像加密法在實作上比加法同代像加密法來得有效率, 使得我們的協定在實作上可以保有這樣的優點。

We proposed a two-round protocol for solving the Millionaires' Problem in the setting of semi-honest parties. Our protocol uses either multiplicative or additive homomorphic encryptions. Previously proposed protocols used additive or XOR homomorphic encryption schemes only. The computation and communication costs of our protocol are in the same asymptotic order as those of the other efficient protocols. Nevertheless, since multiplicative homomorphic encryption scheme is more efficient than an additive one practically, our construction saves computation time and communication bandwidth in practicality.