[Cryptography] Perfect Integrity?

[Kristian Gjøsteen]

4. aug. 2018 kl. 21:44 skrev Peter Fairbrother <peter at tsto.co.uk>:
> On 01/08/18 12:51, Alexandre Anzala-Yamajako wrote:
>> The short answer is : yes.
>> You can find some examples here https://crypto.stackexchange.com/questions/43659/information-theoretic-message-authentication-code-mac
>> I believe that any Wegman-Carter MAC where the key is changed after every use gives you information theoretic security.
> 
> A one-bit W-C MAC will give an attacker no advantage in guessing the bit - but he will still have a 50% chance of guessing right.

For ciphers, «information theoretic security» has a specific meaning that roughly translates into «an adversary with unlimited computing power does not learn anything from the ciphertext».

This definition does not make sense for integrity, so information theoretic has to get a new meaning with respect to integrity.

First, the context. We have a function f that takes a key and a message and outputs a tag. There are n distinct tags. Alice sends (m,t) to Bob, where t = f(k,m) and k is a shared key. Bob receives (m’, t’) and checks if f(k,m’) == t’.

Note (as has been said, already) that - regardless of what f is - Eve has a 1/n chance of creating a valid tag by choosing t’ at random. (At this point, some people say that information theoretic security is impossible and stop. Even though we haven’t defined what information theoretic security means yet…)

There are now two possible ways to define security: (a) no adversary should have greater than 1/n chance of creating a forgery, and (b) no adversary should have greater than eps chance of creating a forgery, for some small eps.

(b) is the most convenient content of «information theoretic integrity», and we may reserve the prefix «perfect» to denote (a).

First, an example that does not work (as has been noted): f(k,m) = k+m. Eve sets m’ = m + Delta and t’ = t + Delta and wins.

Next, an example that works: k = (a,b), f(k,m) = a*m + b. First, since b is random, Eve learns nothing about a from t. Next, suppose Eve sets m’ = m + Delta and t’ = t + Delta’. If Eve wins, then Delta’ = a*Delta. Since Delta is non-zero, the odds of that is exactly 1/n.

This extends in a fairly straight forward manner to longer messages via polynomial evaluation.

This theory was first developed by Carter and Wegman. It has since become very important, also for non-information theoretic cryptography.

-- 
Kristian Gjøsteen