主要な論文，発表

The secure implementation of the Greatest Common Divisor (GCD) algorithm is fundamental for many cryptographic schemes. The binary GCD algorithm has a highly input-dependent behavior. Therefore, we must carefully implement the binary GCD used in cryptographic systems. However, it has been noted that the binary GCD algorithm implemented in OpenSSL 1.1.0-1.1.0h and 1.0.2b-1.0.2o is not secure. Aldaya et al. presented this vulnerability at CHES2019. They also proposed a side-channel attack to collect sequences of operations performed by the binary GCD algorithm and an error correction algorithm (AGTB algorithm) to recover the LSBs of secret keys from the noisy sequences. In this paper, we propose an error correction algorithm that, like the AGTB algorithm, focuses on only a single type of error. We evaluate our algorithm using numerical experiments that reveal that our algorithm achieves a higher recovery rate than the AGTB algorithm.

Ramp secret sharing is a variant of secret sharing which can achieve better information ratio than perfect schemes by allowing some partial information on a secret to leak out. Strongly secure ramp schemes can control the amount of leaked information on the components of a secret. In this paper, we reduce the construction of strongly secure ramp secret sharing for general access structures to a linear algebraic problem. As a result, we show that previous results on strongly secure network coding imply two linear transformation methods to make a given linear ramp scheme strongly secure. They are explicit or provide a deterministic algorithm while the previous methods which work for any linear ramp scheme are non-constructive. In addition, we present a novel application of strongly secure ramp schemes to symmetric PIR in a multi-user setting. Our solution is advantageous over those based on a non-strongly secure scheme in that it reduces the amount of communication between users and servers and also the amount of correlated randomness that servers generate in the setup.

d-Multiplicative secret sharing enables n players to locally compute additive shares of the product of d secrets from their shares. Barkol et al. (Journal of Cryptology, 2010) show that it is possible to construct a d-multiplicative scheme for any adversary structure satisfying the Qd property, in which no d sets cover the whole set of players. In this paper, we focus on multipartite adversary structures and propose efficient multiplicative and verifiably multiplicative secret sharing schemes tailored to them. First, our multiplicative scheme is applicable to any multipartite Qd-adversary structure. If the number of parts is constant, our scheme achieves a share size polynomial in the number n of players while the general construction by Barkol et al. results in exponentially large share size in the worst case. We also propose its variant defined over smaller fields. As a result, for a special class of bipartite adversary structures with two maximal points, it achieves a constant share size for arbitrary n while the share size of the first scheme necessarily incurs a logarithmic factor of n. Secondly, we devise a more efficient scheme for a special class of multipartite ones such that players in each part have the same weight and a set of players belongs to the adversary structure if and only if the sum of their weights is at most a threshold. Thirdly, if the adversary structure is Q{d+1}, our first scheme is shown to be a verifiably multiplicative scheme that detects incorrect outputs with probability 1. For multipartite adversary structures with a constant number of parts, it improves the worst-case share and proof sizes of the only known general construction by Yoshida and Obana (IEEE Transactions on Information Theory, 2019). Finally, we propose a more efficient verifiably multiplicative scheme by allowing small error probability δ and focusing on a more restricted class of multipartite adversary structures. Our scheme verifies computation of polynomials and can achieve a share size independent of δ while the previous construction only works for monomials and results in a share size involving a factor of log δ^{-1}.

To bound information leakage in outputs of protocols, it is important to construct secure multiparty computation protocols which output differentially private values perturbed by the addition of noise. However, previous noise generation protocols have round and communication complexity growing with differential privacy budgets, or require parties to locally generate non-uniform noise, which makes it difficult to guarantee differential privacy against active adversaries. We propose three kinds of protocols for generating noise drawn from certain distributions providing differential privacy. The two of them generate noise from finite-range variants of the discrete Laplace distribution. For (ε,δ)-differential privacy, they only need constant numbers of rounds independent of ε, δ while the previous protocol needs the number of rounds depending on δ. The two protocols are incomparable as they make a trade-off between round and communication complexity. Our third protocol non-interactively generate shares of noise from the binomial distribution by predistributing keys for a pseudorandom function. It achieves communication complexity independent of ε or δ for the computational analogue of (ε,δ)-differential privacy while the previous protocols require communication complexity depending on ε. We also prove that our protocols can be extended so that they provide differential privacy in the active setting.

