Skip to main content

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.

29 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
5 votes
0 answers
506 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 $...
mhsnk's user avatar
  • 151
4 votes
1 answer
607 views

perfectly secret with key chosen uniformly

Prove or refute: Every encryption scheme for which the size of the keyspace equals the size of the message space, and for which the key is chosen uniformly from the keyspace, is perfectly secret. My ...
Amanda's user avatar
  • 51
3 votes
2 answers
2k 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[...
JenyaKh's user avatar
  • 161
3 votes
0 answers
534 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 ...
Ucia's user avatar
  • 31
2 votes
0 answers
39 views

Equivalent conditions for perfect secrecy of a symmetric crypto system

I've been reading about perfect secrecy in crypto systems and I've ran across two definitions which turn out to be equivalent. The first is Shannon secrecy: A crypto system $(\cal K, \cal M$, $\text{...
giorgioh's user avatar
  • 121
2 votes
0 answers
189 views

An exercise from a textbook

Let $\varepsilon>0$ be a constant. Say an encryption scheme is $\varepsilon$-perfectly secret if for every adversary $\mathcal{A}$ it holds that $$ \operatorname{Pr}\left[\operatorname{PrivK}_{\...
user260541's user avatar
2 votes
1 answer
555 views

Proving equivalency of two security definitions of symmetric encryption schemes

how to prove definition 3.8 and 3.9 are equivalence ? picture is from book an introduction to modern cryptography (2nd edition) by j. katz and y. lindell pdf and https://repo.zenk-security.com/...
mike's user avatar
  • 41
2 votes
0 answers
76 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 ...
E. Hambra's user avatar
2 votes
0 answers
812 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 ...
DiscobarMolokai's user avatar
2 votes
0 answers
354 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 ...
sel's user avatar
  • 325
2 votes
1 answer
110 views

Defining the random variables $K,M,C$ and Perfect Secrecy

In many books on Cryptography, we refer to probability distributions over the key space $\mathcal{K}$, over the plaintext space $\mathcal{M}$ and over the ciphertext space $\mathcal{C}$. Then, we let $...
Chris's user avatar
  • 236
1 vote
0 answers
63 views

Can a computationally-unbounded adversary break any cipher which is not perfectly secret?

Imagine we have a cipher defined as $(K, M, C, E, D)$ which is not perfectly secret, namely: $\exists m_0, m_1 \in M, c \in C \text{ s.t. } P[k \leftarrow K; E(k, m_0) = c] \neq P[k \leftarrow K; E(k, ...
joshlf's user avatar
  • 267
1 vote
0 answers
92 views

prove of disprove the modified shannon's theorem when the correctness requirement is relaxed

Suppose the correctness requirement of private-key encryption scheme is now relaxed to require only that $$ \Pr[Dec_k(Enc_k(m)) = m] \ge \frac{1}{2} + \epsilon. $$ Prove of disprove that if an ...
Wan's user avatar
  • 21
1 vote
2 answers
273 views

Question on double-asymmetric encryption and split knowledge

Moin moin, Let‘s assume there are two keypairs (d1,e1) and (d2,e2), where d1 and ...
Charly's user avatar
  • 19
1 vote
0 answers
83 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 ...
AleWolf's user avatar
  • 461
1 vote
0 answers
177 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 ...
Cristian Baeza's user avatar
1 vote
0 answers
554 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 ...
Shadowfirex's user avatar
1 vote
0 answers
148 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} \ \ \ \ \ \ \ \ \ \ ...
atom2ueki's user avatar
  • 157
0 votes
1 answer
65 views

Can a perfectly secret scheme have non-uniform ciphertext distribution if the plaintext and ciphertext length is equal?

I've seen this question asking if perfect secrecy implies uniform ciphertext distribution, and I understand that this is not the case. However, all given counterexamples seem to require a construction ...
Zabbulator's user avatar
0 votes
0 answers
55 views

Proving if two samples hides a value?

Given two values $r'-r \mod q$ $i - r \mod q$ Where $r',r$ sampled randomly from $Z_q$ while i is pick arbitrarily from $Z_q$ and a secret Can we claim that this hides $i$? Here is my sketch: ...
Crypto_Learner's user avatar
0 votes
0 answers
214 views

Relation between the size of key space and message for an encryption scheme that is not perfectly secure

I have been trying to solve the following: Given a scheme that is perfectly correct but not perfect secrecy. It satisfies computational security, however, in that, if Q = Pr[Adv wins no query semantic ...
 nietzsche's user avatar
0 votes
0 answers
138 views

Perfect security - is this definition correct?

I have this definition: each ciphertext is equally probable for a given plaintext and key chosen at random I know that perfect security can be defined as $$\forall c \in \mathcal{C} \ \forall m_1,...
Awerde's user avatar
  • 123
0 votes
0 answers
106 views

difference between unconditionally sure, perfect confidentiality, and semantically sure, adversary-wise and advatnage-wise?

can anyone please tell me the difference between unconditionally secure, perfect confidentiality and semantically secure? I know that for perfect confidentiality, we have an adversary A that has an ...
joxavy's user avatar
  • 11
0 votes
0 answers
177 views

Formal proof that the following definitions of perfect secrecy are equivalent

I've seen the following two definitions of perfect secrecy for an encryption scheme (Gen, Enc, Dec). ...
NJay's user avatar
  • 1
0 votes
0 answers
76 views

Perfectly secure cryptosystem as many keys as plaintexts

Is a cryptosystem perfectly secure if there are at least as many keys as there are plaintexts? My guess is yes but I am not sure, new to cyptosystems
gnarm's user avatar
  • 1
0 votes
0 answers
149 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 ...
sun's user avatar
  • 540
0 votes
0 answers
88 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 ...
Jjang's user avatar
  • 365
0 votes
0 answers
194 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 ...
Kat108's user avatar
  • 55
-1 votes
1 answer
113 views

Advantage of existing Cryptosystems

I have read about the concept of perfect secrecy and statistical distance. The perfect secrecy is impossible to be implemented on real world scenario. So the cryptosystems used at various websites ...
Crypto_researcher's user avatar