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. We generalize this idea to higher residue symbols in cyclotomic rings ℤ[ζr] for r a small odd prime. We present a way to determine a prime number p such that the r-th residue symbol (· | p)r agrees with a desired function f : A → {ζ0r, ⋯, ζr-1r} on a given small subset A ⊂ ℤ[ζr], when this is possible. We also explain how to efficiently compute the r-th residue symbol in a secret shared setting.
Original language | English |
---|---|
Journal | Journal of Mathematical Cryptology |
Volume | 15 |
Issue number | 1 |
Pages (from-to) | 284-297 |
Number of pages | 14 |
ISSN | 1862-2976 |
DOIs | |
Publication status | Published - 29 Jan 2021 |
Keywords
- Cyclotomic rings
- Power residue symbol
- Secure multiparty computation