On the Impossibility of Proving Security of Strong-RSA Signatures via the RSA Assumption

被引：0

作者：

Fukumitsu, Masayuki ^{[1
]}

Hasegawa, Shingo ^{[2
]}

Isobe, Shuji ^{[2
]}

Shizuya, Hiroki ^{[2
]}

机构：

[1] Hokkaido Informat Univ, Fac Informat Media, Nishi Nopporo 59-2, Ebetsu, Hokkaido 0698585, Japan

[2] Tohoku Univ, Grad Sch Informat Sci, Aoba Ku, Sendai, Miyagi 9808576, Japan

来源：

INFORMATION SECURITY AND PRIVACY, ACISP 2014 | 2014年 / 8544卷

关键词：

Strong-RSA Signature Schemes; Pseudo-Free Groups; Adaptive Pseudo-Free Groups; RSA Assumption; Algebraic Reduction; PROGRAMMABLE HASH FUNCTIONS; PSEUDO-FREE; SCHEME; EQUIVALENT;

D O I：

暂无

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

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 Z(N)(x) cannot be proven from the RSA assumption via such reductions.

引用

页码：290 / 305

页数：16

共 38 条

[31] Paillier P, 2007, LECT NOTES COMPUT SC, V4377, P31
[32] Paillier P, 2006, LECT NOTES COMPUT SC, V4284, P252
[33] Rivest RL, 2004, LECT NOTES COMPUT SC, V2951, P505
[34] Schäge S, 2011, LECT NOTES COMPUT SC, V6632, P189, DOI 10.1007/978-3-642-20465-4_12
[35] Schäge S, 2009, LECT NOTES COMPUT SC, V5848, P104, DOI 10.1007/978-3-642-04642-1_10
[36] Seurin Y, 2012, LECT NOTES COMPUT SC, V7237, P554, DOI 10.1007/978-3-642-29011-4_33
[37] ON THE GENERATION OF CRYPTOGRAPHICALLY STRONG PSEUDO-RANDOM SEQUENCES
SHAMIR, A
[J]. ACM TRANSACTIONS ON COMPUTER SYSTEMS, 1983, 1 (01): : 38 - 44
[38] Zhu HF, 2001, CHINESE J ELECTRON, V10, P484

← 1 2 3 4 →