11institutetext:  NISER, HBNI, India<EMAIL_ADDRESS>22institutetext: Indian Statistical Institute, Kolkata, India,
mridul.nandi<EMAIL_ADDRESS>
# Crooked Indifferentiability Revisited

Rishiraj Bhattacharyya 11 Mridul Nandi 22 Anik Raychaudhuri 22

###### Abstract

In CRYPTO 2018, Russell et al introduced the notion of crooked
indifferentiability to analyze the security of a hash function when the
underlying primitive is subverted. They showed that the $n$-bit to $n$-bit
function implemented using enveloped XOR construction (EXor) with $3n+1$ many
$n$-bit functions and $3n^{2}$-bit random initial vectors (iv) can be proven
secure asymptotically in the crooked indifferentiability setting.

  * •

We identify several major issues and gaps in the proof by Russel et al , We
show that their proof can achieve security only when the adversary is
restricted to make queries related to a single message.

  * •

We formalize new technique to prove crooked indifferentiability without such
restrictions. Our technique can handle function dependent subversion. We apply
our technique to provide a revised proof for the EXor construction.

  * •

We analyze crooked indifferentiability of the classical sponge construction.
We show, using a simple proof idea, the sponge construction is a crooked-
indifferentiable hash function using only $n$-bit random iv. This is a
quadratic improvement over the EXor construction and solves the main open
problem of Russel et al

##  1 Introduction

Blackbox Reduction and Kleptographic attack. Many of the modern cryptographic
constructions are analyzed in a modular and inherently black-box manner. The
schemes or protocols are built on underlying primitives only exploiting the
functionality of the primitives. While analyzing the security, one shows a
reduction saying, a successful attack on the construction will lead to an
attack against the underlying primitive. Unfortunately, this approach
completely leaves out the implementation aspects. While the underlying
primitive may be well studied, a malicious implementation may embed trapdoor
or other sensitive information that can be used for the attack. Moreover, such
implementation may well be indistinguishable from a faithful implementation.
These type attacks fall in the realm of _Kleptography_ , introduced by Young
and Young[18, 19]. The real possibility of Kleptographic attacks has been
confirmed by Snowden’s revelation. Recently, starting with the work of
Bellare, Paterson and Rogaway [4], the attention to this setting has been
rejuvenated. BPR showed that it is possible to mount an algorithm-
substitution-attack against almost all known symmetric key encryption scheme
to the extent that the attacker learns the secret key. A series of work has
been done in the recent years formalizing approaches resisting algorithm-
subversion attacks [12, 3, 14, 10, 11, 15, 16, 1, 2]. In his IACR
Distinguished lecture, Rogaway urged for community-wide efforts to work on
defending against Kleptography.

Crooked Indifferentiability. In CRYPTO 2018, Russel et al [17] introduced the
notion of crooked indifferentiability as a security notion for hash functions
in the kleptographic setting. Indeed, hash functions are ubiquitous tool of
modern cryptology, and natural choice for instantiating Random Oracles in
practical protocols. Subverting internal algorithms of a hash function will be
a natural target for kleptographic attack. In the crooked-indifferentiability
setting, thee constructions are randomized. The distinguisher can _substitute_
the ideal primitive $f$ by a subverted implementation which “crooks” the
function on $\epsilon$ fraction of the inputs, producing a crooked primitive
$\tilde{f}$. In order to prove crooked-indifferentiability of a construction
$C^{f}$, one constructs a simulator $S$ such that $(C^{\tilde{f}}(.,R),f)$ and
$(\mathcal{F},S^{\tilde{f}}(R))$ are indistinguishable. As in the case of
classical indifferentiability [13, 9], the notion of crooked
indifferentiability and the corresponding composition theorem aims to
formalize the idea of instantiating hash functions as Random Oracles in
protocols, and prove the kleptographic security.

Unfortunately, not much theory is known about crooked indifferentiability
except the results by [17]. Specifically, it is unknown whether the popular
modes of operations used in cryptographic hash functions can be proven secure
under this notion. Looking at the potential application in the analysis of
hash functions in the post-Snowden era, we believe an in-depth study of the
crooked-indifferentiability notion is an extremely important problem of
theoretical cryptography.

Figure 1: Sponge and EXor constructions.

###  1.1 Our Contribution

In this paper, we introduce new techniques to prove crooked-
indifferentiability of domain extension techniques. We proved crooked
indifferentiability of EXor construction (Figure 1 left) and the sponge
construction (Figure 1 right).

Another Look at RTYZ proof. We uncover that the proof technique of RTYZ [17]
only works under simplifying conditions. The crooked-indifferentiability
proofs of EXor do not go through in the general setting. The simplest-to-
explain issue is the following. RTYZ silently assumes that it is sufficient to
prove indifferentiability showing consistency of the simulator for a single
message. In other words, they implicitly restrict the indifferentiability
distinguisher to make at most a single query to the construction (resp. RO in
the ideal world). When applied with the composition theorem, this restriction
limits the _environment_ , which includes the protocols and the adversary, to
make in total a single query to the Random Oracle (RO). Thus, the result of
[17] is applicable only if the protocol queries the RO once and the adversary
does not even get access to the RO. This makes the results of [17] invalid for
any reasonable setting and the results built on it, e.g. [8], gets nullified.
As we show in Section 5.2, the technique collapses if the distinguisher can
check consistency for more than one message. Thus the results of [17], while
involves heavy technical machineries, fail to achieve any meaningful security
guarantee. In Section 5.2, we discuss this and other technical issues in
detail.

Enveloped Xor Construction and its crooked-indifferentiability. In [17],
Russel et al proved crooked-indifferentiability of the enveloped-xor
construction, albeit as we just discussed, in a very restricted setting. We
prove security without any such restriction. Our techniques, in comparison,
are also quite simple and use basic tools of probability.

Crooked-indifferentiability of Sponge construction. While enveloped-xor
construction serves as a proof of concept of crooked-indifferentiability, the
construction is far from being practical. It uses $3n+1$ _independent_ hash
functions (one call to each) and $3n^{2}$ bits of randomness in order to
construct an $n$-bit to $n$-bit subversion resilient function! When we
instantiate that to construct practical hash functions, then this cost will
amplify and we end up with somewhat impractical construction. Constructing a
crooked-indifferentiable hash function that uses $\mathcal{O}(n)$ random bits,
and makes linear number of calls to the underlying primitive, was left open as
the central question by [17].

We prove crooked-indifferentiability of sponge construction, the construction
underlying the SHA3 hash function, with random initialization vector. We
assume the underlying primitive to be a random function. The construction uses
only $n$-bit randomness and even with the most conservative parameter choices,
makes at most $2n$ many calls to the underlying primitive to construct an
$n$-bit to $n$-bit function. The result is not limited to produce length
preserving hash functions. In fact, similar to the security enjoyed by the
sponge construction in the classical setting, our result is applicable for the
general sponge construction hashing $\ell$-bit messages to $s$-bit digests.

##  2 Notations and Preliminaries

Notations. For any tuples of pairs
$\tau=((x_{\\_}1,y_{\\_}1),\ldots,(x_{\\_}s,y_{\\_}s))$ we write
$\mathcal{D}(\tau)$ (called domain of $\tau$) to denote the set
$\\{x_{\\_}i:1\leq i\leq s\\}$. $\tau_{\\_}j$ denotes the sub-list containing
the first $j$ entries in $\tau$.
$\tau_{\\_}j=((x_{\\_}1,y_{\\_}1),\ldots,(x_{\\_}j,y_{\\_}j))$. We write
$x\xleftarrow{\mbox{\tiny${\$}$}}S$ to denote the process of choosing $x$
uniformly at random from a set $S$ and independently from all other random
variables defined so far. For a positive integer $l$, we use $(l]$ to denote
the set $\\{1,\cdots,l\\}$. $[l]$ is used to denote the set
$\\{0,1,\ldots,l\\}$.

Class of Functions. The positive integer $n$ is our security parameter. Let
$\mathcal{D}:=[l]\times\\{0,1\\}^{n}$. Let $\mathsf{H}$ denote the set of all
functions from $\mathcal{D}$ to $\\{0,1\\}^{n}$. Similarly, $\mathsf{F}$
denote the set of all functions from $\\{0,1\\}^{n}$ to $\\{0,1\\}^{n}$. For
any $z:=((a_{\\_}1,b_{\\_}1),\ldots,(a_{\\_}{q_{\\_}1},b_{\\_}{q_{\\_}1}))$
with $b_{\\_}1,\ldots,b_{\\_}{q_{\\_}1}\in\\{0,1\\}^{n}$ and distinct
$a_{\\_}1,\ldots,a_{\\_}{q_{\\_}1}\in\mathcal{D}$, we write $h\vdash z$ if
$h(a_{\\_}i)=b_{\\_}i$ for all $i\in(q_{\\_}1]$. We denote the set of all
functions $h$ such that $h\vdash z$ as $\mathsf{H}|_{\\_}z$.

Distinguishing Advantage. In this paper, we measure the efficiency of
algorithms by their query complexity. An oracle algorithm $\mathcal{A}$ having
access of one oracle is called $q$-query algorithm if it makes at most $q$
queries to its oracle. Similarly, an oracle algorithm having access to two
oracles is called $(q_{\\_}1,q_{\\_}2)$-query algorithm, if it makes at most
$q_{\\_}1$ and $q_{\\_}2$ queries to its first and second oracles
respectively. We use $X^{t}$ to denote the $t$-tuple
$(X_{\\_}1,\ldots,X_{\\_}t)$.

######  Definition 1 (Distinguishing Advantage)

Let $F^{l}$ and $G^{l}$ be two $l$-tuple of probabilistic oracle algorithms
for some positive integer $l$. We define _advantage_ of an adversary
$\mathcal{A}$ at distinguishing $F^{l}$ from $G^{l}$ as

$\Delta_{\\_}\mathcal{A}(F^{l}\ ;\
G^{l})=\left|\Pr[\mathcal{A}^{F_{\\_}1,F_{\\_}2,\cdots,F_{\\_}l}=1]-\Pr[\mathcal{A}^{G_{\\_}1,G_{\\_}2,\cdots,G_{\\_}l}=1]\right|.$

##  3 Modeling Subversion Algorithms and Crooked Indifferentiability

We recall the related terms and notations introduced in [17] in our
terminologies. Implementor. A $(q,\tau)$ implementor is a $q$ query oracle
algorithm $\mathcal{A}^{\mathcal{O}}$ which outputs a $\tau$ query oracle
algorithm $\tilde{H}^{\mathcal{O}}$, called the implementation. Let $z$ denote
the transcript of oracle queries of $\mathcal{A}$. For the rest of the paper,
we shall assume that $\mathcal{O}$ is a function $h$, sampled uniformly at
random from $\mathsf{H}$. The implementation $\tilde{H}$ is correct if for all
$h\in\mathsf{H}$ and for all $x\in\mathcal{D}$,
$\tilde{h}(x)\stackrel{{\scriptstyle\text{def}}}{{=}}\tilde{H}^{h}(x)=h(x)$.
As $h$ is a random function, we assume without loss of generality that
$\tilde{H}^{h}(x)$ queries $h(x)$ and it is in fact the first query it makes.
The transcript $z$ is hardwired in $\tilde{H}$ and all the $\tau$ queries made
by $\tilde{H}$ are different from $\mathcal{D}(z)$.

Let $\mathcal{Q}^{h}(\alpha)$ denote the set of all queries during the
computation of $\tilde{h}(\alpha)$. We use
$\alpha\twoheadrightarrow_{\\_}h\alpha^{\prime}$ to denote that
$\tilde{h}(\alpha)$ queries $h(\alpha^{\prime})$. Similarly,
$\alpha\not\twoheadrightarrow_{\\_}h\alpha^{\prime}$, denotes that
$\tilde{h}(\alpha)$ does not query $h(\alpha^{\prime})$.
$\tilde{\alpha}_{\\_}j$ denotes the $j^{th}$ query made by
$\tilde{h}(\alpha)$.

######  Definition 2 (crooked implementor)

A $(q,\tau)$ implementor $\mathcal{A}_{\\_}1$ is called $\epsilon$-crooked for
$\mathsf{H}$, if for every $h\in\textsf{H}$ and for all $0\leq i\leq l$,
$\Pr_{\\_}{\alpha\xleftarrow{\mbox{\tiny${\$}$}}\\{0,1\\}^{n}}(\tilde{h}(i,\alpha)\neq
h(i,\alpha))\leq\epsilon$.

Summary. A (crooked) implementation $\tilde{h}$, to compute
$\tilde{h}(\alpha)$, queries $h(\alpha_{\\_}1),\cdots,h(\alpha_{\\_}\tau)$ on
$\tau$ many distinct points ($\alpha_{\\_}1=\alpha$) and its decision of
whether to subvert $h(\alpha)$ depends on this transcript and the hardwired
string $z$. For an $\epsilon$-crooked implementation, for each
$h\in\mathsf{H}$, for at most $\epsilon$ fraction of $\alpha\in\mathcal{D}$,
$h(\alpha)$ is subverted.

Crooked Distinguisher. A crooked distinguisher is a two-stage adversary; the
first stage is a subverted implementor and the second stage is a
distinguisher.

######  Definition 3 (crooked distinguisher)

We say that a pair $\mathcal{A}:=(\mathcal{A}_{\\_}1,\mathcal{A}_{\\_}2)$ of
probabilistic algorithms $((q_{\\_}1,\tau,\epsilon),q_{\\_}2)$-crooked
distinguisher  for $\mathsf{H}$ if

(i) $\mathcal{A}_{\\_}1$ is a $\epsilon$-crooked $(q_{\\_}1,\tau)$ implementor
for H and

(ii) $\mathcal{A}_{\\_}2(r,z,\cdot)$ is a $q_{\\_}2$-query distinguisher where
$r$ is the random coin of $\mathcal{A}_{\\_}1$, and $z$ is the transcript of
interaction of $\mathcal{A}_{\\_}1$ with $h$.

Crooked Indifferentiability. Now we state H-crooked indifferentiable security
definition (as introduced in [17]) in our notation and terminology.

######  Definition 4 ($\mathsf{H}$-crooked indifferentiability [17])

Let $\mathcal{F}$ be an ideal primitive and $C$ be an initial value based
$\mathcal{F}$-compatible oracle construction. The construction $C$ is said to
be $((q_{\\_}1,\tau)$, $(q_{\\_}2,q_{\\_}{\mathrm{sim}})$,
$\epsilon,\delta)$-$\mathsf{H}$-crooked indifferentiable from $\mathcal{F}$ if
there is a $q_{\\_}{\mathrm{sim}}$-query algorithm $S$ (called simulator) such
that for all $((\epsilon,q_{\\_}1,\tau),q_{\\_}2)$-crooked distinguisher
$(\mathcal{A}_{\\_}1(r)$, $\mathcal{A}_{\\_}2(r,\cdot,\cdot))$ for
$\mathsf{H}$, we have

$\Delta_{\\_}{\mathcal{A}_{\\_}2(r,z,R)}\big{(}(h,C^{\tilde{h}}(R,\cdot))\ ;\
(S^{\mathcal{F},\tilde{h}}(z,R),\mathcal{F})\big{)}\leq\delta$ (1)

where $z$ is the advise string of $\mathcal{A}_{\\_}1^{h}$ and $R$ is the
random initial value of the construction sampled after subverted
implementation is set.

$C(R,\cdot)$$\tilde{H}$$h$$S(z,R)$$\mathcal{F}$$\tilde{H}$$\mathcal{A}_{\\_}2(r,z,R)$
Figure 2: The crooked indifferentiability notion. In the first phase of real
world, $\mathcal{A}_{\\_}1$ interacts with $f$ and returns an oracle algorithm
$\tilde{f}$ (which would be accessed by the construction $C$ in the second
phase). In the second phase the random initial value $R$ will be sampled and
given it to the construction $C$ and also to $\mathcal{A}_{\\_}2$. In ideal
world, simulator $S^{\mathcal{F}}$ gets the advise string of the first phase,
blackbox access to the subverted implementation $\tilde{H}$ and the initial
value $R$.

Two-Stage Distinguishing Game. Now we explain the distinguishing game. In the
first stage, $\mathcal{A}_{\\_}1^{h}$ outputs $\tilde{H}$ after interacting
with a random oracle $h$. Then, a random initial value, $R$, of the hash
construction $C$ is sampled. In the real world, $\mathcal{A}_{\\_}2$ interacts
with the same $h$ of the firsts stage and the construction
$C^{\tilde{h}}(R,\cdot)$. In the ideal world, the simulator $S$ gets the
advice-string $z$, the initial value $R$ and blackbox access to the subverted
implementation $H$ as inputs,111If an algorithm $S$ gets a blackbox access to
the oracle algorithm $H$ as an input, it can compute $H(x)$ by invoking $H$
with input $x$ and responding to the oracle queries of $H$. and gets oracle
access of a random oracle $\mathcal{F}$. Simulator is aimed to simulate $h$ so
that behavior of $(h,C^{\tilde{h}})$ is as close as $(S,\mathcal{F})$ to the
distinguisher $\mathcal{A}_{\\_}2$.

