Re: Niggling differential probability question.

From: Scott Fluhrer (sfluhrer@ix.netcom.com)
Date: 02/14/03 

From: "Scott Fluhrer" <sfluhrer@ix.netcom.com>
Date: Fri, 14 Feb 2003 00:16:33 -0800

Matt <cipher_q2000@yahoo.co.uk> wrote in message
news:c1f4ece5.0302130330.507c48eb@posting.google.com...
> Apologies for this somewhat trivial question...
>
> In an early DC paper[1], Biham and Shamir give a formula for the
> probability of a certain (xor) difference after modulo addition: let
> the two inputs be X and Y, yielding Z = X + Y mod 256. Given two
> differences in the inputs, X' and Y', and the output difference Z',
> the probability that X' and Y' may cause Z' = X' xor Y' is "about":
>
> 1 / (2 ** N(X' or Y')), where N(B) is the number of bits set to "1"
> in the lower seven bits of B, "or" is bitwise or, and ** is
> exponentiation.
>
> This seems straightforward, but I don't understand why the word
> "about" was used -- it seems that it should be "exactly", but I know
> it's easy to overlook stuff in probability calculations. The paper
> elaborates:
>
> "This happens because each bit which is different in the pairs (X and
> X*, Y and Y*) gives rise to a different carry with probability close
> to 1/2",
They said "approximately" because it really isn't exact -- if X'=2 and Y'=2,
then the probability that Z'=1 is 0, not 1/2 as their equation suggests. In
the other direction, if X'=255 and Y'=255, then the probability that Z'=254
is 1/2, not 1/128 that the equation would suggest.

If you really want the full analysis of such differential probabilities (and
it's rather more subtle than it appears at first glance), see
_Efficient_Algorithms_for_Computing_Differential_Properties_of_Addition_, by
Lipmaa and Moriai, published in FSE 2001. 

--
poncho

Relevant Pages

  • Niggling differential probability question.
    ... Biham and Shamir give a formula for the ... probability of a certain (xor) difference after modulo addition: ...
    (sci.crypt)
  • Re: The Tuesday boy problem.
    ... reads comic books? ... My apologies for being ambiguous myself! ... any or all of them would affect the probability. ...
    (sci.math)
  • Re: The Tuesday boy problem.
    ... reads comic books? ... My apologies for being ambiguous myself! ... any or all of them would affect the probability. ...
    (sci.math)
  • Re: A first course in probability 7th edition
    ... probability" by sheldon ross? ... They are off-topic and spoil the group for its intended audience. ... (Apologies to the group for the grammatical nonsense in my previous ...
    (sci.math.num-analysis)
  • P(prod_i p_i^{k_i}|n)=?
    ... Apologies if this is a stupid question. ... What is the probability that n has the form prod_i p_i^m, ... I.N. Galidakis ...
    (sci.math)