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
17 votes
12 answers
18k views

Are one-time pads crackable in theory?

I've been taught that one-time pads are the only perfect encryption since the only way to recover the message is by knowing the key. For example, for a target bitstring of 100 bits, I cannot scan all ...
yters's user avatar
  • 429
17 votes
2 answers
13k views

Is perfect-forward secrecy achieved with RSA?

I am new to cryptography and am going through the book Understanding Cryptography by Paar and Pelzl. From what I understand Symmetric key distribution systems like Kerberos do not provide PFS ...
Ben Lamm's user avatar
  • 273
14 votes
2 answers
3k views

Can one claim that AES has perfect secrecy for a key size and message size of 128 bits?

While looking at this question I discovered the following here (question 5), and wanted to ask it as a separate question. Alice knows that she will want to send a single 128-bit message to Bob ...
daniel's user avatar
  • 912
13 votes
3 answers
14k views

One time pad: why is it useless in practice?

The symmetric cryptosystem one-time pad (OTP) seems to be very beautiful since it is perfectly secret according to Shannon. Many books, however, point out the main drawback: one must create a secret ...
Dubious's user avatar
  • 273
12 votes
2 answers
8k views

Definitions of secrecy

I found terms like "forward secrecy", "future secrecy", "backwards secrecy" and "perfect forward secrecy" and I would like to know their definitions and to understand the differences among them. I ...
M-elman's user avatar
  • 1,248
9 votes
5 answers
4k views

Perfectly secret cipher can leak about the key?

As defined by Shannon, a cipher is perfectly secure if ciphertext leaks no information about the plain text. Under this definition, can ciphertext leak something about the key? Are there any ciphers ...
Pratik Soni's user avatar
9 votes
1 answer
4k views

What are the ways to generate Beaver triples for multiplication gate?

So to speed up the function evaluation we use beaver trick, to generate raw data in the offline phase and use them in the online phase to get the output share for the multiplication gate. So what are ...
7sujit's user avatar
  • 573
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 ...
Maarten Bodewes's user avatar
  • 93.2k
8 votes
1 answer
833 views

Does Shannon perfect secrecy imply a deterministic encryption algorithm?

Consider an encryption scheme $(Gen,Enc,Dec)$ where $Gen$ is the key generation algorithm, $Enc$ is the encryption algorithm, where $c \leftarrow Enc_{k}(m) $ is taken to mean that the message $m$ in ...
user308485's user avatar
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 ...
Paul Uszak's user avatar
  • 15.5k
8 votes
2 answers
2k views

Proof that perfect privacy implies that the number of keys is at least the number of messages

I was reading a proof to the statement: Perfect privacy implies that $|K| = |M|$ where I am pretty sure that $K$ is the set of keys and $M$ is the set of messages. The proof is the following, ...
user avatar
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\...
fgrieu's user avatar
  • 142k
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, ...
Bhargav - Retarded Skills's user avatar
6 votes
2 answers
2k views

Why is PerfectForwardSecrecy considered OK, when it has same defects as salt-less password hashing?

PFS suites suffer from the same defects as any other salt-less password hashing scheme. Why is everyone promoting Perfect Forward Secrecy (PFS) ciphersuites so fiercely? Namely, when the group/hash ...
user185953's user avatar
6 votes
3 answers
4k views

If a cipher has key length shorter than plaintext, then it is not perfectly secure

I am trying to verify the statement above. So far I only know that a One-Time-Pad is the only “perfectly secure” cipher. It has a key length which is exactly the same as the plaintext. I think the ...
Idonknow's user avatar
  • 491
6 votes
1 answer
2k views

Proving one time pad is perfectly secret

I'm reading about one-time pad in "Introduction to Modern Cryptography" by Katz and Lindell. I can understand the definition of perfect secrecy. However, how is OTP proven to be perfectly secure ? I'm ...
rranjik's user avatar
  • 217
5 votes
2 answers
4k views

Can a monoalphabetic substitution cipher attain perfect secrecy?