Control modular addition is a core arithmetic function, and we must consider the computational cost for actual quantum computers to realize efficient implementation. To achieve a low computational cost in a control modular adder, we focus on minimizing KQ, defined by the product of the number of qubits and the depth of the circuit. In this paper, we construct an efficient control modular adder with small KQ by using relative-phase Toffoli gates in two major types of quantum computers: Fault-Tolerant Quantum Computers (FTQ) on the Logical layer and Noisy Intermediate-Scale Quantum Computers (NISQ). We give a more efficient construction compared to Van Meter and Itoh’s, based on a carry-lookahead adder. In FTQ, T gates incur heavy cost due to distillation, which fabricates ancilla for running T gates with high accuracy but consumes a lot of specially prepared ancilla qubits and a lot of time. Thus, we must reduce the number of T gates. We propose a new control modular adder that uses only 20% of the number of T gates of the original. Moreover, when we take distillation into consideration, we find that we minimize KQT (the product of the number of qubits and T-depth) by running (n / log n) T gates simultaneously. In NISQ, CNOT gates are the major error source. We propose a new control modular adder that uses only 35% of the number of CNOT gates of the original. Moreover, we show that the KQCX (the product of the number of qubits and CNOT-depth) of our circuit is 38% of the original. Thus, we realize an efficient control modular adder, improving prospects for the efficient execution of arithmetic in quantum computers.

RSA (Rivest-Shamir-Adleman) cryptosystem is the most popular asymmetric key cryptographic algorithm used in computer science and information security. Recently, an RSA-like cryptosystem was proposed using a novel product that arises from a cubic field connected to the cubic Pell equation. The relevant key equation is $ed = 1 mod (p^2+p+1)(q^2+q+1)$ with $N=pq$. This RSA variant is claimed to be robust against the Wiener’s attack and hence the bit-size of the private key could be shorter, namely $d < N^{1/4}$. In this paper, we explore the further security analysis and investigate the potential small private exponent attack. We show that such RSA variant is particularly vulnerable to the lattice-based method. To be specific, we can carry out the lattice-based small private exponent attack if $d < N^{2-√2}}$, which is less secure than the standard RSA. Furthermore, we conduct numerical experiments to verify the validity of the proposed attack.

This paper studies the problem of constructing secure multiparty computation protocols whose outputs satisfy differential privacy. We first provide a general framework for multiparty protocols generating shares of noise drawn from distributions capable of achieving differential privacy. Then, using this framework, we propose two kinds of protocols based on secret sharing. The first one is a constant-round protocol which enables parties to jointly generate shares of noise drawn from the discrete Laplace distribution. This protocol always outputs shares of noise while the previously known protocol fails with non-zero probability. The second protocol allows the parties to non-interactively obtain shares of noise following the binomial distribution by predistributing keys for pseudorandom functions in the setup phase. As a result, the parties can compute a share of noise enough to provide the computational analogue of ε-differential privacy with communication complexity independent of ε. It is much more efficient than the previous protocols which require communication complexity proportional to ε^{-2} to achieve (information-theoretic) (ε,δ)-differential privacy for some δ>0.

