On the impossibility of proving security of strong-RSA signatures via the RSA assumption

Masayuki Fukumitsu; Shingo Hasegawa; Shuji Isobe; Hiroki Shizuya

doi:10.1007/978-3-319-08344-5_19

On the impossibility of proving security of strong-RSA signatures via the RSA assumption

Masayuki Fukumitsu, Shingo Hasegawa, Shuji Isobe, Hiroki Shizuya

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

5 Citations (Scopus)

Abstract

We pose a question whether or not the standard RSA assumption is sufficient to prove the security of the strong RSA-based (SRSA-based, for short) signatures. In this paper, we show a negative circumstantial evidence for the question. Namely, several SRSA-based signatures cannot be proven to be sEUF-CMA, or even EUF-KOA, under the RSA assumption as far as a modulus-preserving algebraic reduction is concerned. Our result is obtained as an important application of the adaptive pseudo-free group introduced by Catalano, Fiore and Warinschi that can be regarded as an abstract framework of signatures. We in fact show that the adaptive pseudo-freeness of the RSA group cannot be proven from the RSA assumption via such reductions.

Original language	English
Title of host publication	Information Security and Privacy - 19th Australasian Conference, ACISP 2014, Proceedings
Publisher	Springer-Verlag
Pages	290-305
Number of pages	16
ISBN (Print)	9783319083438
DOIs	https://doi.org/10.1007/978-3-319-08344-5_19
Publication status	Published - 2014 Jan 1
Event	19th Australasian Conference on Information Security and Privacy, ACISP 2014 - Wollongong, NSW, Australia Duration: 2014 Jul 7 → 2014 Jul 9

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	8544 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	19th Australasian Conference on Information Security and Privacy, ACISP 2014
Country/Territory	Australia
City	Wollongong, NSW
Period	14/7/7 → 14/7/9

Keywords

Adaptive Pseudo-Free Groups
Algebraic Reduction
Pseudo-Free Groups
RSA Assumption
Strong-RSA Signature Schemes

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-319-08344-5_19

Cite this

Fukumitsu, M., Hasegawa, S., Isobe, S., & Shizuya, H. (2014). On the impossibility of proving security of strong-RSA signatures via the RSA assumption. In Information Security and Privacy - 19th Australasian Conference, ACISP 2014, Proceedings (pp. 290-305). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8544 LNCS). Springer-Verlag. https://doi.org/10.1007/978-3-319-08344-5_19

On the impossibility of proving security of strong-RSA signatures via the RSA assumption. / Fukumitsu, Masayuki; Hasegawa, Shingo ; Isobe, Shuji et al.
Information Security and Privacy - 19th Australasian Conference, ACISP 2014, Proceedings. Springer-Verlag, 2014. p. 290-305 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8544 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Fukumitsu, M, Hasegawa, S , Isobe, S & Shizuya, H 2014, On the impossibility of proving security of strong-RSA signatures via the RSA assumption. in Information Security and Privacy - 19th Australasian Conference, ACISP 2014, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8544 LNCS, Springer-Verlag, pp. 290-305, 19th Australasian Conference on Information Security and Privacy, ACISP 2014, Wollongong, NSW, Australia, 14/7/7. https://doi.org/10.1007/978-3-319-08344-5_19

Fukumitsu M, Hasegawa S , Isobe S , Shizuya H. On the impossibility of proving security of strong-RSA signatures via the RSA assumption. In Information Security and Privacy - 19th Australasian Conference, ACISP 2014, Proceedings. Springer-Verlag. 2014. p. 290-305. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-08344-5_19

