Workshop on
Foundations of Computer Security - FCS'03
Ottawa, Canada, 26-27 June 2003
Oblivious Comparator and its Application to Secure Auction Protocol
Hiroaki Kikuchi (Tokai University - Japan)
Abstract
This paper presents a protocol for Secure Function Evaluation (SFC) in which n
players have secret inputs E[a1], E[a2], ... , E[an], of a known boolean
function f, and they collaborate to compute the ciphertext of the output of
the boolean function, E[f(a1, ... , an)] . The main result is a completeness
theorem (Theorem 3.1) which states that an arbitrary function can be evaluated
at the oblivious party without help ofprivate information. The proposed
protocol is based on the Jakobsson and Juels's Mix-and-Match scheme in which
the truth table of a target function is row-wise randomized (mixing) using a
Mix network, and then players perform ``matching'' the designated output
ciphertext and the corresponding rows. The biggest difference between the
proposed SFC and the Mix-and-Match is that the proposed protocol does not
require any involution of key holders to evaluate function, while the
Mix-and-Match needs key holders to perform threshold decryptions at every step
of evaluation of boolean gates. One disadvantage of the proposed scheme is
the Reed-Muller expansion involves an exponential blow-up in the number of
input, n, as conventional schemes such as CyptoComputer proposed by Sander,
Young, and Yung. This paper presents an efficient construction for a
primitive called `oblivious comparator' with n-round complexity between the
comparator and n players but the bandwidth spent by one communication is
independent from n (linear to the size of values to be compared), and hence it
does not suffer the blow-up in n. The oblivious comparator is suitable to
implement a secure auction because an auctioneer communicates with bidders
once at time, and performs evaluation without help of trusted key holders. In
addition, the proposed construction allows arbitrary complicated functions
including a search for second highest, a resolution the winner, and a dynamic
programming (for combinatorial auction).