Secrecy Is Cheap if the Adversary Must Reconstruct
This reduces key requirements for secure communication against reconstruction attacks, though it is incremental as it builds on prior work by Yamamoto.
The paper tackles the problem of minimizing secret key size needed to achieve maximal distortion against an eavesdropper attempting to reconstruct information, showing that an unboundedly growing key space suffices and even a constant-size key can cause arbitrarily close to maximal distortion.
A secret key can be used to conceal information from an eavesdropper during communication, as in Shannon's cipher system. Most theoretical guarantees of secrecy require the secret key space to grow exponentially with the length of communication. Here we show that when an eavesdropper attempts to reconstruct an information sequence, as posed in the literature by Yamamoto, very little secret key is required to effect unconditionally maximal distortion; specifically, we only need the secret key space to increase unboundedly, growing arbitrarily slowly with the blocklength. As a corollary, even with a secret key of constant size we can still cause the adversary arbitrarily close to maximal distortion, regardless of the length of the information sequence.