TY - JOUR
T1 - A note on secure multiparty computation via higher residue symbols
AU - Cascudo, Ignacio
AU - Schnyder, Reto Alexander
PY - 2021/1/29
Y1 - 2021/1/29
N2 - 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.
AB - 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.
KW - Cyclotomic rings
KW - Power residue symbol
KW - Secure multiparty computation
UR - http://www.scopus.com/inward/record.url?scp=85101630275&partnerID=8YFLogxK
U2 - 10.1515/jmc-2020-0013
DO - 10.1515/jmc-2020-0013
M3 - Journal article
SN - 1862-2976
VL - 15
SP - 284
EP - 297
JO - Journal of Mathematical Cryptology
JF - Journal of Mathematical Cryptology
IS - 1
ER -