Partial key exposure attacks on RSA have been intensively studied by using lattice-based Coppersmith’s methods. Ernst et al. (Eurocrypt'05) studied the problem by considering three attack scenarios; (1) the most significant bits (MSBs) of a secret exponent d known, (2) the least significant bits (LSBs) of d known, (3) both the MSBs and the LSBs of d known. The proposed attacks were valuable since they were the first results to handle full size exponents e. Takayasu and Kunihiro (SAC'14, Theoretical Computer Science'19) proposed improved attacks for (1) and (2) when d is sufficiently small, i.e., $d<N^{0.5625}$ for (1) and $d<N^{0.368}$ for (2), by utilizing a linearization technique. In this paper, we extend Takayasu-Kunihiro’s attacks and improve Ernst et al.’s attack for (3). In particular, our attack contains Takayasu-Kunihiro’s attacks for (1) and (2) as special cases when the amount of given LSBs and MSBs are zero, respectively. Furthermore, as opposed to Takayasu-Kunihiro’s attacks, our improvement against Ernst et al.’s attack is not limited to small secret exponents such as $d<N^{0.5625}$. Indeed, we are able to improve Ernst et al.’s attack almost up to full size decryption exponents, i.e., even when $d$ is close to $N$. Technically, the extension is not straightforward. We first modify Takayasu-Kunihiro’s lattice basis matrix for (2), so that it is compatible to embed the given MSBs. The modification is crucial for embedding both the MSBs and the LSBs simultaneously to the matrix.

It is known that Shor’s algorithm can break many cryptosystems such as RSA encryption, provided that large-scale quantum computers are realized. Thus far, several experiments for the factorization of the small composites such as 15 and 21 have been conducted using small-scale quantum computers. In this study, we investigate the details of quantum circuits used in several factoring experiments. We then indicate that some of the circuits have been constructed under the condition that the order of an element modulo a target composite is known in advance. Because the order must be unknown in the experiments, they are inappropriate for designing the quantum circuit of Shor’s factoring algorithm. We also indicate that the circuits used in the other experiments are constructed by relying considerably on the target composite number to be factorized.

A secret sharing scheme is a cryptographic technique to protect a secret from loss and leakage by dividing it into shares. A ramp secret sharing scheme can improve efficiency in terms of the information ratio by allowing partial information about the secret which is composed of several sub-secrets to leak out. The notion of strong security has been introduced to control the amount of information on every subset of the sub-secrets that unauthorized sets can obtain. However, there have been proposed few methods to construct strongly secure schemes for general access structures. Furthermore, all existing methods need strong assumptions, which lead to a loss of efficiency and a limitation of access structures. In this paper, we show that any ramp secret sharing scheme which is linear over a sufficiently large field can be transformed into a strongly secure scheme with the same access structure preserving the information ratio. Since our method only requires linearity, our strongly secure schemes can realize arbitrary access structures and achieve smaller information ratio than the previous schemes.

We address the security issue of RSA with implicitly related keys in this paper. Informally, we investigate under what condition is it possible to efficiently factorize RSA moduli in polynomial time given implicit relation of the related private keys that certain portions of bit pattern are the same. We formulate concrete attack scenarios and propose lattice-based cryptanalysis by using lattice reduction algorithms. A subtle lattice technique is adapted to represent an unknown private key with the help of known implicit relation. We analyze a simple case when given two RSA instances with the known amount of shared most significant bits (MSBs) and least significant bits (LSBs) of the private keys. We further extend to a generic lattice-based attack for given more RSA instances with implicitly related keys. Our theoretical results indicate that RSA with implicitly related keys is more insecure and better asymptotic results can be achieved as the number of RSA instances increases. Furthermore, we conduct numerical experiments to verify the validity of the proposed attacks.

In this paper, we study the generic hardness of the inversion problem on a ring, which is a problem to compute the inverse of a given prime c by just using additions, subtractions and multiplications on the ring. If the characteristic of an underlying ring is public and coprime to c, then it is easy to compute the inverse of c by using the extended Euclidean algorithm. On the other hand, if the characteristic is hidden, it seems difficult to compute it. For discussing the generic hardness of the inversion problem, we first extend existing generic ring models to capture a ring of an unknown characteristic. Then we prove that there is no generic algorithm to solve the inversion problem in our model when the underlying ring is isomorphic to $Z_p$ for a randomly chosen prime p assuming the hardness of factorization of an unbalanced modulus. We also study a relation between the inversion problem on a ring and a self-bilinear map. Namely, we give a construction of a self-bilinear map based on a ring on which the inversion problem is hard, and prove that natural complexity assumptions including the multilinear computational Diffie-Hellman (MCDH) assumption hold w.r.t. the resulting sef-bilinear map.

Secret sharing schemes are said to be d-multiplicative if the i-th shares of any d secrets s^(j), j∈[d] can be converted into an additive share of the product ∏_{j∈[d]}s^(j). d-Multiplicative secret sharing is a central building block of multiparty computation protocols with minimum number of rounds which are unconditionally secure against possibly non-threshold adversaries. It is known that d-multiplicative secret sharing is possible if and only if no d forbidden subsets covers the set of all the n players or, equivalently, it is private with respect to an adversary structure of type Q_d. However, the only known method to achieve d-multiplicativity for any adversary structure of type Q_d is based on CNF secret sharing schemes, which are not efficient in general in that the information ratios are exponential in n. In this paper, we explicitly construct a d-multiplicative secret sharing scheme for any 𝓁-partite adversary structure of type Q_d whose information ratio is O(n^{𝓁+1}). Our schemes are applicable to the class of all the 𝓁-partite adversary structures, which is much wider than that of the threshold ones. Furthermore, our schemes achieve information ratios which are polynomial in n if 𝓁 is constant and hence are more efficient than CNF schemes. In addition, based on the standard embedding of 𝓁-partite adversary structures into ℝ^𝓁, we introduce a class of 𝓁-partite adversary structures of type Q_d with good geometric properties and show that there exist more efficient d-multiplicative secret sharing schemes for adversary structures in that family than the above general construction. The family of adversary structures is a natural generalization of that of the threshold ones and includes some adversary structures which arise in real-world scenarios.

In ICITS 2015, Walter studied the worst case computational cost to enumerate short lattice vectors on two well-known block reduced bases, i.e., BKZ reduced bases and slide reduced bases. Until then, existing works analyzed only extreme preprocessed bases, e.g., LLL reduced bases that are the weakest ones and quasi-HKZ reduced bases that are the strongest ones; hence, Walter tried to interpolate these results. For this purpose, Walter tried to calculate enumeration cost on block reduced bases of arbitrary blocksizes. The topic should be theoretically interesting since hardness of the lattice problem relates to the security of lattice-based cryptography. In this paper, we revisit the problem with refined analyses. For both BKZ and slide reduced bases, we show that the worst case enumeration costs are smaller than Walter’s analyses. In particular, we show that our results are the best possible ones when we follow Walter’s approach. Furthermore, we extend Walter’s result for slide reduced bases. Since Walter only studied the original slide reduced bases proposed by Gama and Nguyen, he did not analyze arbitrary blocksizes. To extend the analyses to arbitrary blocksizes, we use the generalized slide reduction that was defined by Li and Wei. As a side contribution, we also show that the worst case behaviors of the generalized slide reduced bases are better than Li and Wei’s analyses. We obtain all these results by exploiting better geometric properties of block reduced bases.