Convention on Crooked Distinguishers: Note that there is no loss to assume
that both $\mathcal{A}_{\\_}1$ and $\mathcal{A}_{\\_}2$ are deterministic (so
we skip the notation $r$) when we consider computational unbounded
adversary222$\mathcal{A}_{\\_}1$ can fix the best random coin for which the
distinguishing advantage of $\mathcal{A}_{\\_}2$ is maximum.. We also assume
that $\mathcal{A}_{\\_}2$ makes all distinct queries and distinct from the
queries made by $\mathcal{A}_{\\_}1$. We skip the notation $z$ as an input of
$\mathcal{A}_{\\_}2$ as it is fixed throughout the game.

##  4 Basic Tools of Crooked Indifferentiability

In this section we develop the basic notations and tools used throughout the
rest of the paper. The basic technique for designing an efficient simulator in
the classical indifferentiability setting, was lazy sampling maintaining
consistency. The presence of possibly subverted points in the crooked
indifferentiability setting makes direct application of the idea infeasible.
We start by defining the following indicator.

$d(\alpha,h)=\begin{cases}1,&\text{if }\tilde{h}(\alpha)\neq h(\alpha)\mbox{
or }\alpha\in\mathcal{D}(z)\\\ 0,&\text{otherwise }\end{cases}$

In other words, $d$ sets value one for an element
$\alpha\in\mathcal{D}\setminus\mathcal{D}(z)$, if it is crooked.333Note that
$\alpha\in\mathcal{D}(z)$ was not considered in [17]. However, it will be
later clear that we need this simple modification. We say $\alpha$ is
_problematic_ for $h$ if $d(\alpha,h)=1$.

For every $\alpha\in\mathcal{D},\beta\in\\{0,1\\}{n}$, we use
$h_{\\_}{\alpha\rightarrow\beta}$ to denote the function which agrees with $h$
on all points possibly except at $\alpha$ which the function
$h_{\\_}{\alpha\rightarrow\beta}$ maps to $\beta$. Note that if
$h(\alpha)=\beta$ then $h_{\\_}{\alpha\rightarrow\beta}=h$. Let
$D^{1}(\alpha,h)=\mathsf{Ex}_{\\_}{\beta}(d(\alpha,h_{\\_}{\alpha\rightarrow\beta}))$
where the expectation is computed under
$\beta\xleftarrow{\mbox{\tiny${\$}$}}\\{0,1\\}^{n}$.

####  4.0.1 Bounding the Probability of Problematic Points

Our first step is to show that even for the subverted implementation of a
randomly chosen function, a randomly chosen point of the domain is _not
problematic_ with high probability.

We follow the notations developed in the previous sections. For $1\leq
j\leq\tau$, let
$D^{j}(\alpha,h)=\mathsf{Ex}_{\\_}{\beta}(d(\alpha,h_{\\_}{\tilde{\alpha}_{\\_}{j}\rightarrow\beta}))$
(average number of crooked point after we resample the output of the $j$th
query made by the subverted implementation).

###### Lemma 1

Let $\alpha\xleftarrow{\mbox{\tiny${\$}$}}\mathcal{D}$,
$h\xleftarrow{\mbox{\tiny${\$}$}}\mathsf{H}|_{\\_}z$. For any
$\epsilon$-crooked implementation $H_{\\_}z$, for all $1\leq j\leq\ell$

$\displaystyle\mathsf{Ex}_{\\_}{\alpha,h}\big{(}{D}^{j}(\alpha,h)\big{)}$
$\displaystyle\leq\epsilon_{\\_}1:=(\epsilon+q_{\\_}12^{-n})$ (2)

####  4.0.2 Robust points and Robust functions

######  Definition 5 (Robust points)

We say a point $\alpha\in\mathcal{D}$ is robust for function $h$ if

  1. 1.

$\alpha$ is unsubverted under $h$; $d(\alpha,h)=0$.

  2. 2.

If we resample the output of $j^{th}$ query of $\tilde{h}(\alpha)$ then the
probability that $h(\alpha)$ becomes subverted is at most
$\epsilon_{\\_}1^{1/2}$. In other words, it holds that

$\displaystyle{D}^{j}(\alpha,h)\leq\epsilon_{\\_}1^{1/2}$

######  Definition 6 (Good point-function pair)

We call a pair $(\alpha^{\prime},h)$ _good_ if $\alpha^{\prime}$ is queried
only by a few robust points. In other words,

  1. 1.

for all $\alpha\twoheadrightarrow_{\\_}h\alpha^{\prime}$ it holds that
$\alpha$ is robust for $h$.

  2. 2.

the number of $\alpha$ which queries $\alpha^{\prime}$ is at most
$1/\epsilon_{\\_}1^{1/4}$.

We call the pair $(\alpha^{\prime},h)$ bad, if it is not good. Let $G$ be the
collection of all such good pairs. For any function $h$, let
$G_{\\_}h:=\\{\alpha^{\prime}:(\alpha^{\prime},h)\in G\\}$ and
$B_{\\_}h:=\\{\alpha^{\prime}:(\alpha^{\prime},h)\not\in G\\}$.

In what follows we use
$\alpha,\alpha^{\prime}\xleftarrow{\mbox{\tiny${\$}$}}\mathcal{D}$ and
$h\xleftarrow{\mbox{\tiny${\$}$}}\mathsf{H}|_{\\_}z$ whenever these are used
as random variables to compute probabilities. Otherwise, these are considered
to be fixed elements from their respective domains.

The following lemma says that a randomly sampled point-function pair is good
with high probability.

###### Lemma 2

$\Pr_{\\_}{\alpha^{\prime},h}((\alpha^{\prime},h)\mbox{ is
bad})\leq\epsilon_{\\_}2:=3\tau\epsilon_{\\_}1^{1/4}$

A function $h$ is said to be robust if
$\Pr_{\\_}{\alpha^{\prime}}(\alpha^{\prime}\in
B_{\\_}h)\leq\epsilon_{\\_}2^{1/2}$ A simple application of Markov inequality
proves the following lemma which says that a random function is robust with
high probability.

###### Lemma 3

$\Pr_{\\_}h(h\mbox{ is not robust})\leq\epsilon_{\\_}2^{1/2}$

##  5 Crooked Indifferentiability of Enveloped XOR construction

In this section we analyze the crooked indifferentiability of security EXor.
The construction was analyzed in [17], as we shall show, with very restrictive
and impractical assumptions. First, we formally define the Enveloped XOR
construction with randomized iv.

Enveloped XOR Construction or EXor: We fix two positive integers $n$ and $l$.
Let $\mathcal{D}:=[l]\times\\{0,1\\}^{n}$. Let $\mathsf{H}$ be the class of
all functions $h:\mathcal{D}\to\\{0,1\\}^{n}$. For every $x\in\\{0,1\\}^{n}$
and an initial value $R:=(r_{\\_}1,\ldots,r_{\\_}l)\in(\\{0,1\\}^{n})^{l}$, we
define

$g_{\\_}R(m)=\bigoplus_{\\_}{i=1}^{l}h(i,m\oplus r_{\\_}i)\ \mbox{ and }\ \
\textsf{EXor}(R,m)=h(0,g_{\\_}R(m)).$

Our main result in this section is the following theorem.

###### Theorem 5.1

Let $l\geq n$ and $h:\mathcal{D}\to\\{0,1\\}^{n}$ be a family of random
functions and $\textsf{EXor}:\\{0,1\\}^{n}\to\\{0,1\\}^{n}$ be the enveloped-
xor construction. Then there exists a simulator $S$ such that for all
$(\kappa,\tau,\epsilon)$ crooked distinguisher
$\mathcal{A}=(\mathcal{A}_{\\_}1,\mathcal{A}_{\\_}2)$

$\displaystyle\mbox{\bf Adv}_{\\_}{\mathcal{A},(\textsf{EXor},h)}^{\mbox{\sf
crooked-indiff}}\leq 2\epsilon
q_{\\_}2+2q_{\\_}2(q_{\\_}1+q_{\\_}2)/2^{n}+\sqrt[8]{3\tau\left(\epsilon+\frac{q_{\\_}1}{2^{n}}\right)}+\frac{1}{2^{n}}$

where $q_{\\_}1$ and $q_{\\_}2$ are the total number of queries made by the
first and the second stage adversaries respectively. The simulator makes one
query to the random oracle $\mathcal{F}$ and makes $l$ many calls to the
subverted implementation $\tilde{h}$.

Restricting $q_{\\_}1,q_{\\_}2<<2^{n}$ $q_{\\_}2<<1/\epsilon$, and $\tau
q_{\\_}1<<2^{n/8}$ and $\tau\epsilon<<2^{n/8}$, we make the crooked-
indifferentiability advantage of any adversary negligible.

###  5.1 Proof of Theorem 5.1

####  5.1.1 A brief detour: classical indifferentiability simulator for EXor

Before describing the crooked indifferentiability simulator, we would like to
briefly recall the principle behind the indifferentiability simulator and
proof principles behind EXor construction in the classical setting.
The goal of the simulator is to simulate each $h(i,\cdot)$ honestly so that
for every queried message $m$, it holds that
$\textsf{EXor}(R,m)=\mathcal{F}(m)$ for all queried $m$. Without loss of
generality, assume that whenever the adversary makes queries $h(i,x)$ for
$i>0$, it also makes queries $h(j,x\oplus{r}_{\\_}i\oplus{r}_{\\_}j)$ for all
$j>0$ simultaneously. In other words, it makes a batch query of the form
$({h}(j,m\oplus{r}_{\\_}j))_{\\_}{1\leq j\leq l}$ for some
$m\in\\{0,1\\}^{n}$. We simply say that the adversary $\mathcal{A}$ queries
$m$ to $g_{\\_}R$ and obtains responses
$({h}(j,m\oplus{r}_{\\_}j))_{\\_}{1\leq j\leq l}$.

On receiving a batch query $g_{\\_}R(m)$, the simulator will honestly sample
outputs for the corresponding $h(i,m\oplus R_{\\_}i)$ queries for all
$i\in(l]$, and compute $g_{\\_}R(m)$ by xoring those sampled outputs. Also,
the simulator will save the queried $m$ along with the computed $g_{\\_}R(m)$
in a list $L$. For a $h(0,x)$ query, the simulator will first search in $L$,
whether for some $m$, it has given $x=g_{\\_}R(m)$ as output. If yes, the
simulator simply returns $\mathcal{F}(m)$. If no such entry exists, the
simulator samples an output $z$ uniformly at random and returns $z$.

Now, we briefly recall how the indifferentiability is proved for this
simulator. There are two bad events.

  * •

for distinct $m,m^{\prime}$, it holds that $g_{\\_}R(m)=g_{\\_}R(m^{\prime})$.
In this case, the simulator, on query $h(0,g_{\\_}R(m))$ can not be consistent
with both $\mathcal{F}(m)$ and $\mathcal{F}(m^{\prime})$ with any significant
probability.

  * •

For a batch query $g_{\\_}R(m)$ the output is such that it matches with a
previous $h(0,.)$ query. In this case, the simulator has already given output
to the $h(0,.)$ query which, with all but negligible probability, is not equal
to $g_{\\_}R(m)$.

One can indeed summarize these bad events as one; $g_{\\_}R(m)\in E$, where
$E$ is the set of $h(0,.)$ queries made by the adversary.

####  5.1.2 The Simulator for Crooked Indifferentiability

We now describe the simulator in the crooked indifferentiability setting. The
same simulator is used in [17]. We define the functions, when instantiated
with subverted algorithms.

$\tilde{g}_{\\_}R(m):=\bigoplus_{\\_}{i=1}^{l}\tilde{h}(i,m\oplus\textsf{r}_{\\_}i)\mbox{
and }\widetilde{\textsf{EXor}}(R,x)=\tilde{h}(0,\tilde{g}_{\\_}R(x)).$

In other words, if we express ${\textsf{EXor}}(R,x)$ as
${\textsf{EXor}}^{h}(R,x)$ then $\widetilde{\textsf{EXor}}(R,x)$ represents
${\textsf{EXor}}^{\tilde{h}}(R,x)$.

Note, here the main goal of the simulator is different. It needs to simulate
$h\xleftarrow{\mbox{\tiny${\$}$}}\textsf{H}$ as honestly 444perfectly
simulating a random function. If the responses are already in the list it
returns that value, otherwise, it samples a fresh random response and includes
the input and output pairs in the list. as possible such that
$\widetilde{\textsf{EXor}}(R,m)=\mathcal{F}(m)$ for all queried $m$. Thus the
simulator needs to ensure that the output of the random oracle matches with
the _subverted implementation_ of EXor.

The simulator maintains a list $L$ of pairs $(\alpha,\beta)$ to record
$h(\alpha)=\beta$ for $\alpha\in\mathcal{D}$ and $\beta\in\\{0,1\\}^{n}$. It
also maintains a sub-list $L^{A}\subseteq L$ consisting of all those pairs
which are known to the distinguisher. Both lists are initialized to $z$ (the
advice-string in the first stage which we fix to any tuple of $q_{\\_}1$
pairs). $L_{\\_}0=L_{\\_}0^{A}=z$. Now we describe how the simulator responds.

  1. 1.

(Query $h(0,w)$) We call this query a Type-1 Query. Type-1 Queries are
returned honestly. If $((0,w),y)\in L$ for some $y$, the simulator returns the
same $y$. Otherwise, it samples $y$ uniformly from $\\{0,1\\}^{n}$, updates
the list $L$ and $L^{A}$, and returns $y$.

  2. 2.

(Query $g_{\\_}R(m)$) We call this Type-2 Query. For a query $g_{\\_}R(m)$
(i.e. batch query) the simulator computes $\tilde{h}(\alpha_{\\_}j)$ for all
$j$, one by one by executing the subverted implementation $\tilde{H}$, where
$\alpha_{\\_}j=(j,m\oplus R_{\\_}j)$. During this execution, simulator
responds honestly to all queries made by the subverted implementation and
updates the $L$-list by incorporating all query responses of $h$. However, it
updates $L^{A}$ list only with $(\alpha_{\\_}j,h(\alpha_{\\_}j))$ for all $j$.
Let $\tilde{\tt g}:=\bigoplus_{\\_}j\tilde{h}(\alpha_{\\_}j)$. If
$(0,\tilde{\tt g})\in\mathcal{D}(L)$, the simulator aborts . If the simulator
does not abort, it makes a query $\mathcal{F}(m)$ and adds $((0,\tilde{\tt
g}),\mathcal{F}(m))$ into the both lists $L$ and $L^{A}$.

For ${h}(0,w)$ made by $\mathcal{A}_{\\_}2$ where $w=\tilde{g}_{\\_}R(m)$ for
some previous query $m$ to $g_{\\_}R$, the simulator responds as
$\mathcal{F}(m)$.

Cautionary Note. Even though $\mathcal{F}$ is a random oracle, we cannot say
that the probability distribution of the response of $(0,\tilde{\tt g})$ in
the ideal world is uniform. Note that, the adversary can choose $m$ after
making several consultations with $\mathcal{F}$. In other words, $m$ can be
dependent on $\mathcal{F}$. For example, the adversary can choose a message
$m$ for which the last bit of $\mathcal{F}(m)$ is zero. Thus, the response for
the query $(0,w)$ always has zero as the last bit (which diverts from the
uniform distribution).

Transcript: Now we describe what is the transcript to the distinguisher and
for the simulator in more detail. First, we introduce some more relevant
notations.

  1. 1.

Let $L^{F}$ denote the set of all pairs $(m^{\prime},\tilde{z})$ of query
response of $\mathcal{F}$ by $\mathcal{A}_{\\_}2$.

  2. 2.

Let $L^{g}$ denote the set of all pairs $(m,\beta^{l})$ of query response of
$g_{\\_}R$ oracle (batch query) made by $\mathcal{A}_{\\_}2$ to the simulator
where $\beta^{l}:=(\beta_{\\_}1,\ldots,\beta_{\\_}l)$ and
$\beta_{\\_}j=h(j,m\oplus R_{\\_}j)$ for all $j$. According to our convention
all these $m$ must be queried to $\mathcal{F}$ beforehand.

  3. 3.

As we described, we also have two lists, namely $L$ and its sublist $L^{A}$,
keeping the query responses of $h$ oracle.

