In this paper, we study partial key exposure attacks on RSA where the number of unexposed blocks of the private key is greater than or equal to one. This situation, called generalized framework of partial key exposure attack, was first shown by Sarkar [22] in 2011. Under a certain condition for the values of exposed bits, we present a new attack which needs fewer exposed bits and thus improves the result in [22]. Our work is a generalization of [28], and the approach is based on Coppersmith's method and the technique of unravelled linearization.

In 1999, Boneh and Durfee introduced the small inverse problem, which solves the bivariate modular equation x(N+y)≡1(mod e. Absolute values of solutions for x and y are bounded above by X=Nδ and Y=Nβ, respectively. They solved the problem for β=1/2 in the context of small secret exponent attacks on RSA and proposed a polynomial time algorithm that works when δ<(7-2√7)/6≈0.284. In the same work, the bound was further improved to δ<1-1/≈2≈0.292. Thus far, the small inverse problem has also been analyzed for an arbitrary β. Generalizations of Boneh and Durfee's lattices to obtain the stronger bound yielded the bound δ<1-≈β. However, the algorithm works only when β≥1/4. When 0<β<1/4, there have been several works where the authors claimed their results are the best. In this paper, we revisit the problem for an arbitrary β. At first, we summarize the previous results for 0<β<1/4. We reveal that there are some results that are not valid and show that Weger's algorithms provide the best bounds. Next, we propose an improved algorithm to solve the problem for 0<β<1/4. Our algorithm works when δ<1-2(≈β(3+4β)-β)/3. Our algorithm construction is based on the combinations of Boneh and Durfee's two forms of lattices and it is more natural compared with previous works. For the cryptographic application, we introduce small secret exponent attacks on Multi-Prime RSA with small prime differences.

In this paper, we investigate the security property of RSA when some middle bits of the private key d are known to an attacker. Using the technique of unravelled linearization, we present a new attack on RSA with known middle bits, which improves a previous result under certain circumstance. Our approach is based on Coppersmith's method for finding small roots of modular polynomial equations.

At CaLC 2001, Howgrave-Graham proposed the polynomial time algorithm for solving univariate linear equations modulo an unknown divisor of a known composite integer, the so-called partially approximate common divisor problem. So far, two forms of multivariate generalizations of the problem have been considered in the context of cryptanalysis. The first is simultaneous modular univariate linear equations, whose polynomial time algorithm was proposed at ANTS 2012 by Cohn and Heninger. The second is modular multivariate linear equations, whose polynomial time algorithm was proposed at Asiacrypt 2008 by Herrmann and May. Both algorithms cover Howgrave-Graham's algorithm for univariate cases. On the other hand, both multivariate problems also become identical to Howgrave-Graham's problem in the asymptotic cases of root bounds. However, former algorithms do not cover Howgrave-Graham's algorithm in such cases. In this paper, we introduce the strategy for natural algorithm constructions that take into account the sizes of the root bounds. We work out the selection of polynomials in constructing lattices. Our algorithms are superior to all known attacks that solve the multivariate equations and can generalize to the case of arbitrary number of variables. Our algorithms achieve better cryptanalytic bounds for some applications that relate to RSA cryptosystems.

In this paper we propose an algorithm of factoring any integer N which has k different prime factors with the same bit-length, when about ()log2 N high-order bits of each prime factor are given. For a fixed ε, the running time of our algorithm is heuristic polynomial in (log2 N). Our factoring algorithm is based on a lattice-based algorithm of solving any k-variate polynomial equation over Z, which might be an independent interest.

In 1995, Vanstone and Zuccherato proposed a novel method of generating RSA moduli having a predetermined set of bits which are the ASCII representation of user's identification information (i.e., name, email address, etc.). This could lead to a savings in bandwidth for data transmission and storage. In this paper, we apply this idea of Vanstone and Zuccherato for reducing the storage requirement of RSA public moduli to integer factoring based public-key schemes with their moduli of the form prq. More precisely, we explicitly propose two efficient methods for specifying high-order bits of prime factors of their public-keys. We also consider the security of the proposed methods.

In RSA public-key cryptosystem, a small private key is often preferred for efficiency but such a small key could degrade security. Thus the Chinese Remainder Theorem (CRT) is tactically used, especially in time-critical applications like smart cards. As for using the CRT in RSA, care must be taken to resist partial key exposure attacks. While it is common to choose two distinct primes with similar size in RSA, May has shown that a composite modulus N can be factored in the balanced RSA with the CRT of half of the least (or most) significant bits of a private key is revealed with a small public key. However, in the case that efficiency is more critical than security, such as smart cards, unbalanced primes might be chosen. Thus, we are interested in partial key exposure attacks to the unbalanced RSA with the CRT. In this paper, we obtain the similar results as the balanced RSA. We show that in the unbalanced RSA if the N1/4 least (or most) significant bits are revealed, a private key can be recovered in polynomial time under a small public key.

In MPU and ASIC design with 0.2 µm BiCMOS LSIs, it is well known that interconnect delay becomes one of the key data to ensure high operating frequency. To verify the whole path delay accurately, one needs to create huge delay and waveform libraries which reflect updated process and interconnect structure as well as device performance. Because of the necessity for more than 100 k times of circuit simulation to create the libraries, it was impossible to update the library quickly including process variation effects. In this paper, we have proposed a realistic new method to generate the libraries on the basis of RSM (Response Surface Method). In application for a BiCMOS ASIC process, we have verified that the new method has achieved the reduction of library creation time to 1/100 within the delay error of 3%. This technique can be used in our TCAD and DA framework, which gives a predictive TCAD generation of delay libraries in concurrent ASIC system and process development.

The objective, when mapping a wafer, is to capture the the full variation across the wafer while minimising the number of measurements. This is a very similar objective to that of experimental design and this paper applies classical Design Of Experiment (DOE) techniques to the selection of measurement points for wafer mapping. The resulting measurements are then fitted using Response Surface Methodology (RSM) from which contour plots or wafer maps can be generated. The accuracy of the fit can be ascertained by inspection of the adjusted R2 value and it is demonstrated that in many cases transformations can be used to improve the accuracy of the resulting wafer maps.

A new methodology for simulation-based CMOS process design has been proposed, using a Hierarchical Response Surface Method (HRSM) and an efficient experimental calibration. The design methodology has been verified using a 0.4 micron CMOS process. The proposed HRSM achieved a 60% reduction of process and device design cost in comparison with those of conventional TCAD. The procedure was performed in conjunction with an experimental calibration technique to provide a reliable threshold voltage prediction including process variation effects. The total CPU cost was 200 hr. on SUN SPARC 10 and the error of the predicted threshold voltage was less than 0.02 V.