[Cryptography] Perfect Integrity?

[Jonathan Katz]

On Fri, Aug 3, 2018 at 1:33 PM, Phillip Hallam-Baker
<phill at hallambaker.com> wrote:
>
>
> On Wed, Aug 1, 2018 at 7:51 AM, Alexandre Anzala-Yamajako
> <anzalaya at gmail.com> 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 theoritic security.
>
>
> I don't think they do. Rather, I think they provide you with a bounded proof
> of security that depends on some safe but real assumptions.
>
>
> The integrity equivalent to a One Time Pad is to keep a copy of the data
> itself as evidence of integrity. Like an OTP, perfectly secure and perfectly
> useless.
>
> Apart from applications like RAID1 mirroring and such that is.
>
>
> Cryptography is really about compressing the security problem scope. Instead
> of protecting all these terrorbytes of data, I just have to protect a few
> little bits of key.

I have to say, I find some of the discussion surrounding this question
rather silly.

We need to first rigorously define a notion of "information-theoretic
message authentication" before asking whether it is achievable. (You
may or may not like the definition I propose, but arguing without any
definition in place is just a waste of energy. And you are free to
suggest your own definition as long as you can express it formally so
I know precisely what you mean.)

It turns out that information-theoretic message authentication codes
(MACs) have a long history, dating back at least to the 1970s.

One standard definition (covered in "Introduction to Modern
Cryptography, 2nd edition" by Katz and Lindell, Section 4.6) considers
the following experiment:
- Sender and receiver share a uniform key, unknown to the attacker.
- Attacker chooses a message m in some defined message space and the
sender authenticates it. The attacker gets to see the resulting
authentication tag.
- Attacker "wins" if it can output a different message m' along with
an authentication tag that will cause the receiver to accept the pair
as valid.

Then an \epsilon-secure (information-theoretic) MAC is one in which no
attacker can win with probability better than \epsilon.

Now you can start asking all kinds of questions:
- Does a 0-secure MAC exist? (It is easy to see that the answer is no.)
- Does an \epsilon-secure MAC exist for every \epsilon > 0? (Not as
easy to see, but well known that the answer is yes.)
- What is the minimum tag length required in order to achieve a
2^{-n}-secure MAC? (It is easy to see that the tag must have length at
least n.)
- What are the various tradeoffs between size of the message space,
length of the tag, length of the key, and achievable \epsilon? (These
are all research questions, most or all of which have been studied
over the last 4+ decades.)