Questions tagged [perfect-secrecy]

Confidentiality in a very strong sense. Ciphers reaching perfect-secrecy can't be broken to disclose informations over the plaintext from the ciphertext, even with unlimited computing power. The most known example cipher reaching perfect screcy is the one-time-pad.

17 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
5
votes
0answers
479 views

Shannon cipher with fewer keys than messages

Alice and Bob have a set $\mathcal{M}$ of $|\mathcal{M}|$ messages and a set $\mathcal{K}$ of $|\mathcal{K}|$ keys. Alice wants to send a message $m \in \mathcal{M}$ to Bob. She uniformly picks a key $...
3
votes
2answers
514 views

Proving that there is no scheme which would be perfectly CPA-secure

A private-key encryption scheme Π = (Gen, Enc, Dec) has perfectly indistinguishable encryptions under a chosen-plaintext attack, if for all probabilistic polynomial-time adversaries A it holds that Pr[...
3
votes
0answers
372 views

Epsilon Perfect Secrecy: Size of Key Space

I am solving a homework problem which defines $(1-\epsilon)$-perfect secrecy as the secrecy satisfied by the encryption scheme when the following inequality holds $\Pr[M=m\mathrel|C=c]\leq (1+\...
3
votes
0answers
426 views

Perfect secrecy is maintained for other plaintext prob distributions?

Suppose a cryptosystem achieves perfect secrecy for a particular plaintext probability distribution. Prove that perfect secrecy is maintained for any other plaintext probability distribution. Having ...
2
votes
0answers
60 views

Necessity of Randomness when Privately Computing a Sum

I want to show that no 1-private deterministic protocol exists for calculating a sum of $n \geq 3$ parties (within the realms of Perfect rather than Computational Security). I'm having trouble showing ...
2
votes
0answers
188 views

Showing that perfect secrecy implies adversarial indistinguishability

I've been reading the proof in these slides, the last page, and the author is using the lemma: $Pr[A(c)=1|M=m_0]=Pr[A(c)=1|M=m_1]$ I understand on the intuitive level that it's a consequence of the ...
2
votes
1answer
216 views

For perfect secrecy, does the keyspace need to be uniform?

The definition of perfect security is just that: $Pr(M =m | C=c) = Pr(M=m)$. We can prove that one time pad is perfectly secure for any distribution on a message space $M$, and it happens to be that ...
1
vote
0answers
45 views

One Time Pad proof for Perfect Secrecy

In the book "Introduction to Cryptography with Coding Theory" by Trappe, in the paragraph about the security of the One Time Pad, is it told that given the set of possible plaintexts $P$, the set of ...
1
vote
0answers
65 views

Almost (epsilon) perfect secrecy - lower bound of keyspace size

As a newcomer to cryptography, I'm working on Exercise 2.12 in the book, Introduction to Modern Cryptography. Using the proof of the theorem that says if $E$ is a perfectly secret encryption scheme, ...
1
vote
0answers
148 views

Perfect Secrecy for some distribution implies perfect secrecy for any distribution

I'm quite thrilled about this question I got for homework, even though we were given the answer to the problem. It goes like this: Let $\mathcal{M}$ be the set of plaintexts of a symmetric encryption ...
1
vote
0answers
359 views

Perfectly secret scheme for two distinct messages

Following the same definition in this question for perfect secrecy for two messages $m,m' \in \mathcal{M}$. I don't understand how the accepted answer produces a secure system? I mean The adversary ...
1
vote
0answers
550 views

Proving that Perfect Secrecy implies Adversarial Indistinguishability wrt. probabilistic adversaries

In their book Introduction to Modern Cryptography, chapter 2, authors Katz and Lindell ask the reader to show that perfect secrecy is equivalent to adversarial indistinguishability as an exercise. I ...
1
vote
0answers
138 views

How we can said a crypto system have perfect secrecy?

For example: I have 3 plaintexts ($a$, $b$, $c$) and 4 keys ($K_1$, $K_2$, $K_3$, $K_4$), making a table map to the cipher text, key as row and plaintext as column $\begin{matrix} \ \ \ \ \ \ \ \ \ \ ...
0
votes
0answers
100 views

Perfect Secrecy for Message Subset

In "Introduction to Modern Cryptography" by Jonathan Katz exercise 2.6 goes like this: "Say encryption scheme (Gen, Enc, Dec) satisfies DEFINITION 2.1 for all distributions over ℳ that assign non-zero ...
0
votes
0answers
86 views

Interpretation of message space distribution in the definition of perfect secrecy of encryption schemes

I am a beginner to cryptography, and have started reading Katz and Lindell's book titled "Introduction to Modern Cryptography". I'm unable to understand what the probability distribution over the ...
0
votes
0answers
75 views

Perfect Secrecy and Message distributions

It is know that for a perfect secrecy scheme, for all m1,m2 and c: $Pr[C=c | M=m1] = Pr[C=c | M=m2]$ I also know that for all distributions of M, m1,m2 and c: $Pr[M=m1 | C=c] = Pr[M=m2 | C=c]$ Does ...
0
votes
0answers
180 views

Perfect Secrecy of AES file Encryption

Why does AES file encryption not ensure perfect secrecy? I understand that $\Pr[E(K,M_1)=C_1] = \Pr[E(K,M_2)=C_2]$ given $M1\neq M2$ holds for perfect secrecy of a scheme. However, this seems to hold ...