Hi everyone,
The next episode of our group seminars next Tuesday will feature a talk by Christopher Portmann. Do not miss it!
--Frédéric
--------------------------------------- Title: Information-theoretic non-malleable encryption. Date/Time/Place: Tuesday, May 10, 17:00, HIT J51 Speaker: Christopher Portmann
Abstract: An encryption scheme is said to be non-malleable, if no adversary can modify a ciphertext so that the resulting message is meaningfully related to the original message. In the first part of the talk, I'll give the same presentation as at the upcoming ICITS on the classical case (eprint.iacr.org/2011/092). In the second part of the talk I'll review the work by Ambainis, Bouda and Winter (arXiv:0808.0353) on quantum non-malleability.
We compare information-theoretic non-malleability for classical schemes to secrecy and authenticity, and provide a complete characterization of their relative strengths. In particular, we show that information-theoretic perfect non-malleability is equivalent to perfect secrecy of two different messages. This implies that for $n$-bit messages a shared secret key of length roughly $2n$ is necessary to achieve non-malleability, which meets the previously known upper bound. We define approximate non-malleability by relaxing the security conditions and only requiring non-malleability to hold with high probability (over the choice of secret key), and show that any authentication scheme implies approximate non-malleability. Since authentication is possible with a shared secret key of length roughly $\log n$, the same applies to approximate non-malleability.
Ambainis et al. study non-malleable encryption for quantum messages, but restrict their considerations to encryption operations consisting in unitary transformations. They show that such a scheme is equivalent to a "unitary 2-design", as opposed to normal encryption which is a unitary 1-design.