Strong RSA assumption: Difference between revisions

From Wikipedia, the free encyclopedia

Content deleted Content added

Inline

Revision as of 13:20, 24 April 2020

In cryptography, the strong RSA assumption states that the RSA problem is intractable even when the solver is allowed to choose the public exponent e (for e ≥ 3). More specifically, given a modulus N of unknown factorization, and a ciphertext C, it is infeasible to find any pair (M, e) such that C ≡ M^e mod N.

The strong RSA assumption was first used for constructing signature schemes provably secure against existential forgery without resorting to the random oracle model.

References

Barić N., Pfitzmann B. (1997) Collision-Free Accumulators and Fail-Stop Signature Schemes Without Trees. In: Fumy W. (eds) Advances in Cryptology — EUROCRYPT ’97. EUROCRYPT 1997. Lecture Notes in Computer Science, vol 1233. Springer, Berlin, Heidelberg. doi:10.1007/3-540-69053-0_33
Fujisaki E., Okamoto T. (1997) Statistical zero knowledge protocols to prove modular polynomial relations. In: Kaliski B.S. (eds) Advances in Cryptology — CRYPTO '97. CRYPTO 1997. Lecture Notes in Computer Science, vol 1294. Springer, Berlin, Heidelberg. doi:10.1007/BFb0052225
Ronald Cramer and Victor Shoup. 1999. Signature schemes based on the strong RSA assumption. In Proceedings of the 6th ACM conference on Computer and communications security (CCS ’99). Association for Computing Machinery, New York, NY, USA, 46–51. doi:10.1145/319709.319716
Ronald L. Rivest and Burt Kaliski. 2003. RSA Problem. pdf file

This cryptography-related article is a stub. You can help Wikipedia by expanding it.

Public-key cryptography

Algorithms

Integer factorization	Benaloh Blum–Goldwasser Cayley–Purser Damgård–Jurik GMR Goldwasser–Micali Naccache–Stern Paillier Rabin RSA Okamoto–Uchiyama Schmidt–Samoa
Discrete logarithm	BLS Cramer–Shoup DH DSA ECDH X25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV EKE ElGamal signature scheme MQV Schnorr SPEKE SRP STS
Lattice/SVP/CVP/LWE/SIS	BLISS Kyber NewHope NTRUEncrypt NTRUSign RLWE-KEX RLWE-SIG
Others	AE CEILIDH EPOC HFE IES Lamport McEliece Merkle–Hellman Naccache–Stern knapsack cryptosystem Three-pass protocol XTR

Theory

Standardization

Topics

v t e Cryptography
General	History of cryptography Outline of cryptography Cryptographic protocol Authentication protocol Cryptographic primitive Cryptanalysis Cryptocurrency Cryptosystem Cryptographic nonce Cryptovirology Hash function Cryptographic hash function Key derivation function Digital signature Kleptography Key (cryptography) Key exchange Key generator Key schedule Key stretching Keygen Cryptojacking malware Ransomware Random number generation Cryptographically secure pseudorandom number generator (CSPRNG) Pseudorandom noise (PRN) Secure channel Insecure channel Subliminal channel Encryption Decryption End-to-end encryption Harvest now, decrypt later Information-theoretic security Plaintext Codetext Ciphertext Shared secret Trapdoor function Trusted timestamping Key-based routing Onion routing Garlic routing Kademlia Mix network
Mathematics	Cryptographic hash function Block cipher Stream cipher Symmetric-key algorithm Authenticated encryption Public-key cryptography Quantum key distribution Quantum cryptography Post-quantum cryptography Message authentication code Random numbers Steganography
Category

v t e Computational hardness assumptions
Number theoretic	Integer factorization Phi-hiding RSA problem Strong RSA Quadratic residuosity Decisional composite residuosity Higher residuosity
Group theoretic	Discrete logarithm Diffie-Hellman Decisional Diffie–Hellman Computational Diffie–Hellman
Pairings	External Diffie–Hellman Sub-group hiding Decision linear
Lattices	Shortest vector problem (gap) Closest vector problem (gap) Learning with errors Ring learning with errors Short integer solution
Non-cryptographic	Exponential time hypothesis Unique games conjecture Planted clique conjecture

Retrieved from "https://en.wikipedia.org/w/index.php?title=Strong_RSA_assumption&oldid=952866322"

Categories:

Hidden category:

All stub articles

@@ Line 4: / Line 4: @@
 ==References==
-* Niko Barić and Birgit Pfitzmann. Collision-free accumulators and failstop signature schemes without trees. In Advances in Cryptology— EUROCRYPT ’97, volume 1233 of Lecture Notes in Computer Science, pages 480–494. Springer-Verlag, 1997.
+* Barić N., Pfitzmann B. (1997) Collision-Free Accumulators and Fail-Stop Signature Schemes Without Trees. In: Fumy W. (eds) Advances in Cryptology — EUROCRYPT ’97. EUROCRYPT 1997. Lecture Notes in Computer Science, vol 1233. Springer, Berlin, Heidelberg. {{Doi|10.1007/3-540-69053-0_33}}
-* Eiichiro Fujisaki and Tatsuaki Okamoto. Statistical zero knowledge protocols to prove modular polynomial relations. In Burton S. Kaliski Jr., editor, Proc. CRYPTO ’97, volume 1294 of LNCS, pages 16–30. Springer-Verlag, 1997.
+* Fujisaki E., Okamoto T. (1997) Statistical zero knowledge protocols to prove modular polynomial relations. In: Kaliski B.S. (eds) Advances in Cryptology — CRYPTO '97. CRYPTO 1997. Lecture Notes in Computer Science, vol 1294. Springer, Berlin, Heidelberg. {{Doi|10.1007/BFb0052225}}
-* [[Ronald Cramer]] and [[Victor Shoup]]. Signature schemes based on the strong RSA assumption. ACM Transactions on Information and System Security, 3(3):161–185, 2000. [https://www.zurich.ibm.com/security/ace/sig.pdf pdf file]
+* [[Ronald Cramer]] and [[Victor Shoup]]. 1999. Signature schemes based on the strong RSA assumption. In ''Proceedings of the 6th ACM conference on Computer and communications security'' (''CCS ’99''). Association for Computing Machinery, New York, NY, USA, 46–51. {{Doi|10.1145/319709.319716}}
-* [[Ronald L. Rivest]] and [[Burt Kaliski]].  ''RSA Problem''.  [http://theory.lcs.mit.edu/~rivest/RivestKaliski-RSAProblem.pdf pdf file]
+* [[Ronald L. Rivest]] and [[Burt Kaliski]]. 2003. ''RSA Problem''. [http://theory.lcs.mit.edu/~rivest/RivestKaliski-RSAProblem.pdf pdf file]
 [[Category:Computational hardness assumptions]]