Detailed analysis of parameter values in BC(BSC)

Adam Smith

June 1997

1 The basics

1.1 Notation

Table 1: Notation used

ϵ BSC error probability
n Length of code
k Dimension of code
d min. distance of code
R Transmission rate (= r/n)
γ Relative bound on dimension of code
λ Criterion for accepting/rejecting Alice’s codeword
h(x) Entropy function (base 2)
C_{ϵ} Capacity of a BS_{ϵ}
δ R = C_{ϵ} + δ
s Privacy Amplification security parameter
r Privacy Amplification final message length
t Number of bits of the syndrome
β PA param: s = n − r − t − nC_{ϵ+β}
p_{h} Probability that honest Alice fails Bob’s test
p_{m} Prob. that random systematic code has d < γϵ
p_{a} Prob. that Alice can cheat
α Average amount of info. Bob is allowed

1.2 Background

Theorem 1 (Bernstein, in Renyi61) If X_{1}, X_{2}, …, X_{n} are independent random variables such that D = \sqrt{∑_{i} V (X_{i})}, E(X_{i}) = 0 and |X_{i}| < K for all i, and if μ ≤ D/K, then

P r [∑_{i} X_{i} ≥ μD] ≤ e^{\frac{−μ^{2}}{2(1+μK/2D)}} .

Corollary 2 Let p ∈ (0, 1/2), let q = 1 − p > 1/2. If X_{1}, X_{2}, …, X_{n} are independent random Bernouilli variables of probability p or q (not necessarily all identical) such that X is their expected sum, and λ < p, then

P r [∑_{i} X_{i} − X ≥ λn] ≤ e^{\frac{−nλ^{2}}{2pq(1+λ/2p)}}

P r [∑_{i} X_{i} − X ≤ −λn] ≤ e^{\frac{−nλ^{2}}{2pq(1+λ/2p)}}

Lemma 3 (MS77) If μ ∈ (0, 1/2) and n ∈ N, then

\frac{2^{nh(μ)}}{\sqrt{8nμ(1 − μ)}} ≤ \binom{n}{μn} ≤ 2^{nh(μ)}

2 Analysis of different error probabilities

2.1 Finding a good code

We need to find a code such that both k and d are high. We don’t need to be able to decode received codewords, only to check if a given word is part of the code and to generate codewords efficiently. For this we will use systematic linear codes, i.e. codes with a generator matrix of the form (I_{k}|Y) where Y is a random k × (n − k) boolean matrix.

Theorem 4 (Based on MS77) Let n, k ∈ N such that k < n and R = k/n. Let S_{0} = {code generated by G = (I_{k}|Y)|Y ∈ M_{k×(n−k)}(F_{2})}. If R < C_{δ} then the probability of choosing a code at random in S_{0} with min. distance smaller or equal than δn is at most 2^{n(R−C_{δ})}.

Proof: For a given n-bit word w, define

N(w) = #{C ∈ S_{0}|w ∈ C}
= #{Y ∈ M_{k×(n−k)}(F_{2})|w_{1,...,k}Y = w_{k+1,...,n}}

where w_{i,...,j} refers to the word formed by bits i through j of w.

Clearly, if w is the null vector, then N(w) = 2^{k(n−k)}. Also, if w_{1,...,k} is null but w_{k+1,...,n} is not, then N(w) = 0. So let us now investigate the case where w_{1,...,k} is non-zero.

For a given matrix Y, each bit w_{k+i} of w_{k+1,...,n} can be seen as a parity check over certain bits of w_{1,...,k}. The exact parity check is determined by the entries in the corresponding column v_{i} of Y. For a given bit of w_{k+i}, how many different (n-k)-bit vectors are possible for v_{i}?

