Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1103.3746 · Allerton Conference on Communication, Control, and Computing

Using a secret key to foil an eavesdropper

Paul Cuff

Published Sep 1, 2010• 22 citations
arXivHTMLPDF

Abstract

This work addresses secrecy with distributed systems in mind. We consider an adversary who wishes to attack a system and find the optimal communication and use of secret key to share information in such a system. Instead of measuring secrecy by “equivocation,” we define a value function for the system, based on the actions of the system and the adversary, and set out to design a system that maximizes the average value obtained against the worst adversary.

DOI
10.1109/allerton.2010.5707078

Related papers

Rate-distortion theory for secrecy systems

Curt M. Schieler, Paul Cuff

In this work, secrecy in communication systems is measured by the distortion incurred by the worst-case adversary. The transmitter and receiver share secret key, which they use to encrypt communication and cause distortion at an adversary. In our model, we assume that an adversary not only intercepts the communication between the transmitter and receiver, but also may have access to noisy observations of the system. For example, the adversary may have causal access to a signal that is correlated with the source sequence or with the output of the receiver. Our main contribution is the solution of the optimal tradeoff among communication rate, secret key rate, distortion at the adversary, and distortion at the legitimate receiver. We demonstrate that side information at the adversary plays a pivotal role, and provide a number of examples that motivate and give insight into our results.

arXiv:1305.3905•IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2013•16 citations

Eavesdropping Foiled by Decoys

Secure communication between a sender and a receiver generally requires the message to be encrypted, with the sender and recipient sharing a secret key that encodes and deciphers the message. Ideally, the key should be changed often, and so for practical reasons the key should be distributable over normal communication channels. However, the possibility of the interception of the key by an eavesdropper would compromise security. There is, therefore, a need for a method to distribute the key to the recipient securely so that any attack on the communication channel by a potential eavesdropper can be detected and appropriate action taken.

Science•Jan 18, 2007•0 citations

A Framework for Partial Secrecy

Paul Cuff

We consider theoretical limits of partial secrecy in a setting where an eavesdropper attempts to causally reconstruct an information sequence with low distortion based on an intercepted transmission and the past of the sequence. The transmitter and receiver have limited secret key at their disposal but not enough to establish perfect secrecy with a one-time pad. From another viewpoint, the eavesdropper is acting as an adversary, competing in a zero-sum repeated game against the sender and receiver of the secrecy system. In this case, the information sequence represents a sequence of actions, and the distortion function captures the payoff of the game. We give an information theoretic region expressing the tradeoff between secret key rate and max-min distortion for the eavesdropper. We also simplify this characterization to a linear program. As an example, we discuss how to optimally use secret key to hide Bernoulli-p bits from an eavesdropper so that they incur maximal Hamming distortion.

arXiv:1008.0602•Globecom•Dec 1, 2010•41 citations

Secrecy in Cascade Networks

Paul Cuff

We consider a cascade network where a sequence of nodes each send a message to their downstream neighbor to enable coordination, the first node having access to an information signal. An adversary also receives all of the communication as well as additional side-information. The performance of the system is measured by a payoff function evaluated on actions produced at each of the nodes, including the adversary. The challenge is to effectively use a secret key to infuse some level of privacy into the encoding, in order thwart the adversary's attempt to reduce the payoff. We obtain information-theoretic inner and outer bounds on performance, and give examples where they are tight. From these bounds, we also derive the optimal equivocation for this setting as a special case.

arXiv:1411.0060•Nov 1, 2014•0 citations

Rate-Distortion Theory for Secrecy Systems

Curt M. Schieler, Paul Cuff

Secrecy in communication systems is measured herein by the distortion that an adversary incurs. The transmitter and receiver share secret key, which they use to encrypt communication and ensure distortion at an adversary. A model is considered in which an adversary not only intercepts the communication from the transmitter to the receiver, but also potentially has side information. In particular, the adversary may have causal or noncausal access to a signal that is correlated with the source sequence or the receiver's reconstruction sequence. The main contribution is the characterization of the optimal tradeoff among communication rate, secret key rate, distortion at the adversary, and distortion at the legitimate receiver. It is demonstrated that causal side information at the adversary plays a pivotal role in this tradeoff. It is also shown that measures of secrecy based on normalized equivocation are a special case of the framework.

