For privacy-preserving comparison, is it possible to represent the function of $f(a,b)=\max\{a,b\}$ as a binary polynomial $p(a,b)$?

  • $\begingroup$ You have boolean comparator circuits, and maybe you could have another function to just output the larger one determined by the previous circuit. For privacy, you can garble the circuit, other techniques can be used as well. $\endgroup$ – user2505282 Apr 28 '19 at 11:01

I found the following solution due to Damgard et al.

[1]. Ivan Damgard, Martin Geisler, and Mikkel Kroigaard. Efficient and Secure Comparison for On-Line Auctions. ACISP 2007, LNCS 4586, pp. 416-430, 2007.

Background. Given the binary represetations of $m=m_{\ell}..m_1$ and $x=x_{\ell}..x_1$, let $$w_i=m_i\oplus x_i\quad\mbox{and}\quad c_i=x_i-m_i+1+\sum_{j=i+1}^{\ell} w_j,$$ then if $m>x$ there is exactly one position $i$ where $c_i=0$, otherwise, no such position exists. (Please see Page 423 of [1].)

A maple code:


pcomp := proc (a, b)

local abin, bbin, la, lb, w, v, c, i, f;

abin := convert(a, 'base', 2); la := nops(abin);

bbin := convert(b, 'base', 2); lb := nops(bbin);

if la < lb then

abin := [seq(abin[i], i = 1 .. la), seq(0, i = 1 .. lb-la)]; la := lb;

elif lb < la then

bbin := [seq(bbin[i], i = 1 .. lb), seq(0, i = 1 .. la-lb)]; lb := la;

end if;

w := [seq(Xor(abin[i], bbin[i]), i = 1 .. la)];

c := [seq(bbin[i]-abin[i]+1+sum(w[j], j = i+1 .. la), i = 1 .. la)];

for i to la do

if c[i] = 0 then f := 1; return f; end if;

end do;

f := 0; return f;

end proc;

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.