Let us suppose that w_{1,...,k} has j zeros and k − j ones. Then there are j positions in v_{i} which don’t matter at all (they can hence be set in 2^{j} different ways). Also, the total parity of the k − j other bits must equal to w_{k+i}. There are exactly 2^{k−j−1} ways to set k − j bits so they have a given parity. The total number of possiblities for v_{i} is thus 2^{k−1}. Because there are n−k different vectors in Y, there are a total of 2^{(k−1)(n−k)} matrices Y such that w_{1,...,k}Y = w_{k+1,...,n}. Hence, N(w) is constant for all vectors w with at least one 1 in its first k positions and 0 for all other non-zero vectors.

Let us now try to count the number of codes with min. distance smaller than δn. At most, the number of such codes is the sum of N(w) over all non-zero words w of weight less than or equal to δn.

#{C ∈ S_{0}|d(C) ≤ δn} ≤ ∑_{w:0<∥w∥≤δn} N(w)
= 2^{(k−1)(n−k)}#{w|0 < ∥w∥ ≤ δn and w_{1,...,k} ≠ 0}
< 2^{(k−1)(n−k)}#{w|0 < ∥w∥ ≤ δn}
= 2^{(k−1)(n−k)} ∑_{i=1}^{δn} \binom{n}{i}
≤ 2^{(k−1)(n−k)}2^{nh(δ)}
= 2^{k(n−k)+k−n+nh(δ)}
= 2^{k(n−k)+n(R−C_{δ})}

In that there are a total of 2^{k(n−k)} possible matrices of size k × (n − k), the proportion of systematic codes of minimum distance smaller than δn is at most 2^{n(R−C_{δ})}. This implies the theorem. QED.

Hence, we have the bound:

p_{m} < 2^{R−C_{γϵ}}

2.2 Bob’s test: Honest Alice

Bob test is based on the number of differences he expects to see between x, the word Alice claims she sent and x′, the word he received. He accepts iff ∥x ⊕ x′∥ < (ϵ + λ)n.

Because x′ is transmitted over a BS_{ϵ}, the weight of x ⊕ x′ is the sum of n independent Bernouilli trials of probability ϵ. Hence, if Alice is honest, corollary 2 guarantees us that

p_{h} ≤ e^{−n \frac{λ^{2}}{2ϵ(1−ϵ)(1+λ/2ϵ)}}

as long as λ < ϵ.

2.3 Bob’s test: Cheating Alice

What if Alice tries to change her mind, i.e. tries to pass some fraudulent word off as the word she really sent? What are her chances of passing Bob’s test with two different codewords?

Let x be the word Alice originally sent (not necessarily a codeword). We want to bound Alice’s chances of being able to pass off two different codewords. Let y be the farther (from x) of the two codewords Alice would like to pass off as her own.

Let z = ∥y ⊕ x∥. Consider the random variables Y_{i} (for i = 1, …, n) and D_{y} defined as follows:

