Efficient approximate message authentication scheme

An approximate message authentication scheme is a primitive that allows a sender Alice to send a source state to a receiver Bob such that the latter is assured of its authenticity, where the source state is considered as authentic if it only undergoes a minor change. Here, the authors propose an efficient scheme for this problem and prove its security under a rigorous model. Our scheme only needs a lightweight computation cost and hence is very efficient. As the authentication message is transmitted over a noisy channel, we also value the channel efficiency (i.e. the coding rate). For a fixed coding method, this is determined by the admissible decoding bit error probability p e . A larger p eadmits a shorter codeword length and hence a larger coding rate. It turns out that the p ecan be set to be a significantly large constant (determined by the legal distortion level for the source state). Compared with existing schemes, the advantage in p eis evident.