On the Strength of the Strong RSA Assumption

Shintaro ITAGAKI; Masahiro MAMBO; Hiroki SHIZUYA

On the Strength of the Strong RSA Assumption

Shintaro ITAGAKI, Masahiro MAMBO, Hiroki SHIZUYA

Full Text Views

0

Share
Cite this

Summary :

The strong RSA assumption is an assumption that the following problem is hard to solve: Given an RSA modulus and a ciphertext, find a pair of plaintext and exponent corresponding to them. It differs from the standard RSA assumption in a sense that in the strong version, no exponent is given as an input. The strong RSA assumption is considered to be stronger than the RSA assumption, but their exact relationship is not known. We investigate the strength of the strong RSA assumption and show that the strong RSA assumption restricted to low exponents is equivalent to the assumption that RSA problem is intractable for any low exponent. We also show that in terms of algebraic computation, the strong RSA assumption is properly stronger than the RSA assumption if there exists an RSA modulus n such that gcd((n),3)=1 and RSA problem is intractable.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E86-A No.5 pp.1164-1170

Publication Date: 2003/05/01

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)

Category

Cite this

Copy

Shintaro ITAGAKI, Masahiro MAMBO, Hiroki SHIZUYA, "On the Strength of the Strong RSA Assumption" in IEICE TRANSACTIONS on Fundamentals, vol. E86-A, no. 5, pp. 1164-1170, May 2003, doi: .
Abstract: The strong RSA assumption is an assumption that the following problem is hard to solve: Given an RSA modulus and a ciphertext, find a pair of plaintext and exponent corresponding to them. It differs from the standard RSA assumption in a sense that in the strong version, no exponent is given as an input. The strong RSA assumption is considered to be stronger than the RSA assumption, but their exact relationship is not known. We investigate the strength of the strong RSA assumption and show that the strong RSA assumption restricted to low exponents is equivalent to the assumption that RSA problem is intractable for any low exponent. We also show that in terms of algebraic computation, the strong RSA assumption is properly stronger than the RSA assumption if there exists an RSA modulus n such that gcd((n),3)=1 and RSA problem is intractable.
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1587/e86-a_5_1164/_p

Copy

@ARTICLE{e86-a_5_1164,
author={Shintaro ITAGAKI, Masahiro MAMBO, Hiroki SHIZUYA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={On the Strength of the Strong RSA Assumption},
year={2003},
volume={E86-A},
number={5},
pages={1164-1170},
abstract={The strong RSA assumption is an assumption that the following problem is hard to solve: Given an RSA modulus and a ciphertext, find a pair of plaintext and exponent corresponding to them. It differs from the standard RSA assumption in a sense that in the strong version, no exponent is given as an input. The strong RSA assumption is considered to be stronger than the RSA assumption, but their exact relationship is not known. We investigate the strength of the strong RSA assumption and show that the strong RSA assumption restricted to low exponents is equivalent to the assumption that RSA problem is intractable for any low exponent. We also show that in terms of algebraic computation, the strong RSA assumption is properly stronger than the RSA assumption if there exists an RSA modulus n such that gcd((n),3)=1 and RSA problem is intractable.},
keywords={},
doi={},
ISSN={},
month={May},}

Copy

TY - JOUR
TI - On the Strength of the Strong RSA Assumption
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1164
EP - 1170
AU - Shintaro ITAGAKI
AU - Masahiro MAMBO
AU - Hiroki SHIZUYA
PY - 2003
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E86-A
IS - 5
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - May 2003
AB - The strong RSA assumption is an assumption that the following problem is hard to solve: Given an RSA modulus and a ciphertext, find a pair of plaintext and exponent corresponding to them. It differs from the standard RSA assumption in a sense that in the strong version, no exponent is given as an input. The strong RSA assumption is considered to be stronger than the RSA assumption, but their exact relationship is not known. We investigate the strength of the strong RSA assumption and show that the strong RSA assumption restricted to low exponents is equivalent to the assumption that RSA problem is intractable for any low exponent. We also show that in terms of algebraic computation, the strong RSA assumption is properly stronger than the RSA assumption if there exists an RSA modulus n such that gcd((n),3)=1 and RSA problem is intractable.
ER -