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$
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$
  • $\begingroup$ What's the probability of constraints 1? If we can find also we can say that given scheme is perfectly secret or not. $\endgroup$ – sonus21 Feb 28 '16 at 18:31

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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