2022 Developer Survey is open! Take survey.

New answers tagged

1 vote

What are the key difference between Shannon entropy and Guessing Entropy?

Edit: Based on the comment of the OP, one way of thinking of the difference between Guesswork and Shannon Entropy is the following: Shannon: Let's say we have a random variable to encode. Given its ...
user avatar
  • 16.1k
4 votes

What does $(a+b) \bmod{256}$ and $a$ XOR $b$ reveal about $a, b$?

As I didn't see it mentioned yet: $a + b = (a\oplus b) + ((a\&b)<<1) \bmod 256$ (where $<<$ denotes left-shift), so the information you are given is equivalent to knowing $a\oplus b$ ...
2 votes
Accepted

For any numbers $a, b$, what are the operators $X, Y$ such that revealing $a\ X\ b$ and $a\ Y\ b$ doesn't reveal info about $a,b$?

It is possible to leak zero information. Assume uniformly distributed $a$ and $b$ and let $a$ vary along the rows and $b$ along the columns of the operation tables below: $$ \begin{array}{ccc} \begin{...
user avatar
  • 16.1k
5 votes

What does $(a+b) \bmod{256}$ and $a$ XOR $b$ reveal about $a, b$?

fgrieu analyzes the average case; we can also consider the worst case - how much the entropy are we guaranteed to have left. One 'worse case' happens if the $a+b = 0 \pmod {256}$ and $a \oplus b = 0$; ...
user avatar
  • 131k
4 votes
Accepted

What does $(a+b) \bmod{256}$ and $a$ XOR $b$ reveal about $a, b$?

I'll assume bitstrings are assimilated to integers by big-endian notation, $a$ and $b$ are $k$-bits with $k=8$ in the question, and it's given two $k$-bit quantities $s:=a+b\bmod{2^k}$ and $x:=a\oplus ...
user avatar
  • 122k

Top 50 recent answers are included