40 Questions
What is the main difference between perfect secrecy and computational secrecy?
Perfect secrecy leaks absolutely no information about an encrypted message, while computational secrecy leaks information with a tiny probability to eavesdroppers with bounded computational power
What does a (t, ϵ)-secure scheme guarantee?
No adversary running for time at most t can break the scheme with probability at most ϵ
Why is it more convenient to measure running time in terms of CPU cycles for (t, ϵ)-secure schemes?
It aligns with the practical implementation of cryptographic schemes
Which block cipher mode is deterministic and cannot be CPA-secure?
Electronic Code Book (ECB) Mode
In which block cipher mode is a uniform initialization vector (IV) of length n chosen?
Cipher Block Chaining (CBC) Mode
Which block cipher mode has ciphertext length double the plaintext length in a CPA-secure construction?
Electronic Code Book (ECB) Mode
Which block cipher mode involves encrypting a message of length l using a length-preserving block cipher?
Counter (CTR) Mode
Which block cipher mode uses an initialization vector (IV) for encryption?
Cipher Block Chaining (CBC) Mode
What is the key space size for a private-key encryption scheme using a 128-bit key?
$2^{128}$
For c = 1 and n = 64, how many years does a 4 GHz processor with 16 cores require at most to break the scheme?
10 years
How are realistic adversaries modeled in cryptographic schemes?
Probabilistic algorithms running in time polynomial in n
Which of the following is a characteristic of a pseudorandom function?
Efficient and length-preserving
In the context of distinguishing pseudorandom functions, what does the theorem state about the construction's security?
If F is pseudorandom, then the construction is CPA-secure
What is a characteristic of a strong pseudorandom permutation?
Cannot be efficiently distinguished from a random permutation
What is the definition of EAV-security in private-key encryption?
It is a form of security where an adversary behaves the same, regardless of whether it observes an encryption of $m_0$ or $m_1$
What is the key characteristic of a pseudorandom generator used in EAV-secure encryption schemes?
It transforms a short, uniform bitstring into a longer, 'uniform-looking' output string
What is the role of semantic security in private-key encryption?
It is the analog of perfect secrecy for computationally bounded adversaries
In the experiment PrivKA,Π (n), what is A given and what does it output?
A is given 1, outputs pairs of equal-length message lists
What does CPA-Security for Multiple Encryptions involve?
Extending the CPA indistinguishability experiment to multiple encryptions using lists of plaintexts
What is the property of pseudorandom functions?
They are 'random-looking' functions, and pseudorandomness is a property of a distribution over functions
Computational secrecy requirement: Information about the encrypted message is leaked with a tiny probability to eavesdroppers with bounded computational power
Weaker
Upper bounds the success probability of an adversary running for some specified time. A concrete definition of security takes the following form. A scheme is (t, ϵ)-secure is any adversary running for time at most t succeeds in breaking the scheme with probability at most ϵ.
t, \epsilon
How large can t be. How small should ϵ be.
large, small
CPA-secure private-key encryption scheme uses ______ function F
pseudorandom
Distinguisher has no access to the key k
keyed
Strong pseudorandom ______ cannot be efficiently distinguished from a random ______
permutation
An event that occurs with probability $2^{-60}$ each second is expected to occur once every ______
10 billion years
A scheme is secure if for every probabilistic polynomial-time adversary A, the probability of A succeeding in the attack is ______
negligible
Both PPT adversaries and ______ probabilities of success are needed to allow practical encryption schemes
negligible
Semantic security is the analog of perfect secrecy for computationally bounded adversaries and is the first definition of computationally secure encryption to be proposed
semantic security
______ is a form of security in private-key encryption where an adversary behaves the same, regardless of whether it observes an encryption of m0 or m1
EAV-security
A ______ is a polynomial-time deterministic algorithm for transforming a short, uniform bitstring called the seed into a longer, 'uniform-looking' output string
pseudorandom generator
CPA-Security for Multiple Encryptions is stronger than ______
EAV-security
The LR-Oracle Experiment involves A being given 1 and oracle access to LRk,b (⋅, ⋅) and outputs a bit ______
b′
The private-key encryption scheme has indistinguishable encryptions under a chosen-plaintext attack if for all PPT adversaries A there is a negligible function ______
negl
ECB is deterministic and cannot be ______
CPA-secure
Let F be a length-preserving block cipher with block length n. A uniform initialization vector (IV) of length n is ______. c0 = IV. For i = 1, … , l, ci := Fk (ci−1 ⊕ mi )
chosen
Let m = m1 , m2 , … , ml where mi ∈ {0, 1}. n Let F be a length-preserving block cipher with block length n. A uniform initialization vector (IV) of length n is ______.
chosen
Let m = m1 , m2 , … , ml where mi ∈ {0, 1} n Let F be a length-preserving block cipher with length n To encrypt a message of length l
chosen
Fortunately, there exist secure constructions based on block ciphers that have lower ______
overheads
Study Notes
Security Notions in Private-Key Encryption Schemes
- One-time pad scheme with length l(n) has a view eav ~ (n) of A identical to the view of A in PrivKA,Π when w is chosen uniformly from {0, 1}l(n).
- When w is generated by choosing k uniformly from {0, 1}n := G(k), the view of A is identical to the view of A in PrivKA,Π (n) and setting w.
- In the experiment PrivKA,Π (n), A is given 1, outputs pairs of equal-length message lists, and a key k is generated using Gen.
- The one-time pad does not have indistinguishable multiple encryptions in the presence of an eavesdropper.
- Chosen-plaintext attacks allow an adversary to influence honest parties sharing the key to encrypt messages of its choice.
- Chosen-plaintext attacks are modeled by giving the adversary A access to an encryption oracle.
- The private-key encryption scheme has indistinguishable encryptions under a chosen-plaintext attack if for all PPT adversaries A there is a negligible function negl.
- CPA-Security for Multiple Encryptions extends the CPA indistinguishability experiment to multiple encryptions using lists of plaintexts.
- The LR-Oracle Experiment involves A being given 1 and oracle access to LRk,b (⋅, ⋅) and outputs a bit b′.
- A private-key encryption scheme is CPA-secure for multiple encryptions if for all PPT adversaries A there is a negligible function negl.
- CPA-Security for Multiple Encryptions is stronger than EAV-security.
- Pseudorandom functions are "random-looking" functions, and pseudorandomness is a property of a distribution over functions.
Security Notions in Private-Key Encryption Schemes
- One-time pad scheme with length l(n) has a view eav ~ (n) of A identical to the view of A in PrivKA,Π when w is chosen uniformly from {0, 1}l(n).
- When w is generated by choosing k uniformly from {0, 1}n := G(k), the view of A is identical to the view of A in PrivKA,Π (n) and setting w.
- In the experiment PrivKA,Π (n), A is given 1, outputs pairs of equal-length message lists, and a key k is generated using Gen.
- The one-time pad does not have indistinguishable multiple encryptions in the presence of an eavesdropper.
- Chosen-plaintext attacks allow an adversary to influence honest parties sharing the key to encrypt messages of its choice.
- Chosen-plaintext attacks are modeled by giving the adversary A access to an encryption oracle.
- The private-key encryption scheme has indistinguishable encryptions under a chosen-plaintext attack if for all PPT adversaries A there is a negligible function negl.
- CPA-Security for Multiple Encryptions extends the CPA indistinguishability experiment to multiple encryptions using lists of plaintexts.
- The LR-Oracle Experiment involves A being given 1 and oracle access to LRk,b (⋅, ⋅) and outputs a bit b′.
- A private-key encryption scheme is CPA-secure for multiple encryptions if for all PPT adversaries A there is a negligible function negl.
- CPA-Security for Multiple Encryptions is stronger than EAV-security.
- Pseudorandom functions are "random-looking" functions, and pseudorandomness is a property of a distribution over functions.
Test your knowledge of security notions in private-key encryption schemes with this quiz. From one-time pad schemes to chosen-plaintext attacks and CPA-security for multiple encryptions, this quiz covers a range of concepts essential for understanding encryption security.
Make Your Own Quizzes and Flashcards
Convert your notes into interactive study material.
Get started for free