An encryption scheme consists of the following data

  • a plaintext space $\mathcal M$
  • a ciphertext space $\mathcal C$
  • a key space $\mathcal K$
  • a key generating algorithm Gen
  • encryption and decryption algorithms $\operatorname{Enc}_k$ and $\operatorname{Dec}_k$ for each key $k\in \mathcal K$

I would like some clarification on the following extract from Katz & Lindell:


More specifically, my question is: What does, say, $P(K=k)$ mean exactly? What is the domain and codomain of the random variable $K$? What is the set $\{K=k\}$? Also, what is the domain of Gen?

  • 1
    $\begingroup$ This was cross posted on Math. Please don't cross post on multiple sites. It is against SE rules. $\endgroup$
    – mikeazo
    Sep 7 '17 at 22:05
  • $\begingroup$ This could be useful... $\endgroup$
    – fkraiem
    Sep 8 '17 at 3:56

What does, say, $P(K=k)$ mean exactly?

It signifies the probability that the key $K$ selected by the key generation algorithm $Gen$ is the value $k$.

The notation he is using is that $P(condition)$ (actually, they use $Pr[condition]$, perhaps to emphasize that $P$ isn't a function on the value condition, but rather its probability distribution) is the probability that the condition is true. For example, if I flip a fair coin, we have $P(\text{heads}) = 0.5$

What is the domain and codomain of the random variable $K$?

The key space $\mathcal K$

What is the set $\{K=k\}$?

It's not a set; it's an equality which is true with a certain probability.

Also, what is the domain of Gen?

The key space $\mathcal K$

  • 1
    $\begingroup$ The domain of Gen is the key space? $\endgroup$
    – mikeazo
    Sep 7 '17 at 17:22
  • $\begingroup$ $P$ or $Pr$ is a probability measure and as such it takes as input a set. Usually when one writes, say, $P(X=0)$, this is shorthand for $P(\{\omega \in \Omega : X(\omega) = 0\}$ where $\Omega$ is the sample space and $X:\Omega\to \Bbb R$ some random variable. $\endgroup$ Sep 7 '17 at 17:39
  • $\begingroup$ So in short, I still don't know what $P(K = k)$ means. What is the sample space on which $K$ is defined and what is its codomain? What is the set of events on which $Pr$ is defined? @poncho $\endgroup$ Sep 7 '17 at 17:41
  • $\begingroup$ BTW: what do you mean by 'codomain'? $K$ isn't a function, it's a random variable... $\endgroup$
    – poncho
    Sep 7 '17 at 17:53
  • 2
    $\begingroup$ The input of Gen is a constant $n$-bit string, which is overwritten by a non-deterministic Turing machine to give a $n$-bit key. The codomain is $\mathcal{K}$, though. $\endgroup$ Sep 7 '17 at 20:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.