主要な論文，発表

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.