3
$\begingroup$

Let say
$K_{0} = \left \{ 0,1\right \}^n$
$K_{1} = K=\left \{ 0,1\right \}^n$ \ $0^n$
$[b\leftarrow \left \{0,1 \right\}, k \leftarrow K_{b}:b=1|k \neq 0^n]$ --- (1)
Key is chosen using constraints (1).
Is this scheme perfect secret assuming OTP is used as encryption scheme.

I thought of using Shannon theory (|K|>=|M|) of perfect secrecy but the key distribution is different. Therefore I could not come up with any solution.

Also: What's the probability of constraints 1? If we can find also we can say that given scheme is perfectly secret or not.

$\endgroup$
0

1 Answer 1

3
$\begingroup$

It cannot be perfectly secret : if $C = M \oplus K$ is your encrypted message, all the possible values of $M$ do not happen with equal probability. Indeed, the case $M = C$ (corresponding to $K = 0$) is twice less liquely to happen. You cannot have $H(M) = H(M|C)$; if e.g. $M$ is drawn uniformly at random, the distribution of $M$ given $C$ is clearly not the uniform distribution.

What's the probability of constraints 1? If we can find also we can say that given scheme is perfectly secret or not.

The probability distribution of $M$ given $C$ is $1/2(1/2^n + 1/(2^n-1))$ for every $M \neq C$, and $1/2^{n+1}$ for $M = C$. Hence the distribution of $M$ given $C$ is clearly not uniform.

$\endgroup$
0

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.