What are “weak” and “strong” output-input bit dependencies?

lyrically wicked

9/21/23, 6:48 AM

Section 3.3.5 of the paper “Schwaemm and Esch: Lightweight Authenticated Encryption and Hashing using the Sparkle Permutation Family” (the link to PDF can be found in this page) contains the following text:

Alzette provides very fast diffusion. In particular, all outputs bits depend on all the input bits after 4 rounds, though this dependency can be very weak. After 8 rounds however, we have that all output bits strongly depend on all the input bits.

Question: what are “weak” and “strong” dependencies? I thought that the bit dependency was either present or absent. If it is present, how to measure it?

0 + 0

terminology

diffusion

Score:2

Crypto

Daniel S

9/22/23, 9:46 AM

There can be various measures of bit dependency. A classical measure would be how close the process is to achieving what Claude Shannon termed diffusion, which is sometimes termed the strict avalanche criterion. In this case we measure the proportion of input/output pairs for which changing the selected input bit changes the selected output bit. If the proportion is 0 this would be independence, if the proportion is close to 1/2 this would be diffusion/SAC, if the proportion is close to 0 this would be called weak dependence, if the proportion is close to 1/2 this would be called strong dependence.

For example consider the four-bit to one-bit Boolean function $$y=x_1x_2+x_0x_1x_2x_3$$ it is easy to exhaustively check that flipping the $x_0$ or $x_3$ inputs changes the value of $y$ for 2 possible input values out of 16. This is dependency, but quite weak.

By contrast, for the function $$z=x_0x_1+x_1x_2+x_2x_3+x_3x_0$$ it is easy to check that flipping any bit changes the value of $z$ for 8 of the possible input values out of 16. This is strong dependency.

There's a question of what we should term the cases where the proportion that change on flipping is close to 1.

0 + 0

kelalaka

9/22/23, 10:42 PM

full dependent?

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: What are “weak” and “strong” output-input bit dependencies?

TH: การพึ่งพาบิตเอาต์พุต-อินพุตแบบ "อ่อนแอ" และ "แข็งแกร่ง" คืออะไร

RO: Care sunt dependențele „slabe” și „puternice” de biți de intrare-ieșire?

RU: Что такое «слабая» и «сильная» битовые зависимости между выходом и входом?

VI: Phụ thuộc bit đầu ra-đầu vào âyếuâ và âmạnhâ là gì?

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.