Fukumitsu, Masayuki ; Hasegawa, Shingo ; Isobe, Shuji et al. / On the impossibility of proving security of strong-RSA signatures via the RSA assumption. Information Security and Privacy - 19th Australasian Conference, ACISP 2014, Proceedings. Springer-Verlag, 2014. pp. 290-305 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{8458ccf45dc74deba541b9f69bac31de,

title = "On the impossibility of proving security of strong-RSA signatures via the RSA assumption",

abstract = "We pose a question whether or not the standard RSA assumption is sufficient to prove the security of the strong RSA-based (SRSA-based, for short) signatures. In this paper, we show a negative circumstantial evidence for the question. Namely, several SRSA-based signatures cannot be proven to be sEUF-CMA, or even EUF-KOA, under the RSA assumption as far as a modulus-preserving algebraic reduction is concerned. Our result is obtained as an important application of the adaptive pseudo-free group introduced by Catalano, Fiore and Warinschi that can be regarded as an abstract framework of signatures. We in fact show that the adaptive pseudo-freeness of the RSA group cannot be proven from the RSA assumption via such reductions.",

keywords = "Adaptive Pseudo-Free Groups, Algebraic Reduction, Pseudo-Free Groups, RSA Assumption, Strong-RSA Signature Schemes",

author = "Masayuki Fukumitsu and Shingo Hasegawa and Shuji Isobe and Hiroki Shizuya",

year = "2014",

month = jan,

day = "1",

doi = "10.1007/978-3-319-08344-5_19",

language = "English",

isbn = "9783319083438",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer-Verlag",

pages = "290--305",

booktitle = "Information Security and Privacy - 19th Australasian Conference, ACISP 2014, Proceedings",

note = "19th Australasian Conference on Information Security and Privacy, ACISP 2014 ; Conference date: 07-07-2014 Through 09-07-2014",

}

TY - GEN

T1 - On the impossibility of proving security of strong-RSA signatures via the RSA assumption

AU - Fukumitsu, Masayuki

AU - Hasegawa, Shingo

AU - Isobe, Shuji

AU - Shizuya, Hiroki

PY - 2014/1/1

Y1 - 2014/1/1

N2 - We pose a question whether or not the standard RSA assumption is sufficient to prove the security of the strong RSA-based (SRSA-based, for short) signatures. In this paper, we show a negative circumstantial evidence for the question. Namely, several SRSA-based signatures cannot be proven to be sEUF-CMA, or even EUF-KOA, under the RSA assumption as far as a modulus-preserving algebraic reduction is concerned. Our result is obtained as an important application of the adaptive pseudo-free group introduced by Catalano, Fiore and Warinschi that can be regarded as an abstract framework of signatures. We in fact show that the adaptive pseudo-freeness of the RSA group cannot be proven from the RSA assumption via such reductions.

AB - We pose a question whether or not the standard RSA assumption is sufficient to prove the security of the strong RSA-based (SRSA-based, for short) signatures. In this paper, we show a negative circumstantial evidence for the question. Namely, several SRSA-based signatures cannot be proven to be sEUF-CMA, or even EUF-KOA, under the RSA assumption as far as a modulus-preserving algebraic reduction is concerned. Our result is obtained as an important application of the adaptive pseudo-free group introduced by Catalano, Fiore and Warinschi that can be regarded as an abstract framework of signatures. We in fact show that the adaptive pseudo-freeness of the RSA group cannot be proven from the RSA assumption via such reductions.

KW - Adaptive Pseudo-Free Groups

KW - Algebraic Reduction

KW - Pseudo-Free Groups

KW - RSA Assumption

KW - Strong-RSA Signature Schemes

UR - http://www.scopus.com/inward/record.url?scp=84904203379&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84904203379&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-08344-5_19

DO - 10.1007/978-3-319-08344-5_19

M3 - Conference contribution

AN - SCOPUS:84904203379

SN - 9783319083438

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 290

EP - 305

BT - Information Security and Privacy - 19th Australasian Conference, ACISP 2014, Proceedings

PB - Springer-Verlag

T2 - 19th Australasian Conference on Information Security and Privacy, ACISP 2014

Y2 - 7 July 2014 through 9 July 2014

ER -

On the impossibility of proving security of strong-RSA signatures via the RSA assumption

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this