Can a monoalphabetic substitution cipher attain perfect secrecy? Definition of perfect secrecy: $${\rm Pr}[\,{\rm Enc}_k(m_1) = c\,] = {\rm Pr}[\,{\rm Enc}_k(m_2) = c\,]$$
abdolahS's user avatar
  • 439
5 votes
1 answer
2k views

What does the probability subscript mean in Shannon's secrecy definition?

Shannon's secrecy can be defined as: $$P_M (M=m) = P_{SK,M}(M=m|E(SK,m)=c)$$ What does $P_M$ means? (same question for $P_{SK,M}$) I know that is the probability space M, M being the messages; I do ...
graphtheory92's user avatar
5 votes
1 answer
1k views

Why does a perfect secrecy can be achieved when decryption correctness is not totally required?

By Shanon theorem, a perfect secrecy encryption scheme must use a key space of equal size as the message space. But when the correctness requirement is weakened such that $Pr[Dec_k(Enc_k(m))=m]=1/2$ ...
Bush's user avatar
  • 2,140
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
2 answers
554 views

When does multiple OTP encryption become insecure if new keys are permuted? ​

I understand that OTP encryption fulfils perfect secrecy, meaning you can't decrypt the encrypted text to it's original plaintext (and know that this plaintext is indeed the original plaintext) unless ...
AleksanderCH's user avatar
  • 6,462
4 votes
2 answers
369 views

Generate one-time-pad with pre-shared key and public randomness

I know very little about cryptography, so I apologize if the question does not make sense. Let's say we design a function $F(P, X) \rightarrow K$ that takes in a pre-shared private key $P$ and a ...
hklel's user avatar
  • 143
4 votes
2 answers
1k views

Perfect Forward Secrecy in TLS

I read that TLS does PFS using Diffie Hellman. However, DH can be used even without certificates - so how is DHE-RSA better than plain DHE? Is DHE a insecure algorithm, that DHE-RSA is needed?
user93353's user avatar
  • 2,245
4 votes
2 answers
2k views

Prove Vigenere cipher isn't perfectly secret

As part of a homework assignment I have to prove/disprove that a Vigenère Cipher with a key of length n, uniformly distributed in the alphabet, on a plain text of length 2n, also uniformly distributed ...
el-flor's user avatar
  • 183
4 votes
1 answer
2k views

Is the one-time pad still perfectly secret if all-zero keys are excluded?

I'm trying to solve this question related to one-time pads and perfect secrecy: My solution is: I assumed that the current message space is $M = \left\{ 0,1 \right\}^l$ and the new keyspace after ...
Mitch5355's user avatar
4 votes
1 answer
651 views

Can AKE keys provide PFS

Can the channel keys that are derived from an AKE (authenticated key exchange) protocol be used in a secure channel that wants to have perfect forward secrecy? If the goal of AKE is to establish ...
Anonymous's user avatar
  • 431
4 votes
2 answers
17k views

Shannon theorem of perfect secrecy

From the class: Shannon Theorem: For a perfect encryption scheme, the number of keys is at least the size of the message space (number of messages that have a non-zero probability). Proof: Consider ...
Jjang's user avatar
  • 365
4 votes
3 answers
311 views

Can you have perfect secrecy with countable message/key spaces by dropping countable additivity?

This classic paper by Chor and Kushilevitz shows that if the key space and the message space are both countably infinite, then it is impossible to have a perfectly secure private-key encryption scheme....
Keshav Srinivasan's user avatar
4 votes
2 answers
2k views

Perfect Secrecy for two distinct messages

We say that and encryption scheme $\pi$ is perfectly secret for two distinct messages, if for all distributions over $\mathcal{M}\times\mathcal{M}$ ($\mathcal{M}$ is the message space), for all $m_1,...
A-P's user avatar
  • 175
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
5 answers
1k views

Read-once memory

So I've been reading about cryptography and one-time pads, which seem to provide theoretically perfect secrecy. My question is does any form of technology today allow data to be stored in a practical ...
Ape Toshi's user avatar
  • 147
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....
Manoharsinh Rana's user avatar
3 votes
3 answers
14k views

How can a cryptosystem be unconditionally secure?

