A note on secure multiparty computation via higher residue symbols

Abstract We generalize a protocol by Yu for comparing two integers with relatively small difference in a secure multiparty computation setting. Yu's protocol is based on the Legendre symbol. A prime number p is found for which the Legendre symbol (· | p ) agrees with the sign function for integers in a certain range {− N , . . . , N } ⊂ ℤ. This can then be computed efficiently. We generalize this idea to higher residue symbols in cyclotomic rings ℤ[ ζ r ] for r a small odd prime. We present a way to determine a prime number p such that the r -th residue symbol (· | p ) r agrees with a desired function <m:math xmlns:m="http://www.w3.org/1998/Math/MathML" display="inline"> <m:mrow> <m:mi>f</m:mi> <m:mo>:</m:mo> <m:mi>A</m:mi> <m:mo>→</m:mo> <m:mrow> <m:mo>{</m:mo> <m:mrow> <m:msubsup> <m:mi>ζ</m:mi> <m:mi>r</m:mi> <m:mn>0</m:mn> </m:msubsup> <m:mo>,</m:mo> <m:mo>…</m:mo> <m:mo>,</m:mo> <m:msubsup> <m:mi>ζ</m:mi> <m:mi>r</m:mi> <m:mrow> <m:mi>r</m:mi> <m:mo>−</m:mo> <m:mn>1</m:mn> </m:mrow> </m:msubsup> </m:mrow> <m:mo>}</m:mo> </m:mrow> </m:mrow> </m:math> f:A \to \left\{ {\zeta _r^0, \ldots ,\zeta _r^{r - 1}} \right\} on a given small subset A ⊂ ℤ[ ζ r ], when this is possible. We also explain how to efficiently compute the r -th residue symbol in a secret shared setting.