{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T00:40:23Z","timestamp":1764981623543,"version":"3.46.0"},"reference-count":12,"publisher":"Walter de Gruyter GmbH","issue":"1","license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021,1,1]]},"abstract":"Abstract<\/jats:title>\n \n 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\n p<\/jats:italic>\n is found for which the Legendre symbol (\u00b7 |\n p<\/jats:italic>\n ) agrees with the sign function for integers in a certain range {\u2212\n N<\/jats:italic>\n , . . . ,\n N<\/jats:italic>\n } \u2282 \u2124. This can then be computed efficiently.\n <\/jats:p>\n \n We generalize this idea to higher residue symbols in cyclotomic rings \u2124[\n \n \u03b6\n r<\/jats:sub>\n <\/jats:italic>\n ] for\n r<\/jats:italic>\n a small odd prime. We present a way to determine a prime number\n p<\/jats:italic>\n such that the\n r<\/jats:italic>\n -th residue symbol (\u00b7 |\n p<\/jats:italic>\n )\n \n r<\/jats:italic>\n <\/jats:sub>\n agrees with a desired function\n \n \n \n \n \n f<\/m:mi>\n :<\/m:mo>\n A<\/m:mi>\n \u2192<\/m:mo>\n \n {<\/m:mo>\n \n \n \u03b6<\/m:mi>\n r<\/m:mi>\n 0<\/m:mn>\n <\/m:msubsup>\n ,<\/m:mo>\n \u2026<\/m:mo>\n ,<\/m:mo>\n \n \u03b6<\/m:mi>\n r<\/m:mi>\n \n r<\/m:mi>\n \u2212<\/m:mo>\n 1<\/m:mn>\n <\/m:mrow>\n <\/m:msubsup>\n <\/m:mrow>\n }<\/m:mo>\n <\/m:mrow>\n <\/m:mrow>\n <\/m:math>\n f:A \\to \\left\\{ {\\zeta _r^0, \\ldots ,\\zeta _r^{r - 1}} \\right\\}<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n on a given small subset\n A<\/jats:italic>\n \u2282 \u2124[\n \n \u03b6\n r<\/jats:sub>\n <\/jats:italic>\n ], when this is possible. We also explain how to efficiently compute the\n r<\/jats:italic>\n -th residue symbol in a secret shared setting.\n <\/jats:p>","DOI":"10.1515\/jmc-2020-0013","type":"journal-article","created":{"date-parts":[[2021,2,20]],"date-time":"2021-02-20T18:42:12Z","timestamp":1613846532000},"page":"284-297","source":"Crossref","is-referenced-by-count":0,"title":["A note on secure multiparty computation via higher residue symbols"],"prefix":"10.1515","volume":"15","author":[{"given":"Ignacio","family":"Cascudo","sequence":"first","affiliation":[{"name":"IMDEA Software Institute , 28223 Pozuelo de Alarcon , Madrid , Spain ; Much of this work was carried out while Ignacio was with the Department of Mathematical Sciences , Aalborg University , Denmark ."}]},{"given":"Reto","family":"Schnyder","sequence":"additional","affiliation":[{"name":"Department of Mathematical Sciences , Aalborg University , Aalborg , Denmark"}]}],"member":"374","published-online":{"date-parts":[[2021,1,29]]},"reference":[{"key":"2025120600333867779_j_jmc-2020-0013_ref_001","doi-asserted-by":"crossref","unstructured":"M. Abspoel, N. J. Bouman, B. Schoenmakers and N. de Vreede, Fast Secure Comparison for Medium-Sized Integers and Its Application in Binarized Neural Networks, in: Topics in Cryptology \u2013 CT-RSA 2019 (M. Matsui, ed.), Springer, Cham, pp. 453\u2013472, 2019.","DOI":"10.1007\/978-3-030-12612-4_23"},{"key":"2025120600333867779_j_jmc-2020-0013_ref_002","doi-asserted-by":"crossref","unstructured":"J. Bar-Ilan and D. Beaver, Non-Cryptographic Fault-Tolerant Computing in Constant Number of Rounds of Interaction, in: Proc. 8th ACM Symp. on Principles of Distributed Computing, PODC \u201989, pp. 201\u2013209, ACM, New York, 1989.","DOI":"10.1145\/72981.72995"},{"key":"2025120600333867779_j_jmc-2020-0013_ref_003","doi-asserted-by":"crossref","unstructured":"Y. F. Bilu, Y. Bugeaud and M. Mignotte, The Problem of Catalan, Springer, Cham, 2014.","DOI":"10.1007\/978-3-319-10094-4"},{"key":"2025120600333867779_j_jmc-2020-0013_ref_004","doi-asserted-by":"crossref","unstructured":"R. Cramer, I. B. Damg\u00e5rd and J. B. Nielsen, Secure Multiparty Computation and Secret Sharing, Cambridge University Press, New York, 2015.","DOI":"10.1017\/CBO9781107337756"},{"key":"2025120600333867779_j_jmc-2020-0013_ref_005","doi-asserted-by":"crossref","unstructured":"I. Damg\u00e5rd, M. Fitzi, E. Kiltz, J. B. Nielsen and T. Toft, Unconditionally Secure Constant-Rounds Multi-party Computation for Equality, Comparison, Bits and Exponentiation, in: Theory of Cryptography (S. Halevi and T. Rabin, eds.), Springer, Berlin, Heidelberg, pp. 285\u2013304, 2006.","DOI":"10.1007\/11681878_15"},{"key":"2025120600333867779_j_jmc-2020-0013_ref_006","unstructured":"C. Dwork, Lattices and Their Application to Cryptography, Lecture Notes, Stanford University, 1998."},{"key":"2025120600333867779_j_jmc-2020-0013_ref_007","doi-asserted-by":"crossref","unstructured":"U. Feige, J. Killian and M. Naor, A Minimal Model for Secure Computation, in: Proc. 26th ACM Symp. on Theory of Computing, STOC \u201994, pp. 554\u2013563, ACM, New York, 1994.","DOI":"10.1145\/195058.195408"},{"key":"2025120600333867779_j_jmc-2020-0013_ref_008","doi-asserted-by":"crossref","unstructured":"K. Ireland and M. Rosen, A Classical Introduction to Modern Number Theory, 2nd ed, Graduate Texts in Mathematics 84, Springer-Verlag, New York, 1990.","DOI":"10.1007\/978-1-4757-2103-4"},{"key":"2025120600333867779_j_jmc-2020-0013_ref_009","doi-asserted-by":"crossref","unstructured":"T. Nishide and K. Ohta, Multiparty Computation for Interval, Equality, and Comparison Without Bit-Decomposition Protocol, in: Public Key Cryptography \u2013 PKC 2007 (T. Okamoto and X. Wang, eds.), pp. 343\u2013360, Springer, Berlin, Heidelberg, 2007.","DOI":"10.1007\/978-3-540-71677-8_23"},{"key":"2025120600333867779_j_jmc-2020-0013_ref_010","doi-asserted-by":"crossref","unstructured":"A. Shamir, How to Share a Secret, Commun. ACM 22 (1979), 612\u2013613.","DOI":"10.1145\/359168.359176"},{"key":"2025120600333867779_j_jmc-2020-0013_ref_011","unstructured":"W. A. Stein et al., Sage Mathematics Software (Version 9.1), The Sage Development Team, 2020."},{"key":"2025120600333867779_j_jmc-2020-0013_ref_012","unstructured":"C.-H. Yu, Sign Modules in Secure Arithmetic Circuits., Cryptology ePrint Archive, Report 2011\/539, 2011."}],"container-title":["Journal of Mathematical Cryptology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2020-0013\/xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2020-0013\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T00:35:36Z","timestamp":1764981336000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2020-0013\/html"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,1]]},"references-count":12,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2021,4,20]]},"published-print":{"date-parts":[[2021,4,20]]}},"alternative-id":["10.1515\/jmc-2020-0013"],"URL":"https:\/\/doi.org\/10.1515\/jmc-2020-0013","relation":{},"ISSN":["1862-2984"],"issn-type":[{"type":"electronic","value":"1862-2984"}],"subject":[],"published":{"date-parts":[[2021,1,1]]}}}