Join Log in
Score:1
Foobar avatar Crypto

Katz/Lindell Problem 2.2 - Purpose of proof where you redefine the key space?

fr flag
Foobar

I am self-studying by using "Introduction to Modern Cryptography: Principles and Protocols" (2nd edition).

I am looking at the following problem.

Prove that, by redefining the key space, we may assume that $Enc$ is deterministic without changing $Pr[C = c | M = m]$ for any $m$, $c$.

The question seems to be asking "Prove that if we change a non-deterministic encryption algorithm to a deterministic one, the probability a particular cipher text will result from encrypting a chosen message will not change".

However, if we make an algorithm deterministic, then it can only have 1 output instead of choosing randomly between multiple.

So, we must expand the number of keys (as shown in Katz/Lindell Problem 2.2).

My question is: What is the purpose/value of a proof like this? Yes, we have proved that $Enc$ can be deterministic, but only at the cost of changing the key-space, which seems like a very fundamental / important part of the scheme anyways.

56
0 + 0
Maarten Bodewes avatar
in flag
Maarten Bodewes
Deterministic encryption certainly has its merits. Note that the question does not require that $c' \neq c''$ for $m' = m''$
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.