# Tag Info

10

mikeazo's answer clearly covers what the question asks. However, I want to go further and answer this: How much information does a perfectly secure cipher leak about the key? Exactly all the excessive information of the key that does not help in finding anything about the message. In simple words: if the key length is $k$ bits and the message is $m$ bits ...

7

Sure, it can leak something about the key as long as that doesn't leak anything about the plaintext. Consider the following cipher, I'll call it 2-OTP. 2-OTP takes as input a message $M$ and two keys $K_1$ and $K_2$. Each key must be truly random, independent of one another, and each the same length as the message $M$. Define encryption as ...

6

This expands CodesInChaos's comment into an answer. Forward Secrecy (that is, maintaining confidentiality of messages enciphered before compromise of the long term key) can be achieved in a protocol using a public-key signature scheme with a long-term public key, and a public-key encryption scheme with a per-session key; but in the case of RSA signature and ...

6

Actually, the problem with OTP isn't the storage of the pad (although secure erasure of the parts of the pad you used is trickier than it looks), and it isn't the pad generation (although, again, that's trickier than it looks), but the secure transport. After all, it's not enough for you (Alice) to have the secure pad, you also have to give a copy to the ...

5

The one-time pad is perfectly secure. It will also leak the complete key to any attacker who knows the message (and will leak some information about the key to any attacker who knows something about the message). It's important to note that there's nothing in the definition of perfect security that says that the attacker can't already know something, or ...

4

For a nonuniform construction with perfect secrecy, consider this scheme, with 2 bits of plaintext $(b_1, b_0)$, and four bits of key $(k_3, k_2, k_1, k_0)$. The ciphertext consists of the three bits: $$(k_3 \land k_2) \oplus b_0 \oplus k_0$$ $$b_1 \oplus k_1$$ $$b_0 \oplus k_0$$ This has perfect secrecy, in that for each ciphertexts, there is the same ...

4

No, DHE is secure and allows to share a common secret between two parties over an insecure channel. But you cannot know, if the one you share the secret with is the one you want (DHE is vulnerable to man in the middle attacks). So DHE-RSA uses DHE to share a common secret and signs the communication with RSA to make sure, that both persons communicate with ...

3

Imagine the following three scenarios. In each, you intercept an encrypted message and you know from context: the message is a randomly chosen key in $\{0,1\}^n$ for some other cryptosystem the message is either "It's a boy!_" or "It's a girl!", both are equally likely the message is a vote from someone in a referendum; it's either "yes" or "no_", and the ...

3

Since this is homework, let me just give you a hint: consider the two-character messages $m_1 = \text{"aa"}$ and $m_2 = \text{"ab"}$. Given a ciphertext $c$ encrypted with a monoalphabetic substitution cipher, can you tell which of $m_1$ or $m_2$ it corresponds to, even without knowing the key? Why (not)? What does this imply about perfect secrecy?

3

One possibility for what you might be missing: normally the same key (the same matrix) is re-used to encrypt many messages. So now try counting the total entropy in $M$ length-$N$ messages, and the entropy in a $N\times N$ matrix, and compare what happens when $M$ gets large.... Another possibility you might be missing is the consequences of the fact that ...

3

To use the proper terminology: in TLS, cipher suites which include "some Diffie-Hellman" are: Anonymous Diffie-Hellman: DH_anon Static Diffie-Hellman: DH-RSA, DH-DSS... Ephemeral Diffie-Hellman: DHE-RSA, DHE-DSS... There is no "plain DHE" cipher suite in TLS; it is called "DH_anon". As the name indicates, with DH_anon, the server is "anonymous": you ...

2

Well, for perfect secrecy, we require that for all message distributions over $\mathcal{M}$, all messages $m\in\mathcal{M}$, and all (possible) ciphertexts $c$ it holds that $$Pr[M=m\ |\ C = c] = Pr[M=m]$$ In particular, that means, if we can find a single counterexample, i.e. a distribution over $\mathcal{M}$, a message $m\in\mathcal{M}$, and a ...

2

Imagine that you have a ciphertext: Perfect secrecy means, that without knowing the key, any plaintext has to be a possible preimage. Because otherwise the ciphertext would give you information about the plaintext. Encryption is an injective function, because otherwise it could not be reversed. That means, for a given key and ciphertext you have at most ...

2

This would read out to the following: (I'm citing myself here) An encryption scheme, defined by key generator, encryption function and decryption function over a message space $M$ is perfectly secret if for every probability for a message $m$, for every message $m$ and every ciphertext $c$ which might occur ($Pr[C=c]>0$), ...... the ...

1

The threshold for a perfectly secure system is that a computationally unbounded adversary cannot conclude anything about the plaintext from the ciphertext. With a public-key system, the attacker can try to encrypt messages with the real public key; this is not possible with one-time pads. What the attacker can do, quite simply, is to try all one-bit ...

1

Are M and C correlated? No. The distribution that the values the M and C may take on are independent of each other. The condition probability distribution that M has is unchanged no matter what the observed C value is. This is true whether you are using the statistical meaning of correlation, or whether you are looking more specifically at linear ...

1

The usage of the r key forces both parties to "fix" the public DH keys. So Alice doesn't know Bob's public DH key before she's generating her own one. And Bob can not make the choice of the public key dependant on Alice's choice and vice versa. This forces both parties to be honest and to generate both public keys at random as there is no opportunity to ...

1

You might be trying to keep the ciphertext length equal to the plaintext length. This is a "Just Do It" construction: Choose [0 or 1] and [[bit then original output] or [original output then bit]], modify the encryption algorithm to have it concatenate the chosen bit with the original encryption algorithm's output in the chosen order, and modify the ...

1

Here's a more "down to earth" example. The following cryptosystem with plaintext space $\mathcal{M} = \{a,b,c,d\}$, keyspace $\mathcal{K} = \{1,2,3,4\}$ and ciphertext space $\mathcal{C} = \{A,B,C,D\}$ has perfect secrecy: \begin{array}{c|c c c c} & 1 & 2 & 3 & 4 \\ \hline a & A & B & C & D \\ b & B & C & D ...

1

If the key would be smaller than the plaintext then you could brute force the cipher by using less than $N$ steps, where $N$ represents the amount of possible messages. Of course the brute force approach is an upper bound to what can be tried. If there are attacks on the cipher (that are less complex than brute force) then the plaintext may be recovered ...

1

What you are describing is One-Time-Pad encryption, and yes it does have perfect secrecy. Note that for any ciphertext $y$ there is exactly one key $k'$ for each possible plaintext $x'$ so that $E_k(x') = y$. So if you choose the key uniformly at random the ciphertext gives no information on the plaintext, because any plaintext is equally likely.

1

I'll further explain the comment of @CodesInChaos and then give a simple example: Explanation When the correctness requirement is weakened the encryption scheme can omit part of the message $m$ (of length $|m|$) to be encrypted and just "loose" it in a way that the cipher (the output of the Encrypt method) is totally independent of that part. Thus the ...

1

I think they are similar but not equivalent. The first condition says that for any ciphertext $c$ all messages $m$ have equal probability to encrypt to $c$. The second says that for any message $m$ all ciphertexts $c$ have equally probability of encrypting $m$. So I think you can demonstrate non-equivalence as follows: Imagine a (somewhat contrived) ...

1

You're missing that key generation would occur inside the box (if there was one for RSA key agreement), like for $k_{pr,A}$ and $k_{pub,A}$ on page 343, rather than outside the box, as happened for $k_{pub,CA}$ on page 347.

Only top voted, non community-wiki answers of a minimum length are eligible