International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Noboru Kunihiro

Affiliation: The University of Tokyo

Publications

Year
Venue
Title
2016
CRYPTO
2016
PKC
2015
EPRINT
2014
CRYPTO
2014
PKC
2014
EPRINT
2014
EPRINT
2014
CHES
2013
PKC
2012
PKC
2012
PKC
2011
PKC
2010
EPRINT
Solving Generalized Small Inverse Problems
Noboru Kunihiro
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(x_0, x_1, \ldots , x_n)=x_0 h(x_1, \ldots , x_n)+C=0 (\bmod \; 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 are 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.
2008
EUROCRYPT
2007
FSE
2007
PKC
2006
ASIACRYPT
2006
EPRINT
Message Modification for Step 21-23 on SHA-0
In CRYPTO 2005, Xiaoyun Wang, Hongbo Yu and Yiqun Lisa Yin proposed an efficient collision attack on SHA-0. Collision messages are found with complexity $2^{39}$ SHA-0 operations by using their method. Collision messages can be obtained when a message satisfying all sufficient conditions is found. In their paper, they proposed message modifications that can satisfy all sufficient conditions of step 1-20. However, they didn't propose message modifications for sufficient conditions after step 21. In this paper, we propose message modifications for sufficient conditions of step 21-23. By using our message modifications, collision messages are found with complexity $2^{36}$ SHA-0 operations.
2006
EPRINT
How to Construct Sufficient Condition in Searching Collisions of MD5
In Eurocrypt 2005, Wang et al. presented a collision attak on MD5. In their paper, they intoduced gSufficient Conditionh which would be needed to generate collisions. In this paper, we explain how to construct sufficent conditions of MD5 when a differential path is given. By applying our algorithm to a collision path given byWang et al, we found that sufficient conditions introduced by them contained some unnecessary conditions. Generally speaking, when a differential path is given, corresponding sets of sufficient conditions is not unique. In our research, we analyzed the differential path found by Wang et al, and we found a different set of sufficient conditions from that of Wang et al. We have generated collisions by using our sifficient conditions.
2005
EPRINT
Improved Collision Attack on MD4
In this paper, we propose an attack method to find collisions of MD4 hash function. This attack is the improved version of the attack which was invented by Xiaoyun Wang et al [1]. We were able to find collisions with probability almost 1, and the average complexity to find a collision is upper bounded by three times of MD4 hash operations. This result is improved compared to the original result of [1] where the probability were from $2^{-6}$ to $2^{-2}$, and the average complexity to find a collision was upper bounded by $2^8$ MD4 hash operations. We also point out the lack of sufficient conditions and imprecise modifications for the original attack in [1].
2005
EPRINT
Improved Collision Attack on MD5
In EUROCRYPT2005, a collision attack on MD5 was proposed by Wang et al. In this attack, conditions which are sufficient to generate collisions (called ``sufficient condition") are introduced. This attack raises the success probability by modifing messages to satisfy these conditions. In this attack, 37 conditions cannot be satisfied even messages are modified. Therefore, the complexity is $2^{37}$. After that, Klima improved this result. Since 33 conditions cannot be satisfied in his method, the complexity is $2^{33}$. In this paper, we propose new message modification techniques which are more efficient than attacks proposed so far. In this method, 29 conditions cannot be satisfied. However, this method is probabilistic, and the probability that this method work correctly is roughly 1/2. Therefore, the complexity of this attack is $2^{30}$. Furthermore, we propose a more efficient collision search algorithm than that of Wang et al. By using this algorithm, the total complexity is reduced into roughly 5/8.
1999
ASIACRYPT
1998
EUROCRYPT

Program Committees

PKC 2013