Re: perfect security

From: David Wagner (daw_at_taverner.cs.berkeley.edu)
Date: 05/21/05 

Date: Sat, 21 May 2005 21:34:35 +0000 (UTC)

Olga Johann wrote:
>> You have to be careful to specify what space the probability is
>> taken over. In the proper defn of Shannon secrecy, the probability
>> is taken over both the random choice of a message (drawn according to
>> some distribution D) and the random choice of a key (independent of the
>> message, according to the distribution specified by the cryptosystem).
>
>Has it to be the same distribution for the keys, as used for the messages?

No. If you read my post, I said I assumed the key distribution was
uniform, while the scheme must be secure for message distributions
(which means, including non-uniform distributions).

>> Side note: I personally dislike notation like P(x), because it is too
>> unclear about what is the random variable and the observation. I prefer
>> to let X,Y,K denote the random variables, write things like Pr[X=x],
>> Pr[X=x|Y=y], etc. In this case we define Y=E_K(X).
>
>Ok, I like this notation. As I read in your lecture notes, is then X the
> set of possible messages, K the set of possible keys and Y the set of
>possible ciphertexts?

No, what I said above is: "let X,Y,K denote [...] random variables".
They are random variables, not sets. In my post, I tried to follow
your notation, so M and C are sets (the message space, and the ciphertext
space, respectively); X takes values in M, and Y takes values in C.

I do not recall what notation I used in my lecture notes; it may well
be different. I tried to follow the notation of your post as much as
possible, to avoid confusion. I apologize that this wasn't clear.

>> Suppose #{k : x \in M, y \in C, E_k(x)=y} is independent of x,y.
>
>I suppose that you mean with this, that the number of keys is equal
>independent for each x,y, or am I wrong?

Right, that is what I meant. I meant that there exists an integer
n so that
  #{k : x \in M, y \in C, E_k(x)=y} = n for all x,y.

>> Then Pr[Y=y] = \sum_x Pr[Y=y|X=x] Pr[X=x] = p, and Pr[X=x and Y=y] =
>> p * Pr[X=x]. Thus Pr[X=x|Y=y] = p * Pr[X=x] / p = Pr[X=x].
>
>What is the difference between Pr[E_K(x)=y] and Pr[Y=y]?

Recall that X,Y,K are random variables. As I wrote in my post, the
random variable Y is defined by Y = E_K(X). Do you know what that
notation means? It means that Y is defined as a function of the other
random variables X and K.

Are you familiar with the idea that the function of a random variable
can be a random variable? If R is a random variable and f is a function,
then f(R) is a random variable. The definition of Y is similar.

So now I can answer your question. Since, by definition, Y = E_K(X),
this means that Pr[Y=y] = Pr[E_K(X)=y]. Compare that to Pr[E_K(x)=y].
Do you see the difference? X is a random variable (taking values on the
set of messages), x is a particular value (a message).

Yes, this is one example of why I prefer my notation, because it
distinguishes between two different quantities that would be conflated
with your notation. Of course, if you are careful in using your notation,
then it is possible to avoid getting confused -- but if you are not
experienced in manipulating random variables, then I suggest my more
explicit notation as an aid to understanding.

>> If this means that you were going to use
>> C_1 = M_1 + K_2 + K_3
>> C_2 = M_2 + K_1 + K_3
>> C_3 = M_3 + K_1 + K_2
>> then your scheme is insecure, since C_1 + C_2 + C_3 = M_1 + M_2 + M_3.
>
>Yes I mean this. But it is secure, at least Chaum wrote it in his paper
>about DC-net.

I haven't read that paper in a long time, so I'm afraid I don't recall
what Chaum said about it; I'm sorry. But I don't care what anyone says,
it is obviously insecure as an encryption scheme, as demonstrated by my
attack above.

>But for it holds:
>Pr[M=(M_1,M_2,M_3)|C=(C_1,C_2,C_3)] = Pr[M=(M_1,M_2,M_3)|S]
>where S= C_1 + C_2 + C_3 = M_1 + M_2 + M_3.
>
>Btw. if I use your notation what is then the random variable for S?

My notation would be
 Pr[M=(m_1,m_2,m_3)|C=(c_1,c_2,c_3)] = Pr[M=(m_1,m_2,m_3)|S=s]
where M,C,S are the random variables and m_i,c_i,s are the values.
Typographic guideline: capital letters are random variables, lowercase
letters are values.

By the way: Yes, this equation is correct, but the scheme is still
insecure, because it leaks partial information about the messages.

Relevant Pages

  • Re: How random is a random variable
    ... equality between random variables are defined. ... distribution or is it merely a uniform distribution with a different ... specific realization or as a function of all possible realizations. ... Notation is about suitable short cuts and will ...
    (sci.stat.math)
  • Re: How Chapman-Kolmogorov implies Markov ??
    ... Perhaps the notation "f_i" is supposed to imply there is ... something equivalent about all of these random variables, ... concept, that we index the index set iself, or else write a finite ... sequence in it, explicitly using the integers as our indices. ...
    (sci.physics)
  • Re: How random is a random variable
    ... equality between random variables are defined. ... distribution or is it merely a uniform distribution with a different ... specific realization or as a function of all possible realizations. ... Your question seems to be about notation as once you have longer ...
    (sci.stat.math)
  • Re: How random is a random variable
    ... regarding how to interpret random varibles in equations. ... distribution or as a realization of the underlying distribution. ... X_1 and X_2 be independent random variables with the same distribution then ... In addition, however, your notation is not good. ...
    (sci.stat.math)
  • Re: perfect security
    ... > some distribution D) and the random choice of a key (independent of the ... according to the distribution specified by the cryptosystem). ... Has it to be the same distribution for the keys, ... Ok, I like this notation. ...
    (sci.crypt)