2013 | OriginalPaper | Buchkapitel
Toward Separating the Strong Adaptive Pseudo-freeness from the Strong RSA Assumption
verfasst von : Masayuki Fukumitsu, Shingo Hasegawa, Shuji Isobe, Eisuke Koizumi, Hiroki Shizuya
Erschienen in: Information Security and Privacy
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
The notion of pseudo-freeness of a group was introduced by Hohenberger, and formalized by Rivest in order to unify cryptographic assumptions. Catalano, Fiore and Warinschi proposed the adaptive pseudo-free group as a generalization of pseudo-free group. They showed that the RSA group
$\mathbb{Z}_N^\times$
is pseudo-free even if the adversary against pseudo-freeness is allowed to operate adaptively, provided that the adaptive behavior of the adversary is restricted by some specific parametric distribution. They also proposed the notion of strong adaptive pseudo-freeness in which the adaptive behavior of the adversary is not restricted. However, it remains open whether
$\mathbb{Z}_N^\times$
is also strongly-adaptive pseudo-free under the strong RSA (SRSA) assumption.
In this paper, we give a negative circumstantial evidence for the question. We show that the SRSA assumption does not imply the strong adaptive pseudo-freeness of
$\mathbb{Z}_N^\times$
, as far as the algebraic reduction is concerned. The algebraic reduction means that the algorithm of the black-box reduction performs only group operations for elements in
$\mathbb{Z}_N^\times$
. Our result indicates that the strong adaptive pseudo-freeness for the RSA group
$\mathbb{Z}_N^\times$
cannot be shown under the SRSA assumption, by employing only current proof techniques which are used in ordinary security proofs.