Re: paper comment

[dmolnar <dmolnar@hcs.harvard.edu>]

>
> George: Please fix it in the picture and paper as appropriate.
>

George, Roger,

Thanks for doing this - but I'd like to say that I'm not sure you can get
away with using just a generic AONT and still have the "any bit change
produces random garbage" property. Maybe this is implied by the AONT
property, but I'm not seeing it yet. I do note that semantic security in
encryption does **not** imply the property we're looking for.

I am seeing this:

From any AONT build a new AONT' as follows:

	AONT'(M) = flip a random bit b
		   if b = 1 then output AONT(~M) || b
		   if b = 0 then output AONT(M) || b

where ~M means bitwise complement of M and || means concatenation.
To de-AONT', use AONT on all but the last bit, and then complement or not
according to the value of the last bit.

Now AONT' is malleable - the adversary just changes b and can complement
your message. I'm not sure it's still an AONT, because maybe knowing all
the bits but b gives you too much information, but if it is, then this is
a provably stupid counterexample to the claim that an AONT is
non-malleable. (I don't claim that it would help with tagging attacks).

The conservative thing to do, I think, would be to say that you need a
"non-malleable AONT" or a "any bit change randomizes the output AONT" in
the paragraph George just changed.

-David