# Hybrid argument for repeated but alternating sequence

In the usual hybrid argument, it is shown that if two efficiently samplable distributions, $$X$$ and $$Y$$, are indistinguishable given a single sample, then they remain indistinguishable with any polynomial number of samples (say $$N$$).

This is proved by defining two sequences (For independent RVs): $$X_0, X_1, ..., X_N$$ and $$Y_0, Y_1, ..., Y_N$$, and the $$N$$ hybrids $$H_k = X_0, X_1, ..., X_k, Y_{k+1}, Y_{k+2}, ..., Y_N$$, are all indistinguishable — the usual proof creates these sequences and fills the "middle point" ($$k$$-th index) with the single (unknown) sample that we are given and uses the distinguisher on this created hybrid.

[EDIT: I edited the formulation of the question below to make everything more clear. I thank @Marc Ilunga and @ellipsoid for the feedback.]

My question is as follows: Let $$R \in \{0,1\}^N$$ be any possible $$N$$-bit string. Consider the hybrids $$H_R = (Z_1,Z_2,...,Z_N)$$ (recall $$N$$ is polynomial in some security parameter) where $$Z_i=X$$ if $$R_i=0$$ and $$Z_i=Y$$ if $$R_i=1$$ for all $$i\in [N]$$. There are $$2^N$$ possible hybrids, all of polynomial length $$N$$. From the classical hybrid argument formulation, I know that $$H_{0^N}$$ is indistinguishable from $$H_{1^N}$$ and indistinguishable from $$H_{0^k || 1^{N-k}}$$ for all $$k$$ ($$||$$ is bit-string concatenation). Now I have introduced these new alternating bit sequences where every position can be an $$X$$ or a $$Y$$. Are hybrids $$H_R$$ indistinguishable for all bit strings $$R$$ (i.e., any $$H_R$$ is indistinguishable from all other $$H_{R'}$$)?

• The question isn't currently clear to me. What is the meaning of $H'$? One reading is that this is the initial collection of variables. But then, what are we trying to distinguish it from? Should there be an $H''$ from which we want to apply the hybrid argument? Another reading is that $H'$ is a custom hybrid. But then, what are the other hybrids? If so, there should be distributions for which we use these hybrids in a proof. What are these? Commented May 10 at 11:24
• Hello @Marc Ilunga I updated the question to hopefully make it more clear. Commented May 10 at 11:45
• For me it's still unclear what you mean. Let's formalize it differently: For an $N$-bit string $R\in\{0,1\}^N$ define $H_R:=(Z_1,\dots,Z_N)$ where $Z_i=X$ if $R_i=0$ and $Z_i=Y$ else. You are talking about the process of sampling $R$ uniformly at random and then providing samples from $H_R$ being indistinguishable from what? $H_{R'}$ for some fixed $R'$? Or whether there exist some $R$ and $R'$ such that $H_{R}$ and $H_{R'}$ are indistinguishable? In any case, it will be indistinguishable (intuitively $H_{0^N}$ and $H_{1^N}$ are the "easiest" to distinguish but still indistinguishable) Commented May 10 at 14:07
• Thank you @ellipsoid. I have updated my question with a formulation inspired by your interpretation to make it more clear. Commented May 11 at 1:07

Yes, fixing any $$R$$ and $$R'$$ the resulting distributions $$H_R$$ and $$H_{R'}$$ are indistinguishable. You can see (and prove) this similar to the "original" hybrid argument. Beginning with $$H_R$$ as $$H_0$$ replace/flip from left to right the random variables which are different from $$H_R'$$. More formally you can define $$\Delta=R\oplus R'$$ and at the 1st position $$i$$ of $$\Delta$$ which equals $$1$$ you replace Y by X or X by Y to get $$H_1$$. Proceed until the last (k-th) occurrence which leads to $$H_k=H_{R'}$$. A chain of hybrids where $$H_i$$ and $$H_{i+1}$$ are indistinguishable.