Presentation	2007-04-26 Degree Reduction of Lattice Based Attack for RSA Yoshinori AONO,
PDF Download Page	PDF download Page Link
Abstract(in Japanese)	(See Japanese page)
Abstract(in English)	Boneh and Durfee proposed a method for attacking the RSA cryptography, which is based on LLL algorithm and which we call lattice based attack. Experimentally, it was shown that some algorithm following their lattice based attack can break an RSA with public key (e, N) when e ≈ N, factors of N satisfies p+q<3√, and its secret key satisfies d. But unfortunately, we cannot carry out their attack when d ≈ N^<0.2928> because the degree of lattice becomes to large. In this paper, we first overview this lattice based attack and propose our new lattice with which we may be able to reduce the lattice size used to break a given RSA; more specifically, we can reduce the degree of matrix by about 8% to 15% compared with teh algorithm of Boneh and Durfee.
Keyword(in Japanese)	(See Japanese page)
Keyword(in English)	RSA / Lattice based attack / Degree reduction
Paper #	COMP2007-5
Date of Issue

Conference Information
Committee	COMP
Conference Date	2007/4/19(1days)
Place (in Japanese)	(See Japanese page)
Place (in English)
Topics (in Japanese)	(See Japanese page)
Topics (in English)
Chair
Vice Chair
Secretary
Assistant

Paper Information
Registration To	Theoretical Foundations of Computing (COMP)
Language	JPN
Title (in Japanese)	(See Japanese page)
Sub Title (in Japanese)	(See Japanese page)
Title (in English)	Degree Reduction of Lattice Based Attack for RSA
Sub Title (in English)
Keyword(1)	RSA
Keyword(2)	Lattice based attack
Keyword(3)	Degree reduction
1st Author's Name	Yoshinori AONO
1st Author's Affiliation	Dept. of Mathmatical and Computing Sciences Tokyo Institute of Technology()
Date	2007-04-26
Paper #	COMP2007-5
Volume (vol)	vol.107
Number (no)	24
Page	pp.pp.-
#Pages	8
Date of Issue