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.

Filter by
Sorted by
Tagged with
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[...
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 ...
1 vote
1 answer
79 views

Shannon's Perfect Security for Asymmetric Encryption

I have the following definition of Shannon's Perfect Security. Assuming messages and keys are drawn randomly from some distribution then: The probability of guessing plaintext m is not enhanced by ...
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/...
1 vote
1 answer
82 views

Why is perfect secrecy defined under a ciphertext-only threat model?

I recently acquired Katz & Lindell's Introduction to modern cryptography (3d edition). Currently I'm on page 27 where we have the following definition: Definition 2.3: An encryption scheme (Gen, ...
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 ...
2 votes
1 answer
816 views

Proving that a scheme is $\epsilon$-perfectly secret

I am currently trying to solve the following problem (2.18) from the book "Introduction to Modern Cryptography (3rd edition)" by Katz and Lindell: Let $\epsilon > 0$ be a constant. Say an ...
3 votes
2 answers
237 views

Katz and Lindell, proof of lemma 2.4

Can someone explain the logic behind the claim that the second equality is because we condition on the event that $M$ is equal to $m$ in the proof of Lemma 2.4 from "Introduction to Modern ...
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 ...
0 votes
1 answer
80 views

Is there a TLS cipher suite with perfect forward secrecy (PFS) but without authentication, i.e. anonymous, ephemeral key exchange?

Is there a TLS cipher suite with perfect forward secrecy (PFS) but without authentication, i.e. anonymous key exchange? I am not asking or wish to discuss the principle question whether an ...
6 votes
6 answers
2k views

why XOR is recommended/Used in every paper I read for encryption and decryption stream cipher?

Stream ciphers use a deceptively simple mechanism: you combine the plaintext data, bit by bit, with “key” bits, using the exclusive or operation. Why can't I use other opeartions such as NAND, AND, ...
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, ...
7 votes
3 answers
666 views

Manual secret sharing?

What are feasible options for an equivalent of Shamir Secret Sharing using small tables, preferably usable with pen-and-paper? We want to share a secret $K$ into $n\ge2$ shares, so that $m$ shares ($2\...
3 votes
2 answers
901 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, ...
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: ...
0 votes
1 answer
3k views

Is 7-Zip Encryption really secure? [duplicate]

Is 7-Zip really a good encryption tool? I wonder what kind of encryption is used in 7-zip. I see most people using 7-Zip. Just curious about what extent it is safe.
2 votes
2 answers
152 views

Perfect Secrecy other than One-time Pad

The most known example cipher reaching perfect secrecy is One-time Pad, which employs modulus addition for encryption and decryption. Is there any other well-known cipher no less practical than OTP ...
1 vote
1 answer
429 views

Does CCA security imply perfect secrecy?

Can any encryption scheme that is CCA (Chosen Ciphertext Attack) secure be considered to achieve perfect secrecy?
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 $...
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 ...
2 votes
1 answer
484 views

Perfect Secrecy for Shift Cipher

I've read the definition of perfect secrecy as the following: A cryptosystem has perfect secrecy if $\Pr(x | y) = \Pr(x)$, for all $x \in P$ and $y \in C$, where $P,C$ are respectively the set of ...
1 vote
1 answer
55 views

Is it necessary keys to have equal propabillities for the system to have perfect secrecy?

Shannon's theorem for perfect secrecy states that $$\forall x \in M, y \in C:\quad P[x|y]=P[x] $$ I know we need $|M|\leq |C| \leq |K|$. If $|Μ|=|C|=|K|$ all keys should have equal probs. If $|Μ|<|...
1 vote
0 answers
92 views

What is the simplest way to implement data encryption for Raspberry PI project that communicate through Bluetooth? [closed]

I have developed a project based on Raspberry Pi that communicates through Bluetooth with Android application, My idea is to enhance its privacy through encryption. So, I've tried ...
1 vote
1 answer
66 views

AKE using Noise_NNpsk2 vs Noise_NKpsk2

I am working on an implementation based on the Disco library, which itself is based on Noise and strobe framework. The goal is to do bilaterally entity-authenticated key agreement with perfect forward ...
2 votes
4 answers
1k views

Is perfect forward secrecy (PFS) possible without public key cryptography

I have an understanding of PFS as used in most key agreement algorithms as well as things like TextSecure protocol and ratchets. My undestanding is that PFS is not possible without asymmetric (public ...
2 votes
2 answers
780 views

An example of of an information theoretically secure protocol that is not cryptographically secure

Does there exist a protocol $\pi$ for some functionality $F$ which is information theoretically secure protocol that is not cryptographically secure for some threshold number of corrupt parties? ...
0 votes
1 answer
354 views

Why are stream ciphers computationally secure?

In case multiple stream ciphers exist, I'm refering to this specific instance in which you generate a key that is just as long as the msg, M, as a function of a nonce and a smaller key K. My textbook ...
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 ...
1 vote
1 answer
62 views

How can I distribute a set of anonymous tokens digitally among a known limited population to do anonymous voting?

TL:DR How can I give a population of N people the chance to randomly pick one token each person guaranteeing those: Nobody knows noone else's token. Noone can pick more than one token. Every person ...
9 votes
1 answer
3k views

Does perfect forward secrecy (using DH or ECDH) imply quantum resistance?

Does perfect forwarding secrecy, as used for e.g. the DHE_ and ECDHE_ TLS ciphersuites make it impossible for quantum analysis ...
3 votes
1 answer
214 views

Information Theoretic Security for Public Key Encryption

Do there exist information theoretic secure public key crypto-systems? Are they useful in any way, or are they just mathematical curiosities?
3 votes
2 answers
1k views

An unbreakable Hill cipher?

Why don't we use a Hill cipher of 100 × 100? Or even bigger? That would be close to unbreakable. The number of possible keys in a 2 × 2 Hill cipher is 157248. For 100 × 100 the number is beyond limits....
3 votes
2 answers
2k views

Which is better ECDHE with TLS 1.0

I have a webserver which only supports TLS 1.0 and I am not sure about something: Which is the better cipher in this group when aiming for the best security? ...
1 vote
1 answer
90 views

What is the Work Factor of the one time pad?

Work Factor is defined as the minimum amount of work (can be the length of the key) to determine the secret key of an cryptosystem (HAC, Menezes, Alfred J. et al). And One time pad have unconditional ...
2 votes
1 answer
285 views

Proving two definitions of perfect security are equivalent

I'm trying to prove that the following two definitions are equivalent: $\forall m\in M $ and $c\in C$ $\Pr[C=c \mid M=m]=\Pr[C=c]$ $\forall m_1,m_2 \in M $, $E_k(m_1)=E_k(m_2)$, where $E_k(m_i)$ ...
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,...
2 votes
2 answers
322 views

Ideal cipher vs Ideal encryption scheme

Ideal cipher is a random permutation for every key in its key space. And, ideal encryption scheme is the one which has perfect secrecy/indistinguishability. For an encryption scheme, random ...
0 votes
0 answers
105 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 ...
1 vote
1 answer
191 views

Katz/Lindell - 2.10: Is exhaustive search over the key-space allowed in perfect indistinguishability?

I am self studying using "Introduction to Modern Cryptography (2nd edition)" I am trying to understand how the solution to the following problem is valid: Prove that a scheme satisfying ...
2 votes
1 answer
297 views

Katz/Lindell 2.4 - Generalizing from 2 messages to any message space?

I'm trying to solve problem 2.4 in "Introduction to Modern Cryptography" (2nd edition) for self-study. The problem asks to prove that perfect secrecy $$ Pr[M = m | C = c] = Pr[M = m] $$ ...
2 votes
2 answers
3k views

Prove that the affine cipher over Z26 has perfect secrecy if every key is used with equal probability of 1/312

Prove that the affine cipher over Z26 has perfect secrecy if every key is used with equal probability of 1/312. Just some guidance/help with this problem would be greatly appreciated not sure how to ...
8 votes
2 answers
3k views

What is the difference between information-theoretic and perfect types of security?

I'm having a hard time pinning down an exact definition of the difference between information-theoretic and perfect types of security. A rigorous definition seems elusive... A. Wikipedia puts the ...
3 votes
2 answers
1k 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
1 answer
71 views

Secret sharing is based in random variables that are uniformly distributed?

In Rabin and Ben-Or, their basic assumption is that each participant can broadcast a message to all other participants and that each pair of participants can communicate secretly. Hence, they design a ...
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{...
0 votes
1 answer
182 views

One-time pad without zero: proof check

I started learning cryptography and tried to work through this problem: consider one-time pad where $\mathcal{M}=\mathcal{C}=\{0,1\}^n$ and $\mathcal{K}=\{0,1\}^n\setminus 0^n$ (call this scheme $\Pi$)...
2 votes
1 answer
4k views

Cryptography - Perfect secrecy $\implies$ adversarial indistinguishability - proof

I'm just starting out with cryptography now and have gone over the various defnitions for a perfectly secret cipher. One of the equvilant definitons is adversarial indistinguishability. When trying to ...
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}_{\...
2 votes
1 answer
2k views

Is OTP still perfectly secure if we limit message and key space

If we have a message space M {0,1,2,3,4,5,6} and likewise keyspace is K = {0,1,2,3,4,5,6} (generator choosen uniform keys k) We define our encryption to be the XOR of their bitwise rep on K and M ...
3 votes
1 answer
698 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+\...