{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T10:52:44Z","timestamp":1778064764756,"version":"3.51.4"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"12","license":[{"start":{"date-parts":[[2023,8,16]],"date-time":"2023-08-16T00:00:00Z","timestamp":1692144000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,8,16]],"date-time":"2023-08-16T00:00:00Z","timestamp":1692144000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP21K17702"],"award-info":[{"award-number":["JP21K17702"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP23H00479"],"award-info":[{"award-number":["JP23H00479"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001695","name":"Japan Science and Technology Corporation","doi-asserted-by":"crossref","award":["JPMJCR22M1"],"award-info":[{"award-number":["JPMJCR22M1"]}],"id":[{"id":"10.13039\/501100001695","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"crossref","award":["JP20J20797"],"award-info":[{"award-number":["JP20J20797"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"crossref","award":["JP20J00469"],"award-info":[{"award-number":["JP20J00469"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"crossref","award":["JP19H01109"],"award-info":[{"award-number":["JP19H01109"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001695","name":"Japan Science and Technology Corporation","doi-asserted-by":"publisher","award":["JPMJCR2113"],"award-info":[{"award-number":["JPMJCR2113"]}],"id":[{"id":"10.13039\/501100001695","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001695","name":"Japan Science and Technology Corporation","doi-asserted-by":"publisher","award":["JPMJCR22U5"],"award-info":[{"award-number":["JPMJCR22U5"]}],"id":[{"id":"10.13039\/501100001695","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Des. Codes Cryptogr."],"published-print":{"date-parts":[[2023,12]]},"abstract":"Abstract<\/jats:title>Private Simultaneous Messages (PSM) model is a minimal model for secure multiparty computation. Feige, Kilian, and Naor (STOC 1994) and Ishai (Cryptology and Information Security Series 2013) constructed PSM protocols based on quadratic residues. In this paper, we define QR-PSM protocols as a generalization of these protocols. A QR-PSM protocol is a PSM protocol whose decoding function outputs the quadratic residuosity modulo p<\/jats:italic> of what is computed from messages. We design a QR-PSM protocol for any symmetric function $$f: \\{0,1\\}^n \\rightarrow \\{0,1\\}$$<\/jats:tex-math>\n \n f<\/mml:mi>\n :<\/mml:mo>\n \n \n {<\/mml:mo>\n 0<\/mml:mn>\n ,<\/mml:mo>\n 1<\/mml:mn>\n }<\/mml:mo>\n <\/mml:mrow>\n n<\/mml:mi>\n <\/mml:msup>\n \u2192<\/mml:mo>\n \n {<\/mml:mo>\n 0<\/mml:mn>\n ,<\/mml:mo>\n 1<\/mml:mn>\n }<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> of communication complexity $$O(n^2)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n \n n<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. As far as we know, it is the most efficient PSM protocol for symmetric functions since the previously known best PSM protocol was of $$O(n^2\\log n)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n \n n<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n log<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> (Beimel et al., CRYPTO 2014). We also study the sizes of the underlying finite fields $$\\mathbb {F}_p$$<\/jats:tex-math>\n \n F<\/mml:mi>\n p<\/mml:mi>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> in the protocols since the communication complexity of a QR-PSM protocol is proportional to the bit length of the prime p<\/jats:italic>. We show that there is a prime $$p \\le (1+o(1))N^22^{2N-2}$$<\/jats:tex-math>\n \n p<\/mml:mi>\n \u2264<\/mml:mo>\n \n (<\/mml:mo>\n 1<\/mml:mn>\n +<\/mml:mo>\n o<\/mml:mi>\n \n (<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n )<\/mml:mo>\n <\/mml:mrow>\n \n N<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n \n 2<\/mml:mn>\n \n 2<\/mml:mn>\n N<\/mml:mi>\n -<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> such that any length-N<\/jats:italic> pattern of quadratic (non)residues appears modulo p<\/jats:italic> (and hence it can be used for general QR-PSM protocols), which improves the Peralta\u2019s known result (Mathematics of Computation 1992) by a constant factor $$(1+\\sqrt{2})^2$$<\/jats:tex-math>\n \n \n (<\/mml:mo>\n 1<\/mml:mn>\n +<\/mml:mo>\n \n 2<\/mml:mn>\n <\/mml:msqrt>\n )<\/mml:mo>\n <\/mml:mrow>\n 2<\/mml:mn>\n <\/mml:msup>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>.<\/jats:p>","DOI":"10.1007\/s10623-023-01279-5","type":"journal-article","created":{"date-parts":[[2023,8,16]],"date-time":"2023-08-16T12:02:15Z","timestamp":1692187335000},"page":"3915-3932","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Private simultaneous messages based on quadratic residues"],"prefix":"10.1007","volume":"91","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5219-1975","authenticated-orcid":false,"given":"Kazumasa","family":"Shinagawa","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Reo","family":"Eriguchi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shohei","family":"Satake","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Koji","family":"Nuida","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,8,16]]},"reference":[{"key":"1279_CR1","volume-title":"The Probabilistic Method","author":"N Alon","year":"2016","unstructured":"Alon N., Spencer J.H.: The Probabilistic Method. Wiley, New York (2016)."},{"issue":"4","key":"1279_CR2","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1002\/net.3230230404","volume":"23","author":"W Ananchuen","year":"1993","unstructured":"Ananchuen W., Caccetta L.: On the adjacency properties of Paley graphs. Networks 23(4), 227\u2013236 (1993).","journal-title":"Networks"},{"key":"1279_CR3","first-page":"89","volume":"36","author":"W Ananchuen","year":"1993","unstructured":"Ananchuen W., Caccetta L.: On tournaments with a prescribed property. Ars Combinatoria 36, 89\u201396 (1993).","journal-title":"Ars Combinatoria"},{"issue":"3","key":"1279_CR4","doi-asserted-by":"publisher","first-page":"917","DOI":"10.1007\/s00145-019-09334-y","volume":"33","author":"B Applebaum","year":"2020","unstructured":"Applebaum B., Holenstein T., Mishra M., Shayevitz O.: The communication complexity of private simultaneous messages, revisited. J. Cryptol. 33(3), 917\u2013953 (2020).","journal-title":"J. Cryptol."},{"key":"1279_CR5","doi-asserted-by":"crossref","unstructured":"Assouline, L., Liu, T.: Multi-party PSM, revisited. In: TCC 2021, pp. 194\u2013223 (2021). Springer","DOI":"10.1007\/978-3-030-90453-1_7"},{"issue":"3","key":"1279_CR6","doi-asserted-by":"publisher","first-page":"532","DOI":"10.1112\/plms\/83.3.532","volume":"83","author":"RC Baker","year":"2001","unstructured":"Baker R.C., Harman G., Pintz J.: The difference between consecutive primes, II. Proc. London Math. Soc. 83(3), 532\u2013562 (2001).","journal-title":"Proc. London Math. Soc."},{"key":"1279_CR7","unstructured":"Ball, M., Holmgren, J., Ishai, Y., Liu, T., Malkin, T.: On the complexity of decomposable randomized encodings, or: how friendly can a garbling-friendly PRF be? In: 11th Innovations in Theoretical Computer Science Conference (ITCS 2020) (2020). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik"},{"key":"1279_CR8","unstructured":"Ball, M., Randolph, T.: A note on the complexity of private simultaneous messages with many parties. In: 3rd Conference on Information-Theoretic Cryptography (ITC 2022) (2022). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik"},{"key":"1279_CR9","doi-asserted-by":"crossref","unstructured":"Beimel, A., Gabizon, A., Ishai, Y., Kushilevitz, E., Meldgaard, S., Paskin-Cherniavsky, A.: Non-interactive secure multiparty computation. In: CRYPTO 2014, pp. 387\u2013404 (2014). Springer","DOI":"10.1007\/978-3-662-44381-1_22"},{"key":"1279_CR10","doi-asserted-by":"crossref","unstructured":"Beimel, A., Ishai, Y., Kumaresan, R., Kushilevitz, E.: On the cryptographic complexity of the worst functions. In: TCC 2014, pp. 317\u2013342 (2014). Springer","DOI":"10.1007\/978-3-642-54242-8_14"},{"key":"1279_CR11","doi-asserted-by":"crossref","unstructured":"Beimel, A., Kushilevitz, E., Nissim, P.: The complexity of multiparty PSM protocols and related models. In: EUROCRYPT 2018, pp. 287\u2013318 (2018). Springer","DOI":"10.1007\/978-3-319-78375-8_10"},{"issue":"4","key":"1279_CR12","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1002\/jgt.3190050414","volume":"5","author":"A Blass","year":"1981","unstructured":"Blass A., Exoo G., Harary F.: Paley graphs satisfy all first-order adjacency axioms. J. Graph Theory 5(4), 435\u2013439 (1981).","journal-title":"J. Graph Theory"},{"issue":"1","key":"1279_CR13","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/S0195-6698(81)80015-7","volume":"2","author":"B Bollob\u00e1s","year":"1981","unstructured":"Bollob\u00e1s B., Thomason A.: Graphs which contain all small graphs. Eur. J. Combinatorics 2(1), 13\u201315 (1981).","journal-title":"Eur. J. Combinatorics"},{"key":"1279_CR14","doi-asserted-by":"publisher","DOI":"10.11575\/cdm.v4i1.61874","author":"A Bonato","year":"2009","unstructured":"Bonato A.: The search for $$n$$-e.c. graphs. Contrib. Discret. Math. (2009). https:\/\/doi.org\/10.11575\/cdm.v4i1.61874.","journal-title":"Contrib. Discret. Math."},{"key":"1279_CR15","doi-asserted-by":"crossref","unstructured":"Cameron, P.J.: The random graph. The Mathematics of Paul Erd\u00f6s II, 333\u2013351 (1997)","DOI":"10.1007\/978-3-642-60406-5_32"},{"key":"1279_CR16","doi-asserted-by":"crossref","unstructured":"Cleve, R.: Towards optimal simulations of formulas by bounded-width programs. In: Proceedings of the 22nd ACM STOC, pp. 271\u2013277 (1990)","DOI":"10.1145\/100216.100251"},{"key":"1279_CR17","unstructured":"Costea, A.: Computational and theoretical aspects of $$n$$-e.c. graphs. Master\u2019s thesis, Wilfrid Laurier University (2010)"},{"key":"1279_CR18","doi-asserted-by":"crossref","unstructured":"Cramer, R., Fehr, S., Ishai, Y., Kushilevitz, E.: Efficient multi-party computation over rings. In: EUROCRYPT 2003, pp. 596\u2013613 (2003). Springer","DOI":"10.1007\/3-540-39200-9_37"},{"key":"1279_CR19","doi-asserted-by":"crossref","unstructured":"Feige, U., Killian, J., Naor, M.: A minimal model for secure computation. In: Proceedings of the 26th ACM STOC, pp. 554\u2013563 (1994)","DOI":"10.1145\/195058.195408"},{"key":"1279_CR20","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/978-1-4612-3464-7_18","volume-title":"Analytic Number Theory","author":"SW Graham","year":"1990","unstructured":"Graham S.W., Ringrose C.J.: Lower bounds for least quadratic non-residues. In: Berndt B.C., Diamond H.G., Halberstam H., Hildebrand A. (eds.) Analytic Number Theory, pp. 269\u2013309. Springer, Heidelberg (1990)."},{"issue":"1","key":"1279_CR21","doi-asserted-by":"publisher","first-page":"45","DOI":"10.4153\/CMB-1971-007-1","volume":"14","author":"RL Graham","year":"1971","unstructured":"Graham R.L., Spencer J.H.: A constructive solution to a tournament problem. Can. Math. Bull. 14(1), 45\u201348 (1971).","journal-title":"Can. Math. Bull."},{"key":"1279_CR22","unstructured":"Ishai, Y., Kushilevitz, E.: Private simultaneous messages protocols with applications. In: Proceedings of the 5th Israeli Symposium on Theory of Computing and Systems (ISTCS 1997), pp. 174\u2013183 (1997). IEEE"},{"key":"1279_CR23","first-page":"222","volume":"10","author":"Y Ishai","year":"2013","unstructured":"Ishai Y.: Randomization techniques for secure computation. Secur. Multi-Party Comput. 10, 222 (2013).","journal-title":"Secur. Multi-Party Comput."},{"key":"1279_CR24","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511618314","volume-title":"Topics in Multiplicative Number Theory","author":"HL Montgomery","year":"2006","unstructured":"Montgomery H.L.: Topics in Multiplicative Number Theory, vol. 227. Springer, Heidelberg (2006)."},{"issue":"197","key":"1279_CR25","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1090\/S0025-5718-1992-1106978-9","volume":"58","author":"R Peralta","year":"1992","unstructured":"Peralta R.: On the distribution of quadratic residues and nonresidues modulo a prime number. Math. Comput. 58(197), 433\u2013440 (1992).","journal-title":"Math. Comput."},{"issue":"4","key":"1279_CR26","doi-asserted-by":"publisher","first-page":"1451","DOI":"10.1007\/s00373-021-02330-9","volume":"37","author":"S Satake","year":"2021","unstructured":"Satake S.: On explicit random-like tournaments. Graphs Combinatorics 37(4), 1451\u20131463 (2021).","journal-title":"Graphs Combinatorics"},{"key":"1279_CR27","unstructured":"Vaikuntanathan, V.: Some open problems in information-theoretic cryptography. In: 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017) (2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik"},{"key":"1279_CR28","unstructured":"Yoshida, K., Satake, S., Phoa, F., Sawa, M.: Circulant almost-orthogonal arrays with strength 3 and bandwidth 1: constructions and existence. preprint"}],"container-title":["Designs, Codes and Cryptography"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10623-023-01279-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10623-023-01279-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10623-023-01279-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,4]],"date-time":"2023-11-04T12:04:57Z","timestamp":1699099497000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10623-023-01279-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,8,16]]},"references-count":28,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2023,12]]}},"alternative-id":["1279"],"URL":"https:\/\/doi.org\/10.1007\/s10623-023-01279-5","relation":{},"ISSN":["0925-1022","1573-7586"],"issn-type":[{"value":"0925-1022","type":"print"},{"value":"1573-7586","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,8,16]]},"assertion":[{"value":"13 October 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 June 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 July 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 August 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no conflicts of interest associated with this manuscript.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}]}}