{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T00:31:08Z","timestamp":1764981068983,"version":"3.46.0"},"reference-count":9,"publisher":"Walter de Gruyter GmbH","issue":"2","license":[{"start":{"date-parts":[[2019,5,8]],"date-time":"2019-05-08T00:00:00Z","timestamp":1557273600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc-nd\/3.0\/"}],"funder":[{"DOI":"10.13039\/501100002241","name":"Japan Science and Technology Agency","doi-asserted-by":"publisher","award":["JPMJPR14E8","JPMJPR16E3"],"award-info":[{"award-number":["JPMJPR14E8","JPMJPR16E3"]}],"id":[{"id":"10.13039\/501100002241","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["16K05083","JP25800009"],"award-info":[{"award-number":["16K05083","JP25800009"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019,6,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    One of the common ways to design secure multi-party computation is twofold:\nto realize secure fundamental operations and to decompose a target function to be securely computed into them.\nIn the setting of fully homomorphic encryption, as well as some kinds of secret sharing,\nthe fundamental operations are additions and multiplications in the base field such as the field\n                    <jats:inline-formula id=\"j_jmc-2018-0016_ineq_9999_w2aab3b7b2b1b6b1aab1c16b1b1Aa\">\n                      <jats:alternatives>\n                        <m:math xmlns:m=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <m:msub>\n                            <m:mi>\ud835\udd3d<\/m:mi>\n                            <m:mn>2<\/m:mn>\n                          <\/m:msub>\n                        <\/m:math>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"graphic\/j_jmc-2018-0016_eq_0204.png\"\/>\n                        <jats:tex-math>{\\mathbb{F}_{2}}<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    with two elements.\nThen the second decomposition part, which we study in this paper, is (in theory) equivalent to expressing the target function as a polynomial.\nIt is known that any function over the finite prime field\n                    <jats:inline-formula id=\"j_jmc-2018-0016_ineq_9998_w2aab3b7b2b1b6b1aab1c16b1b3Aa\">\n                      <jats:alternatives>\n                        <m:math xmlns:m=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <m:msub>\n                            <m:mi>\ud835\udd3d<\/m:mi>\n                            <m:mi>p<\/m:mi>\n                          <\/m:msub>\n                        <\/m:math>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"graphic\/j_jmc-2018-0016_eq_0206.png\"\/>\n                        <jats:tex-math>{\\mathbb{F}_{p}}<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    has a unique polynomial expression of degree at most\n                    <jats:inline-formula id=\"j_jmc-2018-0016_ineq_9997_w2aab3b7b2b1b6b1aab1c16b1b5Aa\">\n                      <jats:alternatives>\n                        <m:math xmlns:m=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <m:mrow>\n                            <m:mi>p<\/m:mi>\n                            <m:mo>-<\/m:mo>\n                            <m:mn>1<\/m:mn>\n                          <\/m:mrow>\n                        <\/m:math>\n                        <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"graphic\/j_jmc-2018-0016_eq_0298.png\"\/>\n                        <jats:tex-math>{p-1}<\/jats:tex-math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    with respect to each input variable;\nhowever, there has been little study done concerning such minimal-degree polynomial expressions for practical functions.\nThis paper aims at triggering intensive studies on this subject,\nby focusing on polynomial expressions of some auction-related functions such as the maximum\/minimum and the index of the maximum\/minimum value among input values.\n                  <\/jats:p>","DOI":"10.1515\/jmc-2018-0016","type":"journal-article","created":{"date-parts":[[2019,5,8]],"date-time":"2019-05-08T05:07:52Z","timestamp":1557292072000},"page":"69-80","source":"Crossref","is-referenced-by-count":4,"title":["Polynomial expressions of\n                    <i>p<\/i>\n                    -ary auction functions"],"prefix":"10.1515","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7856-6536","authenticated-orcid":false,"given":"Shizuo","family":"Kaji","sequence":"first","affiliation":[{"name":"Institute of Mathematics for Industry , Kyushu University , Fukuoka ; and Japan Science and Technology Agency (JST) PRESTO Researcher , Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Toshiaki","family":"Maeno","sequence":"additional","affiliation":[{"name":"Meijo University , Nagoya , Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8259-9958","authenticated-orcid":false,"given":"Koji","family":"Nuida","sequence":"additional","affiliation":[{"name":"Graduate School of Information Science and Technology , The University of Tokyo , Tokyo ; and National Institute of Advanced Industrial Science and Technology (AIST) , Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1228-7067","authenticated-orcid":false,"given":"Yasuhide","family":"Numata","sequence":"additional","affiliation":[{"name":"Department of Mathematics , Shinshu University , Matsumoto , Nagano , Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"374","published-online":{"date-parts":[[2019,5,8]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"T.  Araki, J.  Furukawa, Y.  Lindell, A.  Nof and K.  Ohara,\nHigh-throughput semi-honest secure three-party computation with an honest majority,\nProceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security,\nACM, New York (2016), 805\u2013817.","key":"2025120600285467040_j_jmc-2018-0016_ref_001_w2aab3b7b2b1b6b1ab1b8b1Aa","DOI":"10.1145\/2976749.2978331"},{"doi-asserted-by":"crossref","unstructured":"R.  Bost, R. A.  Popa, S.  Tu and S.  Goldwasser,\nMachine learning classification over encrypted data,\nIACR Cryptology ePrint Archive (2014), https:\/\/eprint.iacr.org\/2014\/331.pdf.","key":"2025120600285467040_j_jmc-2018-0016_ref_002_w2aab3b7b2b1b6b1ab1b8b2Aa","DOI":"10.14722\/ndss.2015.23241"},{"doi-asserted-by":"crossref","unstructured":"J.  Boyar, R.  Peralta and D.  Pochuev,\nOn the multiplicative complexity of Boolean functions over the basis (cap, +, 1),\nTheoret. Comput. Sci. 235 (2000), no. 1, 43\u201357.\n10.1016\/S0304-3975(99)00182-6","key":"2025120600285467040_j_jmc-2018-0016_ref_003_w2aab3b7b2b1b6b1ab1b8b3Aa","DOI":"10.1016\/S0304-3975(99)00182-6"},{"doi-asserted-by":"crossref","unstructured":"J. H.  Cheon, M.  Kim and M.  Kim,\nSearch-and-compute on encrypted data,\nProceedings of Financial Cryptography and Data Security 2015\u2014FC 2015,\nLecture Notes in Comput. Sci. 8976,\nSpringer, Berlin (2015), 142\u2013159.","key":"2025120600285467040_j_jmc-2018-0016_ref_004_w2aab3b7b2b1b6b1ab1b8b4Aa","DOI":"10.1007\/978-3-662-48051-9_11"},{"doi-asserted-by":"crossref","unstructured":"C.  Gentry,\nFully homomorphic encryption using ideal lattices,\nProceedings of the Forty-first Annual ACM Symposium on Theory of Computing\u2014STOC\u201909,\nACM, New York (2009), 169\u2013178.","key":"2025120600285467040_j_jmc-2018-0016_ref_005_w2aab3b7b2b1b6b1ab1b8b5Aa","DOI":"10.1145\/1536414.1536440"},{"unstructured":"S.  Kaji, T.  Maeno, K.  Nuida and Y.  Numata,\nPolynomial expressions of carries in p-ary arithmetics,\npreprint (2015), http:\/\/arxiv.org\/abs\/1506.02742.","key":"2025120600285467040_j_jmc-2018-0016_ref_006_w2aab3b7b2b1b6b1ab1b8b6Aa"},{"doi-asserted-by":"crossref","unstructured":"K.  Nuida and K.  Kurosawa,\n(Batch) fully homomorphic encryption over integers for non-binary message spaces,\nAdvances in Cryptology\u2013EUROCRYPT 2015,\nLecture Notes in Comput. Sci. 9056,\nSpringer, Berlin (2015), 537\u2013555.","key":"2025120600285467040_j_jmc-2018-0016_ref_007_w2aab3b7b2b1b6b1ab1b8b7Aa","DOI":"10.1007\/978-3-662-46800-5_21"},{"doi-asserted-by":"crossref","unstructured":"A.  Shamir,\nHow to share a secret,\nCommun. ACM 22 (1979), no. 11, 612\u2013613.\n10.1145\/359168.359176","key":"2025120600285467040_j_jmc-2018-0016_ref_008_w2aab3b7b2b1b6b1ab1b8b8Aa","DOI":"10.1145\/359168.359176"},{"doi-asserted-by":"crossref","unstructured":"C.  Sturtivant and G. S.  Frandsen,\nThe computational efficacy of finite-field arithmetic,\nTheoret. Comput. Sci. 112 (1993), 291\u2013309.\n10.1016\/0304-3975(93)90022-L","key":"2025120600285467040_j_jmc-2018-0016_ref_009_w2aab3b7b2b1b6b1ab1b8b9Aa","DOI":"10.1016\/0304-3975(93)90022-L"}],"container-title":["Journal of Mathematical Cryptology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.degruyter.com\/view\/j\/jmc.2019.13.issue-2\/jmc-2018-0016\/jmc-2018-0016.xml","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2018-0016\/xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2018-0016\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T00:29:03Z","timestamp":1764980943000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.degruyterbrill.com\/document\/doi\/10.1515\/jmc-2018-0016\/html"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,5,8]]},"references-count":9,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2019,5,8]]},"published-print":{"date-parts":[[2019,6,1]]}},"alternative-id":["10.1515\/jmc-2018-0016"],"URL":"https:\/\/doi.org\/10.1515\/jmc-2018-0016","relation":{},"ISSN":["1862-2984","1862-2976"],"issn-type":[{"type":"electronic","value":"1862-2984"},{"type":"print","value":"1862-2976"}],"subject":[],"published":{"date-parts":[[2019,5,8]]}}}