For RSA, May showed a deterministic polynomial time equivalence of computing d to factoring N(=pq). On the other hand, Takagi showed a variant of RSA such that the decryption algorithm is faster than the standard RSA, where N=prq while ed=1 mod(p-1)(q-1). In this paper, we show that a deterministic polynomial time equivalence also holds in this variant. The coefficient matrix T to which LLL algorithm is applied is no longer lower triangular, and hence we develop a new technique to overcome this problem.

We introduce a “generalized small inverse problem (GSIP)” and present an algorithm for solving this problem. GSIP is formulated as finding small solutions of f(x0, x1, ..., xn)=x0 h(x1, ..., xn)+C=0 (mod ; M) for an n-variate polynomial h, non-zero integers C and M. Our algorithm is based on lattice-based Coppersmith technique. We provide a strategy for construction of a lattice basis for solving f=0, which is systematically transformed from a lattice basis for solving h=0. Then, we derive an upper bound such that the target problem can be solved in polynomial time in log M in an explicit form. Since GSIPs include some RSA-related problems, our algorithm is applicable to them. For example, the small key attacks by Boneh and Durfee are re-found automatically.

Subspace membership encryption (SME), a generalization of inner product encryption (IPE), was recently formalized by Boneh, Raghunathan, and Segev in Asiacrypt 2013. The main motivation for SME was that traditional predicate encryptions did not yield function privacy, a security notion introduced by Boneh et al. in Crypto 2013 that captures the privacy of the predicate associated to the secret key. Although they gave a generic construction of SME based on any IPE, we show that their construction of SME for small attribute space was incorrect and provide an attack that breaks the attribute hiding security, a baseline security notion for predicate encryptions that captures the privacy of the attribute associated with the ciphertext. Then, we propose a generalized construction of SME and prove that the attribute hiding security can not be achieved even in the newly defined setting. Finally, we further extend our generalized construction of SME and propose a SME that achieves the attribute hiding property even when the attribute space is small. In exchange our proposed scheme does not yield function privacy and the construction is rather inefficient. Although we did not succeed in constructing a SME both yielding function privacy and attribute hiding security, ours is the first attribute hiding SME scheme whose attribute space is polynomial in the security parameter, and we formalized a richer framework for constructing SMEs and discovered a trade-off like relationship between the two security notions.

In this paper, a method is proposed to construct a visual secret sharing (VSS) scheme for multiple secret images in which each share can be rotated with 180 degrees in decryption. The proposed VSS scheme can encrypt more number of secret images compared with the normal VSS schemes. Furthermore, the proposed technique can be applied to the VSS scheme that allows to turn over some shares in decryption. From the theoretical point of view, it is interesting to note that such VSS schemes cannot be obtained from so-called basis matrices straightforwardly.

Although a great deal of research has been done on electronic cash schemes with blind multisignatures to prevent an insider attack, there is no discussion of a formal security model in the literature. Firstly we discussed the security model of e-cash schemes based on the blind multisignature scheme against a (restricted) attack model and proposed a concrete scheme proven to be secure in the model [1]; however, this attack model disallows an attacker from corrupting an issuing bank and shops in the forgery game. In this paper, first, we reconsider the security model to remove the restriction of the attack model. Second, we propose a new untraceable e-cash scheme with a blind multisignature scheme and prove that the proposed scheme is secure against the (non-restricted) attacks under the DDH assumption in the random oracle model.

Maurer and Yacobi proposed an ID-Based key distribution scheme in 1991. In this scheme, the private key for each user is generated by solving discrete logarithm problem. We examine the realizability of this scheme. We show that this scheme can be practical by appropriate parameter setting.

Power exponentiation is an important operation in modern cryptography. This operation can be efficiently calculated using the concept of the addition chain. In this paper, two new systematic methods, a Run-length method and a Hybrid method, are proposed to generate a short addition chain. The performance of these two methods are theoretically analyzed and it is shown that the Hybrid method is more efficient and practical than known methods. The proposed methods can reduce the addition chain length by 8%, in the best case, compared to the Window method.

At Eurocrypt'05, Wang et al. presented efficient collision attacks on MD5 and MD4 hash functions. They found a collision of MD5 with a complexity of less than 237 MD5 hash operations, and a collision of MD4 with complexity less than 28 MD4 hash operations. In their attack, the procedure to generate a collision is divided into 4 steps. First, they determine the message differential and output differentials of chaining variables in each step, which generates a collision with small complexity. Second, they construct sufficient conditions that guarantee that the desired differential is always calculated. Third, they find a message modification that can satisfy the sufficient conditions with high probability. Finally, they search for a message that satisfies all sufficient conditions. In this paper, we focus on the message modification of MD5 and MD4, and propose a new message modification. Using our message modification, a collision of MD5 can be found with complexity less than 229 MD5 hash operations, and a collision of MD4 can be found with complexity less than 3 MD4 hash operations. To improve the complexity from previous attacks, we mainly use two ideas. The first idea is to use message modification that can satisfy more sufficient conditions in the second round than in previous attacks. The second idea is to use message modification that can enable us to search for a collision starting from an intermediate step.

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.

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.

