Calculating statistical distance for simple addition cipher?

Foobar

4/24/23, 10:32 PM

I'm looking at the solutions to this problem set for self study.

One of the questions is to calculate the statistical distance for the following scheme:

The message space is equal to the key space, which is all positive integers $\leq 2^\lambda$
Encryption/decryption is just addition & subtraction

and statistical distance is defined as:

The solution for calculating the statistical distance is:

This solution roughly makes sense.

The probability of any given cipher text being generated by the encryption scheme is either:
- 0 if the cipher text is smaller than the message
- $\frac{1}{2^\lambda}$ if the cipher text is larger than the message (that's the probability that we generate the right key)

Thus, the difference between the 2 messages is the number of cipher texts that can be generated for 1 message but not the other and each of those has a probability of $\frac{1}{2^\lambda}$, so we get $\frac{|m_0 - m_1|}{2^\lambda}$.

What I don't understand is why there is a 2 in the numerator of the fraction that the summation reduces to.

Does anyone know?

0 + 0

cryptanalysis

Score:2

Crypto

kelalaka

4/25/23, 10:22 PM

It should be $$\frac{1}{2} \sum_{i =2}^{\color{red}{2^{\lambda+1}}} |\Pr[k_0 \gets \text{Gen}(1^\lambda):k_0+m_0=i] - \Pr[k_1 \gets \text{Gen}(1^\lambda):k_1+m_1=i]| $$

Since the definition of the $\mathcal{M}$ and $\mathcal{K}$

$$ \mathcal{M = K} = \{ i \in \mathbb{Z}^+ | i \leq 2^\lambda\}$$

since $c = k + m$ then $$\mathcal{C} = \{ \in \mathbb{Z}^+ | 2 \leq i \leq 2^{\color{red}{\lambda\ +1}}\}$$

And this explains where the $2$ comes from.

0 + 0

kelalaka

4/30/23, 4:55 PM

I should wrote as `2^\lambda + 1` vs `2^{\lambda + 1} `

Foobar

4/30/23, 8:53 PM

Apologies, is 2^(lambda + 1) not already in the image I provided?

kelalaka

4/30/23, 8:55 PM

It is $2^{\lambda} + 1$ not $2^{\lambda + 1}$. A small but common typo in $\LaTeX$ `2^{\lambda} + 1` vs `2^{\lambda + 1}`