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
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
0.9277000427246094
0 references
0.8498220443725586
0 references
0.8208450078964233
0 references
0.8129743933677673
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