EECS 376 Review Session
Randomized Algorithms and Analysis
u Random Variables and Expectation
Copyright By PowCoder代写 加微信 powcoder
u Linearity of Expectation
u Randomized Approximations and Markov’s Inequality u Las Vegas, Monte Carlo Methods and Chernoff Bounds
Random Variables
u A random variable X can be regarded as a function from the sample space Ω tothesetofrealnumbers,i.e.,𝑋∶ Ω→R
u 𝑋=𝑎! isanevent
u 𝑋 = 𝑎! = 𝜔 ∈ Ω ∶ 𝑋 𝜔 = 𝑎! u
u Expectation of a random variable is the “average” value that the random variable takes on
Linearity of Expectation
Randomized Approximations
u Idea: exploit randomness to construct simple algorithms that produce some 𝛼- approximation in expectation
u i.e., the expected value of the output is within a factor of 𝛼 of the optimal
u Example: assigning truth value of each variable randomly for the Max-E3SAT problem (maximize number of satisfied clauses in an exact 3CNF formula) gives “# – approximation
Markov’s (/Reverse Markov’s) Inequality
Randomized Algorithms
u Las Vegas
u Output is always correct
u Expected runtime of algorithm is bounded
u Monte Carlo
u Output is not always correct
u Runtime of algorithm is bounded
u One-Sided Error Randomized Algorithms
No false positives
No false negatives
One-Sided Error Amplification
u Information Theoretic Security (unconditional):
Cannot learn the secret from the ciphertext even with unlimited computing
u Computational Security (conditional):
In order to learn the secret from the ciphertext you would have to solve a computationally hard problem
Two Simple Encryption Schemes
u One Time Pad:
u Information Theoretic, cannot get any information knowing the ciphertext
u Have a key 𝑘 = {𝑘$, 𝑘%, ⋯ , 𝑘&}, shift the first character of your message by 𝑘$, the second character by 𝑘%, etc. (mod 26)
u Drawbacks: Need a key as long as the message, cannot use the same key twice or statistical attacks can be used
u Have a key 𝑘, shift all characters in the message by that key (mod 26) u Breakable by statistical attacks
u Not an encryption scheme, allows you to create a secret shared key u Pick a prime 𝑝 and a generator for that prime 𝑔, then:
u Eve knows and wants to learn the shared key
u She can try to compute 𝑎 (i.e. solve the Discrete Log Problem) by trying consecutive powers of g, but this is inefficient (𝑂(𝑝)) WRT the input size (𝑂(log(𝑝)))
RSA Encryption
u An asymmetric encryption scheme that allows other people to encode messages which only you can decode
u Relies on the difficulty of factoring large numbers
RSA Correctness and Security
u For an attacker to determine the message 𝑚 from the ciphertext 𝑐, they would need to have access to the private key 𝑑. The public information is 𝑛, 𝑒 and 𝑐, so to find 𝑑 they would need to @ind e ∗ d ≡ 1 mod(φ(𝑛)).
u You could do this with the Extended Euclidean Algorithm if you knew φ(𝑛), however to find this you would need to factor 𝑛 into 𝑝, 𝑞 which is believed to be hard
RSA Signatures
u Signing a message is designed to show someone that you are the sender, not to encrypt the message.
u Very similar to encrypting a message, but you sign it with your private key and send that ciphertext and the original message, then other parties can authenticate it using the public key
u Note this is still secure: you either need to find d from 𝑚” or factor n
RSA Example 1
RSA Example 2
RSA Example 2 Continued
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com