RSA and Rabin Functions: Certain Parts are as Hard as the Whole (Q3787913)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 4051502
Language Label Description Also known as
default for all languages
No label defined
    English
    RSA and Rabin Functions: Certain Parts are as Hard as the Whole
    scientific article; zbMATH DE number 4051502

      Statements

      RSA and Rabin Functions: Certain Parts are as Hard as the Whole (English)
      0 references
      0 references
      0 references
      0 references
      0 references
      1988
      0 references
      RSA encryption
      0 references
      partial information
      0 references
      Rabin encryption
      0 references
      security
      0 references
      pseudorandom number generation
      0 references
      probabilistic encryption schemes
      0 references
      intractability
      0 references
      factoring
      0 references
      The RSA and Rabin encryption functions \(E_ N(\cdot)\) are respectively defined by raising \(x\in Z_ N\) to the power e (where e is relatively prime to \(\phi\) (N)) and squaring modulo N (i.e., \(E_ N(x)=x^ e(mod N)\), \(E_ N(x)=x^ 2(mod N)\), respectively). We prove that for both functions, the following problems are computationally equivalent (each is probabilistic polynomial-time reducible to the other): (1) Given \(E_ N(x)\), find x. (2) Given \(E_ N(x)\), guess the least-significant bit of x with success probability \(1/2+1/poly(n)\) (where n is the length of the modulus N). This equivalence implies that an adversary, given the RSA/Rabin ciphertext, cannot have a non-negligible advantage (over a random coin flip) in guessing the least-significant bit of the plaintext, unless he can invert RSA/factor N. The proof techniques also yield the simultaneous security of the log n least-significant bits. Our results improve the efficiency of pseudorandom number generation and probabilistic encryption schemes based on the intractability of factoring.
      0 references

      Identifiers