TY - GEN

T1 - Secrecy is cheap if the adversary must reconstruct

AU - Schieler, Curt

AU - Cuff, Paul

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84867489582&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84867489582&partnerID=8YFLogxK

U2 - 10.1109/ISIT.2012.6284287

DO - 10.1109/ISIT.2012.6284287

M3 - Conference contribution

AN - SCOPUS:84867489582

SN - 9781467325790

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 66

EP - 70

BT - 2012 IEEE International Symposium on Information Theory Proceedings, ISIT 2012

T2 - 2012 IEEE International Symposium on Information Theory, ISIT 2012

Y2 - 1 July 2012 through 6 July 2012

ER -