A note on secure multiparty computation via higher residue symbols

Ignacio Cascudo, Reto Alexander Schnyder*

*Corresponding author

Research output: Contribution to journalJournal articleResearchpeer-review

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→{ζr0,…,ζrr−1}f:A \to \left\{ {\zeta _r^0, \ldots ,\zeta _r^{r - 1}} \right\} 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 languageEnglish
JournalJournal of Mathematical Cryptology
Volume15
Issue number1
Pages (from-to)284-297
Number of pages14
ISSN1862-2976
DOIs
Publication statusPublished - 29 Jan 2021

Keywords

  • Cyclotomic rings
  • Power residue symbol
  • Secure multiparty computation

Fingerprint Dive into the research topics of 'A note on secure multiparty computation via higher residue symbols'. Together they form a unique fingerprint.

Cite this