# Tagged Questions

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.

2k 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 ...
134 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, ...
2k 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 ...
419 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 that the main drawback is that one must ...
43 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 ...
120 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 ...
313 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$ ...
66 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 ...
251 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?
65 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 ...
353 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? ...
95 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 ...
60 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 ...
316 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? ...
83 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 ...
333 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 ...
122 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: ...
133 views

### How do I create a secure encryption scheme using addition?

You have a 4 number long PIN code with each number ranging from 0 to 9 which you wish to encrypt. You are then given a random 4 digit number ranging from 0 to 9999, which when added to the original ...
47 views

### Optimal threshold for passive and perfect security

The authors of the book titled "Secure Multiparty Computation and Secret Sharing" claim that there exist functions which cannot be computed with passive perfect security for $t \geq n/2$ corrupt ...
92 views

### Does a stream cipher provide perfect secrecy?

From WAR10CK here: If I actually do create a machine using RC4 or AES-CTR and have a TRNG continually feed it a constant steady stream of random bits. Provided that the stream of bits is purged ...
100 views

### What do these notations mean in the definition of Perfect Secrecy, if we read those in English?

If m: message, M: message space, k: key, K: keyspace, c: cipher, C: cipher space and $E_k$: encryption function, such that $E_k(m) = c,\ m,m^* \in M,\ k\in K,\ c\in C.$ Then, what do the following ...
321 views

### Does perfect secrecy imply uniform ciphertext distribution?

I suspect the answer is no, but I am not able to either prove it, or provide an example. In Katz and Lindell's book, it is only said that with a perfectly secret encryption scheme, the plain and ...
3k 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 ...
49 views

### Lower bound of key space size with relaxed perfect secrecy

My apologies, I'm quite new to cryptography. If we relax the definition of perfect secrecy such that for cyphertext $c$, messages $m_0$ and $m_1$, and constant $E$: $P[c|m_0] \le E * P[c|m_1]$ ...
115 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 ...
110 views

### Is one-time-pad still secure if the number of 1's in the key is revealed to the attacker?

For example, if $m = 10011$, $k = 11001$, $n=3$ (which is the number of 1's in k), $c = m \oplus k = 01010$. If $c$ and $n$ are revealed to the attacker, is this scheme still secure?
601 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\,]$$
480 views

148 views

### Perfect secrecy over Stirling numbers

For all $c_0\leftarrow m_0 \oplus k$ there exists a $k'$ such that $c_1 \leftarrow m_1 \oplus k'$, where $m_0 \neq m_1$ and $c_0 = c_1$. Assuming a truly random $k$, the first assignment is a one-...
72 views

### What is the meaning of the overlapping region on OTP-perfect secrecy diagram?

I'm new to cryptography. I want to ask about OTP-perfect secrecy diagram like figure below: On the overlapping region (middle), notated by R(X;Y;Z). R can be calculated by I(X;Y) - I(X;Y|Z). ...
68 views

### How can I turn this cipher into a perfect cipher by altering only its encryption algorithm?

Given a toy cipher that picks a key, k, from the key space of {00,01,10} and a message,m, from the same set {00,01,10} and encrypts using E = m ⊕ k. How can I change the encryption function E in ...
636 views

### Why cant Public Key Encryption be perfectly secure? [duplicate]

I would be very grateful for any help. I cant figure out why (probabilistic) public key encryption schemes can never provide perfect secrecy? Any Ideas? Excerpt: In contrast to the private-key ...
68 views

### Why perfect secrecy can be ensured when a plain message and a cipher-text based on one-time pad are correlated?

First, some well-known results are as follows. For random variables $X$ and $Y$, we have $$H(X,Y) \leq H(X) + H(Y).$$ The equality is achieved when $X$ and $Y$ are independent. Second, in one-time ...
150 views

### Definition of perfect secrecy using ciphertext

This week my professor in class taught us the definition of perfect secrecy. He said that for any ciphertext the probability that it might have come from any message in the message space should be ...
81 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 ...