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, \ldots, 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 $(\cdot \mid p)_r$ 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
 Published elsewhere. Journal of Mathematical Cryptology
 DOI
 10.1515/jmc20200013
 Keywords
 secure multiparty computationcyclotomic ringspower residue symbol
 Contact author(s)
 reto @ math aau dk
 History
 20210302: last of 2 revisions
 20200218: received
 See all versions
 Short URL
 https://ia.cr/2020/183
 License

CC BY
BibTeX
@misc{cryptoeprint:2020/183, author = {Ignacio Cascudo and Reto Schnyder}, title = {A note on secure multiparty computation via higher residue symbols}, howpublished = {Cryptology {ePrint} Archive, Paper 2020/183}, year = {2020}, doi = {10.1515/jmc20200013}, url = {https://eprint.iacr.org/2020/183} }