0

This problem is from Katz/Lindell:

2.2 Prove that, by redefining the key space, we may assume that $\text{Enc}$ is deterministic without changing $\text{Pr}[\text{Enc}_k(m)=c]$ for any $m, c$.

After banging my head against this problem for a few hours, I honestly don't see a modification of the key space that gives the desired result. For all $k,m,$ and $c$ we have $\text{Enc}_k(m)=c$ with a certain probability $p(k,m,c)\geq 0$. What can we do with that?

Note: Katz/Lindell assume that $|\mathcal M|<\infty$, and $\mathcal C$ is defined as the set of as possible outputs of $\text{Enc}$.

CRYPTONEWBIE
  • 429

1 Answers1

0

Enc works on a message $m \in \mathcal{M}$ under a key $k \in \mathcal{K}$ and is randomised (i.e. it gets a number of random bits from some random tape, that it uses as input as well.). An example is a random IV in a mode like CBC or a random counter value in counter mode, e.g. So usually the number of random bits needed is fixed and known in advance (does not depend on $m$, say), but the book is vague on this (also on what a randomised algorithm is; it does not discuss such matters (Turing machines vc. non-deterministic Turing machines, etc.) at all.

So redefine the key space as $\mathcal{K} \times \mathcal{R}$, where $\mathcal{R}$ is the set of all possible random tapes (of the good length, or the maximal length we could need) that Enc gets its randomness from. Enc then becomes deterministic as it has all the randomness it needs in the new-style key.

Henno Brandsma
  • 242,131