Now we define the transcript and partial transcript of the interaction. We
recall that $q_{\\_}1$ is the number of queries in the first stage and
$\mathcal{A}_{\\_}2$ is a $(q_{\\_}F,q_{\\_}2)$-query algorithm. Let
$q=q_{\\_}2+q_{\\_}F$ For any $1\leq i\leq q$, we define the partial
transcript of $\mathcal{A}$ and the simulator as
$\tau_{\\_}i^{A}:=(L^{F}_{\\_}i,L^{A}_{\\_}i)$ and
$\tau_{\\_}i^{S}:=(L_{\\_}i,L^{g}_{\\_}i)$ respectively, where
$L^{F}_{\\_}i,L^{A}_{\\_}i,L_{\\_}i,L^{g}_{\\_}i$ denote the contents of the
corresponding lists just before making $i$th query of the distinguisher. So
when, $i=1$, $L^{A}_{\\_}1=L_{\\_}1=z$ and the rest are empty and when
$i=q+1$, these are the final lists of transcripts. Let
$\tau_{\\_}i:=(\tau^{A}_{\\_}i,\tau^{S}_{\\_}i)$ and
$\tau:=(\tau^{A},\tau^{S})$ denote the joint transcript on $i$th query or
after completion respectively. As the adversary is deterministic, the
simulator is also deterministic for a given $h$ and $\mathcal{F}$, and we have
fixed $z$, a (partial) transcript is completely determined by the choice of
$R$, $h$ and $\mathcal{F}$ (in the ideal world). We write
$(R,h,\mathcal{F})\vdash\tau_{\\_}i^{S}$ if the transcript $\tau_{\\_}i^{S}$
is obtained when the initial value is $R$, the random oracles are
$\mathcal{F}$ and $h$. We similarly define
$(R,h,\mathcal{F})\vdash\tau_{\\_}i^{A}$ and
$(R,h,\mathcal{F})\vdash\tau_{\\_}i$.

Bad Event. We can now define the bad events. Let $\mathsf{bad}_{\\_}i$ denote
the event that $i$th query is to $g_{\\_}R(m)$ for some message $m$, and
either the simulator aborts (implying $(0,\tilde{g}_{\\_}R(m))\in L_{\\_}i$)
or $(0,\tilde{g}_{\\_}R(m))$ is a crooked point for $h$. Let
$\mathsf{bad}=\vee_{\\_}i\mathsf{bad}_{\\_}i$.

###### Observation 5.2

Given that $\mathsf{bad}$ does not hold, for all queries $m$ we have

$\widetilde{\textsf{EXor}}(R,m)=\mathcal{F}(m).$

From now on, we discuss how to bound the probability of the bad events.

###  5.2 Techniques of [17]

Overview of the techniques in [17]. We assume, without any loss of generality
that the second stage adversary $\mathcal{A}_{\\_}2$ queries $m$ to
$\mathcal{F}$ before it queries to $g_{\\_}R$ oracle. In addition, like
before, we assume that it makes batch queries.

For every query number $i$, we define a set
$E_{\\_}i:=\mathcal{D}(L_{\\_}i)\cup\mathcal{C}^{h}$ where $\mathcal{C}^{h}$
is the set of all crooked elements for $h$. The event $\mathsf{bad}_{\\_}i$
holds if and only if $(0,\tilde{g}_{\\_}R(m_{\\_}i))\in E_{\\_}i$ where
$m_{\\_}i$ denotes the $i$th query of $\mathcal{A}$ (made to $g_{\\_}R$ oracle
of the simulator). So, the crooked indifferentiable advantage is bounded by
$\sum_{\\_}{i=1}^{q_{\\_}2}\Pr(\tilde{g}_{\\_}R(m_{\\_}i)\in E_{\\_}i)$. From
the definition it is clear that $|\mathcal{D}(L_{\\_}{i})|\leq q_{\\_}1+i$.
Moreover, $|\mathcal{C}^{h}|/2^{n}$ is negligible for every fixed function $h$
as $\mathcal{A}$ can crook at most negligible fraction of inputs. Motivated
from the above, the authors wanted to show that the distribution of
$\tilde{g}_{\\_}R(m_{\\_}i)$ is almost uniform. They proposed the following
theorem.

(Theorem 5 from [17]). Let
$h\xleftarrow{\mbox{\tiny${\$}$}}\mathsf{H}|_{\\_}z$. With overwhelming
probability (i.e., one minus a negligible amount) there exists a set
$\mathcal{R}_{\\_}z\subseteq(\\{0,1\\}^{n})^{l}$ and for every $i$, a set of
transcripts $\mathcal{T}^{A}_{\\_}i$ (before $i$th query) such that for all
$R\in\mathcal{R}_{\\_}z$,
$\tau_{\\_}i:=(L_{\\_}i^{F},L_{\\_}i^{A})\in\mathcal{T}^{A}_{\\_}i$, and
$m\not\in\mathcal{D}(L^{g}_{\\_}i)$,

$\Pr_{\\_}h((0,\tilde{g}_{\\_}\textsf{R}(m))\in E_{\\_}i\ |\
(R,\mathcal{F},h)\vdash\tau_{\\_}i)\leq\mathrm{poly}(n)\sqrt{|E_{\\_}i|}+\textsf{negl}(n).\vskip
6.0pt plus 2.0pt minus 2.0pt$

The authors claimed that crooked indifferentiability of ${\sf EXor}$ can be
derived from the above theorem. To describe the issues we need to dive into
the main steps of proving the above theorem. In the first step, the authors
assumed $i=1$ and later with a very sketchy argument justified how it works
for general $i$. Note that $\tau_{\\_}1$ contains only the information of $z$.
As $h\xleftarrow{\mbox{\tiny${\$}$}}\mathsf{H}|_{\\_}z$ is sampled honestly,
it is enough to simply focus on bounding the probability of the event
$(0,\tilde{g}_{\\_}\textsf{R}(m))\in\mathcal{D}(z)\cup\mathcal{C}^{h}$ for any
$m$. The main idea is to show that $\tilde{g}_{\\_}\textsf{R}(m)$ behaves
close to the uniform distribution over $\\{0,1\\}^{n}$. Thus the above
probability would be negligible as $q_{\\_}1/2^{n}$ and
$|\mathcal{C}^{h}|/2^{n}$ is negligible.

By using Markov inequality, authors are able to identify a set of overwhelming
amount of pairs $(R,h)$, called unpredictable pair, such that for any
unpredictable $(R,h)$ all $m$, there exists an index $i$ such that

  1. 1.

$D^{1}(\alpha_{\\_}i,h)$ is negligible and

  2. 2.

$\alpha_{\\_}j\not\twoheadrightarrow_{\\_}h\alpha_{\\_}i$ for all $j\neq i$,
where $\alpha_{\\_}j=m\oplus R_{\\_}i$.

Thus, if we resample $\beta=h(\alpha_{\\_}i)$ then with overwhelming
probability
$\tilde{h}_{\\_}{\alpha_{\\_}i\to\beta}(\alpha)=h_{\\_}{\alpha_{\\_}i\to\beta}(\alpha)$
(i.e. not crooked and returned a random value) and all corresponding values
for indices $j$ different from $i$ will remain same. So,
$\tilde{g}_{\\_}R(m)=\beta+A$ where $A$ does not depend on choice of $\beta$.
Thus, the modified distribution is close to uniform (as almost all values of
$\beta$ will be good). In particular the authors made the following claim:

###### Claim 5.3

Under the modified distribution (i.e. after resampling),
$\Pr(\tilde{g}_{\\_}R(m)\in E_{\\_}1)\leq q_{\\_}1/2^{n}+\epsilon+p_{\\_}n$
where $p_{\\_}n$ denotes the probability that a random pair $(R,h)$ is not
unpredictable.

As the choice of $i$ depends on the function $h$ and so a new rejection
resampling lemma is used to bound the probability of the event under the
original distribution (i.e. before resampling).

######  Lemma 4 (Rejection Resampling [17])

Let $X:=(X_{\\_}1,\ldots,X_{\\_}k)$ be a random variable uniform on
$\Omega=\Omega_{\\_}1\times\Omega_{\\_}2\times\cdots\times\Omega_{\\_}k$. Let
$A:\Omega\to(k]$ and define $Z=(Z_{\\_}1,\ldots,Z_{\\_}k)$ where
$Z_{\\_}i=A_{\\_}i$ except at $j=A(X^{k})$ for which $Z_{\\_}j$ is sampled
uniformly and independently of remaining random variables. Then for any event
$S\subseteq\Omega$, it holds that

$\displaystyle|S|/|\Omega|$ $\displaystyle\leq\sqrt{k\Pr(Z\in S)}$

With this rejection resampling result and the Claim 5.3, the authors concluded
the following under original distribution:

$\Pr_{\\_}{h*}(\tilde{g}_{\\_}R(x)\in
E_{\\_}1)\leq\sqrt{l\cdot\Pr_{\\_}{\mbox{resampled }h}(\tilde{g}_{\\_}R(x)\in
E_{\\_}1)}\leq\sqrt{l\cdot(q_{\\_}1/2^{n}+\epsilon+p_{\\_}n)}.$

###  5.3 Issues with the technique of [17]

Now we are ready to describe the issues and the limitations of the techniques
in [17]. To prove the general case (i.e. for any query), authors provides a
very sketchy argument. It seems that authors argued that with an overwhelming
probability of realizable transcript $\mathcal{T}$ and for all
$\tau\in\mathcal{T}$, $\Pr(\tilde{g}_{\\_}R(m_{\\_}i)\in E_{\\_}i\ |\ \tau)$
is negligible.

Inconsistency for Multiple Queries: Controlling query dependencies for the
same index.

