Search

7.4: Exercises
https://eng.libretexts.org/Under_Construction/Book%3A_The_Joy_of_Cryptography_(Rosulek)/08%3A_Security_against_Chosen_Plaintext_Attacks/8.04%3A_Exercises
Let $\sum$ be an encryption scheme, and suppose there is a program $\mathcal{A}$ that recovers the key from a chosen plaintext attack. Construction $7.4$ is a randomized encryption scheme, but w...Let $\sum$ be an encryption scheme, and suppose there is a program $\mathcal{A}$ that recovers the key from a chosen plaintext attack. Construction $7.4$ is a randomized encryption scheme, but we could also consider defining it as a nonce-based scheme, interpreting $r$ as the nonce: $\operatorname{Enc}(k, r, m)=(r, F(k, r) \oplus m)$ . (b) Prove that the scheme has CPA security if at least one of $\left\{\Sigma_{1}, \Sigma_{2}\right\}$ has CPA security.
4.4: Birthday Probabilities and Sampling with/out Replacement
https://eng.libretexts.org/Under_Construction/Book%3A_The_Joy_of_Cryptography_(Rosulek)/05%3A_Basing_Cryptography_on_Limits_of_Computation/5.04%3A_Birthday_Probabilities_and_Sampling_with_out_Replacement
We can use both of these upper and lower bounds on $e^{-x}$ to show the following: \[\prod_{i=1}^{q-1}\left(1-\frac{i}{N}\right) \leqslant \prod_{i=1}^{q-1} e^{-\frac{i}{N}}=e^{-\sum_{i=1}^{q-1} \fr...We can use both of these upper and lower bounds on $e^{-x}$ to show the following: $\prod_{i=1}^{q-1}\left(1-\frac{i}{N}\right) \leqslant \prod_{i=1}^{q-1} e^{-\frac{i}{N}}=e^{-\sum_{i=1}^{q-1} \frac{i}{N}}=e^{-\frac{q(q-1)}{2 N}} \leqslant 1-0.632 \frac{q(q-1)}{2 N} .$ With the last inequality we used the fact that $q \leqslant \sqrt{2 N}$ , and therefore $\frac{q(q-1)}{2 N} \leqslant 1$ (this is necessary to apply the inequality $e^{-x} \leqslant 1-0.632 x$ ).
6: Pseudorandom Functions and Block Ciphers
https://eng.libretexts.org/Under_Construction/Book%3A_The_Joy_of_Cryptography_(Rosulek)/07%3A_Pseudorandom_Functions_and_Block_Ciphers
A pseudorandom generator allows us to take a small amount of uniformly sampled bits, and “amplify” them into a larger amount of uniform-looking bits. A PRG must run in polynomial time, so the length o...A pseudorandom generator allows us to take a small amount of uniformly sampled bits, and “amplify” them into a larger amount of uniform-looking bits. A PRG must run in polynomial time, so the length of its pseudorandom output can only be polynomial in the security parameter. But what if we wanted even more pseudorandom output? Is it possible to take λ uniformly sampled bits and generate 2λ pseudorandom bits?
2.1: How to Write a Security Definition
https://eng.libretexts.org/Under_Construction/Book%3A_The_Joy_of_Cryptography_(Rosulek)/03%3A_The_Basics_of_Provable_Security/3.01%3A_How_to_Write_a_Security_Definition
"an encryption scheme is a good one if encryptions of $m_{L}$ look like encryptions of $m_{R}$ to an attacker, when each key is secret and used to encrypt only one plaintext, even when the attacke..."an encryption scheme is a good one if encryptions of $m_{L}$ look like encryptions of $m_{R}$ to an attacker, when each key is secret and used to encrypt only one plaintext, even when the attacker chooses $m_{L}$ and $m_{R} .$
2: The Basics of Provable Security
https://eng.libretexts.org/Under_Construction/Book%3A_The_Joy_of_Cryptography_(Rosulek)/03%3A_The_Basics_of_Provable_Security
This chapter is about the fundamental skills that revolve around security definitions: how to write them, how to understand & interpret them, how to prove security using the hybrid technique, and how ...This chapter is about the fundamental skills that revolve around security definitions: how to write them, how to understand & interpret them, how to prove security using the hybrid technique, and how to demonstrate insecurity using attacks against the security definition.
7: Security against Chosen Plaintext Attacks
https://eng.libretexts.org/Under_Construction/Book%3A_The_Joy_of_Cryptography_(Rosulek)/08%3A_Security_against_Chosen_Plaintext_Attacks
Our previous security definitions for encryption capture the case where a key is used to encrypt only one plaintext. Fortunately we have arranged things so that we get the "correct" security definitio...Our previous security definitions for encryption capture the case where a key is used to encrypt only one plaintext. Fortunately we have arranged things so that we get the "correct" security definition when we modify the earlier definition in a natural way. We say that $\Sigma$ has security against chosen-plaintext attacks (CPA security) if $\mathcal{L}_{\text {cpa-L }}^{\Sigma} \approx \mathcal{L}_{\text {cpa-R }}^{\Sigma}$ , where:
12.1: Definitions
https://eng.libretexts.org/Under_Construction/Book%3A_The_Joy_of_Cryptography_(Rosulek)/13%3A_Authenticated_Encryption_and_AEAD/13.01%3A_Definitions
The two libraries are different from each other in two major ways: whether the calling program sees real ciphertexts or random strings (that have nothing to do with the given plaintext), and whether t...The two libraries are different from each other in two major ways: whether the calling program sees real ciphertexts or random strings (that have nothing to do with the given plaintext), and whether the calling program sees the true result of decryption or an error message. By making a distinction between plaintext and associated data separately in AEAD, the ciphertext length can depend only on the length of the plaintext, and not depend on the length of the associated data.
4.3: Indistinguishability
https://eng.libretexts.org/Under_Construction/Book%3A_The_Joy_of_Cryptography_(Rosulek)/05%3A_Basing_Cryptography_on_Limits_of_Computation/5.03%3A_Indistinguishability
\[\begin{gathered} =\left|\begin{array}{c} \left(\operatorname{Pr}\left[\mathcal{A} \diamond \mathcal{L}_{\text {left }} \Rightarrow 1 \mid \mathcal{B}_{\text {left }}\right] \cdot p^{*}+\operatorname...\[\begin{gathered} =\left|\begin{array}{c} \left(\operatorname{Pr}\left[\mathcal{A} \diamond \mathcal{L}_{\text {left }} \Rightarrow 1 \mid \mathcal{B}_{\text {left }}\right] \cdot p^{*}+\operatorname{Pr}\left[\mathcal{A} \diamond \mathcal{L}_{\text {left }} \Rightarrow 1 \mid \overline{\mathcal{B}_{\text {left }}}\right]\left(1-p^{*}\right)\right) \\ -\left(\operatorname{Pr}\left[\mathcal{A} \diamond \mathcal{L}_{\text {right }} \Rightarrow 1 \mid \mathcal{B}_{\text {right }}\right] \cdot p^{*…
10: Message Authentication Codes
https://eng.libretexts.org/Under_Construction/Book%3A_The_Joy_of_Cryptography_(Rosulek)/11%3A_Message_Authentication_Codes
Imagine there was a way to "certify" that a ciphertext was not adversarially generated - i.e., it was generated by someone who knows the secret key. What we are asking for is not to hide the ciphertex...Imagine there was a way to "certify" that a ciphertext was not adversarially generated - i.e., it was generated by someone who knows the secret key. What we are asking for is not to hide the ciphertext but to authenticate it: to ensure that it was generated by someone who knows the secret key. One of the most important applications of a message authentication code is to transform a CPA-secure encryption scheme into a CCA-secure one.
6.2: PRFs vs PRGs; Variable-Hybrid Proofs
https://eng.libretexts.org/Under_Construction/Book%3A_The_Joy_of_Cryptography_(Rosulek)/07%3A_Pseudorandom_Functions_and_Block_Ciphers/7.02%3A_PRFs_vs_PRGs%3B_Variable-Hybrid_Proofs
The inconvenience in the proof stems from a mismatch of the $s$ variable in $\mathcal{L}_{\text {prg-real and }}$ the $k$ variable in $\mathcal{L}_{\text {prf-real. }}$ In \(\mathcal{L}_{\text...The inconvenience in the proof stems from a mismatch of the $s$ variable in $\mathcal{L}_{\text {prg-real and }}$ the $k$ variable in $\mathcal{L}_{\text {prf-real. }}$ In $\mathcal{L}_{\text {prg-real, }} s$ is local to the QUERY subroutine.
0: Review of Concepts and Notation
https://eng.libretexts.org/Under_Construction/Book%3A_The_Joy_of_Cryptography_(Rosulek)/01%3A_Review_of_Concepts_and_Notation
The material in this section is meant as a review. Despite that, many students report that they find this review useful for the rest of the book.

Search

Text Color

Text Size

Margin Size

Font Type

Support Center

How can we help?