IEEE Transactions on Information Theory•Oct 31, 2014•89 citations

Secrecy is cheap if the adversary must reconstruct

Curt M. Schieler, Paul Cuff

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.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2012•22 citations
This work addresses secrecy with distributed systems in mind. We consider an adversary who wishes to attack a system and find the optimal communication and use of secret key to share information in such a system. Instead of measuring secrecy by “equivocation,” we define a value function for the system, based on the actions of the system and the adversary, and set out to design a system that maximizes the average value obtained against the worst adversary.
In this work, secrecy in communication systems is measured by the distortion incurred by the worst-case adversary. The transmitter and receiver share secret key, which they use to encrypt communication and cause distortion at an adversary. In our model, we assume that an adversary not only intercepts the communication between the transmitter and receiver, but also may have access to noisy observations of the system. For example, the adversary may have causal access to a signal that is correlated with the source sequence or with the output of the receiver. Our main contribution is the solution of the optimal tradeoff among communication rate, secret key rate, distortion at the adversary, and distortion at the legitimate receiver. We demonstrate that side information at the adversary plays a pivotal role, and provide a number of examples that motivate and give insight into our results.
Secure communication between a sender and a receiver generally requires the message to be encrypted, with the sender and recipient sharing a secret key that encodes and deciphers the message. Ideally, the key should be changed often, and so for practical reasons the key should be distributable over normal communication channels. However, the possibility of the interception of the key by an eavesdropper would compromise security. There is, therefore, a need for a method to distribute the key to the recipient securely so that any attack on the communication channel by a potential eavesdropper can be detected and appropriate action taken.
We consider theoretical limits of partial secrecy in a setting where an eavesdropper attempts to causally reconstruct an information sequence with low distortion based on an intercepted transmission and the past of the sequence. The transmitter and receiver have limited secret key at their disposal but not enough to establish perfect secrecy with a one-time pad. From another viewpoint, the eavesdropper is acting as an adversary, competing in a zero-sum repeated game against the sender and receiver of the secrecy system. In this case, the information sequence represents a sequence of actions, and the distortion function captures the payoff of the game. We give an information theoretic region expressing the tradeoff between secret key rate and max-min distortion for the eavesdropper. We also simplify this characterization to a linear program. As an example, we discuss how to optimally use secret key to hide Bernoulli-p bits from an eavesdropper so that they incur maximal Hamming distortion.
We consider a cascade network where a sequence of nodes each send a message to their downstream neighbor to enable coordination, the first node having access to an information signal. An adversary also receives all of the communication as well as additional side-information. The performance of the system is measured by a payoff function evaluated on actions produced at each of the nodes, including the adversary. The challenge is to effectively use a secret key to infuse some level of privacy into the encoding, in order thwart the adversary's attempt to reduce the payoff. We obtain information-theoretic inner and outer bounds on performance, and give examples where they are tight. From these bounds, we also derive the optimal equivocation for this setting as a special case.
Secrecy in communication systems is measured herein by the distortion that an adversary incurs. The transmitter and receiver share secret key, which they use to encrypt communication and ensure distortion at an adversary. A model is considered in which an adversary not only intercepts the communication from the transmitter to the receiver, but also potentially has side information. In particular, the adversary may have causal or noncausal access to a signal that is correlated with the source sequence or the receiver's reconstruction sequence. The main contribution is the characterization of the optimal tradeoff among communication rate, secret key rate, distortion at the adversary, and distortion at the legitimate receiver. It is demonstrated that causal side information at the adversary plays a pivotal role in this tradeoff. It is also shown that measures of secrecy based on normalized equivocation are a special case of the framework.
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.