1
$\begingroup$

So I am a math major who is trying to learn some crypto. However I have some difficulties with some of the probability definitions that are assumed in the cryptography book that I am using at the moment. So here it goes:

Def(perfect security): Let $(E,D)$ be a Shannon cipher defined over $(K,M,C)$ where all these are finite sets and are respectively the key space, message space, and ciphertext space. Now consider the probabilistic experiment in which the random variable $k$ is uniformly distributed over $K$. If for all $m_0$, $m_1 \in M$, and all $c\in C$, we have $P(E(k,m_0)=c) = P(E(k,m_1)=c)$, then we say $(E,D)$ is perfectly secure.

As I understand it, the author assumes that we have a probability space on $K$, where the sigma-algebra is taken to be the power set of $K$, and $P$ is the probability measure defined on the power set of $K$. What I don't understand is what does random variable mean here. If I recall correctly, a random variable in probability theory is defined to be a measurable function from(in our case) $K$ to the real numbers. But I do not think the author is using this definition of random variable here. It would be great if anyone could clarify this part of the definition and also clarify what does $k$ uniformly distributed mean rigorously as well. I thought it means probability of each singleton outcome in $K$ is $1/|K|$. I might be wrong though. Thanks.

$\endgroup$
5
  • $\begingroup$ Your understanding of "uniformly distributed" is correct. And yes, the use of "random variable" to denote the sample from K (the event, if you wish) is a bit liberal here. $\endgroup$ Oct 15, 2022 at 10:11
  • $\begingroup$ @GeoffroyCouteau Thanks. Could you also point out how to we rigorously define the probability condition put forth in the definition? The measure P I thought was defined on measurable space K, but in the definition it says that given any cipher c, then any two messages we choose will have the same probability of occurence. P of what event is evaluated exactly? $\endgroup$ Oct 15, 2022 at 11:36
  • $\begingroup$ For the setting of practical cryptography, certainly for symmetric key block ciphers, the fully rigorous measure theoretic properties of probabilistic analysis do not add much in my opinion. They form a scaffolding which usually obscures ideas. For this specific case, I would like to hear opposing ideas and demonstrations of usefulness of the fully abstract approach. $\endgroup$
    – kodlu
    Oct 15, 2022 at 16:46
  • 1
    $\begingroup$ @kodlu Well tbh i dont mind not using rigorous terminology and such as long as i can be assured that it can be put in a rigorous setting. I just don't feel comfortable reasoning with things that i just dont what they are exactly... I guess i should get used to it. $\endgroup$ Oct 15, 2022 at 17:51
  • $\begingroup$ I didn't mean that you should get used to it, just shared an opinion. Maybe @GeoffroyCouteau could provide a more rigorous definition for your specific question if he is so inclined. This is not my strength and haven't seen it nicely used in problems such as the one you asked. And yes I suppose in almost all symmetric key questions the sigma algebra is simply the power set. $\endgroup$
    – kodlu
    Oct 15, 2022 at 18:07

2 Answers 2

1
$\begingroup$

The measurable space is indeed ${\mathcal{K}=(K,2^K)}$ (cryptography mostly deals with discrete probabilities and the $\sigma$-algebra is taken to be the power set), and the probability measure is ${\mu(S)=|S|/|K|}$ for ${S\subseteq K}$. The notation $P(f(k))$, where $f(k)$ is a formula with free variable $k$, means $\mu(\{k\in K:f(k)\})$. Perfect secrecy requires $$\begin{aligned} &\forall m_0,m_1\in M,c\in C: \\&\quad \mu(\{k\in K:E(k,m_0)=c\})=\mu(\{k\in K:E(k,m_1)=c\}). \end{aligned}$$ The less ambiguous term is “random element”, i.e., a measurable map from the event space to a measurable space (not with the assumption that the codomain corresponds to the Borel algebra over $\mathbb{R}$). Here, the random element “$k$” is the identity map $\mathrm{id}_K$.


Edit on 26 Oct 2022: I should rather say that “the easiest way to implement this distribution is…” The random element $k$ could be implemented by any measurable map ${k:\Omega\to K}$ such that ${\nu(k^{-1}(\{z\}))=1/|K|}$ for all ${z\in K}$, where $\nu$ is a probability measure over some measurable space $(\Omega,\Sigma)$.

$\endgroup$
1
  • $\begingroup$ Awesome. Thanks that completely clarified everything for me. $\endgroup$ Oct 19, 2022 at 7:07
0
$\begingroup$

$M$ is not a $\sigma$-algebra, but a set of all possible messages. All three spaces: key space $K$, the message space $M$ and the ciphertext space $C$ are simply sets of all binary sequences of constant lengths $b_k$, $b_m$, $b_c$.

$$K=\underbrace{\{0,1\}\times...\times\{0,1\}}_{k}=\{0,1\}^{b_k}$$

$$M=\{0,1\}^{b_m}$$

$$C=\{0,1\}^{b_c}$$

E.g., for $b_k=2$, $K=\{00,01,10,11\}$.

Key $k$ is uniformly distributed draw from $K$. Continuing in the example above

$$P(k=00)=P(k=01)=P(k=10)=P(k=11)=\frac{1}{2^{b_k}}=0.25$$

Perfect security

The idea behind perfect security is that you should not learn anything by seeing the ciphertext. Note, encryption is a bijection, given a key. You fix the message and change keys, then the encryption produces ciphertexts from ciphertext space equally likely.

A typical example is one-time pad (OTP) of size $2$. You have the same key space as before. We want to send a message $m=01$. The OTP encryption is done with exclusive OR, $x=m\oplus k$.

For our message, all ciphertexts are equally likely.

$$01\oplus00=01$$ $$01\oplus01=00$$ $$01\oplus10=11$$ $$01\oplus11=10$$

The same work the other way around, when we fix the key and iterate messages. This means we have the perfect security - by seeing the ciphertext, we learn nothing about the message, all messages are equally likely! Remember, never reuse key in OTP!

$\endgroup$
1
  • $\begingroup$ Thanks but your answer is irrelevant as it does not address my questions. $\endgroup$ Oct 15, 2022 at 21:58

Your Answer

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

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