The addition chain (A-chain) and addition-subtraction chain (AS-chain) are efficient tools to calculate power Me (or multiplication eM), where integere is fixed andM is variable. Since the optimization problem to find the shortest A (or AS)-chain is NP-hard, many algorithms to get a sub-optimal A (or AS)-chain in polynomial time are proposed. In this paper, a window method for the AS-chain and an extended window method for the A-chain and AS-chain are proposed and their performances are theoretically evaluated by applying the theory of the optimal variable-to-fixed length code, i. e. , Tunstall code, in data compression. It is shown by theory and simulation that the proposed algorithms are more efficient than other algorithms in practical cases in addition to the asymptotic case.

Many knapsack cryptosystems have been proposed but almost all the schemes are vulnerable to lattice attack because of their low density. To prevent the lattice attack, Chor and Rivest proposed a low weight knapsack scheme, which made the density higher than critical density. In Asiacrypt2005, Nguyen and Stern introduced pseudo-density and proved that if the pseudo-density is low enough (even if the usual density is not low enough), the knapsack scheme can be broken by a single call to SVP/CVP oracle. However, the usual density and the pseudo-density are not sufficient to measure the resistance to the lattice attack individually. In this paper, we first introduce the new notion of density D, which naturally unifies the previous two density. Next, we derive conditions for our density so that a knapsack scheme is secure against lattice attack. We obtain a critical bound of density which depends only on the rate of the message length and its Hamming weight. Furthermore, we show that if D<0.8677, the knapsack scheme is solved by lattice attack. Next, we show that the critical bound goes to 1 if the Hamming weight decreases, which means that it is (almost) impossible to construct a low weight knapsack scheme which is supported by an argument of density.

Dr. Kenji Koyama, one of the most respected and prominent Japanese researchers in modern cryptography, passed away on March 27, 2000. He left behind him many outstanding academic achievements in cryptography as well as other areas such as emotion transmission theory, learning and mathematical games. In this manuscript, with our deepest sympathy and greatest appreciation for his contribution to our society, we introduce his major works mainly in cryptography, although his papers in other areas are included in the bibliography list.

In 2005, collision resistance of several hash functions was broken by Wang et al. The strategy of determining message differences is the most important part of collision attacks against hash functions. So far, many researchers have tried to analyze Wang et al.'s method and proposed improved collision attacks. Although several researches proposed improved attacks, all improved results so far were based on the same message differences proposed by Wang et al. In this paper, we propose new message differences for collision attacks on MD4 and MD5. Our message differences of MD4 can generate a collision with complexity of less than two MD4 computations, which is faster than the original Wang et al.'s attack, and moreover, than the all previous attacks. This is the first result that improves the complexity of collision attack by using different message differences from Wang et al.'s. Regarding MD5, so far, no other message difference from Wang et al.'s is known. Therefore, study for constructing method of other message differences on MD5 should be interesting. Our message differences of MD5 generates a collision with complexity of 242 MD5 computations, which is slower than the latest best attack. However, since our attack needs only 1 bit difference, it has some advantages in terms of message freedom of collision messages.

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.

Given an integer n-dimensional lattice basis, the random sampling reduction was proven to find a short vector in arithmetic steps with an integer k, which is freely chosen by users. This paper introduces new random sampling reduction using precomputation techniques. The computation cost is almost independent of the lattice dimension number. The new method is therefore especially advantageous to find a short lattice vector in higher dimensions. The arithmetic operation number of our new method is about 20% of the random sampling reduction with 200 dimensions, and with 1000 dimensions it is less than 1% ( 1/130) of that of the random sampling reduction with representative parameter settings under reasonable assumptions.

In this paper, we discuss the collision search for hash functions, mainly in terms of their advanced message modification. The advanced message modification is a collision search tool based on Wang et al.'s attacks. Two advanced message modifications have previously been proposed: cancel modification for MD4 and MD5, and propagation modification for SHA-0. In this paper, we propose a new concept of advanced message modification, submarine modification. As a concrete example combining the ideas underlying these modifications, we apply submarine modification to the collision search for SHA-0. As a result, we show that this can reduce the collision search attack complexity from 239 to 236 SHA-0 compression operations.

In this paper, we propose password recovery attacks against challenge-response authentication protocols. Our attacks use a message difference for a MD5 collision attack proposed in IEICE 2008. First, we show how to efficiently find a message pair that collides with the above message difference. Second, we show that a password used in authenticated post office protocol (APOP) can be recovered practically. We also show that the password recovery attack can be applied to a session initiation protocol (SIP) and digest authentication. Our attack can recover up to the first 31 password characters in a short time and up to the first 60 characters faster than the naive search method. We have implemented our attack and confirmed that 31 characters can be successfully recovered.

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.