What is the difference between Strict Avalanche Criterion(SAC) and Avalanche criterion?
$\begingroup$
$\endgroup$
1
-
1$\begingroup$ What research have you done? What were your findings? Why didn't you findings satisfy your needs? For more infos, read How do I ask a good question? $\endgroup$– e-sushiCommented Dec 22, 2016 at 7:25
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
The definition of avalanche effect is given in the paper of Webster, A. F. "On the design of S-boxes". Advances in Cryptology - Crypto '85 as :
For a given transformation to exhibit the avalanche effect, an average of one half of the output bits should change whenever a single input bit is complemented.
It is also seen as each bit should have 50% chances to change if you change 1 bit of the input. (strict avalanche)
In the avalanche criterion you look at the output as a whole (average 50% of the bits changes).
In the strict avalanche criterion, you look at each bit one by one and you verify that what ever the other bits will change, it will have a 50% probability to switch.
Related questions:
-
$\begingroup$ Unless you specifically code an algorithm to do something extremely weird, does not avalanche = strict avalanche in all practical regards for a grown up candidate hash function? $\endgroup$ Commented Dec 21, 2016 at 23:01
-
1$\begingroup$ No. For example you can have a look at the aes s box. The strict criterion is not here. And to check it on hash candidates you would need too much time. $\endgroup$– BivCommented Dec 21, 2016 at 23:03
$\begingroup$
$\endgroup$
2
Avalanche criterion, or Avalanche effect is informal. Small changes in inputs should always lead to large changes in outputs.
Consider a vector Boolean function $$f:F_2^n \rightarrow F_2^m$$ with $n$ bit input and $m$ bit output.
Strict Avalanche Criterion (SAC) says that if any input bit is flipped then exactly half of output bits should change. There are higher order versions as well where $k$ input bits are flipped and the same property is required of the output bits.
-
1$\begingroup$
The strict avalanche criterion (SAC) is a formalization of the avalanche effect. It is satisfied if, whenever a single input bit is complemented, each of the output bits changes with a 50% probability.it does not say that exactly half of the bits changes, it says each bit have 50% changes. One bit could change and all the other bits could stay the same. Very unlikely but it is possible. $\endgroup$– BivCommented Dec 21, 2016 at 21:36 -
$\begingroup$ @Biv, thanks for the clarification, I was obviously remembering wrong. $\endgroup$– kodluCommented Dec 21, 2016 at 21:47