Polynomial expressions of p-ary auction functions
One of the common ways to design secure multi-party computation is twofold: to realize secure fundamental operations and to decompose a target function to be securely computed into them. In the setting of fully homomorphic encryption, as well as some kinds of secret sharing, the fundamental operatio...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
De Gruyter
2019-06-01
|
| Series: | Journal of Mathematical Cryptology |
| Subjects: | |
| Online Access: | https://doi.org/10.1515/jmc-2018-0016 |
| _version_ | 1798026373300748288 |
|---|---|
| author | Kaji Shizuo Maeno Toshiaki Nuida Koji Numata Yasuhide |
| author_facet | Kaji Shizuo Maeno Toshiaki Nuida Koji Numata Yasuhide |
| author_sort | Kaji Shizuo |
| collection | DOAJ |
| description | One of the common ways to design secure multi-party computation is twofold:
to realize secure fundamental operations and to decompose a target function to be securely computed into them.
In the setting of fully homomorphic encryption, as well as some kinds of secret sharing,
the fundamental operations are additions and multiplications in the base field such as the field 𝔽2{\mathbb{F}_{2}} with two elements.
Then the second decomposition part, which we study in this paper, is (in theory) equivalent to expressing the target function as a polynomial.
It is known that any function over the finite prime field 𝔽p{\mathbb{F}_{p}} has a unique polynomial expression of degree at most p-1{p-1} with respect to each input variable;
however, there has been little study done concerning such minimal-degree polynomial expressions for practical functions.
This paper aims at triggering intensive studies on this subject,
by 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. |
| first_indexed | 2024-04-11T18:34:17Z |
| format | Article |
| id | doaj.art-7809d528096f43dabe10ce402130f3dd |
| institution | Directory Open Access Journal |
| issn | 1862-2976 1862-2984 |
| language | English |
| last_indexed | 2024-04-11T18:34:17Z |
| publishDate | 2019-06-01 |
| publisher | De Gruyter |
| record_format | Article |
| series | Journal of Mathematical Cryptology |
| spelling | doaj.art-7809d528096f43dabe10ce402130f3dd2022-12-22T04:09:20ZengDe GruyterJournal of Mathematical Cryptology1862-29761862-29842019-06-01132698010.1515/jmc-2018-0016Polynomial expressions of p-ary auction functionsKaji Shizuo0Maeno Toshiaki1Nuida Koji2Numata Yasuhide3Institute of Mathematics for Industry, Kyushu University, Fukuoka; and Japan Science and Technology Agency (JST) PRESTO Researcher, JapanMeijo University, Nagoya, JapanGraduate School of Information Science and Technology, The University of Tokyo, Tokyo; and National Institute of Advanced Industrial Science and Technology (AIST), JapanDepartment of Mathematics, Shinshu University, Matsumoto, Nagano, JapanOne of the common ways to design secure multi-party computation is twofold: to realize secure fundamental operations and to decompose a target function to be securely computed into them. In the setting of fully homomorphic encryption, as well as some kinds of secret sharing, the fundamental operations are additions and multiplications in the base field such as the field 𝔽2{\mathbb{F}_{2}} with two elements. Then the second decomposition part, which we study in this paper, is (in theory) equivalent to expressing the target function as a polynomial. It is known that any function over the finite prime field 𝔽p{\mathbb{F}_{p}} has a unique polynomial expression of degree at most p-1{p-1} with respect to each input variable; however, there has been little study done concerning such minimal-degree polynomial expressions for practical functions. This paper aims at triggering intensive studies on this subject, by 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.https://doi.org/10.1515/jmc-2018-0016secure multi-party computationpolynomial expression of functionsfinite fields94a60 68r05 12y05 |
| spellingShingle | Kaji Shizuo Maeno Toshiaki Nuida Koji Numata Yasuhide Polynomial expressions of p-ary auction functions Journal of Mathematical Cryptology secure multi-party computation polynomial expression of functions finite fields 94a60 68r05 12y05 |
| title | Polynomial expressions of p-ary auction functions |
| title_full | Polynomial expressions of p-ary auction functions |
| title_fullStr | Polynomial expressions of p-ary auction functions |
| title_full_unstemmed | Polynomial expressions of p-ary auction functions |
| title_short | Polynomial expressions of p-ary auction functions |
| title_sort | polynomial expressions of p ary auction functions |
| topic | secure multi-party computation polynomial expression of functions finite fields 94a60 68r05 12y05 |
| url | https://doi.org/10.1515/jmc-2018-0016 |
| work_keys_str_mv | AT kajishizuo polynomialexpressionsofparyauctionfunctions AT maenotoshiaki polynomialexpressionsofparyauctionfunctions AT nuidakoji polynomialexpressionsofparyauctionfunctions AT numatayasuhide polynomialexpressionsofparyauctionfunctions |