International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Takeshi Shimoyama

Publications

Year
Venue
Title
2012
ASIACRYPT
2007
CHES
2007
EPRINT
Low-Density Attack Revisited
The low-density attack proposed by Lagarias and Odlyzko is a powerful algorithm against the subset sum problem. The improvement algorithm due to Coster et al. would solve almost all the problems of density < 0.9408... in the asymptotical sense. On the other hand, the subset sum problem itself is known as an NP-hard problem, and a lot of efforts have been paid to establish public-key cryptosystems based on the problem. In these cryptosystems, densities of the subset sum problems should be higher than 0.9408... in order to avoid the low-density attack. For example, the Chor-Rivest cryptosystem adopted subset sum problems with relatively high densities. In this paper, we further improve the low-density attack by incorporating an idea that integral lattice points can be covered with polynomially many spheres of shorter radius and of lower dimension. As a result, the success probability of our attack can be higher than that of Coster et al.'s attack for fixed dimensions. The density bound is also improved for fixed dimensions. Moreover, we numerically show that our improved low-density attack makes the success probability higher in case of low Hamming weight solution, such as the Chor-Rivest cryptosystem, if we assume SVP oracle calls.
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
Wang's sufficient conditions of MD5 are not sufficient
Jun Yajima Takeshi Shimoyama
In this paper, we report that the "sufficient conditions" of MD5 of the modification technique for the collision search algorithm described by Wang are not sufficient. In our analysis, we show at least 4 extra-conditions for the message modification in the first block and corrections of the several conditions which are correspond to the highest (32nd) bit of the sufficient conditions in the second block should be needed. And we show the new collision message which is completely different from the message pairs showed by Wang by using our extended sufficient conditions.
2004
EPRINT
GNFS Factoring Statistics of RSA-100, 110, ..., 150
Kazumaro Aoki Yuji Kida Takeshi Shimoyama Hiroki Ueda
GNFS (general number field sieve) algorithm is currently the fastest known algorithm for factoring large integers. Up to the present, several running time estimates for GNFS are announced. These estimates are usually based on the previous factoring results. However, since the previous factoring results were done by various programs and/or computers, it is difficult to compare those running time. We implemented GNFS and factored 100- to 150-digits number on the same environment. This manuscript describes the statistics of these factorings.
2002
FSE
2002
FSE
2002
EPRINT
Theoretical Analysis of ``Correlations in RC6''
In this paper, we give the theoretical analysis of Chi-square attack proposed by Knudsen and Meier on the RC6 block cipher. To this end, we propose the novel method of security evaluation against Chi-square attack precisely including key dependency by introducing a technique ``Transition Matrix Computing.'' On the other hand, the way of security evaluation against Chi-square attack has not been known except the computer experiment. We should note that it is the first results the way of security evaluation against Chi-square attack is shown theoretically. Using this method, we can obtain the ``weakest keys'' against the attack.
2001
FSE
1999
FSE
1998
CRYPTO
1998
FSE