The definition of an unconditionally secure cryptosystem states that the cryptosystem cannot be broken even with infinitely computational ressources and time. However, since most books define the ...
Shuzheng's user avatar
  • 321
3 votes
1 answer
131 views

2 party AND computation under passive perfect security

In the book written by Ivan Damagard titled "Secure Multiparty Computation and Secret Sharing", at the end of the third chapter he provides a proof for why it is impossible to securely compute 2 party ...
sun's user avatar
  • 540
3 votes
3 answers
6k views

What is perfect secrecy?

I read some similar questions like Simply put, what does “perfect secrecy” mean? (This one defines perfect secrecy as ciphertext conveys no information about the content of the plaintext. Now, ...
sam's user avatar
  • 133
3 votes
2 answers
695 views

How to prove a symmetric encryption scheme provides perfect secrecy?

I learned in class that in order to achieve perfect secrecy, the source of the plaintext $\mathcal{P}$ needs to be independent from the source of the encryption key $\mathcal{K}$. We also learned that ...
Andres Stadelmann's user avatar
3 votes
2 answers
199 views

(Non-) Perfect Secrecy of Vernam Cipher Using $E(m) = m \oplus k \oplus \operatorname{rev}(k)$

Given the cipher $$E(k, m) = m \oplus k \oplus \operatorname{rev}(k)$$ where $\operatorname{rev}(k)$ is the reversed binary of $k$, how would one prove that the cipher is not perfectly secret. I ...
Paul Herman's user avatar
3 votes
2 answers
547 views

Perfect secrecy with n-time key

How can you encrypt $n$ messages with the same key, and have the same theoretical security you'd have encrypting a single message with a one time pad? For example, how can you encrypt two messages ...
user26167's user avatar
3 votes
1 answer
78 views

Generate a random number $r \in \{1,2, \dots , k\}$, where $k$ is not public and is distributedly held

A set of parties can securely generate a random number $r \in \{1,2,3,\dots, k\}$ when $k$ is publicly known. However, can we generate the random number $r$ if $k$ is not publicly known and is held by ...
sun's user avatar
  • 540
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? ...
Giovanni's user avatar
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 ...
eternalmothra's user avatar
3 votes
1 answer
1k views

monoalphabetic substitution perfect secrecy

I have this question that I'm trying to answer: Consider a monoalphabetic substitution cipher applied to plaintexts consisting of just a single letter. That is, $$M = \{0, 1, . . . , 25\}$$ The ...
R. Kelly's user avatar
3 votes
1 answer
146 views

Rationale of "r" AES key use in OTR version 3 AKE protocol?

I just tried to review & understand AKE (Authenticated Key Exchange) protocol as defined in OTR secure messaging protocol version 3 here , and aiming to achieve Perfect Forward Secrecy I am a ...
william_fr's user avatar
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 ...
MuchToLearn's user avatar
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?
Eli Yablon's user avatar
3 votes
1 answer
9k views

Prove that a given encryption scheme is perfectly secret

I'm studying for an upcoming test and I can't figure out the following sample question: Let $\Pi = (\operatorname{Gen}, \operatorname{Enc}, \operatorname{Dec})$ be an encryption scheme with key ...
Matthew's user avatar
  • 43
3 votes
1 answer
1k views

One time pad (OTP) perfect secrecy with different key space

Let say $K_{0} = \left \{ 0,1\right \}^n$ $K_{1} = K=\left \{ 0,1\right \}^n$ \ $0^n$ $[b\leftarrow \left \{0,1 \right\}, k \leftarrow K_{b}:b=1|k \neq 0^n]$ --- (1) Key is chosen using ...
sonus21's user avatar
  • 151
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, ...
Jung's user avatar
  • 31
3 votes
1 answer
246 views

How can recovered 5-letters plain text help me to recover reused OTP key

I have 10 cipher texts ciphered with One Time Pad (OTP) using the same key. I need to recover the key (or in other words, to recover the 11th cipher text which I assumed would require me to recover ...
user2192774's user avatar
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+\...
steve6617's user avatar