Score:1

Crypto

Clarification of some probability concepts used in crypto

mathInferno

10/15/23, 6:23 AM

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.

143

2 + 5

security-definition

probability

Geoffroy Couteau

10/15/23, 10:11 AM

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.

mathInferno

10/15/23, 11:36 AM

@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?

kodlu

10/15/23, 4:46 PM

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.

mathInferno

10/15/23, 5:51 PM

@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.

kodlu

10/15/23, 6:07 PM

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.

Score:1

Crypto

Gee Law

10/18/23, 6:02 PM

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)$.

+ 1

mathInferno

10/19/23, 7:07 AM

Awesome. Thanks that completely clarified everything for me.

Score:0

Crypto

Martin Benes

10/15/23, 8:22 PM

$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!

+ 1

mathInferno

10/15/23, 9:58 PM

Thanks but your answer is irrelevant as it does not address my questions.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Clarification of some probability concepts used in crypto

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.