Recalling the notion of unpredictable $(R,h)$ we see that the resampling is
done on an index $i$, that is honest ($\tilde{h}(i,m\oplus
R_{\\_}i)=h(i,m\oplus R_{\\_}i)$, and $h(i,m\oplus R_{\\_}i)$ is not queried
by $h(i,m\oplus r_{\\_}j)$ for any other $j$. From here, the authors argued
that the transcript of the interaction remains same, if we resample at such
$i$. However, if the adversary can check consistency for multiple messages,
this is not sufficient.

Consider a $(q,\tau)$ subverted implementation $\tilde{h}$ that is
$\epsilon$-crooked. We construct a $(q,\tau+1)$ subverted implementation
$\hat{h}$ as follows. For every possible input $(i,x)$, $\hat{h}$ simulates
$\tilde{h}$. After the $\tau$ many queries made by $\tilde{h}$, $\hat{h}$
makes an additional query on $h(i,x\oplus 1^{n})$, if not already made.
Finally $\hat{h}$ outputs what $\tilde{h}$ outputs. Clearly, $\hat{h}$ is
$\epsilon$-crooked.
The distinguisher makes two batch queries queries, $\tilde{g}_{\\_}R(m\oplus
1^{n})$, and $\tilde{g}_{\\_}R(m)$. The simulator, while simulating
$\tilde{g}_{\\_}R(m\oplus 1^{n})$ responds to all the queries made by
$\tilde{h}(i,m\oplus 1^{n}\oplus R_{\\_}i)$, and in particular the value of
$h(i,m\oplus R_{\\_}i)$ is now gets fixed. Now consider doing the resampling
for the responses of the batch query $\tilde{g}_{\\_}R(m)$. All the
$h(i,m\oplus R_{\\_}i)$ has been fixed. Thus one can not find an index $i$
such that $h(i,m\oplus R_{\\_}i)$ has never been queried. Thus if we resample
at any index $i$, the transcript gets changed. Hence _the claim that for all
unpredictable $(R,h)$, for all $m$, an index $i$ exists on which the
resampling can be done without affecting the transcript is false._

The bad event $E_{\\_}i$ depends on the function $h$.Claim 5.3 says that
$\Pr_{\\_}{\mbox{resampled }h}(\tilde{g}_{\\_}R(x)\in E_{\\_}1)$ is small
because $\tilde{g}_{\\_}R(x)$ is uniformly distributed under resampling
distribution of $h$ and size of $E_{\\_}1$ is negligibly small. But, that
disregards the fact that the crooked set of $h$ may depend on the function
family $h$ and hence $E_{\\_}1$ is not independent of $\tilde{g}_{\\_}R(x)$.
In particular, one cannot upper bound the $\Pr(\tilde{g}_{\\_}R(x)\in
E_{\\_}1)$ as $|E_{\\_}1|/2^{n}$ . In other words, the Claim 5.3 need not be
true. This is one of the crucial observation which actually makes the crooked
security analysis a bit complex.

The number of queries to $\mathcal{F}$ is essential. Another incompleteness of
the proof of [17] comes from the fact that the analysis does not consider the
$\mathcal{F}$ queries of the distinguisher. The bound is almost vanishing if
$q_{\\_}1=0$ and $q_{\\_}2=2$ and has no crooked point. However, a
distinguisher can search for $m\neq m^{\prime}$ such that
$\mathcal{F}(m)=\mathcal{F}(m^{\prime})$. Conditioned on collision at the
final output, the event $g_{\\_}R(m)=g_{\\_}R(m^{\prime})$ holds with
probability about $1/2$. However, for the honest simulation of all $h$ values,
$g$ value will collide with very low probability. Hence, if the adversary can
make $2^{n/2}$ many queries to $\mathcal{F}$, the above consistency can be
forced. Hence the probability upper bound of Theorem 5 of [17] can not be
independent of the number of queries made to $\mathcal{F}$.

The gap in the technique. The reason, these issues have not cropped up in the
proof is the fact, that the authors _did not prove_ the simulator to be
consistent. In particular, they did not show that the bad events they
considered, are complete. To prove indifferentiability, it is required that
conditioned on not Bad, the real and the ideal games are indistinguishable.
While there are several techniques (like H-coefficient technique, or game-
playing technique), there is no formal argument on why Theorem $5$ proves
crooked indifferentiability.

###  5.4 Our Proof of Theorem 5.1

Our objective is to show that for every message, there is an index where we
can resample without affecting the (partial) transcript.
Critical Set. We construct a set $\mathcal{G}^{*}$ which we call a critical
set. A pair $(R,h)\in\mathcal{G}^{*}$ if  1. $h$is robust,  2. for every $m$
there exists $i$ so that  (a) $(\alpha_{\\_}i:=(i,m\oplus R_{\\_}i),h)$is
good.  (b) $\forall~{}j<i$,
$\alpha_{\\_}j\not\twoheadrightarrow\alpha_{\\_}i$.  We call the smallest
index $i$ that satisfies the above two condition, “index of interest” for
$(m,R,h)$.

If we can identify a critical set $G^{*}$, the following nice condition holds.
_For every fixed $(R,h)\in\mathcal{G}^{*}$ and for every $m$ there exists the
index of interest, $i$ such that $(\alpha_{\\_}i,h)$ is good (see Definition
6) where $\alpha_{\\_}i=(i,m\oplus R_{\\_}i)$._

Thus, for every message, we get an $\alpha_{\\_}i=m\oplus R_{\\_}i$ such that
for all $\alpha$ such that $\tilde{h}(\alpha)$ queries $h(\alpha_{\\_}i)$, is
unsubverted under $h$ and remains unsubverted if we resample
$h(\alpha_{\\_}i)$.

The following lemma says that for a uniform random string $R$ and a randomly
chosen function $h$, with high probability $(R,h)$ is in the critical set.
Recall from Lemma 1, Lemma 2, that we use the notation
$\epsilon_{\\_}1=\epsilon+q_{\\_}12^{-n}$ and
$\epsilon_{\\_}2=3\tau\epsilon_{\\_}1^{1/4}$.

###### Lemma 5

Let $\epsilon_{\\_}2\leq 1/16$ and $\ell\geq n$. It holds that
$\Pr_{\\_}{R,h}((R,h)\not\in\mathcal{G}^{*})\leq
p_{\\_}1:=\epsilon_{\\_}2^{1/2}+2^{-n}$

Resampling on index of interest does not affect the transcript. Fix $(R,h)$
from the critical set. Fix a message $m$ and let $i$ be the index of interest.
Our objective is to show that a transcript remains unchanged when
$h(\alpha_{\\_}i)$ is resampled. For that, our next step is to show the
following. We can identify a set $\mathcal{S}$ (of size close to $2^{n}$) such
that for all $\beta\in\mathcal{S}$ and
$h_{\\_}\beta\stackrel{{\scriptstyle\text{def}}}{{=}}h_{\\_}{\alpha_{\\_}i\to\beta}$,
it holds that $\tilde{h}(x)=\tilde{h_{\\_}\beta}(x)$ for all
$x\neq\alpha_{\\_}i$.
We define
$\mathcal{S}=\\{\beta:d(\alpha,h_{\\_}{\tilde{\alpha}_{\\_}j\to\beta})=0\forall~{}j,\forall~{}\alpha\in\mathcal{Q}^{h}_{\\_}{\twoheadrightarrow\alpha_{\\_}i}\\}$
where
$\mathcal{Q}^{h}_{\\_}{\twoheadrightarrow\alpha_{\\_}i}:=\\{\alpha:\alpha\twoheadrightarrow\alpha_{\\_}i\\}$.

Lower Bounding the size of $S$. From Definition 6, as $(\alpha_{\\_}i,h)$ is
good, the size of the set $\mathcal{Q}^{h}_{\\_}{\rightarrow\alpha_{\\_}i}$ is
at most $1/\epsilon_{\\_}1^{1/4}$. Moreover, for every such
$\alpha\twoheadrightarrow_{\\_}h\alpha_{\\_}i$, we have $d(\alpha,h)=0$ and
$\tilde{D}(\alpha,h)\leq\epsilon_{\\_}1^{1/2}$. So, there are at most
$2^{n}\times\epsilon_{\\_}1^{1/2}$ many $\beta$ for which there exists some
$j\in(l]$ with $d(\alpha,h_{\\_}{\tilde{\alpha}_{\\_}j\to\beta})=1$. Using
union bound for all $\alpha$ that queries $\alpha_{\\_}i$, the size of the set
$\\{0,1\\}^{n}\setminus\mathcal{S}$ is at most
$\frac{2^{n}\epsilon_{\\_}1^{1/2}}{\epsilon_{\\_}1^{1/4}}=2^{n}\cdot\epsilon_{\\_}1^{1/4}$.

###### Observation 5.4

$\tilde{h}(x)=\tilde{h_{\\_}\beta}(x)\ \forall x\neq\alpha_{\\_}i$.

Clearly, $\tilde{h_{\\_}\beta}(x)$ can be different from $\tilde{h}(x)$, only
if $x\twoheadrightarrow\alpha_{\\_}i$. However, for all such $\alpha_{\\_}i$
and for all $\beta\in\mathcal{S}$, we have shown that both
$d(\alpha,h)=d(\alpha,h_{\\_}\beta)=0$. Hence,
$\tilde{h_{\\_}\beta}(\alpha)=h_{\\_}\beta(\alpha)=h(\alpha)=\tilde{h}(x)$. So
from Observation 5.4,

  1. 1.

for all $m^{\prime}\neq m$,
$\tilde{g}_{\\_}R^{h}(m^{\prime})=\tilde{g}_{\\_}R^{h_{\\_}\beta}(m^{\prime})$.

  2. 2.

$d((0,g),h)=d((0,g),h_{\\_}\beta)$ (the crooked set of $h_{\\_}\beta$ for zero
index is same for $h$ for all such $\beta$).

Uniformity conditioned on transcript: Index of Interest is independent of
$\beta$. The last step is to ensure that the point of resampling is
independent of $\beta$. In other words, we need to show that the index of
interest is also independent of $\beta$. This will imply, for every message
$m$, we can identify an index $i$ such that
$\tilde{g}_{\\_}R^{h_{\\_}\beta}(m)=\beta\oplus\tilde{g}^{h}_{\\_}R(m)\oplus
h(\alpha_{\\_}i)$ holds for the fixed transcript.

###### Lemma 6

Fix a good $(R,h)$. Fix a message $m$. Let $i$ be the index of interest for
$(m,R,h)$. Let $\alpha_{\\_}i=(i,m\oplus R_{\\_}i)$. Then the following holds,

  1. 1.

$\alpha_{\\_}i\notin B_{\\_}{h_{\\_}\beta}$.

  2. 2.

for all $j<i$, $\alpha_{\\_}j\not\twoheadrightarrow\alpha_{\\_}i$ where
$\alpha_{\\_}j=(j,m\oplus R_{\\_}j)$.

  3. 3.

$i$ is minimum index that satisfies the above two condition for
$(R,h_{\\_}\beta)$ and $m$.

Finally, we are ready to state the main proposition

###### Proposition 1

For any partial transcript for adversary $\tau_{\\_}j:=(L^{F},L^{A})$, let
$(R,h,F)\vdash\tau_{\\_}j$ such that $(R,h)\in\mathcal{G}^{*}$. For every
$m\not\in\mathcal{D}(L^{g})$, there is a set $\mathcal{S}$ of size at least
$2^{n}(1-\epsilon_{\\_}1^{1/2})$ such that for all $\beta\in\mathcal{S}$,
$(R,h_{\\_}\beta,\mathcal{F})\vdash\tau_{\\_}j$ and
$\tilde{g}_{\\_}R^{h_{\\_}\beta}(m)=\beta\oplus\tilde{g}^{h}_{\\_}R(m)\oplus
h(\alpha_{\\_}i)$, where $i$ is the index of interest of $(m,R,h)$. Moreover,
the crooked sets of $h$ and $h_{\\_}\beta$ are same.
$C_{\\_}0^{h_{\\_}\beta}=C_{\\_}0^{h}$ (the crooked sets are same).

Assuming $\epsilon_{\\_}1^{1/2}\leq 1/2$, and for all
$(R,h,\mathcal{F})\vdash\tau$ with $(R,h)\in\mathcal{G}^{*}$, we have

$\Pr_{\\_}\beta((0,\tilde{g}_{\\_}R^{h_{\\_}\beta}(m))\in\mathcal{D}(L_{\\_}0)\cup
C^{h_{\\_}\beta}\wedge(R,h_{\\_}\beta,F)\vdash\tau)\leq
2\epsilon+2(q_{\\_}1+i)/2^{n}$

####  5.4.1  Bad Events and the Probability Bound.

We describe the bad events in terms of transcript notations as we did before.
Following the transcript notation in Section 5.2, recall that the Bad is
raised by two events, that $i$th query is $m$ to $g_{\\_}R$ oracle for which
$(0,\tilde{g}_{\\_}R(m))\in\mathcal{D}(L_{\\_}i)$ (denotes as $\mbox{\sc
Bad}_{\\_}1$) or $(0,\tilde{g}_{\\_}R(m))\in C^{h}$ (a crooked point for $h$
and rest is same as $\mbox{\sc Bad}_{\\_}2$). Let $\mbox{\sc
Bad}=\vee_{\\_}i\mbox{\sc Bad}_{\\_}i$. Thus, the distinguishing advantage is
bounded by $\Pr(\vee_{\\_}i\mbox{\sc Bad}_{\\_}i)$. We need to compute the
probability given the randomness of $R,h$ $F$ such that
$(R,h,F)\vdash\tau_{\\_}i^{A}$ (transcript of the adversary). We first bound
$\Pr(\mbox{\sc Bad}\wedge(R,h)\in\mathcal{G}^{*})$. By using Proposition 1,
for every $i$, $\Pr(\mbox{\sc
Bad}_{\\_}i|(R,h,F)\vdash\tau_{\\_}i,(R,h)\in\mathcal{G}^{*})\leq
2\epsilon+2(q_{\\_}1+i)/2^{n}$. Hence by summing over all $i$ and using the
bound of probability of not realizing $\mathcal{G}^{*}$, we get

$\displaystyle\Pr(\mbox{\sc Bad})$ $\displaystyle\leq 2\epsilon
q_{\\_}2+2q_{\\_}2(q_{\\_}1+q_{\\_}2)/2^{n}+p_{\\_}1$ $\displaystyle=2\epsilon
q_{\\_}2+2q_{\\_}2(q_{\\_}1+q_{\\_}2)/2^{n}+\sqrt[8]{3\tau\left(\epsilon+\frac{q_{\\_}1}{2^{n}}\right)}+\frac{1}{2^{n}}$

Note that $q_{\\_}2$ denotes the total number of queries of
$\mathcal{A}_{\\_}2$ made to both the simulator and $\mathcal{F}$ (in our
convention adversary makes all $\mathcal{F}$ queries to $g_{\\_}R$ of the
simulator). This finishes the proof of Theorem 5.1.

##  6 Games for the proof of Theorem 5.1

In this section, we show the game transitions in the proof of Theorem 5.1,
concluding that the crooked-indifferentiability of EXor construction is indeed
bounded by the probability of the bad events we considered. We assume that
distinguisher makes all $\mathcal{F}(m)$ queries to $g_{\\_}R(m)$ in case it
is not queried. However, it would be done after all queries are done. Note,
there is no loss to release all these $m$ values after the original
distinguisher finishes the queries. The query complexity of the distinguisher
increases by at most $\ell$ times.

###  6.1 Game Transitions

Our crooked-indifferentiability proof relies on three intermediate game,
denoted by $G_{\\_}0,G_{\\_}1,$ and $G_{\\_}2$. We start with the real game
$G_{\\_}0:=(h,C^{\tilde{h}})$. There are two public interfaces for the
adversary to query. The first one is $\mathcal{O}_{\\_}h$, which can be used
to interact with the function $H_{\\_}l$. The other one is
$\mathcal{O}_{\\_}C$, which can be used to compute $C^{\tilde{h}}$. For ease
of explanation, we add two internal subroutines, one for computing
$\tilde{g}_{\\_}R$ and the other for evaluating $\tilde{h}(0,\cdot)$.

pcvstack Game $(h,C^{\tilde{h}})$

$\mathcal{O}_{\\_}h(i,x)$ ($i\in[\ell]$)$\sum^{A}_{A_{b}}$
$\displaystyle\text{\scriptsize 1}:\quad\mathbf{return}\ h(i,x)$
$\tilde{h}_{\\_}0(x)$$\sum^{A}_{A_{b}}$ $\displaystyle\text{\scriptsize
1}:\quad\mathbf{for}\ \mbox{all queries }(i,\alpha)\mbox{ made by }\tilde{h}$
$\displaystyle\text{\scriptsize 2}:\quad\mbox{Feed }h(i,\alpha)$
$\displaystyle\text{\scriptsize 3}:\quad z=\tilde{h}(0,x)$
$\displaystyle\text{\scriptsize 4}:\quad\mathbf{return}\ z$
$\mathcal{O}_{\\_}C(m)$ 5: Sm= ~gR(m) 6: z=~h(0, Sm) 7: $\mathbf{return}$ z
$\tilde{g}_{\\_}R(m)$$\sum^{A}_{A_{b}}$ $\displaystyle\text{\scriptsize
1}:\quad Sum=0^{n}$ $\displaystyle\text{\scriptsize 2}:\quad\mathbf{for}\
j=1\mbox{ to }\ell\ \mathbf{do}$ $\displaystyle\text{\scriptsize
3}:\quad\mathmakebox{}\mbox{Run }\tilde{h}(j,m\oplus R_{\\_}j)$
$\displaystyle\text{\scriptsize 4}:\quad\mathmakebox{}\mathbf{for}\ \mbox{ all
queries}(i,\alpha)\mbox{ made by }\tilde{h}$ $\displaystyle\text{\scriptsize
5}:\quad\mathmakebox{}\mathmakebox{}\mbox{Feed }h(i,\alpha)$
$\displaystyle\text{\scriptsize
6}:\quad\mathmakebox{}u_{\\_}j=\tilde{h}(j,m\oplus R_{\\_}j)$
$\displaystyle\text{\scriptsize 7}:\quad\mathmakebox{}Sum=Sum\oplus u_{\\_}j$
$\displaystyle\text{\scriptsize 8}:\quad\mathbf{endfor}\ $
$\displaystyle\text{\scriptsize 9}:\quad\mathbf{return}\ Sum$

Figure 3: Game $\mathsf{Real~{}}$

Game ${\bf G}_{\\_}0$.  In this game, we modify the $\mathcal{O}_{\\_}h$
subroutine. For every $(j,x)$ query we recover the message $m=x\oplus
r_{\\_}j$, and precompute the response of all the $(i,m\oplus r_{\\_}i)$
queries. Further, we compute the value of
$\tilde{z}=\tilde{h}(\tilde{g}_{\\_}R(m))$. These precomputations do not
change the output for any of the query. Hence

$\displaystyle\Pr[\mathcal{A}^{h,C^{\tilde{h}}}=1]=\Pr[\mathcal{A}^{{\bf
G}_{\\_}0}=1]$

pcvstack Game $G_{\\_}0$

$\mathcal{O}_{\\_}h(j,x)$ ($j\in[\ell]$)$\sum^{A}_{A_{b}}$
$\displaystyle\text{\scriptsize 1}:\quad\mathbf{if}\ (j,x,y)\in
L\mathmakebox{}\mathbf{return}\ y$ $\displaystyle\text{\scriptsize
2}:\quad\mathbf{if}\ j>0$ $\displaystyle\text{\scriptsize
3}:\quad\mathmakebox{}m=x\oplus R_{\\_}j$ $\displaystyle\text{\scriptsize
4}:\quad S_{\\_}m=\tilde{g}_{\\_}R(m)$ $\displaystyle\text{\scriptsize
5}:\quad\tilde{z}=\tilde{h}(0,S_{\\_}m)$ $\displaystyle\text{\scriptsize
6}:\quad\mathmakebox{}(j,x,y)\leftarrow L$ $\displaystyle\text{\scriptsize
7}:\quad\mathmakebox{}\mathbf{return}\ y$ $\displaystyle\text{\scriptsize
8}:\quad\mathbf{if}\ j=0$ $\displaystyle\text{\scriptsize
9}:\quad\mathbf{return}\ h(0,x)$ $\tilde{h}_{\\_}0(x)$$\sum^{A}_{A_{b}}$
$\displaystyle\text{\scriptsize 1}:\quad\mathbf{for}\ \mbox{all queries
}(i,\alpha)\mbox{ made by }\tilde{h}$ $\displaystyle\text{\scriptsize
2}:\quad\mbox{Feed }h(i,\alpha)$ $\displaystyle\text{\scriptsize
3}:\quad\tilde{z}=\tilde{h}(0,x)$ $\displaystyle\text{\scriptsize
4}:\quad\mathbf{return}\ \tilde{z}$ $\mathcal{O}_{\\_}C(m)$ 5: Sm= ~gR(m) 6:
z=~h(0, Sm) 7: $\mathbf{return}$ z $\tilde{g}_{\\_}R(m)$$\sum^{A}_{A_{b}}$
$\displaystyle\text{\scriptsize 1}:\quad Sum=0^{n}$
$\displaystyle\text{\scriptsize 2}:\quad\mathbf{for}\ j=1\mbox{ to }\ell\
\mathbf{do}$ $\displaystyle\text{\scriptsize 3}:\quad\mathmakebox{}\mbox{Run
}\tilde{h}(j,m\oplus R_{\\_}j)$ $\displaystyle\text{\scriptsize
4}:\quad\mathmakebox{}\mathbf{for}\ \mbox{ all queries}(i,\alpha)\mbox{ made
by }\tilde{h}$ $\displaystyle\text{\scriptsize
5}:\quad\mathmakebox{}\mathmakebox{}\mbox{Feed }h(i,\alpha)$
$\displaystyle\text{\scriptsize
6}:\quad\mathmakebox{}u_{\\_}j=\tilde{h}(j,m\oplus R_{\\_}j)$
$\displaystyle\text{\scriptsize 7}:\quad\mathmakebox{}Sum=Sum\oplus u_{\\_}j$
$\displaystyle\text{\scriptsize 8}:\quad\mathbf{endfor}\ $
$\displaystyle\text{\scriptsize 9}:\quad\mathbf{return}\ Sum$

Figure 4: Game $G_{\\_}0$

Game ${\bf G}_{\\_}1$. In this game, we introduce two lists $L_{\\_}f$ and
$L_{\\_}c$. The entries in both the lists are of the form $(m,x,z,\tilde{z})$.
We also introduce two Bad events in the code of $\mathcal{O}_{\\_}h$ as well
as in the code of $\mathcal{O}_{\\_}C$. Notice that, both the subroutine
computes $\tilde{h}(0,\tilde{g}_{\\_}R(m))$.
The first bad event ($\mbox{\sc Bad}_{\\_}1$) happens if
$h(0,\tilde{g}_{\\_}R(m))$ has been set already. This can happen in two ways.
The first one is during a previous $h(0,\tilde{g}_{\\_}R(m^{\prime}))$
computation for a different $m^{\prime}$. In that case there is a collision in
the output of $\tilde{g}_{\\_}R$. The second way is via a
$\mathcal{O}_{\\_}h(0,x)$ query (by the distinguisher or the subverted
implementations). When queried, such an $x$ was not related to a message.
The second bad event happens ($\mbox{\sc Bad}_{\\_}2$) if
$\tilde{h}(0,\tilde{g}_{\\_}R(m))\neq h(0,\tilde{g}_{\\_}R(m))$. In other
words, $\tilde{g}_{\\_}R(m)$ is a subverted point for $\tilde{h}(0,.)$. The
final change is in the introduction of the random oracle $\mathcal{F}$. Our
intention in this game is to program the $h(0,x)$ as $\mathcal{F}(m)$ if
$x=\tilde{g}_{\\_}R(m)$. Hence after the compuation of $\tilde{g}_{\\_}R(m)$,
if we find $h(0,\tilde{g}_{\\_}R(m))$ is not already set ($\mbox{\sc
Bad}_{\\_}1$ did not happen), we set
$h(0,\tilde{g}_{\\_}R(m))=\mathcal{F}(m)$. As we are not changing the
previously set values, the transcript is consistent. Thus, the distinguisher’s
view remains unchanged. Thus we get,

$\displaystyle\Pr[\mathcal{A}^{{\bf G}_{\\_}0}=1]=\Pr[\mathcal{A}^{{\bf
G}_{\\_}1}=1]$

Before moving to the next game, we state the significance of $\mbox{\sc
Bad}_{\\_}2$. Looking ahead, in such a situation, the simulator will not be
able to “program” the output of $\tilde{h}(0,\tilde{g}_{\\_}R(m))$ as
$\mathcal{F}(m)$, and thus loosing the consistency with the random oracle.

pcvstack Game $G_{\\_}1$

$\mathcal{O}_{\\_}h(0,x)$ $\sum^{A}_{A_{b}}$ $\displaystyle\text{\scriptsize
1}:\quad\mathbf{if}\ (*,x,z,*)\in L_{\\_}f$ $\displaystyle\text{\scriptsize
2}:\quad\mathmakebox{}\mathbf{return}\ z$ $\displaystyle\text{\scriptsize
3}:\quad z=h(0,x)$ $\displaystyle\text{\scriptsize 4}:\quad\mbox{Add the
entry}(-,x,z,-)\rightarrow L_{\\_}f$ $\tilde{g}_{\\_}R(m)$$\sum^{A}_{A_{b}}$
$\displaystyle\text{\scriptsize 1}:\quad Sum=0^{n}$
$\displaystyle\text{\scriptsize 2}:\quad\mathbf{for}\ j=1\mbox{ to }\ell\
\mathbf{do}$ $\displaystyle\text{\scriptsize 3}:\quad\mathmakebox{}\mbox{Run
}\tilde{h}(j,m\oplus R_{\\_}j)$ $\displaystyle\text{\scriptsize
4}:\quad\mathbf{for}\ \mbox{all queries }(0,\alpha)\mbox{ made by }\tilde{h}$
$\displaystyle\text{\scriptsize 5}:\quad z=\mathcal{O}_{\\_}h(0,\alpha)$
$\displaystyle\text{\scriptsize 6}:\quad\mathmakebox{}\mathbf{for}\ \mbox{ all
queries}(i>0,\alpha)\mbox{ made by }\tilde{h}$ $\displaystyle\text{\scriptsize
7}:\quad\mathmakebox{}\mathmakebox{}\mbox{Feed }h(i,\alpha)$
$\displaystyle\text{\scriptsize
8}:\quad\mathmakebox{}u_{\\_}j=\tilde{h}(j,m\oplus R_{\\_}j)$
$\displaystyle\text{\scriptsize 9}:\quad\mathmakebox{}Sum=Sum\oplus u_{\\_}j$
$\displaystyle\text{\scriptsize 10}:\quad\mathbf{endfor}\ $
$\displaystyle\text{\scriptsize 11}:\quad\mathbf{return}\ Sum$
$\tilde{h}_{\\_}0(x)$$\sum^{A}_{A_{b}}$ $\displaystyle\text{\scriptsize
1}:\quad\mathbf{for}\ \mbox{all queries }(0,\alpha)\mbox{ made by }\tilde{h}$
$\displaystyle\text{\scriptsize 2}:\quad z=\mathcal{O}_{\\_}h(0,\alpha)$
$\displaystyle\text{\scriptsize 3}:\quad\mathbf{for}\ \mbox{all queries
}(i,\alpha)\mbox{ made by }\tilde{h}$ $\displaystyle\text{\scriptsize
4}:\quad\mbox{Feed }h(i,\alpha)$ $\displaystyle\text{\scriptsize
5}:\quad\tilde{z}=\tilde{h}(0,x)$ $\displaystyle\text{\scriptsize
6}:\quad\mathbf{return}\ \tilde{z}$ $\mathcal{O}_{\\_}h(j,x)$ ($j>0$)7:
$\mathbf{if}$ (j,x,y)∈L$\mathbf{return}$ y 8: m=x$\oplus$Rj 9: $\mathbf{for}$
i=1  to ℓ 10: Add (i,m$\oplus$Ri,f(i,m$\oplus$Ri))  to  L 11:
$\mathbf{endfor}$ 12: Sm= ~gR(m) 13: $\mathbf{if}$ (*,Sm,z,*)∈Lf  for any z
14: Bad1=1 15: $\displaystyle\tilde{z}=\tilde{h}(0,S_{\\_}m)$
$\tilde{z}=\mathcal{F}(m)$ 16: Add the entry(m,Sm,z,~z)→Lf 17: $\mathbf{else}$
18: ~z=z=F(m) 19: Add the entry(m,Sm,z,~z)→Lf 20: ~z’=~h(0, Sm) 21:
$\mathbf{if}$ ~z≠~z’ 22: Bad2=1 23:
$\displaystyle\tilde{z}=\tilde{z^{\prime}}$ Do nothing 24: $\mathbf{endif}$
25: Overwrite the entry(m,Sm,z,~z)→Lf 26: $\mathbf{endif}$ 27: (j,x,y)←L 28:
$\mathbf{return}$ y

Figure 5: Game $G_{\\_}1,G_{\\_}2$ of EXor proof. The boxed entries are
executed in $G_{\\_}1$ whereas the highlighted entries are executed in
$G_{\\_}2$.

Game ${\bf G}_{\\_}2$. In this game, we introduce the changes in the
computation. First, we (re)program $h(0,\tilde{g}_{\\_}R(m))=\mathcal{F}(m)$
even if it was previously set. Moreover, we set $\tilde{z}$, the output of
$O_{\\_}c(m)$ query to always be same as $h(0,\tilde{g}_{\\_}R(m))$. These
modifications create changes in the output in two places. The first one is in
the case of $\mbox{\sc Bad}_{\\_}1$. The second is in the case of $\mbox{\sc
Bad}_{\\_}2$, $\tilde{g}_{\\_}R(m)$ is a subverted point for $\tilde{h}(0,.)$.
The rest of the game remains unchanged. As the two games are identical until
one of the bad event happens, using the fundamental lemma of game playing
proofs,

$\displaystyle\left|\Pr[\mathcal{A}^{{\bf G}_{\\_}1}=1]=\Pr[\mathcal{A}^{{\bf
G}_{\\_}2}=1]\right|\leq\Pr[\mbox{\sc Bad}_{\\_}1\cup\mbox{\sc Bad}_{\\_}2].$

Game $(S^{\mathcal{F}},\mathcal{F})$. It is also easy to see that the output
distribution of the game ${\bf G}_{\\_}2$ is identical to the game
$(S^{\mathcal{F}},\mathcal{F})$.

$\displaystyle\Pr[\mathcal{A}^{{\bf
G}_{\\_}2}=1]=\Pr[\mathcal{A}^{(S^{\mathcal{F}},\mathcal{F})}=1]$

Finally, collecting all the probabilities, we get,

$\displaystyle\Delta_{\\_}{\mathcal{A}_{\\_}2(r,z,R)}\big{(}(h,C^{\tilde{h}}(R,\cdot))\
;\ (S^{\mathcal{F}}(H_{\\_}{z,r},z,R),\mathcal{F})\big{)}\leq\Pr[\mbox{\sc
Bad}_{\\_}1\cup\mbox{\sc Bad}_{\\_}2].$

##  7 Crooked-Indifferentiability of Sponge Construction

pcvstack  Procedure Sponge (Random string $R$, Message
$m_{\\_}1,\cdots,m_{\\_}\ell$)$\sum^{A}_{A_{b}}$
$\displaystyle\text{\scriptsize 1}:\quad x=(x_{\\_}a,x_{\\_}c)=R$
$\displaystyle\text{\scriptsize 2}:\quad\mathbf{for}\ i=0\mbox{ to
}\left\lceil\frac{\ell}{r}\right\rceil-1\ \mathbf{do}$
$\displaystyle\text{\scriptsize
3}:\quad\mathmakebox{}(x_{\\_}a,x_{\\_}c)=h(x_{\\_}a\oplus m_{\\_}i,x_{\\_}c)$
$\displaystyle\text{\scriptsize 4}:\quad\mathbf{endfor}\ $
$\displaystyle\text{\scriptsize 5}:\quad\mathbf{for}\ i=0\mbox{ to
}\left\lceil\frac{h}{r}\right\rceil-1\ \mathbf{do}$
$\displaystyle\text{\scriptsize 6}:\quad\mathmakebox{}\mbox{Append
}x_{\\_}a\mbox{ to output}$ $\displaystyle\text{\scriptsize
7}:\quad\mathmakebox{}(x_{\\_}a,x_{\\_}c)=h(x_{\\_}a,x_{\\_}c)$
$\displaystyle\text{\scriptsize 8}:\quad\mathbf{endfor}\ $

Figure 6: Sponge Based Construction

###  7.1 Sponge Construction

We recall the sponge-construction [5]. Fix positive integers $r,c$, and let
$n=r+c$. Let $h:\\{0,1\\}^{n}\to\\{0,1\\}^{n}$ be a function. The sponge
construction $C^{h}$ maps binary strings of length $\ell$ bits to $s$ bit
binary digest.

###  7.2 Crooked Indifferentiable Sponge Construction

To handle subversion, we randomize the sponge construction by setting the IV
to be equal to the random string $R$. The rest of the construction is
unchanged. Our main result in this section is Theorem 7.1.

###### Theorem 7.1

Let $h:\\{0,1\\}^{n}\to\\{0,1\\}^{n}$ be a random function and
$C^{h}:\\{0,1\\}^{\ell}\to\\{0,1\\}^{s}$ be the sponge construction. Let $r$
be the rate part and $c$ be the capacity part of the chain. Then there exists
a simulator $S$ such that for all $(\kappa,\tau,\epsilon)$ crooked
distinguisher $\mathcal{A}=(\mathcal{A}_{\\_}1,\mathcal{A}_{\\_}2)$

$\displaystyle\mbox{\bf Adv}_{\\_}{\mathcal{A},(C,f)}^{\mbox{\sf crooked-
indiff}}\leq\frac{q^{2}\tau^{2}+q_{\\_}2(\ell+s)\kappa}{2^{c}}+2^{r}\epsilon
q_{\\_}2(\ell+s)$

where $q_{\\_}2$ is the total number of construction queries made by
$\mathcal{A}_{\\_}2$ and $q$ is the total number of blocks in the queries made
by $\mathcal{A}_{\\_}2$.

Proof Sketch. We start from the following observation. If for all construction
query made by $\mathcal{A}_{\\_}2$, none of the intermediate queries (made
$C$to $\tilde{h}$) are subverted, then by the indifferentiability result of
[7], we achieve crooked-indifferentiability. Hence, we say the Bad event
occurs, if for some construction query $M$, made by $\mathcal{A}_{\\_}2$, the
intermediate query is subverted. We bound the Bad probability in the real
world. By the definition of crooked-indifferentiability, the probability that
$\tilde{h}(R)$ is subverted, for a randomly chosen $R$, $h$ is $\epsilon$. By
union bound, the probability that for some $m_{\\_}0\in\\{0,1\\}^{r}$,
$\tilde{h}\left(R\oplus(m\|0^{c})\right)$ is not equal to
$h\left(R\oplus(m\|0^{c})\right)$ is at most $\epsilon 2^{r}$. Conditioned on
the input being “non-subverted”, the output of $\tilde{h}$ is independently
and uniformly distributed. Hence, we get a uniform random chaining value.
Repeating the argument, and taking union bound, we get the following. For any
message $M$, the probability that one of the $\ell+s$ many queries made by
$C^{h}$ is subverted, is at most $(\ell+s)\epsilon 2^{r}$. Taking union bound
over all the queries made by the distinguisher, the probability becomes
bounded by $q(\ell+s)\epsilon 2^{r}$. In addition, the probability that the
$c$-part of the chaining value is equal to the $c$-part of some queries in the
first stage is $\frac{q_{\\_}2(s+\ell)\kappa}{2^{c}}$. Given that none of the
above two events happens, the distinguishing advantage of any adversary is the
same as the standard indifferentiability advantage. For every query $q$, the
simulator needs to run the subverted implementation which makes $\tau$ many
queries for each invocation. Hence, our simulator makes at most $q\tau$ many
queries to the simulator of Bertoni et al  [6]. Thus the advantage of the
adversary is at most
$\frac{q^{2}\tau^{2}+q_{\\_}2(\ell+s)\kappa}{2^{c}}+2^{r}\epsilon
q_{\\_}2(\ell+s)$. For detail proof using game-playing technique, we refer the
reader to Section 8.

##  8 Proof of Theorem 7.1

####  8.0.1 The Simulator

Our simulator emulates the simulator of Bertoni et al [7]. For completeness,
we recall the simulator below. Specifically, we recall the following objects
used in the proof.

####  8.0.2 The Simulator Graph

The simulator maintains a graph $G$ for recording the interactions for $f$.
The vertex set of the graph is
$V(G)\subseteq\\{0,1\\}^{r}\times\\{0,1\\}^{c}$. We represent a $v\in V(G)$ by
an ordered pair $(v_{\\_}r,v_{\\_}c)$ where $v_{\\_}r\in\\{0,1\\}^{r}$ and
$v_{\\_}c\in\\{0,1\\}^{c}$. The (directed) edge set of the graph is
represented by $E(G)$. The simulator also keeps a list
$L\subseteq\\{0,1\\}^{c}$. $L$ is used to ensure that the $c$-part of all the
responses of the simulators are unique.

####  8.0.3 NewNode Algorithm.

The algorithm Newnode samples a node randomly in the simulator graph.

####  8.0.4 Findpath Algorithm

The Findpath algorithms finds a message $m\in\\{0,1\\}^{\leq\ell}$ such that
evaluating $C$ with the random string $R$ as IV, message $m$ and simulator’s
responses so far will generate $x$ as a query to $f$. In other words, $x$ will
be a chaining value in the computation of $C_{\\_}R^{h}(m)$.

####  8.0.5 Simulating $f$ in Stage I

We denote our simulator using $\hat{S}$. In the first stage, $\hat{S}$
simulates $f$ honestly. $\hat{S}$ starts with a _local copy_ of the simulator
graph with all the nodes, but no edges ($E(G)=\emptyset$) and an empty list
$L$. When queried with a new input $x$, the simulator generates
$y_{\\_}c\xleftarrow{\mbox{\tiny${\$}$}}\\{0,1\\}^{c}\setminus L$ and
$y_{\\_}r\xleftarrow{\mbox{\tiny${\$}$}}\\{0,1\\}^{r}$, creates node
$(y_{\\_}r,y_{\\_}c)$, and adds an edge $(x,(y_{\\_}r,y_{\\_}c))$ to $E(G)$.
$\hat{S}$ updates $L$ by including $y_{\\_}c$ to the list.

pcvstack  Procedure $\hat{S}_{\\_}1(x)$ //  Stage I$\sum^{A}_{A_{b}}$
$\displaystyle\text{\scriptsize 1}:\quad\mathbf{if}\ \exists(x,y)\in
E(G^{\prime})~{}\mathbf{return}\ y$ $\displaystyle\text{\scriptsize
2}:\quad\mathbf{else}\ $ $\displaystyle\text{\scriptsize
3}:\quad~{}y_{\\_}c\xleftarrow{\mbox{\tiny${\$}$}}\\{0,1\\}^{c}\setminus L$
$\displaystyle\text{\scriptsize
4}:\quad~{}y_{\\_}r\xleftarrow{\mbox{\tiny${\$}$}}\\{0,1\\}^{r}$
$\displaystyle\text{\scriptsize 5}:\quad~{}y=(y_{\\_}r,y_{\\_}c)$
$\displaystyle\text{\scriptsize
6}:\quad~{}E(G^{\prime})=E(G^{\prime})\cup(x,y)$
$\displaystyle\text{\scriptsize 7}:\quad~{}L=L\cup y_{\\_}c$
$\displaystyle\text{\scriptsize 8}:\quad~{}\mathbf{return}\ y$
$\displaystyle\text{\scriptsize 9}:\quad\mathbf{endif}\ $ Procedure
$\hat{S}_{\\_}2(R,x)$ //  Stage II with fixed random string $R$10:
$\mathbf{if}$ ∃(x,y)∈E(G) $\mathbf{return}$ y 11: $\mathbf{if}$ x=R mark x 12:
$\mathbf{if}$ x  is marked 13: Run ~h(x) 14: $\mathbf{for}$ every query  xj
made by  ~h 15: Feed  y=Sim(xj) 16: $\mathbf{endfor}$ 17: ~y= ~h(x) 18:
$\mathbf{if}$ ~y≠Sim(x) 19: Bad=1 20: $\mathbf{return}$ ⟂ 21: $\mathbf{endif}$
22: $\mathbf{endif}$ 23: $\mathbf{return}$ Sim(x)

Figure 7: Simulator for Sponge Construction. $S_{\\_}2$ is initialized with
$z,R$ and $\tilde{h}$.

pcvstack  Procedure $Newnode$$\sum^{A}_{A_{b}}$
$\displaystyle\text{\scriptsize 1}:\quad\mathbf{if}\ |L|=2^{c}\mathbf{return}\
\perp$ $\displaystyle\text{\scriptsize 2}:\quad
y_{\\_}c\xleftarrow{\mbox{\tiny${\$}$}}\\{0,1\\}^{c}\setminus L$
$\displaystyle\text{\scriptsize 3}:\quad
y_{\\_}r\xleftarrow{\mbox{\tiny${\$}$}}\\{0,1\\}^{r}$
$\displaystyle\text{\scriptsize 4}:\quad L=L\cup y_{\\_}c$
$\displaystyle\text{\scriptsize 5}:\quad\mathbf{return}\
y=(y_{\\_}c,y_{\\_}r)$ Procedure $Findpath(R,x)$$\sum^{A}_{A_{b}}$
$\displaystyle\text{\scriptsize 1}:\quad p=\lambda$
$\displaystyle\text{\scriptsize 2}:\quad\mathbf{if}\ x=r~{}\mathbf{return}\ p$
$\displaystyle\text{\scriptsize 3}:\quad\mathbf{else}\ $
$\displaystyle\text{\scriptsize 4}:\quad~{}~{}\mbox{Parse
}x=(x_{\\_}r,x_{\\_}c)$ $\displaystyle\text{\scriptsize
5}:\quad~{}~{}\mbox{Find }\hat{x}_{\\_}r\mbox{ such that}$
$\displaystyle~{}~{}~{}\left((t,(\hat{x}_{\\_}r,x_{\\_}c))\in
E(G)\right)\wedge t\mbox{ is marked}$ $\displaystyle\text{\scriptsize
6}:\quad~{}~{}m^{\prime}=x_{\\_}r\oplus\hat{x}_{\\_}r$
$\displaystyle\text{\scriptsize 7}:\quad~{}~{}p^{\prime}=Findpath(r,t)$
$\displaystyle\text{\scriptsize 8}:\quad p=p^{\prime}||m^{\prime}$
$\displaystyle\text{\scriptsize 9}:\quad\mathbf{return}\ p$ Procedure $Sim(x)$
//  Bertoni etal simulator [7]$\sum^{A}_{A_{b}}$
$\displaystyle\text{\scriptsize 1}:\quad\mathbf{if}\ \exists(x,y)\in
E(G)~{}\mathbf{return}\ y$ $\displaystyle\text{\scriptsize 2}:\quad
L=L\cup\\{x_{\\_}c\\}$ $\displaystyle\text{\scriptsize 3}:\quad\mathbf{if}\
x\mbox{ is marked}$ $\displaystyle\text{\scriptsize
4}:\quad~{}~{}m=Findpath(R,x)$ $\displaystyle\text{\scriptsize
5}:\quad~{}~{}\mathbf{if}\ |m|<\ell$ $\displaystyle\text{\scriptsize
6}:\quad~{}~{}~{}~{}y=Newnode()$ $\displaystyle\text{\scriptsize
7}:\quad~{}~{}~{}~{}E(G)=E(G)\cup(x,y)$ $\displaystyle\text{\scriptsize
8}:\quad~{}~{}~{}~{}\mbox{Mark all node }(*,y_{\\_}c)$
$\displaystyle\text{\scriptsize 9}:\quad~{}~{}~{}~{}\mathbf{return}\ y$
$\displaystyle\text{\scriptsize 10}:\quad~{}~{}\mathbf{else}\ {\mbox{/\\!\\!/
}\text{\scriptsize$|m|=\ell$}}$ $\displaystyle\text{\scriptsize
11}:\quad~{}~{}~{}~{}z=\mathcal{F}(m)$ $\displaystyle\text{\scriptsize
12}:\quad~{}~{}~{}~{}\mbox{Break
}z=z_{\\_}1||z_{\\_}2||\cdots||z_{\\_}t{\mbox{/\\!\\!/
}\text{\scriptsize$tr=s$}}$ $\displaystyle\text{\scriptsize
13}:\quad~{}~{}~{}~{}y^{(0)}=x$ $\displaystyle\text{\scriptsize
14}:\quad~{}~{}~{}~{}\mathbf{for}\ i=1~{}\mbox{to}~{}t\ \mathbf{do}$
$\displaystyle\text{\scriptsize
15}:\quad~{}~{}~{}~{}~{}~{}y_{\\_}c\xleftarrow{\mbox{\tiny${\$}$}}\\{0,1\\}^{c}\setminus
L$ $\displaystyle\text{\scriptsize
16}:\quad~{}~{}~{}~{}~{}~{}y_{\\_}r=z_{\\_}i$ $\displaystyle\text{\scriptsize
17}:\quad~{}~{}~{}~{}~{}~{}y^{(j)}=(y_{\\_}r,y_{\\_}c)$
$\displaystyle\text{\scriptsize
18}:\quad~{}~{}~{}~{}~{}~{}E(G)=E(G)\cup(y^{(j-1)},y^{(j)})$
$\displaystyle\text{\scriptsize
19}:\quad~{}~{}~{}~{}~{}~{}L=L\cup\\{y_{\\_}c\\}$
$\displaystyle\text{\scriptsize 20}:\quad~{}~{}~{}~{}\mathbf{endfor}\ $
$\displaystyle\text{\scriptsize 21}:\quad~{}~{}~{}~{}\mathbf{return}\ y^{(1)}$
$\displaystyle\text{\scriptsize 22}:\quad~{}~{}\mathbf{endif}\ $
$\displaystyle\text{\scriptsize 23}:\quad\mathbf{else}\ {\mbox{/\\!\\!/
}\text{\scriptsize x is unmarked}}$ $\displaystyle\text{\scriptsize
24}:\quad~{}~{}~{}~{}y=Newnode()$ $\displaystyle\text{\scriptsize
25}:\quad~{}~{}~{}~{}E(G)=E(G)\cup(x,y)$ $\displaystyle\text{\scriptsize
26}:\quad~{}~{}~{}~{}\mathbf{return}\ y$ $\displaystyle\text{\scriptsize
27}:\quad\mathbf{endif}\ $

Figure 8: Bertoni et al Simulator for Classical indifferentiability of Sponge
Construction.[7]

####  8.0.6 Simulating $f$ in Stage II

The simulator gets the implementation $\tilde{h}$, along with the advice
string $z$. In addition, the simulator receives the random string
$R\in\\{0,1\\}^{n}$. $S$ initializes by _marking_ the node $R$ in the
simulator graph. Following the simulator of [7], the idea of marking a node
$x$ is to declare that there is a path in the simulator graph from the root
$R$ to $x$.

Now, the simulator invokes $\tilde{h}$ on input $x$. For each query $x_{\\_}i$
made by $\tilde{h}$, $\hat{S}$ forwards the query to the simulator $Sim$ as a
query and upon receiving an answer, forwards it to the distinguisher. Finally
when $\tilde{h}(x)$ returns a value, $\hat{S}$ checks whether
$\tilde{h}(x)=Sim(x)$. If the check fails, the simulator raises the flag ${\sc
Bad}0$ and aborts. Otherwise, it returns $Sim(x)$.

####  8.0.7 Proving the Crooked Indifferentiability.

The detail of the games and transitional probabilities are described in
Section8.1. The crooked indifferentiability is proved via the following lemma.

###### Lemma 7

If Bad does not happen then $\epsilon\leq\frac{q^{2}\tau^{2}}{2^{c}}$.
Moreover,

$\displaystyle\Pr[\mbox{\sc Bad}]\leq q_{\\_}2(\ell+s)\epsilon\cdot
2^{r}+\frac{q_{\\_}2(\ell+s)\kappa}{2^{c}}$

####  8.0.8 Proof of Lemma 7.

If Bad does not happen, then our simulator emulates the simulator of [7]
perfectly. Note, the Newnode subroutine does not sample any $x_{\\_}c$ such
that for some $x_{\\_}r$, $(x_{\\_}r,x_{\\_}c)\in z$. Moreover, none of the
marked nodes in the tree is subverted. Hence, in that case, the classical
indifferentiability simulator perfectly simulates $f$ maintaining consistency
with the random oracle $F$. By the classical indifferentiability theorem of
[7], $\epsilon\leq\frac{q^{2}\tau^{2}}{2^{c}}$. Here $\tau$is the number of
queries made by the implementation.

Recall that the event Bad happens if for some marked node $x$ in the graph,
$x$ is subverted; $\tilde{h}(x)\neq h(x)$. We say a simulator query to be safe
if it is unsubverted or the $c$ part of the output does not match with any
input of the transcript of $\mathcal{A}_{\\_}1$.Observe that for each safe
query $x$, $h(x)$ is uniformly distributed.

Let $E_{\\_}i$ denote the event that $i^{th}$ query made by $\mathcal{A}$ to
the simulator, the input $x_{\\_}i$ is marked and $x_{\\_}i$ is not safe. .
$x_{\\_}i=x_{\\_}r||x_{\\_}c$. If $x_{\\_}i$ is marked, then for some marked
$x_{\\_}j$, $j<i$, and for some $m_{\\_}i\in\\{0,1\\}^{r}$,
$x_{\\_}i=m||0^{c}\oplus\tilde{h}(x_{\\_}j)$. Conditioned on $x_{\\_}j$ is
safe, $\tilde{h}(x_{\\_}j)=h(x_{\\_}j)$ is uniformly distributed. Hence,
$x_{\\_}c$ is independently distributed. By definition of subversion, and
taking union bound over all possible $x_{\\_}r$, the probability
$\tilde{h}(x_{\\_}i)$ is subverted is bounded by $\epsilon\cdot 2^{r}$. Given
that $\tilde{h}(x_{\\_}i)$ is not subverted, the probability of the $c$-part
of the output matches with the $c$-part of some query of $\mathcal{A}_{\\_}1$
is $\frac{\kappa}{2^{c}}$

$\displaystyle\Pr[\mbox{\sc Bad}]$
$\displaystyle\leq\sum_{\\_}{i=1}^{q}\Pr[E_{\\_}i|\wedge_{\\_}{j=1}^{i-1}E_{\\_}j]$
$\displaystyle\leq\sum_{\\_}{i=1}^{q}\left(\epsilon\cdot
2^{r}\right)+\frac{\kappa}{2^{c}}$
$\displaystyle=q_{\\_}2(\ell+s)\epsilon\cdot
2^{r}+\frac{q_{\\_}2(\ell+s)\kappa}{2^{c}}$

pcvstack Game $(h,C^{\tilde{h}})$

$\mathcal{O}_{\\_}h(x)$ $\sum^{A}_{A_{b}}$ $\displaystyle\text{\scriptsize
1}:\quad\mathbf{return}\ h(x)$ $\mathcal{O}_{\\_}C(m)$$\sum^{A}_{A_{b}}$
$\displaystyle\text{\scriptsize 1}:\quad
x=(x_{\\_}a,x_{\\_}c)=(R_{\\_}0,R_{\\_}1)$ $\displaystyle\text{\scriptsize
2}:\quad\mathbf{for}\ i=0\mbox{ to }\left\lceil\frac{\ell}{r}\right\rceil-1\
\mathbf{do}$ $\displaystyle\text{\scriptsize
3}:\quad\mathmakebox{}(x_{\\_}a,x_{\\_}c)=\tilde{h}(x_{\\_}a\oplus
m_{\\_}i,x_{\\_}c)$ $\displaystyle\text{\scriptsize 4}:\quad\mathbf{endfor}\ $
$\displaystyle\text{\scriptsize 5}:\quad\mathbf{for}\ i=0\mbox{ to
}\left\lceil\frac{s}{r}\right\rceil-1\ \mathbf{do}$
$\displaystyle\text{\scriptsize 6}:\quad\mathmakebox{}\mbox{Append
}x_{\\_}a\mbox{ to output}$ $\displaystyle\text{\scriptsize
7}:\quad\mathmakebox{}(x_{\\_}a,x_{\\_}c)=\tilde{h}(x_{\\_}a,x_{\\_}c)$
$\displaystyle\text{\scriptsize 8}:\quad\mathbf{endfor}\ $ Game $({\bf
G}_{\\_}0)$ $\mathcal{O}_{\\_}h(x)$ ($i\in[\ell]$)$\sum^{A}_{A_{b}}$
$\displaystyle\text{\scriptsize 1}:\quad\mathbf{return}\ \mathcal{G}(1,x)$
$\mathcal{O}_{\\_}C(m)$$\sum^{A}_{A_{b}}$ $\displaystyle\text{\scriptsize
1}:\quad x=(x_{\\_}a,x_{\\_}c)=(R_{\\_}0,R_{\\_}1)$
$\displaystyle\text{\scriptsize 2}:\quad\mathbf{for}\ i=0\mbox{ to
}\left\lceil\frac{\ell}{r}\right\rceil-1\ \mathbf{do}$
$\displaystyle\text{\scriptsize
3}:\quad\mathmakebox{}(x_{\\_}a,x_{\\_}c)=\mathcal{G}(0,x_{\\_}a\oplus
m_{\\_}i,x_{\\_}c)$ $\displaystyle\text{\scriptsize 4}:\quad\mathbf{endfor}\ $
$\displaystyle\text{\scriptsize 5}:\quad\mathbf{for}\ i=0\mbox{ to
}\left\lceil\frac{s}{r}\right\rceil-1\ \mathbf{do}$
$\displaystyle\text{\scriptsize 6}:\quad\mathmakebox{}\mbox{Append
}x_{\\_}a\mbox{ to output}$ $\displaystyle\text{\scriptsize
7}:\quad\mathmakebox{}(x_{\\_}a,x_{\\_}c)=\mathcal{G}(0,x_{\\_}a,x_{\\_}c)$
$\displaystyle\text{\scriptsize 8}:\quad\mathbf{endfor}\ $
$\mathcal{G}(i,x)$$\sum^{A}_{A_{b}}$ $\displaystyle\text{\scriptsize 1}:\quad
y=\tilde{y}=h(x)$ $\displaystyle\text{\scriptsize 2}:\quad\mathbf{if}\
i=1~{}~{}\mathbf{return}\ y$ $\displaystyle\text{\scriptsize
3}:\quad\mathbf{else}\ $ $\displaystyle\text{\scriptsize
4}:\quad\mathmakebox{}\mbox{Run}\tilde{h}(x)$ $\displaystyle\text{\scriptsize
5}:\quad\mathmakebox{}\mathbf{for}\ \mbox{ every query }x_{\\_}j\mbox{ made by
}\tilde{h}$ $\displaystyle\text{\scriptsize
6}:\quad\mathmakebox{}\mathmakebox{}\mbox{Feed }y=h(x_{\\_}j)$
$\displaystyle\text{\scriptsize 7}:\quad\mathmakebox{}\mathbf{endfor}\ $
$\displaystyle\text{\scriptsize 8}:\quad\mathmakebox{}\tilde{y}=\tilde{h}(x)$
$\displaystyle\text{\scriptsize 9}:\quad\mathmakebox{}\mathbf{return}\
\tilde{y}$ $\displaystyle\text{\scriptsize 10}:\quad\mathbf{endif}\ $

Figure 9: Game $\mathsf{Real~{}}$ and Game ${\bf G}_{\\_}0$

###  8.1 Game Transitions

Our crooked-indifferentiability proof relies on four intermediate game,
denoted by ${\bf G}_{\\_}0,{\bf G}_{\\_}1,{\bf G}_{\\_}1,$ and ${\bf
G}_{\\_}2$. We start with the real game $(h,C^{\tilde{h}})$. There are two
public interfaces for the adversary to query. The first one is
$\mathcal{O}_{\\_}h$, which can be used to interact with the function $h$. The
other one is $\mathcal{O}_{\\_}C$, which can be used to compute
$C^{\tilde{h}}$. In the intermediate games we shall use additional subroutine
$\mathcal{G}$.

Game ${\bf G}_{\\_}0$.  In this game, we introduce the subroutine
$\mathcal{G}$ which acts as a common interface to $h,\tilde{h}$. We modify the
$\mathcal{O}_{\\_}h$ and $\mathcal{O}_{\\_}C$ subroutine. For queries to $h$,
$\mathcal{G}$ is called with parameter $h$ whereas for $\tilde{h}$ the
parameter value is set to be 0. These changes are ornamental and do not change
the output for any of the query. Hence

$\displaystyle\Pr[\mathcal{A}^{h,C^{\tilde{h}}}=1]=\Pr[\mathcal{A}^{{\bf
G}_{\\_}0}=1]$

pcvstack Game ${\bf G}_{\\_}1a,\mbox{{\hbox{\pagecolor{highlight-gray}${\bf
G}_{\\_}1b$}} }$

$\mathcal{O}_{\\_}h(x)$ $\sum^{A}_{A_{b}}$ $\displaystyle\text{\scriptsize
1}:\quad\mathbf{return}\ \mathcal{G}(1,x)$
$\mathcal{O}_{\\_}C(m)$$\sum^{A}_{A_{b}}$ $\displaystyle\text{\scriptsize
1}:\quad x=(x_{\\_}a,x_{\\_}c)=(R_{\\_}0,R_{\\_}1)$
$\displaystyle\text{\scriptsize 2}:\quad\mathbf{for}\ i=0\mbox{ to
}\left\lceil\frac{\ell}{r}\right\rceil-1\ \mathbf{do}$
$\displaystyle\text{\scriptsize
3}:\quad\mathmakebox{}(x_{\\_}a,x_{\\_}c)=\mathcal{G}(0,x_{\\_}a\oplus
m_{\\_}i,x_{\\_}c)$ $\displaystyle\text{\scriptsize 4}:\quad\mathbf{endfor}\ $
$\displaystyle\text{\scriptsize 5}:\quad\mathbf{for}\ i=0\mbox{ to
}\left\lceil\frac{s}{r}\right\rceil-1\ \mathbf{do}$
$\displaystyle\text{\scriptsize 6}:\quad\mathmakebox{}\mbox{Append
}x_{\\_}a\mbox{ to output}$ $\displaystyle\text{\scriptsize
7}:\quad\mathmakebox{}(x_{\\_}a,x_{\\_}c)=\mathcal{G}(0,x_{\\_}a,x_{\\_}c)$
$\displaystyle\text{\scriptsize 8}:\quad\mathbf{endfor}\ $
$\mathcal{G}(i,x)$$\sum^{A}_{A_{b}}$ $\displaystyle\text{\scriptsize 1}:\quad
y=\tilde{y}=h(x)$ $\displaystyle\text{\scriptsize 2}:\quad\mathbf{if}\
i=1~{}~{}\mathbf{return}\ y$ $\displaystyle\text{\scriptsize
3}:\quad\mbox{Run}\tilde{h}(x)$ $\displaystyle\text{\scriptsize
4}:\quad\mathbf{for}\ \mbox{ every query }x_{\\_}j\mbox{ made by }\tilde{h}$
$\displaystyle\text{\scriptsize 5}:\quad\mathmakebox{}\mbox{Feed
}y=h(x_{\\_}j)$ $\displaystyle\text{\scriptsize 6}:\quad\mathbf{endfor}\ $
$\displaystyle\text{\scriptsize 7}:\quad\mathbf{if}\ {\tilde{h}(x)\neq h(x)}$
$\displaystyle\text{\scriptsize 8}:\quad\mathmakebox{}\mbox{\sc Bad}=1$
$\displaystyle\text{\scriptsize
9}:\quad{\framebox{$\displaystyle\tilde{y}=\tilde{h}(x)$}}~{}~{}{\hbox{\pagecolor{highlight-
gray}$\tilde{y}=h(x)$}}$ $\displaystyle\text{\scriptsize
10}:\quad\mathbf{return}\ \tilde{y}$ $\displaystyle\text{\scriptsize
11}:\quad\mathbf{endif}\ $ Game $({\bf G}_{\\_}2)$ $\mathcal{O}_{\\_}h(x)$
$\sum^{A}_{A_{b}}$ $\displaystyle\text{\scriptsize 1}:\quad\mathbf{return}\
\mathcal{G}(1,x)$ $\mathcal{O}_{\\_}C(m)$$\sum^{A}_{A_{b}}$
$\displaystyle\text{\scriptsize 1}:\quad
x=(x_{\\_}a,x_{\\_}c)=(R_{\\_}0,R_{\\_}1)$ $\displaystyle\text{\scriptsize
2}:\quad\mathbf{for}\ i=0\mbox{ to }\left\lceil\frac{\ell}{r}\right\rceil-1\
\mathbf{do}$ $\displaystyle\text{\scriptsize
3}:\quad\mathmakebox{}(x_{\\_}a,x_{\\_}c)=h(,x_{\\_}a\oplus
m_{\\_}i,x_{\\_}c)$ $\displaystyle\text{\scriptsize 4}:\quad\mathbf{endfor}\ $
$\displaystyle\text{\scriptsize 5}:\quad\mathbf{for}\ i=0\mbox{ to
}\left\lceil\frac{s}{r}\right\rceil-1\ \mathbf{do}$
$\displaystyle\text{\scriptsize 6}:\quad\mathmakebox{}\mbox{Append
}x_{\\_}a\mbox{ to output}$ $\displaystyle\text{\scriptsize
7}:\quad\mathmakebox{}(x_{\\_}a,x_{\\_}c)=h(x_{\\_}a,x_{\\_}c)$
$\displaystyle\text{\scriptsize 8}:\quad\mathbf{endfor}\ $
$\mathcal{G}(i,x)$$\sum^{A}_{A_{b}}$ $\displaystyle\text{\scriptsize 1}:\quad
y=\tilde{y}=h(x)$ $\displaystyle\text{\scriptsize 2}:\quad\mathbf{if}\
i=1~{}~{}\mathbf{return}\ y$ $\displaystyle\text{\scriptsize
3}:\quad\mbox{Run}\tilde{h}(x)$ $\displaystyle\text{\scriptsize
4}:\quad\mathbf{for}\ \mbox{ every query }x_{\\_}j\mbox{ made by }\tilde{h}$
$\displaystyle\text{\scriptsize 5}:\quad\mathmakebox{}\mbox{Feed
}y=h(x_{\\_}j)$ $\displaystyle\text{\scriptsize 6}:\quad\mathbf{endfor}\ $
$\displaystyle\text{\scriptsize 7}:\quad\mathbf{if}\ {\tilde{h}(x)\neq h(x)}$
$\displaystyle\text{\scriptsize 8}:\quad\mathmakebox{}\mbox{\sc Bad}=1$
$\displaystyle\text{\scriptsize 9}:\quad\tilde{y}=h(x)$
$\displaystyle\text{\scriptsize 10}:\quad\mathbf{return}\ \tilde{y}$
$\displaystyle\text{\scriptsize 11}:\quad\mathbf{endif}\ $

Figure 10: Game ${\bf G}_{\\_}1a,{\bf G}_{\\_}1b,{\bf G}_{\\_}2$. In the game
${\bf G}_{\\_}1b$ the highlighted statement will be executed instead of the
boxed statement.

Game ${\bf G}_{\\_}1a$. In this game, we modify the subroutine $\mathcal{G}$.
When queried with $(0,x)$ for intended value of $\tilde{h}(x)$, $\mathcal{G}$
checks whether $\tilde{h}(x)=h(x)$. If the equality does not hold
$\mathcal{G}$ sets the Bad flag. However, it still returns $\tilde{h}(x)$. As
the output of any query does not change,

$\displaystyle\Pr[\mathcal{A}^{{\bf G}_{\\_}0}=1]=\Pr[\mathcal{A}^{{\bf
G}_{\\_}1a}=1]$

Game ${\bf G}_{\\_}1b$. In this game, when Bad flag is set, $h(x)$ is
returned. Everything else remain unchanged. Using the fundamental lemma of
game playing proof,

$\displaystyle\left|\Pr[\mathcal{A}^{{\bf G}_{\\_}1a}=1]-\Pr[\mathcal{A}^{{\bf
G}_{\\_}1b}=1]\right|\leq\Pr[\mbox{\sc Bad}]$

Game ${\bf G}_{\\_}2$. We note that in game ${\bf G}_{\\_}1$, all the
$\mathcal{G}(x)$ queries made by $O_{\\_}c$ is answered with $h(x)$. Hence, in
Game ${\bf G}_{\\_}2$, we give $O_{\\_}c$ direct access to $h$. Output
distribution of the game remains exactly same after this change. Hence,

$\displaystyle\Pr[\mathcal{A}^{{\bf G}_{\\_}1b}=1]=\Pr[\mathcal{A}^{{\bf
G}_{\\_}2}=1]$

Game ${\bf G}_{\\_}3$. We replace the oracles $(h,C^{h})$ by
$(S,\mathcal{F}^{S})$ where $S$ is the simulator of Bertoni et al  [7]. By the
results in [7],

$\displaystyle\left|\Pr[\mathcal{A}^{{\bf G}_{\\_}2}=1]-\Pr[\mathcal{A}^{{\bf
G}_{\\_}3}=1]\right|\leq\frac{q^{2}\tau^{2}}{2^{c}}.$

Note that the numerator in the right hand side is the square of total number
of queries made to the simulator, which in Game ${\bf G}_{\\_}3$, $q\tau$ as
the implementation makes $\tau$ many queries for each invocation.

Finally, we observe that $\mathcal{G}$ works identically with the second stage
simulator of Figure7. So As we initialize the simulator of [7] with $L$ from
the stage I, the two games are identical. Hence we get,

$\displaystyle\Pr[\mathcal{A}^{{\bf
G}_{\\_}3}=1]=\Pr[\mathcal{A}^{(S^{\mathcal{F}},\mathcal{F})}=1]$

Collecting all the probabilities, we get

$\displaystyle\Delta_{\\_}{\mathcal{A}_{\\_}2(r,z,R)}\big{(}(h,C^{\tilde{h}}(R,\cdot))\
;\ (S^{\mathcal{F}}(H_{\\_}{z,r},z,R),\mathcal{F})\big{)}$
$\displaystyle\leq\Pr[\mbox{\sc Bad}]+\frac{q^{2}\tau^{2}}{2^{c}}$
$\displaystyle\leq\frac{q^{2}\tau^{2}+q_{\\_}2(\ell+s)\kappa}{2^{c}}+q_{\\_}2(\ell+s)\epsilon
2^{r}.$

pcvstack Game $({\bf G}_{\\_}3)$

$\mathcal{O}_{\\_}h(x)$ $\sum^{A}_{A_{b}}$ $\displaystyle\text{\scriptsize
1}:\quad\mathbf{return}\ \mathcal{G}(1,x)$
$\mathcal{O}_{\\_}C(m)$$\sum^{A}_{A_{b}}$ $\displaystyle\text{\scriptsize
1}:\quad\mathbf{return}\ \mathcal{F}(m)$ $\mathcal{G}(i,x)$2: y=~y=h(x) 3:
$\mathbf{if}$ i=1 $\mathbf{return}$ y 4: Run ~h(x) 5: $\mathbf{for}$ every
query  xj  made by  ~h 6: Feed  y=Sim(xj) 7: $\mathbf{endfor}$ 8:
$\mathbf{if}$ ~h(x)≠Sim(x) 9: Bad=1 10: ~y= Sim(x) 11: $\mathbf{return}$ ~y
12: $\mathbf{endif}$

Figure 11: Game ${\bf G}_{\\_}3$

##  9 Conclusion

In this paper, we revisited the recently introduced crooked
indifferentiability notion. We showed that the proof of crooked
indifferentiability of enveloped XOR construction in [17] is incomplete. We
developed new technique to prove crooked indifferentiability of the same
construction. We also show that the sponge construction with randomized
initial value is also crooked indifferentiable secure hash function.

## References

  * [1] Ateniese, G., Francati, D., Magri, B., Venturi, D.: Public immunization against complete subversion without random oracles. In: Deng, R.H., Gauthier-Umaña, V., Ochoa, M., Yung, M. (eds.) ACNS 19. LNCS, vol. 11464, pp. 465–485. Springer, Heidelberg (Jun 2019). https://doi.org/10.1007/978-3-030-21568-223
  * [2] Ateniese, G., Magri, B., Venturi, D.: Subversion-resilient signature schemes. In: Ray, I., Li, N., Kruegel, C. (eds.) ACM CCS 2015. pp. 364–375. ACM Press (Oct 2015). https://doi.org/10.1145/2810103.2813635
  * [3] Bellare, M., Hoang, V.T.: Resisting randomness subversion: Fast deterministic and hedged public-key encryption in the standard model. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015, Part II. LNCS, vol. 9057, pp. 627–656. Springer, Heidelberg (Apr 2015). https://doi.org/10.1007/978-3-662-46803-621
  * [4] Bellare, M., Paterson, K.G., Rogaway, P.: Security of symmetric encryption against mass surveillance. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014, Part I. LNCS, vol. 8616, pp. 1–19. Springer, Heidelberg (Aug 2014). https://doi.org/10.1007/978-3-662-44371-21
  * [5] Bertoni, G., Daemen, J., Peeters, M., Assche, G.: Sponge functions. ECRYPT Hash Workshop 2007 (01 2007)
  * [6] Bertoni, G., Daemen, J., Peeters, M., Assche, G.V.: On the indifferentiability of the sponge construction. In: Advances in Cryptology - EUROCRYPT 2008, 27th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Istanbul, Turkey, April 13-17, 2008. Proceedings. pp. 181–197 (2008), https://doi.org/10.1007/978-3-540-78967-3_11
  * [7] Bertoni, G., Daemen, J., Peeters, M., Van Assche, G.: On the indifferentiability of the sponge construction. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 181–197. Springer, Heidelberg (Apr 2008). https://doi.org/10.1007/978-3-540-78967-311
  * [8] Chow, S.S.M., Russell, A., Tang, Q., Yung, M., Zhao, Y., Zhou, H.S.: Let a non-barking watchdog bite: Cliptographic signatures with an offline watchdog. In: Lin, D., Sako, K. (eds.) PKC 2019, Part I. LNCS, vol. 11442, pp. 221–251. Springer, Heidelberg (Apr 2019). https://doi.org/10.1007/978-3-030-17253-48
  * [9] Coron, J.S., Dodis, Y., Malinaud, C., Puniya, P.: Merkle-Damgård revisited: How to construct a hash function. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 430–448. Springer, Heidelberg (Aug 2005). https://doi.org/10.1007/1153521826
  * [10] Degabriele, J.P., Farshim, P., Poettering, B.: A more cautious approach to security against mass surveillance. In: Leander, G. (ed.) FSE 2015. LNCS, vol. 9054, pp. 579–598. Springer, Heidelberg (Mar 2015). https://doi.org/10.1007/978-3-662-48116-528
  * [11] Degabriele, J.P., Paterson, K.G., Schuldt, J.C.N., Woodage, J.: Backdoors in pseudorandom number generators: Possibility and impossibility results. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016, Part I. LNCS, vol. 9814, pp. 403–432. Springer, Heidelberg (Aug 2016). https://doi.org/10.1007/978-3-662-53018-415
  * [12] Dodis, Y., Ganesh, C., Golovnev, A., Juels, A., Ristenpart, T.: A formal treatment of backdoored pseudorandom generators. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015, Part I. LNCS, vol. 9056, pp. 101–126. Springer, Heidelberg (Apr 2015). https://doi.org/10.1007/978-3-662-46800-55
  * [13] Maurer, U.M., Renner, R., Holenstein, C.: Indifferentiability, impossibility results on reductions, and applications to the random oracle methodology. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 21–39. Springer, Heidelberg (Feb 2004). https://doi.org/10.1007/978-3-540-24638-12
  * [14] Mironov, I., Stephens-Davidowitz, N.: Cryptographic reverse firewalls. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015, Part II. LNCS, vol. 9057, pp. 657–686. Springer, Heidelberg (Apr 2015). https://doi.org/10.1007/978-3-662-46803-622
  * [15] Russell, A., Tang, Q., Yung, M., Zhou, H.S.: Cliptography: Clipping the power of kleptographic attacks. In: Cheon, J.H., Takagi, T. (eds.) ASIACRYPT 2016, Part II. LNCS, vol. 10032, pp. 34–64. Springer, Heidelberg (Dec 2016). https://doi.org/10.1007/978-3-662-53890-62
  * [16] Russell, A., Tang, Q., Yung, M., Zhou, H.S.: Generic semantic security against a kleptographic adversary. In: Thuraisingham, B.M., Evans, D., Malkin, T., Xu, D. (eds.) ACM CCS 2017. pp. 907–922. ACM Press (Oct / Nov 2017). https://doi.org/10.1145/3133956.3133993
  * [17] Russell, A., Tang, Q., Yung, M., Zhou, H.S.: Correcting subverted random oracles. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018, Part II. LNCS, vol. 10992, pp. 241–271. Springer, Heidelberg (Aug 2018). https://doi.org/10.1007/978-3-319-96881-09
  * [18] Young, A., Yung, M.: The dark side of “black-box” cryptography, or: Should we trust capstone? In: Koblitz, N. (ed.) CRYPTO’96. LNCS, vol. 1109, pp. 89–103. Springer, Heidelberg (Aug 1996). https://doi.org/10.1007/3-540-68697-58
  * [19] Young, A., Yung, M.: Kleptography: Using cryptography against cryptography. In: Fumy, W. (ed.) EUROCRYPT’97. LNCS, vol. 1233, pp. 62–74. Springer, Heidelberg (May 1997). https://doi.org/10.1007/3-540-69053-06

## Appendix

##  10 Leftout Definitions

Detection Algorithm. Given an implementation one may check the correctness of
the algorithm by comparing the outputs of the implementation with a known
correct algorithm. More precisely, we sample
$\alpha_{\\_}1,\ldots,\alpha_{\\_}t\xleftarrow{\mbox{\tiny${\$}$}}\\{0,1\\}^{m}$
and then for all $0\leq i\leq l$, we check whether
$\tilde{h}(i,\alpha)=h(i,\alpha)$ holds. If it does not hold, the
implementation would not be used. It is easy to see that for
$\epsilon$-crooked implementation the subversion would not be detected with
probability at least $(1-\epsilon)^{t}$. So for negligible $\epsilon$ this
probability would be still close to one for all polynomial function $t$ and so
the implementation can be survived for further use.

###  10.1 Classical Indifferentiability

IV-based oracle construction $C^{\mathcal{O}}(\cdot,\cdot)$ first fixes an
initial value $R$ (chosen randomly from an initial value space). Afterwards,
on input $M$, it interacts with the oracle $\mathcal{O}$ and finally it
returns an output, denoted as $C^{\mathcal{O}}(R,M)$. When the initial value
space is singleton (i.e., degenerated), we simply call $C$ an oracle
construction. An (initial value based) oracle construction $C$ is called
$\mathcal{F}$-compatible if the domains and ranges of $C$ and $\mathcal{F}$
(an ideal primitive) are same. Now we state the definition of
indifferentiability of an oracle construction as stated in [9, 13] in our
terminologies.

######  Definition 7 (Indifferentiability)

Let $\mathcal{F}$ be an ideal primitive and $C^{P}$ be a
$\mathcal{F}$-compatible oracle construction. $C$ is said to be
$((q_{\\_}{P},q_{\\_}C,q_{\\_}{\mathrm{sim}}),\varepsilon)$ indifferentiable
from an ideal primitive $\mathcal{F}$ if there exists a
$q_{\\_}{\mathrm{sim}}$-query algorithm $S^{\mathcal{F}}$ (called simulator)
such that for any $(q_{\\_}P,q_{\\_}C)$-query algorithm $\mathcal{A}$, it
holds that

$\Delta_{\\_}{\mathcal{A}}\left((P,C^{P}(\cdot))\ ;\
(S^{\mathcal{F}}(\cdot),\mathcal{F})\right)<\varepsilon.$

In the above definition one may include the complexity (time, query etc.) of
the adversary and simulator. However, for information theoretic security
analysis, we may ignore the time complexity of the simulator as well as the
adversary.555One can easily extend the concrete setup to an asymptotic setup.
Let $\langle\mathcal{F}_{\\_}n,P_{\\_}n\rangle_{\\_}{n\in\mathbb{N}}$ be a
sequence of primitives and $C(n)$ be a polynomial time
$\mathcal{F}_{\\_}n$-compatible oracle algorithm. $C^{P_{\\_}n}(n)$ is said to
be (computationally) indifferentiable from $\mathcal{F}_{\\_}n$ if there
exists a polynomial time simulator $S^{\mathcal{F}_{\\_}n}$ such that for all
polynomial time oracle algorithm $\mathcal{A}$,
$\Delta_{\\_}\mathcal{A}\left((P_{\\_}n,C^{P_{\\_}n}(n))\ ;\
(S^{\mathcal{F}_{\\_}n},\mathcal{F}_{\\_}n)\right)=\textsf{negl}(n)$. A
popular indifferentiability treatment for hash function considers
$\mathcal{F}$ to be a $n$-bit random oracle which returns independent and
uniform $n$-bit strings for every distinct queries. However, the hash function
$C^{P}$ can be defined through different types of primitives $P$ (a random
oracle, or a random permutation $\pi_{\\_}n$, chosen uniformly from the set of
all permutations over $\\{0,1\\}^{n}$).

$P$$C$$S$$\mathcal{F}$$\mathcal{A}$ Figure 12: The distinguishing game of
$\mathcal{A}$ in the indifferentiability security game.

###  10.2 Markov Inequality

###### Lemma 8

Let $X$ be a non-negative random variable and $a>0$ be a real number. Then it
holds that

$\displaystyle\Pr[X\geq a]\leq\frac{\mathsf{Ex}(X)}{a}$

A simple application of Markov inequality (which is used repeatedly in this
paper) is the following. Consider a joint distribution of random variables $X$
and $Y$. Suppose $E$ is an event for which $\Pr((X,Y)\in E)\leq\epsilon$. Let
$f(x):=\Pr((X,Y)\in E|X=x)$ and $E_{\\_}1:=\\{x:f(x)\geq\delta\\}$. It follows
from the definition that $\mathsf{Ex}(f(X))=\Pr(E)$. Now, we use Markov’s
inequality

$\displaystyle\Pr(E_{\\_}1)$ $\displaystyle=\Pr(f(X)\geq\delta)$
$\displaystyle\leq\mathsf{Ex}(f(X))/\delta$ $\displaystyle=\epsilon/\delta.$

Note that when $X$ and $Y$ are independent, $f(x)=\Pr((x,Y)\in E)$

##  11 Leftout Proofs

###  11.1 Proof of Lemma 1

For any $\epsilon$-crooked implementation $H$ and every
$h\in\textsf{H}|_{\\_}z$, $0\leq i\leq l$, we have
$\Pr_{\\_}x(\tilde{h}(i,x)\neq h(i,x))\leq\epsilon$ where
$x\xleftarrow{\mbox{\tiny${\$}$}}\\{0,1\\}^{n}$. So, for
$\alpha\xleftarrow{\mbox{\tiny${\$}$}}\mathcal{D}$,

$\displaystyle\mathsf{Ex}_{\\_}\alpha(d(\alpha,h))$
$\displaystyle=\Pr_{\\_}\alpha(\tilde{h}(\alpha)\neq
h(\alpha)\vee\alpha\in\mathcal{D}(z))$
$\displaystyle\leq\epsilon+q_{\\_}12^{-n}.$

Now, we fix any $\alpha:=(i,x)$ and $1\leq j\leq\tau$. For any function
$g\in\textsf{H}|_{\\_}z$, let
$\mathcal{S}_{\\_}{\alpha,g}:=\\{(f,\beta)\in\textsf{H}_{\\_}z\times\\{0,1\\}^{n}:\
f|_{\\_}{\mathcal{Q}^{f}_{\\_}j(\alpha)\rightarrow\beta}=g\\}$. We shall use
the following Claim which we prove later.

###### Claim 11.1

For a function $g$, we have $|\\{(f,\beta):\
f|_{\\_}{\mathcal{Q}^{f}_{\\_}j(\alpha)\rightarrow\beta}=g\\}|=N$.

Now for each $j\in\\{1,2,\cdots,\ell\\}$,

$\displaystyle\mathsf{Ex}_{\\_}{\alpha,h}D^{j}(\alpha,h)$
$\displaystyle=\mathsf{Ex}_{\\_}{\alpha,h}\mathsf{Ex}_{\\_}\beta\big{(}d(\alpha,h|_{\\_}{\tilde{\alpha}_{\\_}j\rightarrow\beta})\big{)}$
$\displaystyle=\sum_{\\_}{\alpha,h,\beta}\Pr(h)\Pr(\alpha)\Pr(\beta)\cdot
d(\alpha,h|_{\\_}{\tilde{\alpha}_{\\_}j\rightarrow\beta})$
$\displaystyle=2^{-n}\sum_{\\_}{(h,\beta)\in\mathcal{S}_{\\_}{\alpha,g}}\sum_{\\_}{\alpha,g}\Pr(g)\Pr(\alpha)\cdot
d(\alpha,g)$ $\displaystyle=\sum_{\\_}{\alpha,g}\Pr(g)\Pr(\alpha)\cdot
d(\alpha,g)$ $\displaystyle=\mathsf{Ex}_{\\_}{\alpha,g}d(\alpha,g)$
$\displaystyle\leq\mathsf{Ex}_{\\_}g(\epsilon+q_{\\_}12^{-n})$
$\displaystyle\leq(\epsilon+q_{\\_}12^{-n})\hskip 50.0pt\squareforqed\vskip
6.0pt plus 2.0pt minus 2.0pt$

###  11.2 Proof of Lemma 2

###### Proof

A pair can be bad in two ways and we bound each case separately. We first
bound that for a random $\alpha$ and $h$, either $d(\alpha,h)=1$ or
${D}^{j}(\alpha,h)>\epsilon_{\\_}1^{1/2}$. The probability of the first event
is clearly bounded by $\epsilon$ and whereas the probability of the second
event is bounded by $\epsilon_{\\_}1^{1/4}$ (Applying Markov inequality and
the Lemma 1). So a random $\alpha^{\prime}$ is queried by some $\alpha$
satisfying the above event holds with probability at most
$\tau(\epsilon+\epsilon_{\\_}1^{1/4})\leq 2\tau\epsilon^{1/4}$.

By using simple averaging argument, average number of $\alpha^{\prime}$ for
which the number of $\alpha$ that queries $\alpha^{\prime}$ is at least
$1/\epsilon^{1/4}$ is at most $\tau\epsilon_{\\_}1^{1/4}$. By adding this two
cases we complete our proof. ∎

###  11.3 Proof of Claim 11.1

Suppose $j=1$ and so $\mathcal{Q}^{f}_{\\_}j(\alpha)=\alpha$. Now, the
function $f$ agrees with $g$ except that the output of $f$ at ${\alpha}$ can
be any $n$-bit string, which should be $\beta$. Now assume $j>1$. So,
$f(\mathcal{Q}^{f}_{\\_}k(\alpha))=g(\mathcal{Q}^{f}_{\\_}k(\alpha))$ for all
$k<j$. For $k=j$, $f(\mathcal{Q}^{f}_{\\_}j(\alpha))=\beta$ (for any choice of
$\beta\in\\{0,1\\}^{n}$). For all other inputs, $f$ agrees with $g$. So the
claim follows. ∎

###  11.4 Proof of Lemma 5

From Lemma 3, we know that $\Pr_{\\_}h(h\mbox{ is not
robust})\leq\epsilon_{\\_}2^{1/2}$. Now, fix a robust $h$. Then

$\displaystyle\Pr_{\\_}{R}((R,h)\not\in\mathcal{G}^{*})$
$\displaystyle\leq\sum_{\\_}{m\in\\{0,1\\}^{n}}\prod_{\\_}{i=1}^{l}\Pr_{\\_}{R_{\\_}i}(((i,m\oplus
R_{\\_}i),h)\mbox{ is not good})\leq 2^{n}\times\epsilon_{\\_}2^{l/2}\leq
1/2^{n}.$

Hence, we have

$\displaystyle\Pr_{\\_}{R,h}((R,h)\not\in\mathcal{G}^{*})$
$\displaystyle\leq\Pr_{\\_}h(h\mbox{ is not
good})+\Pr_{\\_}{R}((R,h)\not\in\mathcal{G}^{*}|h\mbox{ is
good})\leq\epsilon_{\\_}2^{1/2}+1/2^{n}.\squareforqed$

###  11.5 Proof of Lemma 6

We start with the following observation.

###### Observation 11.2

$\displaystyle
Q_{\\_}{\twoheadrightarrow\alpha_{\\_}i}^{h}=Q_{\\_}{\twoheadrightarrow\alpha_{\\_}i}^{h_{\\_}\beta}$

###### Proof

Let $\alpha^{\prime}\twoheadrightarrow_{\\_}h\alpha_{\\_}i$. Suppose
$\alpha_{\\_}i$ is the $j^{th}$ query in the computation of
$\tilde{h}(\alpha^{\prime})$. Clearly, $j^{th}$ query in the computation of
$\tilde{h}(\alpha^{\prime})$ depends on the query and responses of first $j-1$
queries made by $\tilde{h}(\alpha^{\prime})$. Let
$\tilde{\alpha}_{\\_}1,\cdots,\tilde{\alpha}_{\\_}{j-1}$ be those queries. As
$\alpha_{\\_}i\notin\\{\tilde{\alpha}_{\\_}1,\cdots,\tilde{\alpha}_{\\_}{j-1}\\}$,
we get $h(\tilde{\alpha}_{\\_}k)=h_{\\_}\beta(\tilde{\alpha}_{\\_}k)$. As all
the previous query responses are same,
$\alpha^{\prime}\twoheadrightarrow_{\\_}{h_{\\_}\beta}\alpha_{\\_}i$. ∎

We are now ready to prove the required three statements. Assume that $i$ is
the index of interest for $(R,h)$ and $m$. by definition $\alpha_{\\_}i\notin
B_{\\_}h$.

###### Claim 11.3

$\alpha_{\\_}i\notin B_{\\_}{h_{\\_}\beta}$ if and only if
$\alpha_{\\_}i\notin B_{\\_}{h}$.

###### Proof

As $\beta\in S$, $d(\alpha_{\\_}i,h_{\\_}\beta)=d(\alpha_{\\_}i,h)$. By
Observation
11.2,$Q_{\\_}{\twoheadrightarrow\alpha_{\\_}i}^{h}=Q_{\\_}{\twoheadrightarrow\alpha_{\\_}i}^{h_{\\_}\beta}$.
So, only things that require proofs are the following. First, for each $k$ it
should hold that, $\alpha_{\\_}i$ is the $k^{th}$ query of $\tilde{h}(\alpha)$
if and only if $\alpha_{\\_}i$ is also the $k^{th}$ query of
$\tilde{h_{\\_}{\beta}}(\alpha)$. Moreover, it needs to hold that
${D}^{k}(\alpha,h)={D}^{k}(\alpha,h_{\\_}\beta)$. The first statement follows
from the following observation. As all the previous $k-1$ query responses are
same in both cases, the $k^{th}$ query made by the implementation on $\alpha$
will be same. Hence $\alpha_{\\_}i$ is the $k^{th}$ query of
$\tilde{h}(\alpha)$, if and only if $\alpha_{\\_}i$ is also the $k^{th}$ query
of $\tilde{h_{\\_}{\beta}}(\alpha)$. The second statement follows from the
definition.

$\displaystyle{D}^{k}(\alpha,h)=\mathsf{Ex}_{\\_}{\beta^{\prime}}(d(\alpha,h_{\\_}{\alpha_{\\_}i\rightarrow\beta^{\prime}}))={D}^{k}(\alpha,h_{\\_}\beta)$

∎

The next claim proves the second statement

###### Claim 11.4

For all $j<i$,
$\alpha_{\\_}j\not\twoheadrightarrow_{\\_}{h_{\\_}\beta}\alpha_{\\_}i$ where
$\alpha_{\\_}j=(j,m\oplus R_{\\_}j)$.

###### Proof

Fix a $j<i$. We know
$\alpha_{\\_}j\not\twoheadrightarrow_{\\_}{h}\alpha_{\\_}i$. This implies
$\alpha_{\\_}j\notin Q_{\\_}{\rightarrow\alpha_{\\_}i}^{h}$. By Observation
11.2, $\alpha_{\\_}j\notin Q_{\\_}{\rightarrow\alpha_{\\_}i}^{h_{\\_}\beta}$.
Hence, $\alpha_{\\_}j\not\twoheadrightarrow_{\\_}{h_{\\_}\beta}\alpha_{\\_}i$.
∎

The final step is to prove that $i$ is the minimum such index even for
$(R,h_{\\_}\beta)$ that satisfies first two points. For that we prove the
following,

###### Claim 11.5

If there exists and index $i^{\prime}<i$ such that
$\alpha_{\\_}{i^{\prime}}\notin B_{\\_}{h_{\\_}\beta}$ and
$\forall~{}j<i^{\prime}\alpha_{\\_}j\not\twoheadrightarrow_{\\_}{h_{\\_}\beta}\alpha_{\\_}{i^{\prime}}$,
then it holds that $\alpha_{\\_}{i^{\prime}}\notin B_{\\_}{h}$ and
$\forall~{}j<i^{\prime}$,$\alpha_{\\_}j\not\twoheadrightarrow_{\\_}{h}\alpha_{\\_}{i^{\prime}}$

###### Proof

Using Claim 11.3, we get

$\displaystyle\alpha_{\\_}{i^{\prime}}\notin
B_{\\_}{h_{\\_}\beta}\implies\alpha_{\\_}{i^{\prime}}\notin B_{\\_}{h}$

For the second part, we show the contrapositive. Suppose for some
$j<i^{\prime}$,
$\alpha_{\\_}j\twoheadrightarrow_{\\_}{h}\alpha_{\\_}{i^{\prime}}$. Hence
$\alpha_{\\_}j\in Q^{h}_{\\_}{\rightarrow\alpha_{\\_}{i^{\prime}}}$. Moreover
from assumption $\alpha_{\\_}j\not\twoheadrightarrow_{\\_}{h}\alpha_{\\_}{i}$.
All the queries made by $\tilde{h}(\alpha_{\\_}j)$ and the responses remain
same in $\tilde{h_{\\_}\beta}(\alpha_{\\_}j)$. This implies
$\alpha_{\\_}j\twoheadrightarrow_{\\_}{h_{\\_}\beta}\alpha_{\\_}{i^{\prime}}$.
∎

###  11.6 Proof of Proposition 1

###### Proof

We let $B_{\\_}j$ denote the event of the choice of $h(\alpha_{\\_}i)$ such
that $(0,\tilde{g}_{\\_}R^{h_{\\_}\beta}(m))\in\mathcal{D}(L_{\\_}0)\cup
C^{h_{\\_}\beta}\wedge(R,h_{\\_}\beta,F)\vdash\tau$ holds.

$\displaystyle|B_{\\_}j|\leq\epsilon 2^{n}+(q_{\\_}1+i).$

Fix a function $h$. $E_{\\_}j=\tau_{\\_}j\wedge i\mbox{ is the index of
interest for
}(m,R,h)\wedge\\{h_{\\_}{\alpha_{\\_}i\rightarrow\beta}\\}_{\\_}{\beta\in
S}\\}$. As there are $|S|$ many choices of $h(\alpha_{\\_}i)$ in $E_{\\_}j$,
for all $y\in S$

$\displaystyle\Pr[h(\alpha_{\\_}i)=y|E_{\\_}j]\leq\frac{1}{|S|}$

Hence

$\displaystyle\Pr[B_{\\_}j|E_{\\_}j]\leq\frac{|B_{\\_}j|}{|S|}\leq\frac{2|B_{\\_}j|}{2^{n}}\leq
2\epsilon+\frac{2(q_{\\_}1+i)}{2^{n}}$

In the second inequality we use that
$|S|\geq(1-\epsilon_{\\_}1^{1/2})2^{n}>2^{n-1}$. Taking sum over all candidate
$h$ and thus all choice of $i$, we get the proposition. ∎