# How to rigorously prove that $Enc_{\Pi'(k)}(M) = Enc_{\Pi(k)}(M) || LSB(k)$ is CPA secure assuming $\Pi$ is?

Assume $\Pi$ is a CPA secure scheme. Let $\Pi'$ be a derived scheme, such that the encryption of a message $M$ is as follows:

$Enc_{\Pi'(k)}(M) = Enc_{\Pi(k)}(M) || LSB(k)$, where

$LSB(k)$ is the least significant bit of the randomly chosen key.

Can someone help me to finish my proof that the $\Pi'$ scheme is also CPA secure?

My proof:

Assume the contrary, $\Pi'$ is not CPA secure. Then the adversary can find two messages $M_0$ and $M_1$, such that whenever a challenger returns him $C'_b = Enc_{\Pi'(k)}(M_b)$, he can guess correctly the randomly chosen bit $b$ with the probability higher than $\frac{1}{2} + 2\epsilon_{fixed}$.

Now the adversary wants to win a game for $\Pi$ against me. He sends me those two messages $M_0$ and $M_1$. He asks me to randomly pick a bit b and return $C_b = Enc_{\Pi(k)}(M_b)$. The adversary then guesses the LSB(k):

• With probability $\frac{1}{2}$ he will have guessed the LSB(k) correctly. Thus, he knows the value of $C'_b$ and can guess the bit $b$ with probability higher than $\frac{1}{2} + 2\epsilon_{fixed}$

• With probability $\frac{1}{2}$ he will have guessed the LSB(k) incorrectly. In this case, he will guess the bit b with probability 1/2. // Why?

Hence, the adversary can guess the bit b correctly with probability $p > \frac{1}{2}(\frac{1}{2} + 2\epsilon_{fixed}) + \frac{1}{2}(\frac{1}{2}) = \frac{1}{2} + \epsilon_{fixed}$. This contradicts the assumption that $\Pi$ is CPA secure.

$\square$

The part I struggle to prove is why when the adversary has guessed the wrong $LSB(k)$ bit, he can still guess the correct $b$ with probablity $\frac{1}{2}$. For example, suppose the adversary runs an algorithm $\alpha$ to guess a bit $b$ when being challenged to win a game for $\Pi'$:

• If we return him $C$ that equals $Enc_{\Pi'(k)}(M_b)$, then $\alpha$ guesses correct $b$ with probability 0.6

• If we return him $C$ that differs from $Enc_{\Pi'(k)}(M_b)$ in the last bit, then $\alpha$ guesses correct $b$ with probability 0.

So now the adversary with the $\alpha$ algorithm would win the CPA game for $\Pi'$, because the game rules force us to send the correct ciphertext $C$. However, $\alpha$ used in the way described in the proof will not win the CPA game for $\Pi$ because $\frac{1}{2} 0.6 + \frac{1}{2} 0 < \frac{1}{2}$

So what I want to ask is why we can always find a better algorithm than $\alpha$?

• Do you mean the key generation algorithm chooses a random key and them all calls to encryption function use that key, right? Because if the encryption key is chosen at random at each encryption in the scheme $\Pi'$, there is no way to decrypt the message. – Hilder Vítor Lima Pereira May 31 '17 at 11:53
• You conclude that the adversary can guess the bit $b$, but which bit is it? It should be the bit returned by the challenger of the original $\Pi$ so that you could say that you were "breaking" $\Pi$. But in your proof, the adversary is just guessing a bit that you chose. – Hilder Vítor Lima Pereira May 31 '17 at 12:04
• @Vitor, yes, all calls to encryption function use that randomly chosen key. – mercury0114 May 31 '17 at 12:35
• @Vitor, but I am a challenger - so the bit I choose is the bit the challenger returns. – mercury0114 May 31 '17 at 12:37
• @mercury0114 If you are only the challenger for $\Pi'$, how can this be a contradition for the security game of $\Pi$? – tylo May 31 '17 at 12:53

For your question: In this case, he will guess the bit b with probability 1/2. // Why?, I guess this is the point of your proof which is making you doubt it?

This is simply the probability to guess correctly the value of $b$ when you are doing it completely at random: the bit $b$ can only take two values, $0$ and $1$, so if you try a "wild guess" you have probability $\frac{1}{2}$ to get the correct answer, that's it.

So you are correct, you have probability $\frac{1}{2}$ to have an advantage and probability $\frac{1}{2}$ to not have any advantage, which in the end translates in an advantage thanks to the law of total probability, as you described.

Now for your edited question: you say that then α guesses correct b with probability 0 but if this is the case, then the algorithm outputing $\neg\alpha$ would have probability $1-\frac{1}{2}0.6+\frac{1}{2}0 = \frac{1}{2}0.4+\frac{1}{2}1 >\frac{1}{2}$ to find the correct value.
Thus, in practice, the "best" algorithm to win the CPA game will not have probability $0$ to output the correct $b$, since otherwise we could construct a better algorithm (excepted if it had proba 1 to find the correct value in the "equals" case).

Now I prefer personally, like tylo, to look at the advantage of the adversary, when dealing with something which is assumed not IND-CPA.

Here I would show that any efficient IND-CPA adversary $\mathcal{A}_{LSB}$ in the LSB case with an advantage of $\epsilon$ can be translated into an IND-CPA adversary $\mathcal{A}$ with polynomially similar efficiency and an advantage of $\frac{\epsilon}{2}$ in the non-LSB case.

This is exactly the same idea as behind Tylo's answer excepted that I formulate it a bit differently:

1. $\mathcal{A}$ poses as a LSB-Challenger, so $\mathcal{A}_{LSB}$ can send him two message $(m_0,m_1)$, as if it were the LSB-Challenger;
2. $\mathcal{A}$ would then send them to the normal Challenger;
3. The Challenger sends back the value $\mathcal{C}=Enc_{\Pi(k)}(m_b)$ to $\mathcal{A}$;
4. $\mathcal{A}$ now flip a coin and get a value $b'$;
5. $\mathcal{A}$ can now pass the value $\mathcal{C}|b'$ as if it were the answer of the LSB-challenger to $\mathcal{A}_{LSB}$;
6. $\mathcal{A}$ returns the same answer as $\mathcal{A}_{LSB}$.

So, $\mathcal{A}_{LSB}$ would have advantage $\epsilon$ to win the game if $b'=LSB(k)$ and would have no specific advantage if $b'\neq LSB(k)$, we have:

\begin{aligned} Adv(\mathcal{A}) =& |P(\mathcal{A}_{LSB} \text{ wins})- P(\mathcal{A}_{LSB} \text{ looses})| \\\geq& P(\mathcal{A}_{LSB} \text{ wins})- P(\mathcal{A}_{LSB} \text{ looses}) \\ =& P(\mathcal{A}_{LSB} \text{ wins} | b'=LSB(k))P[b'=LSB(k)] \\ -& P(\mathcal{A}_{LSB} \text{ looses} | b'=LSB(k))P[b'=LSB(k)] \\ +& P(\mathcal{A}_{LSB} \text{ wins} | b'\neq LSB(k))P[b'\neq LSB(k)] \\ -& P(\mathcal{A}_{LSB} \text{ looses} | b'\neq LSB(k))P[b'\neq LSB(k)] \end{aligned}

Coming directly from the law of total probability, too.

But both $b'$ and the key $k$ are chosen uniformly at random from $\{0, 1\}$, so $P(b'\neq LSB(k)) = P(b'= LSB(k)) = \frac{1}{2}$. Now, when the adversary is in the case $b'\neq LSB(k)$ it can at worse try to guess at random, and has proba $\frac{1}{2}$ to both win and loose. This is a valid assumption, since if it were to have the exact inverse probability to win/loose than in the case $b'= LSB(k)$, then we could construct a polynomial adversary trying multiple queries against different $b'$ with fixed $b$ (i.e. our $\mathcal{A}$ would forward $(m_b,m_b)$ for $b$ a bit of its choosing) and determining which $b'$ has the most often correct answers, thus our adversary would have an advantage bigger than $\frac{1}{2}$.

Finally we know that $$|P(\mathcal{A}_{LSB} \text{ wins} | b'=LSB(k))P[b'=LSB(k)] \\ - P(\mathcal{A}_{LSB} \text{ looses} | b'=LSB(k))P[b'=LSB(k)]| = \epsilon$$ by assumption, so we end up with:

$Adv(\mathcal{A}) \geq \epsilon\frac{1}{2} + 0\frac{1}{2} = \frac{\epsilon}{2}$

So if there exists such an adversary for the second scheme, the first scheme would also be broken.

• The comment to output NOT(b) clears out the confusion, thanks :-) – mercury0114 May 31 '17 at 15:37
• Hey Lery! So, how to show that $Adv(\mathcal{A}_{LSB} | b'\neq LSB(k))$ is zero? – Hilder Vítor Lima Pereira May 31 '17 at 16:45
• Well, I should correct my answer : the advantage, by definition is at least 0, so you'll end up with an advantage at least as if it were 0. But it is true that I should see to better define the advantage knowing X. – Lery May 31 '17 at 17:12
• You can't add advantages like this though, when each is the absolute value of the adversary's deviation from $\frac{1}{2}$. You can add the probabilities, but you then run into the problem that the probability of success (minus 1/2) when $b\neq LSB(k)$ negates the probability of success when $b=LSB(k)$ (minus 1/2), so the advantage is removed. Remember that you don't know $LSB(k)$ and can't determine which case you're in. – Andrew Poelstra Jun 1 '17 at 14:18
• Nice edit. Now in the formula $P(\mathcal{A}_{LSB} \text{ wins }|\dots) - P(\mathcal{A}_{LSB} \text{ looses }|\dots) = \epsilon$ you should use its absolute value for the lefthand side. Also you could note that you used the triangle inequality in the part above. – tylo Jun 6 '17 at 15:06

We want to prove that

$\Pi$ is CPA secure $\Rightarrow$ $\Pi'$ is CPA secure.

So, let's prove it using the equivalent contrapositive proposition:

$\Pi'$ isn't CPA secure $\Rightarrow$ $\Pi$ isn't CPA secure.

So, it means we have to suppose that there is an adversary $\mathcal{A'}$ that can win the CPA-game of $\Pi'$ with non negligible probability and then construct some adversary $\mathcal{A}$ to break the CPA security of $\Pi$, in other words, $\mathcal{A}$ must win the CPA game of $\Pi$. (This is the point you seem to be missing, since you are not interacting with $\Pi$ at all).

So, we construct $\mathcal{A}$ as follows:

1. $\mathcal{A}$ receives $m_0$ and $m_1$ from $\mathcal{A'}$.
2. $\mathcal{A}$ sends both messages to the encryption oracle of $\Pi$.
3. $\mathcal{A}$ receives a ciphertext $c_b = Enc_{\Pi(k)}(M)$.
4. $\mathcal{A}$ chose a random bit $b_k$ and send $c_b||b_k$ to $\mathcal{A'}$.
5. $\mathcal{A}$ receives a guess $b'$ from $\mathcal{A'}$.
6. $\mathcal{A}$ outputs $b'$.

Now, what is the chance that $\mathcal{A}$ wins CPA game against $\Pi$? It is $Pr[b' = b]$, that is equal to

(i) $Pr[b' = b | b_k = LSB(K)] \cdot Pr[b_k = LSB(K)]$

plus

(ii) $Pr[b' = b | b_k \not =LSB(K)] \cdot Pr[b_k \not = LSB(K)]$

But $Pr[b' = b | b_k = LSB(K)] \ge \frac{1}{2} + \alpha$ for some non-negligible function $\alpha$ (because $\mathcal{A'}$ can breaks $\Pi$). Therefore, (i) is greater than or equal to $(\frac{1}{2} + \alpha)\frac{1}{2}$.

And if $\mathcal{A}$ didn't guess the least significant bit of $K$ correctly, we don't know how $\mathcal{A'}$ would proceed, so, let's say that $Pr[b' = b | b_k \not =LSB(K)]$ is $\frac{1}{2} + \beta$ some function $\beta$, then, we have that (ii) is equal to $( \frac{1}{2} + \beta ) \frac{1}{2}$.

Therefore,

(i) + (ii) $\ge \frac{1}{4} + \frac{\alpha}{2} + \frac{1}{4} + \frac{\beta}{2} = \frac{1}{2} + \frac{\alpha}{2} + \frac{\beta}{2}$.

If $\beta$ is negligible, then $\alpha \ge \beta$ and then (i) + (ii) $\ge \frac{1}{2} + \frac{\alpha}{2} + \frac{\alpha}{2} = \frac{1}{2} + \alpha$.

If $\beta$ is non-negligible, then take $\gamma$ to be the minimun between $\alpha$ and $\beta$. That way, we get (i) + (ii) $\ge \frac{1}{2} + \frac{\gamma}{2} + \frac{\gamma}{2} = \frac{1}{2} + \gamma$.

In both cases, $\mathcal{A}$ can guess the bit $b$ output by the oracle to $\Pi$ with non-negligible probability, i.e., $\mathcal{A}$ breaks the CPA security of $\Pi$.

• What exactly is the extra information in this answer over the one I wrote earlier and the one written by Lery (with a slightly different point of view), except some equavalence transformations of equations based on a formula given in the question already? – tylo May 31 '17 at 19:22
• @tylo I think I was written my answer at the same time that Lery was writing him/her, because I just saw him/her answer when I posted mine. And about the difference between this and yours, well, I was not going to post it because I though yours was ok (this is why I first commented in the question), but he seemed to be still confused, so I decided to give a explicit proof, working with the probabilities and negligible and non-negligible functions. – Hilder Vítor Lima Pereira May 31 '17 at 20:33
• Why is $\beta$ assumed to be nonnegative here? – Andrew Poelstra Jun 1 '17 at 14:10
• Hi @AndrewPoelstra at the moment I wrote this answer, I thought it should be non negative because the chance of guessing a random bit is at least $\frac{1}{2}$. But now I am somehow puzzled because it doesn't seem natural anymore. Do you have any argument against or for this? Please, share it with me. – Hilder Vítor Lima Pereira Jun 1 '17 at 20:28
• @Vitor Consider an analogous "proof" where you append a bit $b'$ to the ciphertext rather than $LSB(k)$. I write an adversary that just reads $b'$ and guesses this as the bit $b$. The above logic would let you write "if $b' = b$, the adversary has advantage 1/2, and if $b'\neq b$ the adversary has advantage 0, so the total advantage is 1/4". But this is clearly untrue, the adversary in this example is basically guessing at random and we know its true advantage is 0. – Andrew Poelstra Jun 1 '17 at 22:04

In your proof it's not clear (and I can only guess there is an error) which messages you send:

• You can't produce the value $Enc_{\Pi(k)}(M_b)$ yourself

Your argument is flawed in the sense that you want the original adversary to win the other game and calculate that probability. That doesn't work, because the adversary expects a challenge of the form $Enc_{\Pi(k)}(M_b)||LSB(k)$ and not $Enc_{\Pi(k)}(M_b)$ - and you don't know if there is a different $k'$, s.t. $Enc_{\Pi(k)}(M_b) = Enc_{\Pi(k')}(M_b)||LSB(k')$.

Here's the idea with adversary $\mathcal{A}$ for $\Pi'$ and the challenger $\mathcal{C}$ for $\Pi$ - we act as adversary for $\Pi$ and as challenger for $\Pi'$:

• $\mathcal{A}$ chooses $m_1,m_2$ and sends them to you. We relay those to $\mathcal{C}$.
• We get a challenge of the form $Enc_{\Pi(k)}(M_b)$. We choose a single bit $b'$ randomly, and send $Enc_{\Pi(k)}(M_b)||b'$ to $\mathcal{A}$.
• $\mathcal{A}$ guesses $b$, and we just relay that guess to $\mathcal{C}$.

With probability $1/2$ we guesses $b'$ correctly, s.t. $b' = LSB(k)$. In the other case, the adversary can't do worse than having no advantage. Then we can actually use the formula at the bottom of the question to calculate our advantage - based on the advantage of $\mathcal{A}$.

• I disagree, in his proof, he is the challenger and so he can produce the value $Enc_{\Pi(k)}(M_b)$. He has a valid reductio ad absurdum, in my opinion, while your method is tampering with the way the oracle behaves, which is not the way to go to solve the CPA game. – Lery May 31 '17 at 11:46
• @Lery I disagree. In his proof there are assumptions about the adversary and his behavior, e.g. "The adversary then guesses the LSB(k):". So the the result in the contrapositive isn't for all poly time adversaries ... but instead for all poly time adversaries, who calculate $LSB(k)$ in this specific way ....My proposed way is to act as the adversary for $\Pi$ and as challenger for $\Pi'$ - which is quite standard for various cryptographic primitives, e.g. for constructions of PRFs based on some other PRF. Just in this case, we adapt it to the CPA game. – tylo May 31 '17 at 12:27
• "We choose a single bit $b'$ randomly, and send $Enc_{\Pi(k)}(M_b)||b'$ to A. But in this case, if $b'$ does not equal the $LSB(k)$, we're sending a wrong encryption of a message $M_b$, aren't we? – mercury0114 May 31 '17 at 12:50
• @tylo, I think your proof is close to what I am looking for. However, the part which I want to be explained is why when the adversary is given a wrong ciphertext, he can do no worse than having no advantage? Why can't it be that the algorithm the adversary uses is constructed in such a way that whenever you give a correct ciphertext $C_b$ he will extract the bit $b$ with probability 1, however, if you give him a wrong ciphertext, he will extract the bit $b$ with probability 0? – mercury0114 May 31 '17 at 13:04
• @mercury0114 When the adversary is given the wrong ciphertext, we don't know what he does and can in no way predict the result. But we do know that he sends an answer. A worst case assumption is that he has advantage $0$ in this case - the advantage is defined as absolute value, which can't be below $0$. If you want to go into further details, absolute values obey the triangle inequality. Alternatively we can say that he answers with a random bit (exactly uniform) - which is a correct guess exactly $1/2$ the time. – tylo May 31 '17 at 13:14

You wrote

If we return him $C$ that differs from $Enc_{\Pi'(k)}(M_b)$ in the last bit, then $\alpha$ guesses correct $b$ with probability $0$.

I suspect, there is a misconception in the understanding of the advantage. If an algorithm is able to always output the wrong result, then this has exactly the same advantage as an alorithm, which always outputs the correct result. The advantage is not equal to the probability of outputting the correct result (or winning the game). It is a measure about actually finding some hidden information which tips the scales. If an algorithm can reliably find $\bar{b}$, then it's really trivial to adapt this algorithm to find $b$ instead (just invert the output) and vice versa.

It is also really simple to generate a trivial adversary for any algorithm with the lowest possible advantage:

• You know by the definition of the securitay game, some bit $b$ is drawn from a uniform distribution
• The adversary $\mathcal{A}$ ignores any input he gets
• The adversary $\mathcal{A}$ outputs a bit from a fixed distribution (regardless which one). If the adversary always outputs $0,1$ or a randomly drawn bit - it doesn't matter.
• The advantage of this adversary is always $0$: If $b$ is dawn uniformly and $b'$ from any distribution, then $b=b'$ happens with probability $1/2$. The proof is equal to perfect secrecy of OTP.

So when we assume some algorithm $A$ with a non-negligible advantage and generate some algorithm $B$ using $A$ and the advantage is some polynomial of the advantage of $A$, then $B$ also has non-negligible advantage. This is easily explained/ proven by the fact that polynomials are closed under composition (and in most proofs it's even a linear in the original advantage). Formally this can be said as:

• Polynomial functions are not negligible (easy to prove with the definition of negligible functions) - keep in mind, the definition of negligible already includes taking the absolute value, so it doesn't matter if the range is positive or negative. But if you want to be precise, you need to exclude the polynomial $f(x) = 0$
• Polynomials are closed under function composition (if $f(x)$ is a polynomial of degree $k$, g(x) is a polynomial of degree $l$, then $f(g(x))$ is a polynomial of degree $kl$)
• Thus we can state: If some advantage/function $f(x)$ is non-negligible, then for any polynomial g(x) we have that $g(f(x))$ is also non-negligible. In this case $x$ would be the security parameter obviously (you can also use $\lambda$ instead).

This is a very interesting question. I think the answers here reflect the intuition that in real life, if revealing a bit of the secret key were to break an encryption scheme, that encryption scheme would necessarily exhibit a visible bias that revealed that bit, and thereby be unconditionally broken. So if the original scheme is secure, the scheme with a revealed bit must be.

However, the IND-CPA game does not directly allow detection of key biases like this because there is only one key for the entire game, and only one challenge. So the solutions which take a single adversary $\mathcal{A}'$ and feed them a random bit as "LSB(k)" run the risk that they are hurting $\mathcal{A}'$ by getting the bit wrong just as much as they'd help it by getting the bit right -- and since they are in one of these two cases with 50% probability, they can't then infer anything about $\mathcal{A}'s$ behaviour!

(By the way, it is not stated whether we are working with asymmetric or symmetric encryption. I assume the symmetric case because it's hard to define revealing one bit of the key like this in the asymmetric case. The difference is simply that the symmetric case allows $\mathcal{A}'$ to make encryption queries.)

With all this said, here is my solution. We have a probabilistic polynomial time (p.p.t.) adversary $\mathcal{A}'$ which can break $\Pi'$ and we produce a p.p.t. simulator $\mathcal{A}$ which can break $\Pi$ using it. $\mathcal{A}$ works as follows, and can break $\Pi$ with the same probability $\epsilon$ as $\mathcal{A}'$ can break $\Pi'$.

1. Immediately $\mathcal{A}$ forks $\mathcal{A}'$ into $2n$ copies $\mathcal{A}'_n$, where $n$ is some positive integer.

2. For all $i$, $\mathcal{A}$ responds to encryption queries from $\mathcal{A}'_i$ by forwarding them to its IND-CPA challenger. For even $i$ it appends a zero bit to the response and for odd $i$ it appends a one bit, and forwards it to $\mathcal{A}'_i$.

3. For $i>2$, when $\mathcal{A}'_i$ makes a challenge query $(m_0, m_1)$, $\mathcal{A}$ flips a random bit $b$, queries its IND-CPA challenger for an encryption of $m_b$, appends the appropriate bit to the response according to the parity of $i$, and gives this to $\mathcal{A}'_i$. Then $\mathcal{A}'_i$ replies with a guess for $b$ and $\mathcal{A}$ notes whether this is correct.

4. For $i\in\{1,2\}$, if $\mathcal{A}'_i$ gives a challenge query $(m_0, m_1)$, $\mathcal{A}$ responds as follows.

• $\mathcal{A}$ waits first for all $\mathcal{A}_i'$, $i>2$, to make their challenge queries, and replies as in step (3).
• If the odd $\mathcal{A}_i$'s were correct with higher frequency than the evens, it sets $k' = 1$. Otherwise it sets $k' = 0$. If the odds and evens were tied it chooses $k'$ randomly.
• If $i = k'$ it responds by forwarding the challenge to the IND-CPA challenger, appending $k'$ to the reply, and forwarding this to $\mathcal{A}'_i$. It forwards the reply bit to the IND-CPA challenger.
• Otherwise it aborts $\mathcal{A}'_i$ and waits for the other one to make a challenge.

The intuition here is that we're first doing a majority-rules of the adversaries to which we're claiming $LSB(k) = 0$ and those to which we're claiming $LSB(k) = 1$, then using the winning bit for our "real" challenge.

The reason this scheme works is simple, though it uses some heavy machinery, and I haven't followed through to get exact numbers.

First, suppose that $\mathcal{A}'$ wins with probability $\frac12+\alpha$ when given the correct bit and probability $\frac12+\beta$ when given the wrong one. By hypothesis, since $\mathcal{A}'$ can break $\Pi'$, one of $\{\alpha,\beta\}$ is non-negligible, and since $\Pi$ is IND-CPA, $\alpha + \beta = negl$ (otherwise you coud break $\Pi$ by just appending a random bit to its ciphertexts and giving the result to $\mathcal{A}'$). We conclude that $\epsilon = \max\{\alpha,\beta\}$ is positive and non-negligible.

By the central limit theorem, for $n$ large enough, can can get the number of wins by the correct parity arbitrarily close (percentage-wise) to $2n(1/2 + \alpha)$ and the number of wins by the incorrect parity arbitrarily close to $2n(1/2 + \beta)$. So the majority winner will, with probability close to 1, be the one with advantage $\epsilon$. The result then follows.

Addendum: We observe critically that $n$ must be at least 1, which by construction means that $\mathcal{A}$ does twice as much work as $\mathcal{A}'$. I initially worried about getting same probability $\epsilon$, because doesn't that imply inductively that you could reveal the whole key without changing the attacker's advantage, leading to a reductio ad absurdum? The answer is no, because the above algorithm applied to a variant $\Pi'$ that exposed $n$ bits would need to do $2^n$ work, and therefore not be probabilistic polynomial time.

• I think you have a few typo, for example the adversary breaking $\Pi'$ is $\mathcal{A}'$ and later it is not $\mathcal{A}_i$, since those are not defined, but $\mathcal{A}_i'$. As for your last part, I don't see why you need the permutation: if the odd $i$ (those with appended 1s) are correct with higher frequency than the evens, you want to forward the query of an odd $i$, don't you? But then $i=k'+1$ will be even. – Lery Jun 7 '17 at 8:19
• Fixed the $k' + 1$ thing, I had done that because the $\mathcal{A}_i'$s were 1-indexed instead of 0-indexed but that just means that $\mathcal{A}_2'$ should get bit 0. I skimmed through my proof and can't find anywhere I said $\mathcal{A}'$ instead of $\mathcal{A}'_i$. Note that in the description of the scheme I am talking about a specific fork while in the analysis I'm talking about the general algorithm. – Andrew Poelstra Jun 7 '17 at 14:35
• Oh, I see , you already fixed my typos :) – Andrew Poelstra Jun 7 '17 at 14:37
• Yes, but I didn't touch the $k'+1$ part. – Lery Jun 7 '17 at 14:55