Consider a situation in which one part Alice wants to communicate with another part Bob over a discrete memoryless channel with crossover probability 
while ensuring a low level of detection in the presence of a warden Willie, who observes the communication through another discrete memoryless channel with crossover probability 
. We assume that all parts are equally computationally bounded.
In this situation, we require that 
for non-zero 
. Let 
be a sequence of secret bits she wants to transmit.
NOTE: Alice and Bob may on forehand agree upon any strategy they desire, but the strategy is known also to Willie.
Communicating with a secret key
If Alice and Bob share a secret key 
, they may use it to pick a common encoding, i.e., an error-correcting code. This encoding in turn is used to encode the message, which of course must be able to correct the errors produced by the channel. Assuming that the correction capability is below the error rate of Willie’s channel, he cannot decode. Let 
bits be the length of the publicly transmitted sequence. An established result states that if 
bits are shared between Alice and Bob, they can transmit 
secret bits without Willie seeing them (with high probability).
Communicating without a secret key
Now, assume that Alice and Bob do not share a common key. Alice performs the following steps:
- Picks a cryptographically secure random vector
.
- Computes the scalar product
.
- Sends the bits
over the channel.
This reduces to the problem of 
(LPN) and can be solved with the BKW algorithm (or similar) if is sufficiently low. In particular, if Bob receives
such sequences, or equivalently,
bits, he will be able to decode with high probability. Here we have exploited the piling-up lemma disregrading the fact that some bits in 
are zero and does not contribute. For some probabilities 
and natural number , the information is hidden from Willie. The information rate is determined as follows: 
, so
.
This bound can be improved upon by an increase in the number of parities.
Here is a more detailed paper on a similar topic. Another paper is here.
Like this:
Like Loading...
