THE QUANTUM INTELLIGENCER

The constant-rate question for worst-case classical messages in the entangled two-split-state model has been answered. In that model a codeword is divided into two shares, and two adversaries each tamper with one share; the adversaries may not communicate during the attack, but they may share arbitrary quantum entanglement arranged beforehand. A new construction of non-malleable codes appears on the arXiv and secures classical messages against such tampering without computational assumptions. Non-malleability means that a tampered codeword decodes either to the original message or to a value unrelated to it, never to a related message. The codes are efficient and perfectly correct, and they attain rate at least one-fifth, less any fixed positive constant, for all sufficiently large share lengths, with an error that decays faster than any polynomial in the share length. Security holds for every message rather than only for uniformly random messages, and each attack is met by a single message-independent simulator. The construction keeps the permutation-based architecture of Batra, Boddu and Jain, which approached rate one-fifth for uniform messages, and feeds that permutation a prescribed message concatenated with fresh uniform padding; the contribution is a worst-case security reduction for the alteration. This closes the constant-rate question for the model. Five terms carry the weight of this report. The rate of a code is the ratio of the length of the message to the length of the codeword, which in the split-state model is the length of the two shares together. At a rate of one-fifth, five bits of codeword are expended for every bit of meaning, and the remaining four are the price of the guarantee. Perfect correctness is the plain assurance that a codeword left untouched decodes to the message first sent, always, with no allowance for failure. The error of the scheme is the greatest probability, taken over all attacks and all messages, that a tampered codeword decodes to a value related to the original: neither the original itself nor an independent value. In this construction that error decays faster than any polynomial in the length of a share, and therefore becomes negligible as shares grow. Information-theoretic security places no computational limit upon the adversary; the assurance rests on information and probability, not on the difficulty of a calculation. Worst-case protection means the guarantee covers every message a sender may choose, including the message least favourable to the code; it does not depend on the mercy of averages. A constant-rate code holds its rate as messages lengthen rather than letting it dwindle; the present code holds at one-fifth, less any fixed positive constant. A message-independent simulator, finally, is proof apparatus rather than machinery: a single procedure, seeing no message, reproduces the distribution of decoded outputs that a real attack would yield, and one such procedure answers for every message. These are the definitions that make the construction legible. —Inspector Grey Dispatch from The Prepared E0