Companion to “Provably Secure Steganography”

Nicholas J. Hopper, John Langford, and Luis von Ahn

Carnegie Mellon University

                                   {hopper,jcl,biglou}@cs.cmu.edu

Abstract. We point out and correct a flaw in our paper “Provably Secure Steganography”, which appeared in the proceedings of CRYPTO 2002. The claims of the paper remain correct, but small changes need to be made in one of our protocols.

1 Introduction

Lea Kissner, Tal Malkin and Omer Reingold have pointed out a small flaw in our paper “Provably Secure Steganography”. The flaw has to do with Construction 1 in Section 3.1. In this construction, RS samples the channel oracle |K| times. As Kissner, Malkin and Reingold point out, this construction, as stated, is insecure. Luckily, the construction remains secure if RS samples from the oracle only twice. Hence, the construction should be changed to the following:

Construction 1 (Steganographic Secrecy)

Procedure S1.Encode:

Input: key K, hiddentext m′, history h Let m = Enc(m′) Parse m as m_{1}^{1}||m_{2}^{1}|| ⋯ ||m_{l}^{1} for i = 1 … l do

c_{i} ← RS^{M(h),F_{K}(N,·)}(m_{i}, 2)

set h = h||c_{i} increment N Output: c_{1}||c_{2}|| … ||c_{l} Procedure S1.Decode: Input: key K, Stegotext c Parse c as c_{1}^{b}||c_{2}^{b}|| … ||c_{l}^{b} for i = 1 … l do

set m_{i} = F_{K}(N, c_{i}) increment N let m = m_{1}||m_{2}|| ⋯ ||m_{l} Output: Dec(m)

The following section (in conjunction with our paper) should prove the correctness of this construction.

2 Correctness

Notation

Assume the channel has symbols {S_{1}, ..., S_{k}} with probabilities p_{1}, ..., p_{k}. Assume f is a random function from {S_{1}, ..., S_{k}} to {0, 1}. Consider the following experiment:

Draw from the channel to get a symbol S. If f(S) = 0 output S. Otherwise draw again from the channel and output the result.

Denote the outcome of this experiment by S_{E}.

Let D be the event that after drawing twice from the channel you get a different symbol (a non-collision). Let \overline{D} denote the event that after drawing twice from the channel you get the same symbol.

Lemmas

We need to show that drawing from the channel with replacement twice doesn’t change the distribution. In other words:

Lemma 1.

Pr_{f,C}[S_{E} = S_{i}] = p_{i}

Proof.

Pr_{f,C}[S_{E} = S_{i}] = p_{i}/2 + \frac{p_{i}}{4} ∑_{j≠i} p_{j} + \frac{p_{i}}{4} ∑_{j≠i} p_{j} + p_{i}^{2}/2

= p_{i}/2 + p_{i}(1 − p_{i})/2 + p_{i}^{2}/2
= p_{i}

The first line is true because the probability of getting symbol S_{i} is the sum of the probabilities of the following disjoint events:

– The first draw from the channel results in S_{i} and f(S_{i}) = 0.

– The first draw from the channel is S_{j} for i ≠ j and f(S_{j}) = 1 and the second draw from the channel is S_{i} and f(S_{i}) = 0.

– The first draw from the channel is S_{j} for i ≠ j and f(S_{j}) = 1 and the second draw from the channel is S_{i} and f(S_{i}) = 1.

– The first draw from the channel is S_{i} and f(S_{i}) = 1 and the second draw from the channel is S_{i}.

Next we need to show that drawing twice from the channel results in a symbol that maps to the correct bit with a probability bounded away from 1/2:

Lemma 2.

Pr_{f,C}[f(S_{E}) = 0] > 5/8

Proof. First, note that:

Pr_{f,C}[f(S_{E}) = 0] = \frac{1}{2} + \frac{1}{4} Pr_{f,C}[D]

The right side is the sum of the probabilities of the following disjoint events:

– The first draw results in a symbol that maps to zero.

– The first draw results in a symbol that maps to 1 and the second draw results in a different symbol that maps to 0.

Let S_{i} be a symbol with highest probability (p_{i} ≥ p_{j} for all j), then

Pr_{f,C}[\overline{D}] = p_{1}^{2} + ... + p_{k}^{2} ≤ p_{i}(p_{1} + ... + p_{k})

So Pr_{f,C}[D] ≥ (1 − p_{i}), and we have that

Pr_{f,C}[f(S_{E}) = 0] ≥ \frac{1}{2} + \frac{1}{4}(1 − p_{i})
> \frac{1}{2} + \frac{1}{8}

(since we are assuming that H_{∞}(C) > 1).

Acknowledgments We are greatful to Lea Kissner, Tal Malkin and Omer Reingold for pointing out the flaw in our paper.

References

1. Nicholas J. Hopper, John Langford and Luis von Ahn. Provably Secure Steganography. In Proceedings of CRYPTO