Y_{i} = \{ \begin{matrix}1 & if x′ and y differ in position i \\ 0 & otherwise \end{matrix}
D_{y} = ∥y ⊕ x′∥ = ∑_{i} Y_{i}

We can partition the Y_{i}’s into to two sets, S_{1} and S_{2} where S_{1} contains the Y_{i}’s for which x and y differ in position i (#S_{1} = z) and S_{2} contains the n − z others. S_{1} contains variables with expected value 1 − ϵ, while S_{2} contains variables with expected value ϵ. Thus,

E(D_{y}) = ϵ(n − z) + z(1 − ϵ) = ϵn + z(1 − 2ϵ).

We assume here that the code Bob chose was good, i.e. d ≥ γϵ. No matter what word x Alice really sends, she cannot find two codewords both of which are at distance less than γϵ/2 from x. In that we chose y to be the farther of the two codewords Alice would like to be able to unveil, we know that z ≥ γϵ/2. Hence,

E(D_{y}) ≥ ϵn + γϵ(1/2 − ϵ)

Because all of the Y_{i}’s are Bernouilli variables with probability ϵ or 1 − ϵ, we can apply corollary 2:

P r [D_{y} − E(D_{y}) ≤ −λ_{0}n] ≤ e^{−n \frac{λ^{2}_{0}}{2ϵ(1−ϵ)(1+λ_{0}/2ϵ)}}

In our situation, λ_{0} = E(D_{y})−ϵn+λ, where λ is from Bob’s test. Because we cannot be guaranteed that E(D_{y}) will be significantly larger than ϵn+γϵ(1/2− ϵ), we may as well assume that it isn’t. Hence,

p_{a} ≤ e^{−n \frac{λ^{2}_{0}}{2ϵ(1−ϵ)(1+λ_{0}/2ϵ)}}

where λ_{0} = γϵ(1/2 − ϵ) − λ.

2.4 Optimal value for λ

Clearly, as long as 0 < λ < γϵ(1/2 − ϵ), both p_{a} and p_{h} will be exponentially small in n. The question is, for fixed γ and ϵ, what is the best value for λ?

What we are trying to maximize is the probability that an honest Alice will pass the test and that a cheating Alice will be unable to unveil x as two different codewords. Hence, we want λ such that p_{h,a} = (1 − p_{h})(1 − p_{a}) is minimal.

We notice that p_{h}(λ) and p_{a}(λ_{0}) are identical functions which are strictly decreasing when their variable is positive. It is clear that when λ_{0} = γϵ(1/2 − ϵ) − λ, the function p_{h,a}(λ) will have a critical point at λ = γϵ(1/2 − ϵ)/2. We want to show that this is the absolute maximum of the function (in any case, it will be pretty damn close).

2.5 Bob’s information

This discussion is based on Theorem 3 in [BBCM95]:

Theorem 5 (Privacy Amplification) Let W be a random variable over some alphabet W with Renyi entropy R(W). Let G be a random variable distributed uniformly over a universal_{2} class of hash functions W → {0, 1}^{r}. Then

H(G(W)|G) ≥ R(G(W)|G) ≥ r − log_{2}(1 + 2^{r−R(W)})
≥ r − \frac{2^{r−R(W)}}{ln 2}

If X is the random variable representing the string Alice sends Bob through the BSC, we will call BS_{ϵ}(X) the r.v representing the string Bob receives and D_{X} the r.v. representing the Hamming distance between X and BS_{ϵ}(X). We will assume that what information Bob could get is actually of some use to him, that is we assume Alice sent a valid codeword in the first place. In our situation, the W of the previous theorem will be the r.v. X|BS_{ϵ} = v, D_{X} = d, syn(X) = 0.

Given v, w ∈ F_{2}^{n}, consider the number of words of the same syndrome as w which are at the same distance as w from v. Because of the additivity of the syndrome, this is the same as the number of words at distance ∥v ⊕ w∥ from 0 which have syndrome syn(w) ⊕ syn(v). So define N_{d}(S), S ∈ F_{2}^{n−k} to be the number of words of weight d which have syndrome S.

Assume Bob has an oracle which tells him the value of D_{X} = d. He also has BS_{ϵ}(X) = v. How many possibilities does he have for the value of X? There are exactly N_{d}(syn(v)) different words of syndrome 0 at distance d from v (because 0 ⊕ syn(v) = syn(v)). The Renyi entropy of X from his point of view is thus:

R(X|BS_{ϵ}(X) = v, D_{X} = d, syn(X) = 0) = log_{2} N_{d}(syn(v))

Hence, by 5, we can conclude that, for G randomly distributed over a universal_{2} class of hash functions:

H(G(X)|G, BS_{ϵ}(X) = v, D_{X} = d, syn(X) = 0) ≥ r − \frac{2^{r−log_{2} N_{d}(syn(v))}}{ln 2}
= r − \frac{2^{r}}{N_{d}(syn(v)) ln 2}

From this, we can calculate:

H(G(X)|G, BS_{ϵ}(X), D_{X} = d, syn(X) = 0) = \frac{1}{\binom{n}{d}} ∑_{v:∥v∥=d} H(G(X)|G, BS_{ϵ}(X) = v, D_{X} = d, syn(X) = 0)

≥ \frac{1}{\binom{n}{d}} ∑_{v:∥v∥=d} r − \frac{2^{r}}{N_{d}(syn(v)) ln 2}

= \frac{1}{\binom{n}{d}} ∑_{Y ∈\{0,1\}^{n−k}} N_{d}(Y) (r − \frac{2^{r}}{N_{d}(Y) ln 2})

= r − \frac{1}{\binom{n}{d}} ∑_{Y ∈\{0,1\}^{n−k}} N_{d}(Y)\frac{2^{r}}{N_{d}(Y) ln 2}

= r − \frac{2^{r+n−k}}{\binom{n}{d} ln 2}

By 2, we know (ϵ−β)n ≤ D_{X} ≤ (ϵ+β)n with probability at least 1−2e^{−nβ^{2}}. By 3, this implies \binom{n}{D_{X}} ≥ \frac{2^{nh(ϵ−β)}}{\sqrt{2n}}. Averaging over D_{X}, we get:

H(G(X)|G, BS_{ϵ}(X), D_{X}, syn(X) = 0) ≥ (1 − 2e^{−nβ^{2}}) (r − \frac{\sqrt{2n}2^{r+n−k}}{2^{nh(ϵ−β)} ln 2})

= (1 − 2e^{−nβ^{2}}) (r − \frac{\sqrt{2n}2^{r+n[1−R−h(ϵ−β)]}}{ln 2} )

= (1 − 2e^{−nβ^{2}}) (r − \frac{\sqrt{2n}2^{r−n[R−C_{ϵ−β}]}}{ln 2} )

This means that Bob’s real average uncertainty (without the oracle) is even higher than this. Hence, α, Bob’s average information, is bounded above.

We notice that the β used here is a pure mathematical construct used to get around possible extreme values of D_{X}. We are free to choose its value however we wish.

2.6 Picking the hash vector M

Most values of m will give good hash functions i.e. exactly one half of the codewords will hash to 1 and the other half to 0. However, a bad case can arrive (with probability exponentially small in n): m could be a dual codeword. This case could arrise but can be avoided by simply checking if mG^{T} = 0. This is supported by the following little lemma.

Lemma 6 (Good m are very likely) The function f_{m} from a linear code C onto {0, 1} defined by f_{m}(x) = x ⊙ m is balanced over its image. This image is {0} if m is in the dual code D and {0, 1} otherwise.

This is true because f_{m} is always a homomorphism of vector spaces (and hence balanced) and because if m ∉ the dual code, then there is at least one word x in the code such that x ⊙ m = 1.

2.7 Summary of results

Normally, ϵ is fixed, we choose: γ, δ, λ and β, where R = k/n = C_{ϵ} + δ and:

0 < ϵ < 1/2
0 < γ < 1
0 < δ < h(ϵ) − h(ϵγ)
0 < λ < γϵ(1/2 − ϵ)
0 < β < ϵ

We get the following bounds:

p_{h} ≤ e^{−n \frac{λ^{2}}{2ϵ(1−ϵ)(1+λ/2ϵ)}}  (1)
p_{a} ≤ e^{−n \frac{λ^{2}_{0}}{2ϵ(1−ϵ)(1+λ_{0}/2ϵ)}} where λ_{0} = γϵ(1/2 − ϵ) − λ  (2)
p_{m} ≤ 2^{n(h(ϵγ)−h(ϵ)+δ)}  (3)
α ≤ 2e^{−nβ^{2}} + (1 − 2e^{−nβ^{2}}) \frac{\sqrt{2n}2^{1−n[h(ϵ−β)−h(ϵ)+δ]}}{ln 2}  (4)

3 Questions

1. Can we refine the argument to get rid of the multiplicative factor 1 − 2e^{−nβ^{2}}?

2. What is the optimal value of β as a function of the other parameters?

3. Are there values of λ, γ and δ which are optimal? What are they?

4. How stable is the protocol when the value of ϵ is not known exactly? Just how much uncertainty still permits exponential bounds on the error probabilities? Do the optimal values of the parameters change in such a case?