Welcome to the resource topic for 2020/183
Title:
A note on secure multiparty computation via higher residue symbols
Authors: Ignacio Cascudo, 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.
ePrint: https://eprint.iacr.org/2020/183
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .