Paper 2020/183
A Note on Secure Multiparty Computation via Higher Residue Symbol Techniques
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 in $\mathbb{F}_p$ agrees with the sign function for integers in a certain range $\{-N, \ldots, N\}$. 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 $f\colon A \to \{\zeta_r^0, \ldots, \zeta_r^{r - 1}\}$ on a given small subset $A \subset \mathbb{Z}[\zeta_r]$, when this is possible. We also explain how to efficiently compute the $r$-th residue symbol in a secret shared setting.
Metadata
- Available format(s)
- Category
- Cryptographic protocols
- Publication info
- Preprint. MINOR revision.
- Keywords
- secure multi-party computation
- Contact author(s)
- reto @ math aau dk
- History
- 2021-03-02: last of 2 revisions
- 2020-02-18: received
- See all versions
- Short URL
- https://ia.cr/2020/183
- License
-
CC BY