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.

Keywords

• secure multiparty computation
• cyclotomic rings
• power residue symbol
• 11t71
• 94a60