Paper 2020/183

A note on secure multiparty computation via higher residue symbols

Ignacio Cascudo and Reto Schnyder

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 $(\cdot \mid p)$ agrees with the sign function for integers in a certain range $\{-N,\dots ,N\}\subset \mathbb{Z}$. This can then be computed efficiently. We generalize this idea to higher residue symbols in cyclotomic rings $\mathbb{Z}[{\zeta }_r]$ for $r$ a small odd prime. We present a way to determine a prime number $p$ such that the $r$-th residue symbol $$ agrees with a desired function $$ on a given small subset $$, when this is possible. We also explain how to efficiently compute the $$-th residue symbol in a secret shared setting.