Koji Nuida

Keita Suzuki, Koji Nuida

Akiyama et al. (Int. J. Math. Indust., 2019) proposed a post-quantum key exchange protocol that is based on the hardness of solving a system of multivariate non-linear polynomial equations but has a design strategy different from ordinary multivariate cryptography. Their protocol has two versions, an original one and a modified one, where the modified one has a trade-off that its security is strengthened while it has non-zero error probability in establishing a common key. In fact, the evaluation in their paper suggests that the probability of failing to establish a common key by the modified protocol with the proposed parameter set is impractically high. In this paper, we improve the success probability of Akiyama et al.'s modified key exchange protocol significantly while keeping the security, by restricting each component of the correct common key from the whole of the coefficient field to its small subset. We give theoretical and experimental evaluations showing that our proposed parameter set for our protocol is expected to achieve both failure probability $2^{-120}$ and $128$-bit security level.

Takuto Odagawa, Koji Nuida

DeepLLL algorithm (Schnorr, 1994) is a famous variant of LLL lattice basis reduction algorithm, and PotLLL algorithm (Fontein et al., 2014) and $S^2$LLL algorithm (Yasuda and Yamaguchi, 2019) are recent polynomial-time variants of DeepLLL algorithm developed from cryptographic applications. However, the known polynomial bounds for computational complexity are shown only for parameter $δ< 1$; for "optimal" parameter $δ= 1$ which ensures the best output quality, no polynomial bounds are known, and except for LLL algorithm, it is even not formally proved that the algorithm always halts within finitely many steps. In this paper, we prove that these four algorithms always halt also with optimal parameter $δ= 1$, and furthermore give explicit upper bounds for the numbers of loops executed during the algorithms. Unlike the known bound (Akhavi, 2003) applicable to LLL algorithm only, our upper bounds are deduced in a unified way for all of the four algorithms.

Koji Nuida

The group structure on the rational points of elliptic curves plays several important roles, in mathematics and recently also in other areas such as cryptography. However, the famous proofs for the group property (in particular, for its associative law) require somewhat advanced mathematics and therefore are not easily accessible by non-mathematician. On the other hand, there have been attempts in the literature to give an elementary proof, but those rely on computer-aided calculation for some part in their proofs. In this paper, we give a self-contained proof of the associative law for this operation, assuming mathematical knowledge only at the level of basic linear algebra and not requiring computer-aided arguments.

Satsuya Ohata, Koji Nuida

Secure multi-party computation (MPC) allows a set of parties to compute a function jointly while keeping their inputs private. Compared with the MPC based on garbled circuits,some recent research results show that MPC based on secret sharing (SS) works at a very high speed. Moreover, SS-based MPC can be easily vectorized and achieve higher throughput. In SS-based MPC, however, we need many communication rounds for computing concrete protocols like equality check, less-than comparison, etc. This property is not suited for large-latency environments like the Internet (or WAN). In this paper, we construct semi-honest secure communication-efficient two-party protocols. The core technique is Beaver triple extension, which is a new tool for treating multi-fan-in gates, and we also show how to use it efficiently. We mainly focus on reducing the number of communication rounds, and our protocols also succeed in reducing the number of communication bits (in most cases). As an example, we propose a less-than comparison protocol (under practical parameters) with three communication rounds. Moreover, the number of communication bits is also $38.4\%$ fewer. As a result, total online execution time is $56.1\%$ shorter than the previous work adopting the same settings. Although the computation costs of our protocols are more expensive than those of previous work, we confirm via experiments that such a disadvantage has small effects on the whole online performance in the typical WAN environments.

Yuji Hashimoto, Kazumasa Shinagawa, Koji Nuida et al.

We consider a problem, which we call secure grouping, of dividing a number of parties into some subsets (groups) in the following manner: Each party has to know the other members of his/her group, while he/she may not know anything about how the remaining parties are divided (except for certain public predetermined constraints, such as the number of parties in each group). In this paper, we construct an information-theoretically secure protocol using a deck of physical cards to solve the problem, which is jointly executable by the parties themselves without a trusted third party. Despite the non-triviality and the potential usefulness of the secure grouping, our proposed protocol is fairly simple to describe and execute. Our protocol is based on algebraic properties of conjugate permutations. A key ingredient of our protocol is our new techniques to apply multiplication and inverse operations to hidden permutations (i.e., those encoded by using face-down cards), which would be of independent interest and would have various potential applications.

Shizuo Kaji, Toshiaki Maeno, Koji Nuida et al.

It is known that any $n$-variable function on a finite prime field of characteristic $p$ can be expressed as a polynomial over the same field with at most $p^n$ monomials. However, it is not obvious to determine the polynomial for a given concrete function. In this paper, we study the concrete polynomial expressions of the carries in addition and multiplication of $p$-ary integers. For the case of addition, our result gives a new family of symmetric polynomials, which generalizes the known result for the binary case $p = 2$ where the carries are given by elementary symmetric polynomials. On the other hand, for the case of multiplication of $n$ single-digit integers, we give a simple formula of the polynomial expression for the carry to the next digit using the Bernoulli numbers, and show that it has only $(n+1)(p-1)/2 + 1$ monomials, which is significantly fewer than the worst-case number $p^n$ of monomials for general functions. We also discuss applications of our results to cryptographic computation on encrypted data.

Koji Nuida, Takuro Abe, Shizuo Kaji et al.

In this paper, we specify a class of mathematical problems, which we refer to as "Function Density Problems" (FDPs, in short), and point out novel connections of FDPs to the following two cryptographic topics; theoretical security evaluations of keyless hash functions (such as SHA-1), and constructions of provably secure pseudorandom generators (PRGs) with some enhanced security property introduced by Dubrov and Ishai [STOC 2006]. Our argument aims at proposing new theoretical frameworks for these topics (especially for the former) based on FDPs, rather than providing some concrete and practical results on the topics. We also give some examples of mathematical discussions on FDPs, which would be of independent interest from mathematical viewpoints. Finally, we discuss possible directions of future research on other cryptographic applications of FDPs and on mathematical studies on FDPs themselves.