2
$\begingroup$

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:

picture

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?

Improve this question
$\endgroup$
2
  • 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, 2017 at 22:05
  • $\begingroup$ This could be useful... $\endgroup$
    – fkraiem
    Sep 8, 2017 at 3:56

1 Answer 1

Reset to default
1
$\begingroup$

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$

Improve this answer
$\endgroup$
6
  • 1
    $\begingroup$ The domain of Gen is the key space? $\endgroup$
    – mikeazo
    Sep 7, 2017 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$
    – CRYPTONEWBIE
    Sep 7, 2017 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$
    – CRYPTONEWBIE
    Sep 7, 2017 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, 2017 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$
    – Henno Brandsma
    Sep 7, 2017 at 20:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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