thesis/chap-OT-LWE.tex

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\chapter{Lattice-Based Oblivious Transfer with Access Control}
%\addcontentsline{tof}{chapter}{\protect\numberline{\thechapter} Transfert inconscient adaptatif avec contrôle d'accès à base de réseaux euclidiens}
%\label{ch:ot-lwe}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{comment}
\section{Introduction}
\end{comment}


Oblivious transfer ($\mathsf{OT}$) is a central cryptographic  primitive coined by Rabin~\cite{Rab81}  and extended by Even \textit{et al.} \cite{EGL85}.
It involves  a
sender $\mathsf{S}$ with a database of messages $M_1, \ldots, M_N$ and a receiver $\mathsf{R}$ with an index $\rho \in \{1,\ldots,N\}$. The
protocol allows  $\mathsf{R}$ to retrieve the $\rho$-th   entry $M_{\rho}$ from $\mathsf{S}$ without letting $\mathsf{S}$ infer anything
on $\mathsf{R}$'s choice $\rho$. Moreover, $\mathsf{R}$ only obtains $M_{\rho}$     learns nothing about   $\{M_i\}_{i \neq \rho}$.

In its adaptive flavor \cite{NP99}, $\mathsf{OT}$ allows the receiver to interact $k$ times with  $\mathsf{S}$ to retrieve
$M_{\rho_1},\ldots,M_{\rho_k}$ in such a way that, for each index $i \in \{2,\ldots,k\}$, the $i$-th index $\rho_{i} $ may depend on the messages
$M_{\rho_1},\ldots,M_{\rho_{i-1}}$ previously obtained by $\mathsf{R}$.

$\mathsf{OT}$ is known to be  a complete building block for cryptography (as for example, \cite{GMW87}) in that, if it can be realized, then
any secure multiparty computation can be. In its adaptive variant, $\mathsf{OT}$ is motivated by applications in privacy-preserving access
to sensitive databases (e.g., medical records or financial data) stored in encrypted form on remote servers, oblivious searches or location-based
services.

As far as efficiency goes, adaptive  $\mathsf{OT}$ protocols should be designed in such a way that, after an inevitable initialization phase with
linear	communication complexity in $N$ and the security parameter $\lambda$, the complexity of each transfer is   at most poly-logarithmic  in $N$. At the same time, this   asymptotic efficiency should not come at the expense of sacrificing ideal security properties.
The most efficient adaptive $\mathsf{OT}$ protocols  that satisfy the latter criterion stem from the work of Camenisch, Neven and shelat
\cite{CNS07} and its follow-ups \cite{GH07,GH08,GH11}.

In its basic form, (adaptive) $\mathsf{OT}$ does not restrict in any way the population of users who can obtain specific records. In many
sensitive databases (e.g., DNA databases or patients' medical history),
however, not all users should be able to download all records: it is vital access to certain  entries be conditioned on the receiver holding suitable  credentials delivered by  authorities. At the same time, privacy protection mandates that authorized users be able to query database records while
leaking as little as possible about their interests or activities. In medical datasets, for example, the specific entries retrieved by a given doctor
could reveal which disease his patients are suffering from. In financial or patent datasets, the access pattern of  a company could betray its investment
strategy or the invention it is developing.
In order to combine user-privacy and fine-grained database security, it is thus desirable to  enrich adaptive $\mathsf{OT}$ protocols  with refined access control mechanisms in many of their natural use cases. 

This motivated Camenisch, Dubovitskaya and Neven \cite{CDN09} to introduce
a variant
named \textit{ oblivious transfer with access control} (OT-AC), where each database record is protected by a different access control policy $P : \{0,1\}^\ast
\rightarrow \{0,1\}$.
Based on their attributes, users can obtain credentials generated by pre-determined authorities, which entitle  them to  anonymously retrieve database records of which the access  policy accepts their certified attributes: in other words,  the user can only download the records for which he has a
valid credential $\mathsf{Cred}_x$ for an attribute string $x \in \{0,1\}^\ast$ such that
$P(x)=1$. During the transfer phase, the user demonstrates possession of a   pair $(\mathsf{Cred}_x,x)$ and simultaneously
convinces the sender that he is querying some record $M_{\rho}$ associated with a policy $P$ such that $P(x)=1$. The only
information that the database holder eventually learns is that some user retrieved some   record which he was authorized to obtain.

Camenisch \textit{et al.} formalized  the OT-AC primitive and provided a construction in groups with a bilinear map \cite{CDN09}.
While efficient, their solution ``only'' supports access policies consisting of conjunctions: each policy $P$ is specified by a list
of attributes that a given user should obtain a credential for in order to complete the transfer.  Several subsequent works
\cite{ZAW+10,CDNZ11,CDEN12}
considered more expressive access policies while even hiding the access policies in some cases \cite{CDNZ11,CDEN12}. Unfortunately,
all of them rely on non-standard assumptions (known as ``$q$-type assumptions'' as described in~\cref{ch:proofs}) in groups with a bilinear maps. For the sake of not putting
all one's eggs in the same basket,  a primitive as powerful as OT-AC ought to have alternative realizations based on firmer  foundations.

In this chapter, we propose a solution based on lattice assumptions where access policies consist of any  branching program of width $5$,
which is known \cite{Bar86} to   suffice for the realization of any  access policy in $\mathsf{NC1}$. As a result of independent interest, we provide
protocols for proving the correct evaluation of a committed branching program. More precisely, we give zero-knowledge arguments for demonstrating possession of a secret input $\mathbf x \in \{0,1\}^\kappa$ and
a secret (and possibly certified) branching program $\BPR$ such that $\BPR(\mathbf x)=1$.
\index{Complexity classes!$\mathsf{NC}1$}

\paragraph{Related Work.}
Oblivious transfer with adaptive queries dates back to the work of Naor and Pinkas \cite{NP99}, which
requires $O( \log N)$ interaction rounds per transfer.
Naor and Pinkas \cite{NP05} also gave generic constructions of
(adaptive) $k$-out-of-$N$ OT from private information retrieval (PIR) \cite{CGKS95}. The constructions of~\cite{NP99,NP05}, however,  are only    secure  in the half-simulation model, where simulation-based
security is only considered for one of the two parties (receiver security being formalized in terms of a  game-based definition).
Moreover, the  constructions  of Adaptive OT from PIR  \cite{NP05}
requires a complexity $O(N^{1/2})$ at each transfer where Adaptive OT allows for $O(\log N)$ cost.
Before 2007, many OT protocols (e.g., \cite{NP01,AIR01,tau05}) were   analyzed in terms of  half-simulation.

While several efficient fully simulatable  protocols appeared   the last 15 years (e.g., \cite{DN03,Lin08,PVW08} and references therein),
full simulatability
remained elusive in
the adaptive $k$-out-of-$N$ setting \cite{NP99}  until the work~\cite{CNS07} of
Camenisch, Neven and shelat, who introduced the ``assisted decryption''
paradigm. The latter consists in having the sender obliviously decrypt a re-randomized version of one of the original  ciphertexts contained in the database.  This technique  served as a blueprint for many subsequent protocols \cite{GH07,GH08,GH11,JL09}, including those with access control
\cite{CDN09,CDNZ11,CDEN12,ACDN13} and those presented in this chapter.  In the adaptive $k$-out-of-$N$ setting (which we denote as \OTA),
the difficulty is to achieve full simulatability without having to transmit a $O(N)$ bits at each transfer.  To our knowledge, except
the oblivious-PRF-based approach of Jarecki and Liu \cite{JL09},
all known fully simulatable \OTA protocols rely on bilinear maps\footnote{Several
  pairing-free candidates were suggested in \cite{KPN10,KPN11} but, as pointed out in \cite{GH11},
  they cannot achieve full simulatability in the sense of \cite{CNS07}. In particular, the sender can detect if the receiver fetches the same
  record in two distinct transfers.
%The constructions of \cite{KN09} do achieve full simulatability but each transfer costs $\Theta(N)$ bits in terms
%of communication.
}. A recent work of D\"ottling \textit{et al.}~\cite{DFKS16} uses non-black-box techniques to realize $\LWE$-based  $2$-round oblivious PRF  (OPRF) protocols~\cite{FIPR05}.    However, while fully simulatable OPRFs imply \cite{JL09}
fully simulatable adaptive OT, the OPRF construction of~\cite{DFKS16} does not satisfy the standard
notion of full simulation-based security against malicious adversaries (which is impossible to achieve in two rounds). It also relies on the full power of
homomorphic encryption, which we do not require.

A number of works introduced various forms of access control in OT.  Priced OT  \cite{AIR01}
assigns variable prices to all database records. In conditional OT \cite{DCOR99}, access to a record is made contingent on the user's secret
satisfying some predicate. Restricted OT \cite{Her11} explicitly protects each record with an independent access policy. Still, none of these
OT flavors aims at protecting the anonymity of users. The model of Coull, Green and Hohenberger \cite{CGH09} does consider user anonymity via stateful
credentials. For the applications of OT-AC, it would nevertheless require re-issuing user credentials at each transfer.

While efficient, the initial OT-AC protocol of Camenisch \textit{et al.} \cite{CDN09} relies on non-standard
assumptions in groups with a bilinear map and only realizes access policies made of conjunctions. Abe \textit{et al.} \cite{ACDN13}
gave a  different protocol which they proved secure under more standard assumptions in the universal composability framework \cite{Can01}.
Their policies, however,  remain limited to  conjunctions.  It was mentioned in \cite{CDN09,ACDN13}
that disjunctions and DNF formulas can be handled by duplicating database entries. Unfortunately, this approach rapidly
becomes prohibitively expensive in the case of $(t,n)$-threshold policies with $t \approx n/2$.
Moreover, securing the protocol against malicious senders
requires them to prove that
all duplicates encrypt the same message.  More expressive policies were considered by Zhang \textit{et al.} \cite{ZAW+10} who
gave a construction based on attribute-based encryption \cite{SW05} that
extends to access policies expressed by any Boolean formulas (and thus $\mathsf{NC}1$ circuits).
Camenisch, Dubovitskaya, Neven and Zaverucha  \cite{CDNZ11} generalized the OT-AC functionality so as
to hide the access policies.   In \cite{CDEN12}, Camenisch \textit{et al.} gave a   more efficient
construction with hidden policies based on the attribute-based
encryption scheme of \cite{NYO08}. At the expense of a proof in the generic group model, \cite{CDEN12} improves upon the expressiveness
of \cite{CDNZ11} in that its policies
extend into CNF formulas. While the solutions of \cite{CDNZ11,CDEN12} both hide the access policies to users (and the successful termination
of transfers to the database), their policies can only live in  a proper subset of $\mathsf{NC1}$. As of now,
threshold policies can only be efficiently handled by the ABE-based construction of Zhang \textit{et al.}   \cite{ZAW+10}, which requires
\textit{ad hoc} assumptions in groups with a bilinear map.
\bigskip

In the forthcoming sections, we first present the adaptive oblivious transfer scheme and its access control flavour, then we present the needed building blocks, in particular a simpler version of the signature scheme presented in~\cref{se:gs-lwe-sigep}.
We next present our constructions and the zero-knowledge protocol to guarantee the correct execution of a branching program.
Finally, we close this chapter with the description of a shift of our scheme from the standard model to the random oracle model to reduce the communication complexity cost, and a comparison table between the different existing solutions.

\section{Adaptive Oblivious Transfer}
\label{sec:def-OT}

\index{Adaptive Oblivious Transfer}
In the syntax of \cite{CNS07}, an adaptive $k$-out-of-$N$ OT scheme $\OT_k^N$ is a tuple of stateful $\ppt$ algorithms $(\SI, \RI, \ST, \RT)$.
The sender $\mathsf{S}=(\SI,\ST)$ consists of two interactive algorithms $\SI$ and $\ST$ and the receiver has a similar representation as algorithms $\RI$ and $\RT$.
In the \textit{initialization phase}, the sender and the receiver  run interactive algorithms $\SI$ and $\RI$, respectively, where $\SI$ takes as input   messages $M_1, \ldots, M_N$ while  $\RI$ has no input.
This phase ends with the two algorithms $\SI$ and $\RI$ outputting their state information $S_0$ and $R_0$ respectively.

During the $i$-th \textit{transfer}, $1 \leq i \leq k$,  both parties run an interactive protocol via the $\RT$ and $\ST$ algorithms.
The sender starts runs   $\ST(S_{i-1})$  to obtain its updated state information $S_i$ while the receiver runs $\RT(R_{i-1}, \rho_i)$ on input of  its previous state $R_{i-1}$ and the index $\rho_i \in \{1, \ldots, N \}$ of the message it wishes to retrieve. At the end, $\RT$ outputs an updated state  $R_i$ and a message $M'_{\rho_i}$.

\textit{Correctness} mandates  that, for all   $M_1, \ldots, M_N$, for all   $\rho_1, \ldots, \rho_k \in [ N]$ and all coin tosses $\varpi$ of the (honestly run) algorithms, we have $M'_{\rho_i} = M_{\rho_i}$ for all $i$.

We consider protocols that are secure (against static corruptions) in the sense of simulation-based definitions. The security
properties against a cheating sender and a cheating receiver are formalized via  the  ``real-world/ideal-world'' paradigm. The
security definitions of \cite{CNS07}  are recalled in the following Section.

\subsection{Security Definitions for Adaptive $k$-out-of-$N$ Oblivious Transfer} \label{def-AOT}

Security is defined via the  ``real-world/ideal-world'' paradigm which was first introduced in the Universal Composability (UC) framework~\cite{Can01}. Like \cite{CNS07,CDN09}, however, we do not incorporate all the formalities of the UC framework.
We define two experiments: the \textbf{Real} experiment, where the two parties run the actual protocol, and the \textbf{Ideal} experiment  wherein a \textit{trusted third party} assumes the role of the functionality.

The model of \cite{CNS07} formalizes two security notions called  \textit{sender security} and \textit{receiver security}. 
The former considers the security of honest senders against cheating senders whereas the latter considers the security of honest receivers interacting 
with malicious senders.  

For an adaptive OT protocol $\OT_k^N$ comprised of algorithms $(\SI, \ST, \RI, \RT)$, we denote define the honest sender $\mathsf S$ as the algorithm that runs
$\SI(M_1, \ldots, M_N)$ during the initialization phase, runs $\ST$ at each transfer  and eventually returns $S_k = \epsilon$ as its final output.
 Similarly,  the honest receiver $\mathsf R$ is the algorithm that runs $\RI$ in the initialization phase, runs $\RT(R_{i-1}, \rho_i)$ during the $i$-th transfer and eventually returns $R_k = (M'_{\rho_1}, \ldots, M'_{\rho_k})$ as its final output.
\medskip

\paragraph{Real Experiment.}
Here, a  sender $\hS$ and a receiver $\hR$ which proceed as follows for  experiment $\textbf{Real\,}_{\hS, \hR}(N, k, M_1, \ldots, M_N, \rho_1, \ldots, \rho_k)$.\\ \smallskip
The sender $\hS$ is given messages $M_1, \ldots, M_N$  and interacts with $\hR$ which does not have any input in the initialization phase.
At end of the latter, $\hS$ and \hR output their initial states $S_0$ and $R_0$ respectively. Then,  $\hS$ and \hR start $k$ sequential interactions:
for $i \in [k]$, in the $i$-th transfer, the sender $\hS$ and the receiver $\hR$ run $S_i \gets \hS(S_{i-1})$ and $(R_i, M'_{\rho_i}) \gets \hR(R_{i-1}, \rho_i)$, where $\rho_i \in [N]$ is a message index and $(S_i,R_i)$ denote updated states for $\hS$ and $\hR$, respectively.
Note that $M'_{\rho_i}$ may be different from $M_{\rho_i}$ if one of the participant deviates from the protocol. At the end of the $k$-th interaction, $\hS$ and $\hR$  output strings $S_k$ and $R_k$ respectively. The output of $\textbf{Real\,}_{\hS,\hR}$ is the pair $(S_k, R_k)$.
\smallskip

The honest sender $\mathsf{S}$ is the algorithm that runs $\mathsf{S}(M_1,\ldots,M_N)$ as in the initialization phase, runs $\mathsf{S}_\mathsf{T}$ in all subsequent interactions 
and always outputs $S_k=\varepsilon$. The honest receiver $\mathsf{R}$ is the algorithm that runs $\mathsf{R}_\mathsf{I}$ in the initialization phase, runs 
$\mathsf{R}_{\mathsf{T}}(\mathsf{R}_{i-1},\rho_i)$ at the $i$-th transfer and returns  the list of received messages  
$R_k=(M_{\rho_1}',\ldots,M_{\rho_k}')$ as its final output.  
\medskip

\paragraph{Ideal Experiment.}
We define the experiment $\textbf{Ideal\,}_{\hS', \hR'}(N, k, M_1, \ldots, M_N, \rho_1, \ldots, \rho_k)$ as follows.\\ \smallskip
The (possibly malicious) algorithm $\hS'(M_1, \ldots, M_N)$ generates messages $M'_1, \ldots, M'_N$ which are given to the trusted party $\mathsf{T}$. In each of the $k$ transfers, $\mathsf{T}$ obtains 
a bit $b_i$ from the sender $\hS'$ and an index $\rho'_i$ from the (possibly malicious) receiver $\hR'(\rho_i)$. If $b_i = 1$, and 
$\rho_i' \in [N]$,
then $\mathsf{T}$ reveals $M'_{\rho_i}$ to the receiver $\hR'$.
Otherwise, $\hR'$ receives  $\bot$ from $\mathsf{T}$. At the end of the $k$-th transfer, $\hS'$ and $\hR'$ output a string $S_k$ and $R_k$ and 
the 
output of the experiment is the pair $(S_k, R_k)$.

The ideal sender $\mathsf{S}'(M_1,\ldots,M_N)$ is defined the be the sender that sends $(M_1,\ldots,M_N)$ which sends the messages 
$(M_1,\ldots,M_N)$ to $\mathsf{T}$ in the initialization phase, sends $b_i=1$ in each transfer and outputs the final state $S_k=\varepsilon$.  The honest 
ideal receiver $\mathsf{R}'$ is defined to be the algorithm that sends $\mathsf{T}$ the real selection index $\rho_i$  at each transfer and eventually outputs 
the list of all received messages $R_k=(M_{\rho_1}',\ldots,M_{\rho_k}')$ as its final state.  
 
The bit $b_i$ sent by $\hS'$ at each transfer models its capability of making the transfer fail. By forcing $\hS'$ to choose $b_i$ without seeing 
$\rho_i$, the definition prevents the cheating sender 
$\hS'$ from deciding to cause a failure of the transfer for specific values of $\rho_i$. 

\begin{definition}[Sender Security] \label{def:sender-sec}
  \index{Adaptive Oblivious Transfer!Sender Security}
  An $\OT_k^N$ protocol is   \textit{sender-secure} if, for any PPT real-world cheating receiver $\hR$, there exists a PPT ideal-world receiver $\hR'$ such that, for any polynomial $N_m(\lambda)$, any $N \in [N_m(\lambda)]$, any $k \in [N]$, any messages $M_1, \ldots, M_N$, and any indices $\rho_1, \ldots, \rho_k \in [N]$, no PPT distinguisher can separate the two following distributions with noticeable advantage:
  \[ \mathbf{Real}_{\mathsf{S},\hR}(N, k, M_1, \ldots, M_N, \rho_1, \ldots, \rho_k) \]
  and
  \[ \mathbf{Ideal}_{\mathsf{S}', \hR'}(N, k, M_1, \ldots, M_N, \rho_1, \ldots, \rho_k). \]
\end{definition}

\begin{definition}[Receiver Security] \label{def:receiver-sec}
  \index{Adaptive Oblivious Transfer!Receiver Security}
  An $\OT_k^N$ protocol is  \textit{receiver-secure} if, for any PPT real-world cheating sender $\hS$, there exists a PPT ideal-world sender $\hS'$ such that, for any polynomial $N_m(\lambda)$, any $N \in [N_m(\lambda)]$, any $k \in [N]$, any messages $M_1, \ldots, M_N$, and any indices $\rho_1, \ldots, \rho_k \in [N]$, no PPT distinguisher can tell apart the two following distributions with non-negligible advantage:
  \[ \mathbf{Real}_{\hS,\mathsf{R}}(N, k, M_1, \ldots, M_N, \rho_1, \ldots, \rho_k) \]
  and
  \[ \mathbf{Ideal}_{\hS', \mathsf{R}'}(N, k, M_1, \ldots, M_N, \rho_1, \ldots, \rho_k). \]
\end{definition}
 


\subsection{Adaptive Oblivious Transfer with Access Control} \label{se:def-AC-OT}

Camenisch \textit{et al.} ~\cite{CDN09} define oblivious transfer with access control (OT-AC)
 as a tuple of PPT algorithms/protocols $(\ISetup, \Issue, \DBSetup, \Transfer)$ such that:
\begin{description}
  \item[$\ISetup$:] takes as inputs public parameters $\pp$ specifying a set $\mathcal{P}$ of access policies and generates a key pair $(PK_I, SK_I)$ for the issuer.
  \item[$\Issue$:] is an interactive protocol between the issuer \textsf{I} and a stateful user $\USR$ under common input $(\pp, {x})$, where $x$ is an attribute string. The issuer \textsf{I} takes as inputs its key pair $(PK_I, SK_I)$ and a user pseudonym $P_\USR$. The user takes as inputs its state information $st_\USR$. The user $\USR$ outputs either an error symbol $\bot$ or a credential $\mathsf{Cred}_\USR$, and an updated state $st'_\USR$.
  \item[$\DBSetup$:] is an algorithm that takes as input the issuer's public key $PK_I$, a database $DB = \left(M_i, \mathsf{AP}_i \right)_{i=1}^N$ containing records $M_i$ whose access is restricted by an access policy $\mathsf{AP}_i$ and outputs a database public key $PK_\mathsf{DB}$, an encryption of the records $(ER_i)_{i=1}^N$ and a database secret key $SK_\mathsf{DB}$.
  \item[$\Transfer$:] is a  protocol between the database $\mathsf{DB}$ and a user $\USR$  with common inputs $(PK_I, PK_\mathsf{DB})$. $\mathsf{DB}$ inputs   $SK_\mathsf{DB}$ and
	 $\USR$ inputs $(\rho, st_\USR, ER_\rho, \mathsf{AP}_\rho)$, where $\rho \in [N]$ is a record index to which $\USR$ is requesting access. The interaction ends with $\USR$ outputting  $\bot$ or a string $M_{\rho'}$ and an updated state $st'_\USR$.
\end{description}

We assume private communication links, so that   communications between a user and the issuer are authenticated, and those between a user and the database are anonymized:  otherwise, anonymizing the $\Transfer$ protocol is impossible.

The security definitions formalize two properties called \textit{user anonymity} and \textit{database security}. The former captures that the database should be unable to tell which {honest user} is making a query and neither can tell which records are being accessed. This should remain true even if the database colludes with corrupted users and the issuer. As for database security, the intuition is that a cheating user cannot access a record for  which it does not have the required credentials, even when colluding with other dishonest users. In case  the issuer is colluding with these cheating users, they cannot obtain more records from the database than  they retrieve.

 Similarly  to the  \OTA case,  security is defined by requiring  that any PPT real-world adversary $\mathcal A$ and any environment $\env$, there exists a PPT adversary $\mathcal A'$ which controls the same parties and  such that no environment $\mathcal E$ can tell if it is 
running in the real world interacting with the real $\mathcal A$ or in the ideal-world interacting with $\adv'$.
The distribution of outputs of the environment in the different settings is denoted by $\mathbf{Real}_{\mathcal{E}, \adv}(\lambda)$ and $\mathbf{Ideal}_{\mathcal E, \adv'}(\lambda)$ for real-world adversary $\adv$ and ideal-world adversary $\adv'$, respectively.
\medskip

\begin{definition}
  \index{Adaptive Oblivious Transfer!with Access Control}
  An AC-OT protocol is said to securely implement the functionality if for any real-world adversary $\adv$ and any real world environment $\mathcal E$, there exists an ideal-world simulator $\mathcal A'$ controlling the same parties in the ideal-world as $\adv$ does in the real-world, such that
  \[ | \mathbf{Real}_{\mathcal E, \adv}(\lambda) - \mathbf{Ideal}_{\mathcal{E}, \adv}(\lambda) | \leq \negl(\lambda). \]
\end{definition}


\paragraph{Real World.}
We describe  the way that real-world algorithms  interact when all participants (i.e., the real-world users $\USR_1,\ldots, \USR_{U}$, the database $\mathsf{DB}$ and the issuer $\mathsf{I}$) are honest. The issuer starts by generating a key pair $(PK_I, SK_I) \gets \mathsf{ISetup}(\pp)$, and sends $PK_I$ to all users $\{\USR_i\}_{i=1}^U$ and the database $\mathsf{DB}$.

When $\mathcal E$ sends a message $\bigl(\texttt{initdb}, \mathrm{DB} = (M_i, \mathsf{AP}_i)_{i=1}^N\bigr)$ to the database $\mathsf{DB}$, the latter encrypts the database $\mathrm{DB}$ by running $\DBSetup$ and sends the encrypted records to all users.

When $\mathcal E$ sends a message $(\texttt{issue},  {x})$ to user $\USR_i$, this user starts an $\Issue$ protocol with the issuer on common input ${x}$, at the end of which it returns $1$ to the environment if the protocol succeeded or $0$ otherwise.

When $\mathcal E$ sends a message $(\texttt{transfer}, \rho)$ to user $\USR_i$, this user first checks if its credentials $\mathsf{Cred}_\USR$ are sufficient to access the record $M_\rho$. If it is the case, it engages in a $\Transfer$ protocol with the database $\mathsf{DB}$, at the end of which it receives either the message $M_\rho$, or an error symbol $\bot$. If it failed at any steps, the user returns $0$ to $\mathcal E$, or $1$ if it succeeded.

Notice that in this setting, neither the database nor the issuer return any outputs to the environment.
\medskip

\paragraph{Ideal World.}
In the ideal world,   participants only communicate via the trusted party $\mathsf{T}$ which implements the functionality of the protocol. We describe how 
 $\mathsf{T}$ proceeds when receiving inputs from the ideal-world users $\{\USR'_i\}_{i=1}^U$, issuer $\mathsf{I}'$ and database $\mathsf{DB}'$.   $\mathsf{T}$ maintains an initially empty set $C_i$ for each user $\USR'_i$ and sets $\mathrm{DB} \gets \bot$. It handles the queries of the different parties as follows:\\
\begin{itemize}
\item[$\bullet$ ] When receiving a message $(\texttt{initdb}, \mathrm{DB} = (M_i, \mathsf{AP}_i)_{i=1}^N)$ from $\mathsf{DB}'$, $\mathsf{T}$ sets  $\mathrm{DB} = (M_i, \mathsf{AP}_i)_{i=1}^N$.
\item[ $\bullet$] When receiving $(\texttt{issue}, {x})$ from $\USR'_i$, $\mathsf{T}$ sends $(\texttt{issue}, \USR'_i, {x})$ to $\mathsf{I}'$ which
replies with  a bit $b$. If $b=1$, then $\mathsf{T}$ adds ${x}$ to $C_i$. In any cases, $\mathsf{T}$ sends $b$ to $\USR'_i$. 
\item[ $\bullet$ ] When receiving $(\texttt{transfer}, \rho)$ from $\USR'_i$, the trusted party $\mathsf{T}$ acts as follows. If $\USR_i'$ previously sent 
  a message of the form $(\texttt{transfer},.)$, $\mathsf{T}$ defines $f_{\USR',DB}=1$. Otherwise, it sets $f_{\USR',DB}=0$. 
 If $\mathrm{DB} \neq \bot$, 
it sends $(\texttt{transfer},f_{\USR',DB})$ to $\mathsf{DB}'$, who sends a bit $b$. If $b=1$ and if $st_i$ contains a vector $\mathbf{x}$ such that $\mathsf{AP}_i({x})=1$, then it sends the record to $\USR'_i$. In any other cases, it sends $\bot$ to $\USR'_i$.
\end{itemize} 

In other words, the ideal-world users, database and issuer relay inputs and outputs between the environment $\mathcal E$ and the trusted party $\mathsf{T}$.

Note that, like \cite{CDN09}, the ideal functionality allows the database to learn whether a given user interacts with the database for the first time or
not. The reason is that, like the protocol of \cite{CDN09}, our basic OT-AC scheme requires the database to provide a particular interactive zero-knowledge proof at the very first time each user queries the database. 
In protocols where the database generates such an interactive proof, it  is inevitable for $\USR$ to reveal his state bit $f_{DB}$ to $\mathsf{DB}$. 
In constructions where the zero-knowledge proof is made non-interactive and made publicly available at the same time as the database itself, 
this can be avoided and we can prevent $\mathsf{DB}$ from learning the state bit $f_{DB}$. In this case,  $\mathsf{T}$ does not send $f_{\USR',DB}$ to  $\mathrm{DB}'$ in  
 the ideal-world experiment.
\medskip
 
The ideal world thus implies the following security properties. 

\begin{description}
\item[User Anonymity.] The database cannot tell which user  a given query comes from and  neither can it tell which record is being accessed. 
It only learns whether the user previously queried the database or not. Otherwise, two transfers involving the same users are unlinkable. 
\item[Database Security.] A single cheating user cannot access a record for which he does not have a certified authorized attribute string. 
Colluding users cannot pool their credentials to gain access to a record which  none of them can  individually access. 
Moreover, if the issuer colludes with some users,  the protocol still provides the equivalent of sender security in the \OTA functionality. 
\end{description}

\section{Building Blocks}

We will use two distinct signature schemes because one of them only needs to be secure in
the sense of a weaker security notion and can be more
efficient. This weaker notion is sufficient to sign the database entries and
allows a better efficiency in the scheme of Section \ref{OT-scheme}. In particular, by making
it stateful (which also suffices since all database entries are signed at once), we
can reduce the public key size to $\log N$  matrices if $N$ is the number of database entries. The second scheme must be stateful and secure in the
standard EUF-CMA sense since the issuer uses it to certify users' attributes. The
signature scheme of \cref{se:gs-lwe-sigep} is only used in the OT-AC protocol of Section \ref{OT-scheme}
while the scheme of Section \ref{RMA-sec} is used in the adaptive OT protocol of Section
 \ref{OT-AC-scheme} as well.

We first use the signature scheme described in \cref{se:gs-lwe-sigep} which extends the 
the B\"ohl \textit{et al.}  signature~\cite{BHJ+15} in order to sign messages comprised of multiple blocks while keeping the scheme compatible with zero-knowledge proofs.

\subsection{A Simpler Variant with Bounded-Message Security and Security Against Non-Adaptive Chosen-Message Attacks} \label{RMA-sec}


We  consider a stateful variant  of the scheme in Section \ref{se:gs-lwe-sigep} where a  bound $Q \in \mathsf{poly}(n)$ on the number of signed  messages is fixed  at key generation time. In the context of \OTA, this is sufficient and leads to efficiency  improvements.
In the   modified scheme hereunder, the  string $\tau \in \{0,1\}^\ell$ is   an $\ell$-bit counter maintained by the signer to keep track of the number of previously signed messages.

This  simplified variant   resembles
 the $\mathsf{SIS}$-based signature scheme of B\"ohl \textit{et al.} \cite{BHJ+15}.

 In this version, the message space is $ \{0,1\}^{n \lceil \log q \rceil} $ so that vectors of  $\Zq^n$ can be signed by first decomposing them using
$\mathsf{vdec}_{n,q-1}(.)$.

\begin{description}
\item[\textsf{Keygen}$(1^\lambda,1^Q)$:] Given   $\lambda>0$ and the maximal number $Q \in \mathsf{poly}(\lambda)$ of signatures, choose     $n = \mathcal{O}(\lambda)$, a prime $q = \widetilde{\mathcal{O}}(Q \cdot n^{4})$,    $m =2n \lceil \log q \rceil $,  an integer $\ell = \lceil \log Q \rceil$  and  Gaussian parameters $\sigma = \Omega(\sqrt{n\log q}\log n)$. The message space is $ \{0,1\}^{m_d} $, for some $m_d \in \mathsf{poly}(\lambda)$ with $m_d \geq m$.
  \smallskip   \smallskip
\begin{itemize}
\item[1.] Run $\TrapGen(1^n,1^m,q)$ to get~$\mathbf{A} \in
  \Zq^{n \times m}$ and a short basis $\mathbf{T}_{\mathbf{A}}$ of
  $\Lambda_q^{\perp}(\mathbf{A}),$  which allows sampling short vectors in $\Lambda_q^{\perp}(\mathbf{A})$ with a Gaussian parameter $\sigma$.

Next, choose $\ell+1$ random   $\mathbf{A}_0,\mathbf{A}_1,\ldots,\mathbf{A}_{\ell} \sample U(\Zq^{n \times m})$. 
	\item[2.]  Choose   $\mathbf{D} \sample U(\Zq^{n \times m_d})$    as well as a random     vector
	$\mathbf{u} \sample U(\Zq^n)$. \smallskip \smallskip
\end{itemize}
 The counter $\tau$ is initialized to $\tau=0$. The  private key consists of $SK:=
 \mathbf{T}_{\mathbf{A}}   $ and the   public key is  ${PK}:=\big( \mathbf{A}, ~
  \{\mathbf{A}_j \}_{j=0}^{\ell},  ~\mathbf{D}, ~\mathbf{u} \big).$
\item[\textsf{Sign}$\big(SK, \tau, \mathfrak{m} \big)$:] To sign a message $\mathfrak{m} \in \{0,1\}^{m_d}$,     \smallskip
\begin{itemize}
\item[1.] Increment the counter by setting $\tau:=\tau+1$ and interpret it as a string $\tau \in \{0,1\}^\ell $. Then, using  $SK:=
 \mathbf{T}_{\mathbf{A}}   $,  compute a short delegated basis $\mathbf{T}_\tau \in \ZZ^{2m \times 2m}$
for the matrix
$	\mathbf{A}_{\tau}=
	 [ \mathbf{A} \mid  \mathbf{A}_0 +
\sum_{j=1}^\ell \tau[j] \mathbf{A}_j
] \in  \Zq^{ n  \times 2m}.$
 \item[2.]  Compute the vector   $\mathbf{u}_M=\mathbf{u} + \mathbf{D} \cdot \mathfrak{m} \in \Zq^n .$
 Then,
 using the delegated basis $\mathbf{T}_\tau \in \ZZ^{2m \times 2m}$, sample  a short vector $\mathbf{v} \in \ZZ^{2m}$ in $D_{\Lambda_q^{\mathbf{u}_M}(\mathbf{A}_\tau), \sigma}$.
\end{itemize}
Output the signature $sig=(\tau,\mathbf{v} ) \in \{0,1\}^\ell \times  \ZZ^{2m}  $. \smallskip
\item[\textsf{Verify}$\big(PK,\mathfrak{m},sig\big)$:] Given  $PK$,   $\mathfrak{m} \in \{0,1\}^{m_d}$ and a
signature $sig=(\tau,\mathbf{v}) \in \{0,1\}^\ell \times  \ZZ^{2m} $,
return $1$ if $\| \mathbf{v} \| < \sigma \sqrt{2m}$ and
$  \mathbf{A}_{\tau} \cdot \mathbf{v}  =  \mathbf{u} +  \mathbf{D} \cdot  \mathfrak{m} \bmod q.$
\end{description}

For our purposes, the scheme only needs to satisfy a notion of bounded-message security under non-adaptive chosen-message
attack. In this relaxed model,
the adversary only obtains a
bounded number of signatures for messages that are chosen non-adaptively
(i.e., all at once and before seeing the public key) by the adversary. This
security notion is sufficient for signing the $N$ database entries. Note that the queries are
non-adaptive but the adversary can adaptively choose its forgery message.


\begin{theorem} \label{thm-version-3}
The scheme is bounded message secure under non-adaptive chosen-message attacks if the $\mathsf{SIS}$ assumption holds.
\end{theorem}

\begin{proof}
  We show that the scheme presented in Section~\ref{RMA-sec} is secure against non-adaptive chosen-message attacks ({na-CMA}) under the $\SIS$ assumption.
  The shape of the proof is similar to the security proof of the signature scheme of~\cref{se:gs-lwe-sigep}. Namely, to prove the security, we distinguish two kinds of attacks:
  \begin{description}
    \item[Type I attacks,] where in the adversary's forgery $sig^\star = (\tau^\star, \mathbf v^\star)$, $\tau^\star$ did not appear in any outputs of the signing oracle.
    \item[Type II attacks,] where in the adversary's forgery $sig^\star = (\tau^\star, \mathbf v^\star)$, $\tau^\star$ has been recycled from an output $sig^{(i^\star)} = \bigl(\tau^{(i^\star)}, \mathbf v^{(i^\star)} \bigr)$ of the signing oracle for some query $i^\star \in \{ 1, \ldots, Q \}$.
  \end{description}

  Lemma~\ref{le-type1-RMA} states that the signature scheme is secure against Type I forgery using the same technique as is~\cite{ABB10,Boy10,MP12}.
  Lemma~\ref{le-type2-RMA} claims that the signature scheme resists Type II attacks, with a proof that is very similar to the one of Lemma~\ref{le-type1-RMA}. Both security proofs assume the computational hardness of the $\SIS$ problem.
\end{proof}

\begin{lemma}
  The signature scheme of Section~\ref{RMA-sec} is secure against Type I attacks if the $\SIS_{n, m, q, \beta'}$ assumption holds, with $\beta' = \sigma^2 m^{3/2} (\ell + 2) + \sigma m^{1/2}$.
  \label{le-type1-RMA}
\end{lemma}

\begin{proof}
  Let $\adv$ be a $\ppt$ adversary against the \textsf{na-CMA} security of our scheme that mounts Type I attacks with non negligible success probability $\varepsilon$.
  We construct a $\ppt$ algorithm $\bdv$ using $\adv$ to break the $\SIS_{n,m,q,\beta'}$ assumption.
  Our reduction $\bdv$ takes as input a target matrix $\bar{\mathbf A} \in \ZZ_q^{n \times m}$ and computes $\mathbf v \in \Lambda_q^\perp(\bar{\mathbf A})$ satisfying $0 < \| \mathbf v \| \leq \beta'$.
  \smallskip

  At first, $\bdv$ calls $\adv$ to obtain the messages to be queried: $\mathfrak m^{(1)}, \ldots, \mathfrak m^{(Q)}$.
  For the sake of readability, let us define $\tau^{(i)} = i$, viewed as a bit-string, to be the tag corresponding to the $i$-th signature in our scheme. \medskip

  \textbf{Setup.} As in~\cite{HW09}, the reduction guesses the shortest prefix such that the string $\tau^\star$ embedded in $\adv$'s forgery differs from all prefixes to $\{\tau^{(1)}, \dots, \tau^{(Q)}\}$.
  To achieve this, $\bdv$ chooses at random $i^\dag \sample U(\{1, \ldots, Q\})$ and $t^\dag \sample U(\{1, \ldots, \ell\})$.
  Then, with probability $1/(Q \cdot \ell)$, the longest common prefix between $\tau^\star$ and one of the tags $\{ \tau^{(i)} \}_{i = 1}^{Q}$ is the string $\tau^\star[1] \cdots \tau^\star[t^\dag - 1] \in \bit^{t^\dag - 1}$: the first $(t^\dag - 1)$-th bits of $\tau^\star$.
  Let us define $\tau^\dag = \tau^\star_{\mid t^\dag}$, where $s_{|i}$ denotes the $i$-th prefix for a string~$s$.
  By construction $\tau^\dag \notin \{ \tau_{\mid t^\dag}^{(1)}, \ldots, \tau_{\mid t^\dag}^{(Q)} \}$ with probability $1/(Q \cdot \ell)$.

  Next, the reduction $\bdv$ runs $\TrapGen(1^n, 1^m, q)$ to obtain matrices $\mathbf C \in \Zq^{n \times m}$ and a short basis $\mathbf{T_C} \in \ZZ^{m \times m}$ of
  $\Lambda_q^\perp(\mathbf C)$, which will be useful to answer the following opening oracle queries.
  The reduction $\bdv$ continues by picking $\ell + 1$ matrices $\mathbf Q_0, \ldots, \mathbf Q_\ell \in \ZZ^{m \times m}$ where each matrix $\mathbf Q_i$ has its column independently sampled from
  $D_{\ZZ^m, \sigma}$, and \bdv defines the matrices $\mathbf A=\bar{\mathbf A}$ and $\{\mathbf A_j\}_{j=0}^{\ell}$ as follows
  \[\begin{cases}
      \mathbf A_0 = \bar{\mathbf A} \cdot \mathbf Q_0 + \left( \sum_{j=1}^{t^\dag} \tau^\star[j] \right) \cdot \mathbf C \\
      \mathbf A_j = \bar{\mathbf A} \cdot \mathbf Q_j + (-1)^{\tau^\star[j]} \cdot \mathbf C & \text{for $j \in [ 1, t^\dag ]$} \\
      \mathbf A_j = \bar{\mathbf A} \cdot \mathbf Q_j & \text{for $j \in [t^\dag + 1, \ell]$}
  \end{cases}.\]
  We can notice that
  \begin{align*}
    \mathbf A_{\tau^{(i)}} & = \Bigr[ \mathbf A ~\Big|~ \mathbf A_0 + \sum_{j=1}^\ell \tau^{(i)}[j] \mathbf A_j \Bigl] \\
    & = \Bigr[ \bar{\mathbf A} ~\Big|~ \bar{\mathbf A} \cdot \bigl(\mathbf Q_0 + \sum_{j=1}^\ell \tau^{(i)}[j] \cdot \mathbf Q_j\bigr) + \bigl(\sum_{j=1}^{t^\dag} \tau^\star[j] + (-1)^{\tau^\star[j]} \cdot \tau^{(i)}[j]\bigr) \cdot \mathbf C \Bigl] \\
    & = \Bigr[ \bar{\mathbf A} ~\Big|~ \bar{\mathbf A} \cdot \bigl(\mathbf Q_0 + \sum_{j=1}^\ell \tau^{(i)}[j] \cdot \mathbf Q_j\bigr) + h_{\tau^{(i)}} \cdot \mathbf C \Bigl],
  \end{align*}
  where $h_{\tau^{(i)}}$ denotes the hamming distance between $\tau^{(i)}_{\mid t^\dag}$ and $\tau^\dag$. With probability $1/(Q\cdot \ell)$, and as $\ell > q$, it holds that $h_{\tau^{(i)}} \neq 0 \bmod q$ whenever  $\tau^{(i)}_{\mid t^\dag} \neq \tau^\star_{\mid t^\dag}$.

  The reduction then picks a random short matrix $\mathbf R \sample \ZZ^{m \times m_d}$ which has its $m_d$ columns independently sampled from $D_{\ZZ^m, \sigma}$, and \bdv computes
  \[ \mathbf D = \bar{\mathbf A} \cdot \mathbf R \in \ZZ_q^{n \times m_d}. \]

  To finish, $\bdv$ samples a short vector $\mathbf e_u \in D_{\ZZ^m, \sigma}$ and computes the vector $\mathbf u = \bar{\mathbf A} \cdot \mathbf e_u$. The following public key is finally given to \adv:
  \[ PK := (\mathbf A, \{ \mathbf A_j \}_{j=0}^\ell, \mathbf D, \mathbf u). \]

  \textbf{Signing queries.} To handle signature queries,   the reduction $\bdv$ uses the trapdoor $\mathbf{T_C} \in \ZZ^{m \times m}$ to generate a signature.
  To this end, $\bdv$ starts by computing the vector $\mathbf u_M = \mathbf u + \mathbf D \cdot \mathfrak m^{(i)}$.
  Then $\bdv$ can use $\mathbf{T_C}$ with the algorithm \textsf{SampleRight} from Lemma~\ref{lem:sampler} to
  compute a short vector $\mathbf v^{(i)}$ in $D_{\Lambda^\perp(\mathbf A_{\tau^{(i)}}), \sigma}^{\mathbf u_M}$, distributed like a
  valid signature and satisfying the verification equation~\eqref{ver-eq-block}.
  \medskip

  \textbf{Output.} At some point, the attacker $\adv$ halts and outputs a \textit{valid} signature $sig^\star = (\tau^\star, \mathbf v^\star)$ for a message $\mathfrak m^\star \notin \{ \mathfrak{m}^{(1)}, \ldots, \mathfrak{m}^{(Q)}\}$.
  Since the signature is valid, it satisfies $\| \mathbf v^\star \| \leq \sigma \sqrt{2m}$.

  Parsing $\mathbf v^\star$ as $[ \mathbf{v}_1^\star \mid \mathbf{v}_2^\star]$ with $\mathbf v_1^\star, \mathbf v_2^\star \in \ZZ^m$ and injecting it in~\eqref{ver-eq-block} give:
  \begin{align*}
    \Bigr[ \bar{\mathbf A} ~\Big|~ \bar{\mathbf A} \cdot \bigl(\mathbf Q_0 + \sum_{j=1}^\ell \tau^\star[j] \cdot \mathbf Q_j\bigr) \Bigl] \cdot \begin{bmatrix} \mathbf v_1^\star \\ \hline \mathbf v_2^\star \end{bmatrix}
    & = \mathbf u + \mathbf D \cdot \mathfrak m^\star \mod q \\
    & = \bar{\mathbf A} \cdot \bigl( \mathbf e_u + \mathbf R \cdot \mathfrak m^\star \bigr) \mod q
  \end{align*}
  Thus, the vector
  \[ \mathbf v' = \mathbf v_1^\star + \bigl( \mathbf Q_0 + \sum_{j=1}^\ell \tau^\star[j] \cdot \mathbf Q_j \bigr) \cdot \mathbf v_2^\star - \mathbf e_u - \mathbf R \cdot \mathfrak m^\star \]
  is in $\Lambda^\perp(\bar{\mathbf A})$, and $\mathbf v'$ is non-zero with overwhelming probabilities, since in $\adv$'s view, the distribution of $\mathbf e_u$ is
  $D_{\Lambda^\mathbf u_q(\mathbf A), \sigma}$, which guarantees that $\mathbf e_u$ is statistically hidden by the syndrome $\mathbf u = \bar{\mathbf A} \cdot \mathbf e_u$.
  Finally, the norm of $\mathbf v'$ is upper bounded by
  $\beta' = \sigma^2 m^{3/2} (\ell + 2) + 2 \sigma m^{1/2}$.
\end{proof}

\begin{lemma}
  The signature scheme of Section~\ref{RMA-sec} is secure against Type II attacks if $\SIS_{n,m,q,\beta''}$ holds, with $\beta'' = \sqrt 2 (\ell + 2) \sigma m^{3/2} + m^{1/2}$.
  \label{le-type2-RMA}
\end{lemma}

\begin{proof}
  We will prove this result using techniques analogous to the previous proof. We show that given an adversary $\adv$ that comes out with a Type II signature in the \textsf{na-CMA} game with non negligible probability $\varepsilon$, we can construct a PPT $\bdv$ that breaks the $\SIS$ assumption with advantage $\varepsilon/Q$ using $\adv$.
  \medskip

  Firstly, the reduction $\bdv$ is given a matrix $\mathbf{A} \in \Zq^{n \times m_d}$ as input and has to output an integer vector $\mathbf v \in \ZZ^{m_d}$ in $\Lambda^\perp_q(\mathbf{A})$ such that $0 < \| \mathbf v \| \leq \beta''$.
  Next, $\bdv$ receives from $\adv$ the messages $\mathfrak{m}^{(1)}, \ldots, \mathfrak{m}^{(Q)}$ for which $\adv$ will further ask signature queries.
  \medskip

  To compute the public key, at the outset of the game, the reduction $\bdv$ starts by sampling $i^\dag \sample U(\{1, \ldots, Q\})$ corresponding to the guess that $\adv$'s forgery will recycle $\tau^{(i\dag)}$.
  This is independent of $\adv$'s view, and the guess will be correct with probability $1/Q$.
  Using this guess to compute $PK$, the reduction $\bdv$ picks $h_0, \ldots, h_\ell \in \Zq$ subject to the constraints
  \begin{equation} \label{eq:h-constraints}
    \begin{cases}
      h_0 + \sum_{j=1}^\ell \tau^{(i^\dag)}[j] \cdot h_j = 0 \mod q & \\
      h_0 + \sum_{j=1}^\ell \tau^{(i)}[j] \cdot h_j \neq 0 \mod q & \forall i \in \{1, \ldots, Q\} \backslash \{i^\dag\}
    \end{cases}
  \end{equation}

  \bdv then runs $(\mathbf C, \mathbf{T_C}) \gets \TrapGen(1^n, 1^m, q)$.
  The resulting matrix $\mathbf C \in \Zq^{n \times m}$ is statistically random, and the trapdoor $\mathbf{T_C} \in \ZZ^{m \times m}$ is a short basis of $\Lambda^\perp_q(\mathbf C)$.
  Next \bdv re-randomize $\mathbf{A}$ using short matrices $\mathbf S, \mathbf S_0, \mathbf S_1, \ldots, \mathbf S_\ell \in \ZZ^{m_d \times m}$ which are obtained by sampling their columns from the distribution $D_{\ZZ^{m_d}, \sigma}$.
  The challenger $\bdv$ then uses these matrices to define:
  \begin{align*}
    \mathbf A &= \mathbf{A} \cdot \mathbf S \nonumber \\
    \mathbf A_0 &= \mathbf{A} \cdot \mathbf S_0 + h_0 \cdot \mathbf C \label{eq:rel-rerand} \\
    \mathbf A_j &= \mathbf{A} \cdot \mathbf S_j + h_j \cdot \mathbf C & j \in \{1, \ldots, \ell\} \nonumber
  \end{align*}
  and sets $\mathbf D = \mathbf{A} \in \ZZ_q^{n \times m_d}$. Observe that matrices $\mathbf{A},\{\mathbf{A}_j\}_{j=0}^\ell$ are all statistically uniform over $\ZZ_q^{n \times m}$.
  Then, $\bdv$ samples short vectors ${\mathbf v_1^\dag, \mathbf v_2^\dag \sample D_{\ZZ^m, \sigma}}$ and computes $\mathbf u \in \Zq^n$ as
  \begin{equation} \label{eq:rel-uM}
    \mathbf u = \mathbf A_{\tau^{(i^\dag)}} \cdot \begin{bmatrix} \mathbf v_1^{\dag} \\\hline \mathbf v_2^{\dag} \end{bmatrix} - \mathbf{A} \cdot \mathfrak m^{(i^\dag)} \mod q.
  \end{equation}

  Finally, $\bdv$ sends to $\adv$ the public key
  \[ PK := \bigl( \mathbf A, \{\mathbf A_j \}_{j=0}^\ell, \mathbf D, \mathbf u \bigr) \]
  which is distributed as the $PK$ of the real scheme.
  \smallskip \smallskip

  To answer signing queries, the challenger $\bdv$ do as follows.
  \begin{itemize}
    \item If the query is not the $i^\dag$-th, we have:
      \begin{align*}
        \mathbf A_{\tau^{(i)}} &= \Bigl[ \mathbf A ~\Big|~ \mathbf A_0 + \sum_{j=0}^\ell \tau^{(i)} [j] \cdot \mathbf A_j \Bigr] \\
        &= \Bigl[ \mathbf{A} \cdot \mathbf S ~\Big|~ \mathbf{A} \cdot ( \mathbf S_0 + \sum_{j=0}^\ell \tau^{(i)} [j] \cdot \mathbf S_j) + h_{\tau^{(i)}} \cdot \mathbf C \Bigr],
      \end{align*}
      with $h_{\tau^{(i)}} = h_0 + \sum \tau^{(i)}[j] \cdot h_j \neq 0$ due to the first constraint of~\eqref{eq:h-constraints}. Thus, using the same technique as in the previous proof from~\cite{MP12}, the challenger $\bdv$ can use the trapdoor $\mathbf{T_C}$ along with \textsf{SampleRight} algorithm to sample a short vector in $\Lambda_q^{\mathbf u_M}(\mathbf A_{\tau^{(i)}})$ satisfying~\eqref{ver-eq-block}.
    \item At the $i^\dag$-th query, thanks to the second constraint of~\eqref{eq:h-constraints}, we have:
      \begin{align*}
        \mathbf A_{\tau^{(i^\dag)}} &= \Bigl[ \mathbf A ~\Big|~ \mathbf A_0 + \sum_{j=0}^\ell \tau^{(i^\dag)} [j] \cdot \mathbf A_j \Bigr] \\
        &= \Bigl[ \mathbf{A} \cdot \mathbf S ~\Big|~ \mathbf{A} \cdot ( \mathbf S_0 + \sum_{j=0}^\ell \tau^{(i^\dag)} [j] \cdot \mathbf S_j) \Bigr].
      \end{align*}
      To answer this specific query, the challenger $\bdv$ returns $sig^{(i^\dag)} = (\tau^{(i^\dag)}, \mathbf v^{(i^\dag)})$ where $\mathbf v^{(i^\dag)} = ( \mathbf v_1^{\dag T} \mid \mathbf v_2^{\dag T})^T$ verifying~\eqref{eq:rel-uM}, which furthermore implies that $sig^{(i^\dag)}$ verifies~\eqref{ver-eq-block}.
  \end{itemize}

  Thus we claim that $\bdv$ can solve the $\SIS$ problem using the Type II forgery provided by $\adv$.
  At the end of the game, the adversary outputs a valid signature $sig^\star = (\tau^{(i^\star)}, \mathbf v^\star)$ on a message $\mathfrak m^\star$ with $\| \mathbf v^\star \| \leq \sigma \sqrt{2m}$.
  In the event that $\tau^{(i^\star)} \neq \tau^{i^\dag}$, the reduction aborts. The latter event happens with probability $1-1/Q$.
  If we parse $\mathbf v^\star$ as $(\mathbf v_1^{\star, T} \mid \mathbf v_2^{\star T})^T \in \ZZ^{2m}$, with $\mathbf v_1^{\star}, \mathbf v_2^\star \in \ZZ^m$, it holds that:
  \begin{equation} \label{eq:sub-rel-1}
    \mathbf A_{\tau^{(i^\dag)}} \cdot \begin{bmatrix} \mathbf v_1^{\star} \\\hline \mathbf v_2^{\star} \end{bmatrix} = \mathbf u + \mathbf{A} \cdot \mathfrak m^{\star} \mod q.
  \end{equation}
  According to the way $\mathbf u$ was defined at the beginning of the game, we also have a vector $\mathbf v^\dag = (\mathbf v_1^{\dag T} \mid \mathbf v_2^{\dag T})^T$ such that
  \begin{equation} \label{eq:sub-rel-2}
    \mathbf A_{\tau^{(i^\dag)}} \cdot \begin{bmatrix} \mathbf v_1^{\dag} \\\hline \mathbf v_2^{\dag} \end{bmatrix} = \mathbf u + \mathbf{A} \cdot \mathfrak m^{\dag} \mod q.
  \end{equation}
  As $sig^\star$ is a valid forgery for the dn-CMA game, it follows that $m^\dag \neq m^\star$. And we get by subtracting \eqref{eq:sub-rel-1} and \eqref{eq:sub-rel-2}
  \begin{align*}
    \mathbf A_{\tau^{(i^\dag)}} \cdot \begin{bmatrix} \mathbf v_1^\star - \mathbf v_1^{\dag} \\\hline \mathbf v_2^\star - \mathbf v_2^{\dag} \end{bmatrix} &= \mathbf{A} \cdot \left (\mathfrak m^{\star} - \mathfrak m^\dag \right) \mod q, \\
    \Bigl[ \mathbf{A} \cdot \mathbf S ~\Big|~ \mathbf{A} \cdot ( \mathbf S_0 + \sum_{j=0}^\ell \tau^{(i^\dag)} [j] \cdot \mathbf S_j) \Bigr]\cdot \begin{bmatrix} \mathbf v_1^\star - \mathbf v_1^{\dag} \\\hline \mathbf v_2^\star - \mathbf v_2^{\dag} \end{bmatrix} &= \mathbf{A} \cdot \left (\mathfrak m^{\star} - \mathfrak m^\dag \right) \mod q.
  \end{align*}
  Leading us to the fact that
  \begin{equation} \label{eq:non-zero}
    \mathbf v' = \underbrace{\mathbf S \cdot (\mathbf v_1^\star - \mathbf v_2^\dag) + \left( \mathbf S_0 + \sum_{j=1}^\ell \tau^{(i^\dag)}[j] \cdot \mathbf S_j \right) \cdot (\mathbf v_2^\star - \mathbf v_2^\dag)}_{(a)} + \underbrace{\mathfrak m^\dag - \mathfrak m^\star}_{-(b)}
  \end{equation}
  is an integer vector of $\Lambda_q^\perp(\mathbf{A})$, with norm bounded by $\| \mathbf v' \| \leq \sqrt 2 (\ell + 2) \sigma m^{3/2} + m^{1/2} = \beta''$.
  Furthermore, if $\mathbf v'$ was zero, it implies that $(a) = (b)$ in Equation~\eqref{eq:non-zero}.
  And as $sig^\star \neq sig^\dag$, we have that either $\mathbf v_1^\star \neq \mathbf v_1^\dag$ or $\mathbf v_2^\star \neq \mathbf v_2^\dag$.
  As a consequence, $(a)$ is information theoretically unpredictable for $\adv$ since the columns of $\mathbf S, \mathbf S_0, \ldots \mathbf S_\ell$ are statistically hidden from $\adv$, as shown in~\cite{MP12} for instance: conditionally on the public key, each column of $\mathbf S$ and $\{\mathbf S_j\}_{j=0}^\ell$ has at least $n$ bits of min-entropy.
\end{proof}

\section{A Fully Simulatable Adaptive OT Protocol} \label{OT-scheme}


Our basic \OTA protocol builds on  the ``assisted decryption'' technique \cite{CNS07}. The databases holder encrypts all entries
using a multi-bit variant \cite{PVW08} of Regev's cryptosystem \cite{Reg05} and proves the well-formedness of its public key and all ciphertexts. In addition,
all ciphertexts are signed using a   signature scheme. At each
transfer, the receiver statistically re-randomizes a blinded version of the desired ciphertext, where the blinding is done via the additive
homomorphism of Regev. Then, the receiver provides a witness indistinguishable (\textsf{WI}) argument that the modified  ciphertext (which is
submitted for oblivious decryption) is
a transformation of one of the original ciphertexts by arguing knowledge of a signature  on this hidden ciphertext. In response,
the sender obliviously decrypts the modified ciphertext  and argues in zero-knowledge that the response is correct.


Adapting the  technique of \cite{CNS07} to the lattice setting requires the following building blocks:
(i) A signature scheme allowing to sign ciphertexts while remaining compatible with ZK proofs; (ii) A ZK protocol allowing to prove knowledge of a signature on some hidden ciphertext which belongs to a public set and was transformed into a given   ciphertext; (iii)  A protocol for  proving the correct decryption of a ciphertext; (iv) A method of statistically re-randomizing an $\LWE$-encrypted ciphertext in a way that enables oblivious decryption. The first three ingredients can be obtained from \cref{ch:gs-lwe}. Since component (i) only needs to be secure against random-message attacks as
long as the adversary obtains at most $N$ signatures, we  use the   simplified $\SIS$-based signature scheme
of Section \ref{RMA-sec}. 	
The statistical re-randomization of Regev ciphertexts is handled via the noise flooding technique \cite{AJL+12}, which consists in drowning the initial noise with a sub-exponentially larger
noise. While recent results \cite{DS16,BDPMW16} provide potentially more efficient alternatives,
we chose the flooding  technique for simplicity because it does not require the use of  FHE (and also because
the  known multi-bit version \cite{HAO15} of the GSW FHE~\cite{GSW13}   incurs an \textit{ad hoc} circular security assumption).


\subsection{Description}
Our scheme works with security parameter $\lambda$, modulus $q$, lattice dimensions $n = \mathcal{O}(\lambda)$ and $m= 2 n \lceil \log q \rceil$. Let $B_\chi = \widetilde{\mathcal{O}}(\sqrt{n})$, and let $\chi$ be a $B_\chi$-bounded distribution. We also define an integer~$B$ as a randomization parameter such that $B= n^{\omega(1)}\cdot (m+1)B_\chi$ and $B+ (m+1)B_\chi \leq q/5$ (to ensure decryption correctness).
Our basic \OTA protocol goes as follows.





\begin{description}
\item[\textsf{Initialization}$\big(\mathsf{S}_\mathsf{I}(1^\lambda,\mathsf{DB}),\mathsf{R}_{\mathsf{I}}(1^\lambda) \big)$:] In this protocol, the sender $\mathsf{S}_\mathsf{I}$   has a database $\mathsf{DB}=(M_1,\ldots,M_N)$ of $N$ messages, where $M_i \in \{0,1\}^{t}$ for each $i \in [N]$,
for some $t \in \mathsf{poly}(\lambda)$. It  interacts with the receiver $\mathsf{R}_\mathsf{I}$ as follows. \smallskip \smallskip
\begin{itemize}
\item[1.] Generate a key pair for the signature scheme of Section \ref{RMA-sec} in order to sign $Q=N$ messages of length $m_d = (n+t) \cdot \lceil \log q \rceil$ each.
This key pair consists of $SK_{sig}=\mathbf{T}_{\mathbf{A}} \in \ZZ^{m \times m}$ and
${PK}_{sig}:=\big( \mathbf{A},
\{\mathbf{A}_j \}_{j=0}^{\ell},   \mathbf{D}, \mathbf{u} \big),$ where $\ell=\log N$ and $\mathbf{A},\mathbf{A}_0,\ldots,\mathbf{A}_{\ell} \in U(\Zq^{n \times m})$, $\mathbf{D} \in U(\Zq^{n \times m_d})$.
  %with $m = 2n \lceil \log q \rceil$, $m_d = (n+t) \lceil \log q \rceil$.
  The counter is initialized to $\tau=0$.
	\item[2.] Choose  $\mathbf{S} \sample \chi^{n \times t}$ that will serve as a secret key  for an $\LWE$-based encryption scheme.
	Then, sample   $\mathbf{F} \sample U(\Zq^{n \times m})$, $\mathbf{E} \sample \chi^{m \times t  }$ and compute
		\begin{eqnarray} \label{PK-gen}
		 \mathbf{P} = [\mathbf{p}_1 | \ldots | \mathbf{p}_t]  =  \mathbf{F}^T \cdot \mathbf{S}  + \mathbf{E} ~\in \Zq^{m \times t},
		\end{eqnarray}
		so that $(\mathbf{F},\mathbf{P}) \in \Zq^{n \times m} \times \Zq^{m  \times t }$  forms a public key for a $t$-bit variant of Regev's encryption scheme \cite{Reg05}.
	%	 (or, equivalently,
	%	a set of $m$ encryptions of the all-zeroes $t$-bit string).
	\item[3.]
	Sample    vectors $\mathbf{a}_1,\ldots ,\mathbf{a}_N \sample
	 U(\Zq^n)$ and $\mathbf{x}_1,\ldots,\mathbf{x}_{N} \sample \chi^{t}$ to
	compute
	\begin{align} \label{init-db}
	 (\mathbf{a}_i,\mathbf{b}_i) &= \bigl( \mathbf{a}_i, ~ \mathbf{S}^T \cdot \mathbf{a}_i + \mathbf{x}_i + M_i \cdot \lfloor q/2 \rfloor  \bigr) \in \Zq^n \times \Zq^{t} & \forall i \in [N].
	\end{align}

\item[4.] For each $i \in [N]$, generate a signature $(\tau_i,\mathbf{v}_i ) \leftarrow \mathsf{Sign}(SK_{sig},\tau,\mathfrak{m}_i)$ on the decomposition
 $\mathfrak{m}_i=\mathsf{vdec}_{n+t,q-1}(\mathbf{a}_i^T |\mathbf{b}_i^T )^T \in \{0,1\}^{m_d}$. % of $(\mathbf{a}_i^T | \mathbf{b}_i^T)^T \in \Zq^{n+t}$.
\item[5.] $\mathsf{S}_\mathsf{I}$ sends
 $ R_0= \bigl(  PK_{sig} ,~(\mathbf{F},\mathbf{P}),~\{(\mathbf{a}_i,\mathbf{b}_i),(\tau_i,\mathbf{v}_i ) \}_{i=1}^N \bigr) $ to $\mathsf{R}_\mathsf{I}$ and interactively proves knowledge of small-norm  $\mathbf{S} \in \ZZ^{n \times t}$, $\mathbf{E} \in \ZZ^{m \times t}$, short  vectors $\{\mathbf{x}_i\}_{i=1}^N$ and
$t$-bit messages $\{M_i\}_{i=1}^N$,
for which~\eqref{PK-gen} and~\eqref{init-db} hold. To this end, $\mathsf{S}_\mathsf{I}$ plays the role of the prover in the  ZK argument system described in Section~\ref{subsection:ZK-protocol-1}.
%\item[c.]
If the argument of knowledge does not verify
%at step b
or if there exists $i \in [N]$ such that $(\tau_i,\mathbf{v}_i)$ is an invalid signature on the message
 $\mathfrak{m}_i=\mathsf{vdec}_{n+t,q-1} (\mathbf{a}_i^T |\mathbf{b}_i^T)^T   $ w.r.t. $PK_{sig}$, then $\mathsf{R}_\mathsf{I}$ aborts.
%\end{itemize}
\item[6.] Finally $\mathsf{S}_\mathsf{I}$ defines $S_0= \big( (\mathbf{S},\mathbf{E}) ,(\mathbf{F},\mathbf{P}),PK_{sig}  \big)$, which it keeps to itself. \medskip \smallskip
\end{itemize}

\item[\textsf{Transfer}$\big(\mathsf{S}_\mathsf{T}(S_{i-1}),\mathsf{R}_{\mathsf{T}}(R_{i-1},\rho_i) \big)$:] At the $i$-th transfer, the receiver $\mathsf{R}_\mathsf{T}$ has state $R_{i-1}$ and
an index $\rho_i \in [1,N]$. It interacts as follows with the sender $\mathsf{S}_\mathsf{T}$ that has state $S_{i-1}$ in order to obtain $M_{\rho_i}$ from $\mathsf{DB}$.  \smallskip \smallskip \smallskip
\begin{itemize}
\item[1.] $\mathsf{R}_\mathsf{T}$ samples vectors $\mathbf{e} \sample U(\{-1,0,1\}^m)$, $\mu \sample U(\{0,1\}^t)$ and a random $\nu \sample U([-B,B]^t)$ to compute
\begin{eqnarray} \label{rand-CT}
(\mathbf{c}_0,\mathbf{c}_1) = \big( \mathbf{a}_{\rho_i} + \mathbf{F} \cdot \mathbf{e} , ~\mathbf{b}_{\rho_i} + \mathbf{P}^T \cdot \mathbf{e} + \mu \cdot \lfloor q/2 \rfloor  + \nu \big) \in \Zq^n \times \Zq^t,
 \qquad
\end{eqnarray}
which is a re-randomization of $(\mathbf{a}_{\rho_i},\mathbf{b}_{\rho_i} + \mu \cdot \lfloor q/2 \rfloor  )$. The   ciphertext $(\mathbf{c}_0,\mathbf{c}_1)$ is sent to
$\mathsf{S}_\mathsf{T}$. In addition,  $\mathsf{R}_\mathsf{T}$ provides an interactive \textsf{WI} argument that $(\mathbf{c}_0,\mathbf{c}_1)$ is indeed a transformation of $(\mathbf{a}_{\rho_i},\mathbf{b}_{\rho_i})$ for some   $\rho_i \in [N]$, and $\mathsf{R}_\mathsf{T}$ knows
a  signature on  $\mathfrak{m} = \mathsf{vdec}_{n+1,q-1}(\mathbf{a}_{\rho_i}^T | \mathbf{b}_{\rho_i}^T)^T \in \{0,1\}^{m_d}$.
To this end, $\mathsf{R}_\mathsf{T}$ runs the prover in the ZK argument system in Section~\ref{subsection:ZK-protocol-3}.


\item[2.] If the argument of step 1 verifies, $\mathsf{S}_\mathsf{T}$ uses $\mathbf{S}$ to decrypt $(\mathbf{c}_0,\mathbf{c}_1) \in \Zq^n \times \Zq^t$ and
obtain $M' = \lfloor (\mathbf{c}_1 - \mathbf{S}^T \cdot \mathbf{c}_0) / ( q/2 ) \rceil \in \{0,1\}^t,$
which is sent back to $\mathsf{R}_\mathsf{T}$. In addition, $\mathsf{S}_\mathsf{T}$ provides a zero-knowledge argument of knowledge of vector $\mathbf{y}= \mathbf{c}_1 - \mathbf{S}^T \cdot \mathbf{c}_0 - M' \cdot \lfloor q/2 \rfloor \in \ZZ^t$
of norm $\| \mathbf{y} \|_{\infty} \leq q/5$ and small-norm matrices $\mathbf{E}\in \ZZ^{m \times t}$, $\mathbf{S} \in \ZZ^{n \times t}$ satisfying (modulo $q$)
\begin{align} \label{test-transfer}
\mathbf{P} &= \mathbf{F}^T \cdot \mathbf{S} + \mathbf{E} & \mathbf{c}_0^T \cdot \mathbf{S} + \mathbf{y}^T &= \mathbf{c}_1^T - {M'}^T \cdot \lfloor q/2 \rfloor.
\end{align}
To this end, $\mathsf{S}_\mathsf{T}$ runs the prover in the ZK argument system  in Section~\ref{subsection:ZK-protocol-2}.
\item[3.] If the ZK argument produced by $\mathsf{S}_\mathsf{T}$ does not properly verify at step 2, $\mathsf{R}_\mathsf{T}$ halts and outputs $\perp$. Otherwise, $\mathsf{R}_\mathsf{T}$ recalls
the random string $\mu \in \{0,1\}^t$ that was chosen at step 1 and computes $M_{\rho_i}=M' \oplus  \mu$. The transfer ends with $\mathsf{S}_\mathsf{T}$ and $\mathsf{R}_\mathsf{T}$
outputting $S_i=S_{i-1}$ and $R_i=R_{i-1}$, respectively.
\end{itemize}
\end{description}





In the initialization phase,  the sender has to repeat step 5 with each
	receiver to prove that   $\left\{(\mathbf{a}_i,\mathbf{b}_i)\right\}_{i=1}^N$ are well-formed. Using the Fiat-Shamir heuristic \cite{FS86}, we can decrease this  initialization
	cost from $O(N \cdot U)$   to $O(N)$ (regardless of the number of users $U$) by making the proof  non-interactive.
  This modification also reduces each transfer to $5$ communication rounds since, even in the transfer phase, the sender's ZK arguments can  be non-interactive    and the receiver's arguments only need to be \textsf{WI}, which is preserved when  the basic ZK protocol (which has a ternary challenge space) is repeated $\omega(\log n)$ times in parallel. To keep the security proof
	simple, we derive the  matrix $\mathbf{F} \in \Zq^{n \times m}$ from a second random oracle.
	%which the sender can build his $\LWE$-based public key $\mathbf{P}=\mathbf{F} \cdot \mathbf{S} + \mathbf{E}$, for small-norm matrices $\mathbf{S} \in \ZZ^{n \times t}$
	%and $\mathbf{E} \in \ZZ^{m \times t}$.
Knowing  a short basis of $\Lambda_q^{\perp}(\mathbf{F})$, the simulator can  extract
	the columns of $\mathbf{S}$ from the public key $\mathbf{P} \in \Zq^{n \times m}$.  Details are given in Appendix~\ref{optimized}.

\subsection{Security}
The security of the above \OTA protocol against static corruptions is stated by the following theorems.

\begin{theorem} \label{sender-sec}
The   $\OTA$ protocol provides receiver security under the $\SIS$ assumption.
\end{theorem}

\begin{proof}
 We prove that any real-world cheating sender $\hat{\mathsf{S}}$ implies an ideal-world cheating sender $\hat{\mathsf{S}}'$ such that, under the $\SIS$ assumption,
 the two distributions $\REAL_{\hat{\mathsf{S}},{\mathsf{R}}}$ and $\IDEAL_{\hat{\mathsf{S}}',{\mathsf{R}}'}$ with common inputs $(N,k,M_1,\ldots,M_N,\rho_1,\ldots,\rho_k)$ are indistinguishable
to any PPT distinguisher $\ddv$.

To this end, we consider a sequence of hybrid experiments with binary outputs. In each experiment $\textsf{Exp}_i$,  a distinguisher $\ddv$ takes
as input  the states $(S_k,R_k)$ produced by $\hat{\mathsf{S}}$ and $\mathsf{R}'$ at the end of the experiment and outputs a bit. We  define $W_i$ as the event that the output of experiment $\textsf{Exp}_i$ is $1$. The first experiment outputs whatever the distinguisher $\ddv$ outputs and corresponds to the real interaction between the cheating sender $\hat{\mathsf{S}}$ and the
receiver $\mathsf{R}$. \smallskip
\begin{description}
\item[\textsf{Exp}$_0$:]  This experiment  involves a real execution of $\hat{\mathsf{S}}$ in interaction with a honest receiver $\mathsf{R}$ which queries the index $\rho_i \in [N]$ at
the $i$-th transfer for each $i \in [k]$. The output of  $\textsf{Exp}_0$
is  exactly the output of the distinguisher $\ddv$ on input of $X=(S_k,R_k)  \leftarrow \REAL_{\mathsf{S},\hat{\mathsf{R}}} $, so that
 we have
 $$\Pr[W_0]=\Pr[    \ddv (X) =1 \mid X \leftarrow \REAL_{\hat{\mathsf{S}},{\mathsf{R}}} ].$$
\item[\textsf{Exp}$_1$:]  This experiment is like $\textsf{Exp}_0$ except that, at step 5 of the initialization phase, the knowledge extractor of the argument system is used to
extract the witnesses   $\mathbf{s}_j \in \chi^n$, $\mathbf{e}_j \in \chi^m$, $\bar{\mathbf{x}}_j \in \chi^N$, $\bar{M}_j \in \{0,1\}^N$, for each $j \in [t]$,   from the sender's argument. In the event that the knowledge
extractor fails to extract valid witnesses, the experiment aborts and outputs $\perp$. We know that the zero-knowledge argument system is computationally sound
as long as  the underlying commitment is computationally binding. If  the perfectly hiding commitment of \cite{KTX08}  is used, the binding property  is in turn
 implied by the $\SIS$ assumption. Under the
$\SIS$ assumption, it follows that  $\textsf{Exp}_1$ returns $1$ with about the same probability as $\textsf{Exp}_0$. Specifically, there  exists a $\SIS$ solver $\bdv$ such that
$ | \Pr[W_1] -\Pr[W_0] | \leq \mathbf{Adv}^{\SIS}_\bdv (\lambda). $ \smallskip


\item[\textsf{Exp}$_2$:] This experiment is identical to  \textsf{Exp}$_1$ except that  the    receiver $\mathsf{R}'$ makes use of the matrix $\mathbf{S} \in \chi^{n \times t}$, which underlies $\mathbf{P} \in \ZZ_q^{m \times t}$ in
\eqref{PK-gen} and was extracted at step 5 of the initialization phase. Namely, at step 2 of each transfer, $\mathsf{R}'$ uses
 $\mathbf{S}$ to determine if the ZK argument sent by $\hat{\mathsf{S}}$ is really an argument for a true statement or if $\hat{\mathsf{S}}$ somehow managed
to break the soundness of the argument system. Namely, upon receiving the response $M ' \in \{0,1\}^t$ of $\hat{\mathsf{S}}$ at step 2, $\mathsf{R}'$
uses the previously extracted $\mathbf{S} \in \chi^{n \times t}$ to determine whether there exists a vector $\mathbf{y} \in \ZZ^t$ of norm $\| \mathbf{y} \|_{\infty}
 \leq q/5$ such that
\begin{eqnarray} \label{test-deux}
  \mathbf{c}_0^T \cdot \mathbf{S} + \mathbf{y}^T = \mathbf{c}_1^T - {M'}^T \cdot \lfloor q/2 \rfloor .
	\end{eqnarray}
If no such vector $\mathbf{y}$ exists, $\mathsf{R}'$ infers that $\hat{\mathsf{S}}$ broke the soundness of the argument system. In this case,  $\hat{\mathsf{S}}$ can be
rewound so as to break the binding property of the statistically hiding commitment scheme used by the ZK argument system, which in turn contradicts
the $\SIS$ assumption. We thus have $ | \Pr[W_2] -\Pr[W_1] | \leq \mathbf{Adv}^{\SIS}_\bdv (\lambda)  $ for some efficient algorithm $\bdv$ which
is given rewinding access to $\hat{\mathsf{S}}$.
 \smallskip

\item[\textsf{Exp}$_3$:] This experiment is like $\textsf{Exp}_2$ with the difference that, at each transfer, the receiver $\mathsf{R}'$ chooses the index $\rho_i=1$ and thus always requests
the first message of the encrypted database.  In more details, at each transfer, $\mathsf{R}'$
samples vectors $\mathbf{e} \sample U(\{-1,0,1\}^m)$, $\mu \sample U(\{0,1\}^t)$ and  $\nu \sample U([-B,B]^t)$ to compute and send
\begin{eqnarray*}
(\mathbf{c}_0,\mathbf{c}_1) = \big( \mathbf{a}_{1} + \mathbf{F} \cdot \mathbf{e} , ~\mathbf{b}_{1} + \mathbf{P}^T \cdot \mathbf{e} + \mu \cdot \lfloor q/2 \rfloor  + \nu \big) \in \ZZ_q^n \times \ZZ_q^t,
\end{eqnarray*}
which is a re-randomization of $(\mathbf{a}_{1},\mathbf{b}_{1} + \mu \cdot \lfloor q/2 \rfloor   )$.
Moreover,   $\mathsf{R}_\mathsf{T}'$ uses the witness $\rho_i=1$ to faithfully generate an interactive \textsf{WI} argument that
   $(\mathbf{c}_0,\mathbf{c}_1)$ is a re-randomization of $(\mathbf{a}_{\rho_i},\mathbf{b}_{\rho_i})$.
   It thus generates a \textsf{WI} argument of knowledge of vectors $\mathfrak{m} = \mathsf{vdec}_{n+t,q-1}(\mathbf{a}_1| \mathbf{b}_1) \in \{0,1\}^{m_d}$, $\mathbf{e} \in \{-1,0,1\}^t$, $\mu \in \{0,1\}^t$,
$\nu \in [-B,B]^t$, $\tau \in \{0,1\}^{\ell}$ and $(\mathbf{v}_1^T | \mathbf{v}_2^T)^T \in \ZZ^{2m}$ satisfying relations~\eqref{eq:protocol-3-original}. %(\ref{statement-rand-un})-(\ref{statement-rand-deux}).
By the statistically \textsf{WI} of the interactive argument system, this modification has no noticeable impact on the output distribution of a cheating sender $\hat{\mathsf{S}}$. Indeed, since we chose $B$ as a randomization parameter
such that $(m+1) \alpha q / B $ is negligible, the result of \cite[Section 4.1]{DS16} implies that always re-randomizing
$(\mathbf{a}_{1},\mathbf{b}_{1} + \mu \cdot \lfloor q/2 \rfloor   )$ leaves the view of $\hat{\mathsf{S}}$ statistically unchanged.
We have  $ | \Pr[W_2] -\Pr[W_1] | \leq \mathsf{negl}(\lambda). $ \smallskip
\end{description}
In $\textsf{Exp}_3$, we can define the  ideal-world cheating sender $\hat{\mathsf{S}}'$ which emulates the honest receiver $\mathsf{R}'$ interacting with $\hat{\mathsf{S}}$. At the initialization
phase,  $\hat{\mathsf{S}}'$ appeals to the knowledge extractor of the argument system so as to extract the small-norm matrices $\mathbf{S} = [\mathbf{s}_1|\ldots|\mathbf{s}_t] \in \chi^{n \times t}$
and $\mathbf{E}=[\mathbf{e}_1| \ldots |\mathbf{e}_t] \in \chi^{m \times t}$  satisfying \eqref{PK-gen}. Armed with the decryption key $\mathbf{E} \in \chi^{m \times t}$ of the cryptosystem,
$\hat{\mathsf{S}}'$ can decrypt $\{(\mathbf{a}_i,\mathbf{b}_i)\}_{i=1}^N$ and obtain the messages $M_1,\ldots,M_N \in \{0,1\}^N$ that were encrypted in \eqref{init-db} by $\hat{\mathsf{S}}$.
It then submits  $M_1,\ldots,M_N \in \{0,1\}^N$ to the trusted party $\mathsf{T}$. As in $\textsf{Exp}_2$, during each transfer phase,  $\hat{\mathsf{S}}'$ computes $(\mathbf{c}_0,\mathbf{c}_1)$ as
a re-randomization of $(\mathbf{a}_1,\mathbf{b}_1) \in \ZZ_q^n \times \ZZ_q^t$ and faithfully generates the receiver's argument of knowledge using the witness $\rho_i=1$ at step 1.
 At step 2 of each transfer,  $\hat{\mathsf{S}}'$ plays the role of the verifier on behalf of $\mathsf{R}'$ in the interactive zero-knowledge argument generated by $\hat{\mathsf{S}}$. If  $\hat{\mathsf{S}}'$ detects that  $\hat{\mathsf{S}}$ creates a verifying argument for a false statement (which $\hat{\mathsf{S}}'$ can detect using the
extracted matrix $\mathbf{S} \in \ZZ^{n \times t}$,  by applying the test
 \eqref{test-deux}), it aborts the interaction as in $\textsf{Exp}_3$.
 If the ZK
argument involves a true statement,    $\hat{\mathsf{S}}'$ sends $1$ to the trusted party $\mathsf{T}$ so as to authorize the transfer in the ideal world. Otherwise,  $\hat{\mathsf{S}}'$ sends $0$ to  $\mathsf{T}$.
At the end of the $k$-th transfer phase,  $\hat{\mathsf{S}}'$ outputs whatever  $\hat{\mathsf{S}}$ outputs as its final state $S_k$.

In $\textsf{Exp}_3$, it is easy to see that
$$ \Pr[W_3] =  \Pr[    \ddv (X) =1 \mid X \leftarrow \IDEAL_{\hat{\mathsf{S}}',{\mathsf{R}}'} ] .$$
When putting the above altogether, we find that there exists  a PPT $\SIS$ solver $\bdv$  such that
\begin{multline*}
|  \Pr[    \ddv (X) =1 \mid X \leftarrow \REAL_{\hat{\mathsf{S}},{\mathsf{R}}} ] \\ -  \Pr[    \ddv (X) =1 \mid X \leftarrow \IDEAL_{\hat{\mathsf{S}}',{\mathsf{R}}'} ] | \leq 2 \cdot \mathbf{Adv}_\bdv^{\SIS}(\lambda)
+ \mathsf{negl}(\lambda) ,
\end{multline*}
  which proves the result.
\end{proof}

\begin{theorem} \label{rec-sec}
The   $\OTA$ protocol provides sender security under the $\SIS$ and $\LWE$ assumptions.
\end{theorem}

%-------------------- PROOF --------------------
\begin{proof}
Given a real malicious receiver $\hat{\mathsf{R}}$, we construct a cheating receiver $\hat{\mathsf{R}}'$ in the ideal world such that, under the $\SIS$ and $\LWE$ assumption, no PPT distinguisher $\ddv$ can tell apart
the  distributions $\REAL_{\mathsf{S},\hat{\mathsf{R}}}$ and $\IDEAL_{\mathsf{S}',\hat{\mathsf{R}}'}$ under common inputs: $N$, $k$, $M_1,\ldots,M_N$, $\rho_1,\ldots,\rho_k$.

To do this, we proceed again via a sequence of hybrid experiments with binary outputs.
For each $i$, we consider the probability that a distinguisher $\ddv$ outputs $1$ on input of the states $(S_k,R_k)$ that constitute the outcome of experiment $\textsf{Exp}_i$. We also define $W_i$ to be the event that  experiment $\textsf{Exp}_i$ outputs $1$.

\begin{description}
\item[\textsf{Exp}$_0$:] This experiment  corresponds to a real execution of $\hat{\mathsf{R}}$ in interaction with a honest sender $\mathsf{S}(M_1,\ldots,M_N)$. The output of the experiment
is identical to that of the distinguisher $\ddv$ on input of $X=(S_k,R_k)  \leftarrow \REAL_{\mathsf{S},\hat{\mathsf{R}}} $.
 We have
 $$\Pr[W_0]=\Pr[    \ddv (X) =1 \mid X \leftarrow \REAL_{\mathsf{S},\hat{\mathsf{R}}} ].$$

\item[\textsf{Exp}$_1$:]  This experiment departs from $\textsf{Exp}_0$ in that,
when the dishonest receiver $\hat{\mathsf{R}}_{\mathsf{T}}$ sends the ciphertext $(\mathbf{c}_0,\mathbf{c}_1) \in \Zq^n \times \Zq^t$
 at step 1 of each transfer, the knowledge extractor of the argument system is used to
extract the witnesses  $\mathfrak{m}   \in \{0,1\}^{m_d}$, $\mathbf{e} \in \{-1,0,1\}^t$, $\mu \in \{0,1\}^t$,
$\nu \in [-B,B]^t$, $\tau \in \{0,1\}^{\ell}$ and $\mathbf{v} =(\mathbf{v}_1^T | \mathbf{v}_2^T)^T \in \ZZ^{2m}$ which
satisfy \eqref{eq:protocol-3-original}. %(\ref{statement-rand-un})-(\ref{statement-rand-deux}).
If the knowledge extractor fails to produce valid witnesses at some transfer, the experiment aborts and outputs $\perp$. Recall that the zero-knowledge argument system is computationally sound
if the underlying commitment is binding, which is equivalent to the $\SIS$ assumption if the perfectly hiding commitment of \cite{KTX08} is used. Under the
$\SIS$ assumption, experiment $\textsf{Exp}_1$ returns $1$ with about the same probability as $\textsf{Exp}_0$.  There thus exists a $\SIS$ solver $\bdv$ such that
$ | \Pr[W_1] -\Pr[W_0] | \leq  k \cdot \mathbf{Adv}^{\SIS}_\bdv (\lambda)  $, where $k$ is the number of transfers.

\item[\textsf{Exp}$_2$:] This experiment is identical to $\textsf{Exp}_1$ except that, at step 1 of each transfer, the experiment aborts if the extracted
  witnesses  $\mathfrak{m} \in \{0,1\}^{m_d}$, ${\mathbf{e} \in \{-1,0,1\}^t}$, $\mu \in \{0,1\}^t$,
$\nu \in [-B,B]^t$, $\tau \in \{0,1\}^{\ell}$ and $\mathbf{v} =(\mathbf{v}_1^T | \mathbf{v}_2^T)^T \in \ZZ^{2m}$ are such that the product
\begin{eqnarray*}
  \left[ \begin{array}{c} \mathbf{a}_{\mathfrak{m}} \\ \hline \mathbf{b}_{\mathfrak{m}} \end{array} \right]  =  \left[ \begin{array}{cc}
\mathbf{H}_{n,q-1}  ~ &  ~  ~       \\  \hline
&   ~\mathbf{H}_{t,q-1}~
 \end{array} \right] \cdot  \mathfrak{m}  ~ \in \Zq^{n + t}
\end{eqnarray*}
does not match any   ciphertext  $\{(\mathbf{a}_i,\mathbf{b}_i)\}_{i=1}^N$ appearing in $R_0$ (namely, we have $(\mathbf{a}_{\mathfrak{m}} ,  \mathbf{b}_{\mathfrak{m}}) \neq (\mathbf{a}_i,\mathbf{b}_i)$
for each $i \in  [N]$). We claim that such an event implies a breach in the bounded message security of the signature scheme: \smallskip

\begin{lemma} \label{sig-rely}
Under the $\SIS$   assumption, experiments $\mathsf{Exp}_2$ and $\mathsf{Exp}_1$ are computationally indistinguishable: there exists a PPT algorithm $\bdv$ such that
$|\Pr[W_2]-\Pr[W_1]| \leq N \cdot \mathbf{Adv}^{\SIS}_\bdv(\lambda)$.
\end{lemma}

\smallskip \smallskip

\item[\textsf{Exp}$_3$:] This experiment is like $\textsf{Exp}_2$ except that, at step 5 of the initialization phase, the zero-knowledge argument of knowledge of
   $\mathbf{s}_j \in \chi^n$, $\mathbf{e}_j \in \chi^m$, $\bar{\mathbf{x}}_j \in \chi^N$, $\bar{M}_j \in \{0,1\}^N$ such that
\begin{eqnarray*} \label{sender-proof-sim}
  \left[ \begin{array}{c|c|c|c} ~ \mathbf{F}^T  ~ & ~ \mathbf{I}_m  ~ & ~  & ~ ~\\ \hline
      \rule{0pt}{2.5ex}~\mathbf{A}_{\mathsf{DB}}^T  ~ & ~  ~ & ~ \mathbf{I}_N  ~ &  ~ \lfloor q/2 \rfloor \cdot \mathbf{I}_N  ~
     \end{array} \right]
     \cdot  \left[ \begin{array}{c} \mathbf{s}_j \\ \hline \mathbf{e}_j \\ \hline \bar{\mathbf{x}}_j \\ \hline \rule{0pt}{2.5ex} \bar{{M}}_j \end{array} \right]  = \left[ \begin{array}{c}
\mathbf{p}_j \\ \hline
\bar{\mathbf{b}}_j
\end{array} \right] \qquad \forall j \in [t]
\end{eqnarray*}
is replaced by  a simulated interactive argument  and
so is the ZK argument of knowledge of $\{(\mathbf{s}_j,\mathbf{e}_j,\mathbf{y}[j])\}_{j=1}^t$ satisfying \eqref{eq:protocol-2-original}
%\eqref{sender-proof-two}
at step 2 of each transfer protocol. From this experiment on,
 we notice that
the small-norm matrices  $\mathbf{S}=[\mathbf{s}_1 | \ldots |\mathbf{s}_t] \in \ZZ^{n \times t}$, $\mathbf{E} = [\mathbf{e}_1 | \ldots | \mathbf{e}_t ] \in \chi^{m \times t}$ satisfying
\eqref{PK-gen}
are no longer used by the sender $\mathsf{S}$. Yet, the statistical  ZK property of the zero-knowledge argument system ensures that
$|\Pr[W_3]-\Pr[W_2]| \leq \mathsf{negl}(\lambda)$. \smallskip

\item[\textsf{Exp}$_4$:] This experiment is like $\textsf{Exp}_3$ with the difference that, at step 2 of the initialization phase, each column $\mathbf p_i$ of the Regev's encryption public key matrix $\mathbf{P}= \left[ \mathbf{p}_1 \mid \ldots \mid \mathbf{p}_t \right] = \mathbf{F}^T \cdot \mathbf{S} + \mathbf{E} \in \Zq^{m \times t}$ is traded for a uniformly random vector $\mathbf{p}_i \gets U(\ZZ_{q}^{m})$.
  At the same time, each $\mathbf b_i = \mathbf S^T \cdot \mathbf a_i + \mathbf x_i + M_i \lfloor \tfrac{q}{2} \rfloor \in \Zq^t$ is replaced by a truly uniform random vector in $\Zq^t$.
  Therefore, $\mathbf P$ is a uniformly distributed matrix in $\Zq^{m \times t}$, and the $(\mathbf b_i)_{i=1}^N$ are distributed as uniform vectors in $(\Zq^t)^N$.
  Now, at step 5 of the initialization phase and step 2 of each transfer,  the sender's zero-knowledge arguments are simulated arguments for false statements.
  However, a straightforward reduction shows that, under the $\LWE$ assumption over $t\cdot(m + N)$ samples,
  these changes should remain unnoticed to the malicious receiver $\hat{\mathsf{R}}$ and have no impact on the distinguisher's output: we have $|\Pr[W_4]-\Pr[W_3]| \leq \mathbf{Adv}^{\LWE}_\bdv(\lambda)$. \smallskip


%\item[\textsf{Exp}$_5$:] In this experiment, we modify again the initialization phase and replace $\{(\mathbf{a}_i,\mathbf{b}_i)\}_{i=1}^N$ by truly random pairs $(\mathbf{a}_i,\mathbf{b}_i)
%\leftarrow U(\Zq^{n} \times \Zq^t)$.% As in \cite{Reg05}, the Leftover Hash Lemma implies that this experiment is statistically indistinguishable
%from $\textsf{Exp}_4$: we have  $|\Pr[W_5]-\Pr[W_4]| \leq \mathsf{negl}(\lambda)$. \medskip

\end{description}

The ideal-world receiver $\hat{\mathsf{R}}'$ is defined as follows. It assumes the role of the sender $\mathsf{S}'$ in interaction with the real-world receiver $\hat{\mathsf{R}}$ in $\textsf{Exp}_4$.
 This implies that, in the initialization phase, the matrices $(\mathbf{F},\mathbf{P})$ are chosen as uniformly random matrices  $(\mathbf{F},\mathbf{P}) \leftarrow U(\Zq^{n \times m}
 \times \Zq^{m \times t}  )$ and while, at step 3,  $(\mathbf{a}_i,\mathbf{b}_i) \leftarrow U(\Zq^{n} \times \Zq^t)$ is chosen at random for each $i \in [N]$.
The randomly generated pairs $\{(\mathbf{a}_i,\mathbf{b}_i)\}_{i=1}^N$ are faithfully signed using $SK_{sig}=\mathbf{T}_{\mathbf{A}}$ at step 4. In step 5 of the initialization phase,
$\hat{\mathsf{R}}'$ appeals to the  simulator of the ZK argument. At the $i$-th transfer, when $\hat{\mathsf{R}}$ sends $(\mathbf{c}_0,\mathbf{c}_1)$ and argues knowledge
of $(\mathfrak{m},\mathbf{e},\mu,\nu,\tau,\mathbf{v}_1,\mathbf{v}_2)$ at step 1,  $\hat{\mathsf{R}}'$ uses the knowledge extractor of the argument system to extract the witnesses
 $(\mathfrak{m},\mathbf{e},\mu,\nu,\tau,\mathbf{v}_1,\mathbf{v}_2) \in \{0,1\}^{m_d} \times \{-1,0,1\}^t \times \{0,1\}^t \times [-B,B]^t \times \{0,1\}^{\ell}$  and determine
the index $\rho_i \in [N]$ such that
\begin{eqnarray*}
  \left[ \begin{array}{c} \mathbf{a}_{\rho_i} \\ \hline \mathbf{b}_{\rho_i} \end{array} \right] =  \left[ \begin{array}{cc}
\mathbf{H}_{n,q-1}  ~ &  ~  ~       \\  \hline
&   ~\mathbf{H}_{t,q-1}~
 \end{array} \right] \cdot  \mathfrak{m}  ~ \in \Zq^{n + t}.
\end{eqnarray*}
Note that, by Lemma \ref{sig-rely}, such an index must exist unless $\hat{\mathsf{R}}$ can forge a signature. Having determined  the index  $\rho_i \in [N]$ of the queried
database entry, $\hat{\mathsf{R}}'$ sends $\rho_i$ to  the trusted party $\mathsf{T}$  which returns  the message $M_{\rho_i} \in \{0,1\}^t$. The latter is used together with the
extracted witness $\mu \in \{0,1\}^t$ to define the response $M'=M_{\rho_i} \oplus \mu \in \{0,1\}^t$ that  $\hat{\mathsf{R}}'$ generates on behalf of the sender $\hat{\mathsf{S}}'$ at step 2 of the transfer. In addition,
the ideal-world dishonest receiver $\hat{\mathsf{R}}'$ appeals to the simulator of the zero-knowledge argument system to simulate an argument of knowledge
of $\{(\mathbf{s}_j,\mathbf{e}_j,\mathbf{y}[j])\}_{j=1}^t$ for the statement~\eqref{eq:protocol-2-original}.

It is easy to see that, when $\hat{\mathsf{R}}$ interacts with the simulator $\hat{\mathsf{R}}'$ that emulates the real-world sender $\mathsf{S}'$, its view is identical to that
 of $\textsf{Exp}_4$: we have
$$ \Pr[W_4] =  \Pr[    \ddv (X) =1 \mid X \leftarrow \IDEAL_{{\mathsf{S}}',\hat{\mathsf{R}}'} ] .$$
When combining the above, we conclude that there exist  PPT algorithms $\bdv$ and $\bdv'$ such that
\begin{multline*}
|  \Pr[    \ddv (X) =1 \mid X \leftarrow \REAL_{{\mathsf{S}},\hat{\mathsf{R}}} ] \\ -  \Pr[    \ddv (X) =1 \mid X \leftarrow \IDEAL_{{\mathsf{S}}',\hat{\mathsf{R}}'} ] | \leq 2 \cdot \mathbf{Adv}_\bdv^{\SIS}(\lambda)
 + \mathbf{Adv}_{\bdv'}^{\LWE}(\lambda)
+ \mathsf{negl}(\lambda) .  \end{multline*}
This proves the sender security under the $\SIS$  and $\LWE$ assumptions.
\end{proof}









%%%%%%%%%%%% Access control







\section{OT with Access Control for Branching Programs} \label{OT-AC-scheme}

In this section, we extend our  protocol of Section  \ref{OT-scheme} into a protocol where database entries can be protected
by access control policies consisting of branching programs. In a nutshell, the construction goes as follows.

When the database is set up, the sender signs (a binary representation of) each database entry $(\mathbf{a}_i,\mathbf{b}_i)$ together
with a  hash value $\mathbf{h}_{\BPR,i} \in \Zq^n$ of the corresponding branching program. For each possessed attribute $\mathbf{x} \in \{0,1\}^\kappa$,
the user $\USR$
obtains  a credential $\mathsf{Cred}_{\USR,\mathbf{x}}$ from the issuer. \\ \indent If $\USR$ has a credential $\mathsf{Cred}_{\USR,\mathbf{x}}$ for an attribute $\mathbf{x}$ satisfying
the $\rho$-th branching program, $\USR$ can re-randomize  $(\mathbf{a}_\rho,\mathbf{b}_\rho)$ into $(\mathbf{c}_0,\mathbf{c}_1)$, which is given to the sender,
while proving that: (i) He knows a signature
$(\tau,\mathbf{v})$ on some message $(\mathbf{a}_\rho,\mathbf{b}_\rho,\mathbf{h}_{\BPR,\rho})$ such that $(\mathbf{c}_0,\mathbf{c}_1)$ is a re-randomization of
$(\mathbf{a}_\rho,\mathbf{b}_\rho)$; (ii) The corresponding $\mathbf{h}_{\BPR,\rho}$ is the hash value of (the binary representation of) a branching program
$\BPR_{\rho}$ that accepts an   attribute $\mathbf{x} \in \{0,1\}^\kappa$ for which he has a valid credential $\mathsf{Cred}_{\USR,\mathbf{x}}$
(i.e., $\BPR_{\rho}(\mathbf{x})=1$). \\
\indent While statement (i) can be proved as in Section \ref{OT-scheme}, handling (ii) requires a method of proving the possession of a (committed) branching program $\BPR$ and a (committed) input $\mathbf{x} \in \{0,1\}^\kappa$ such that $\BPR(\mathbf{x})=1$ while demonstrating possession of a credential for
$\mathbf{x}$.




Recall that a branching program $\BPR$ of length $L$, input space $\{0,1\}^{\kappa}$ and width $5$ is specified by $L$ tuples of the
form  $(\var(\theta),\pi_{\theta,0},\pi_{\theta,1})$ where
\begin{itemize}
\item[-] $\var: [L] \rightarrow [0, \kappa-1]$ is a function that associates the  $\theta$-th tuple with the coordinate ${x}_{\var(\theta)} \in \{0,1\}$ of
the input $\mathbf{x} = (x_0, \ldots, x_{\kappa-1})^T$.
\item[-] $\pi_{\theta,0},\pi_{\theta,1} : \{0,1,2,3,4\} \rightarrow   \{0,1,2,3,4\}$ are permutations that determine the $\theta$-th step of the
evaluation.
\end{itemize}
On input $\mathbf{x} = (x_0, \ldots, x_{\kappa-1})^T$, $\BPR$ computes its output as follows.
For each bit $b \in \{0,1\}$, let $\bar{b}$ denote the bit $1-b$.
Let $\eta_\theta$ denote the state of computation at step $\theta$. The initial state is  $\eta_0 = 0$ and, for $\theta \in [1,L]$, the state $\eta_\theta$ is computed as
\[
\eta_\theta = \pi_{\theta, x_{\mathrm{var}(\theta)}}(\eta_{\theta-1}) = \pi_{\theta, 0}(\eta_{\theta-1})\cdot \bar{x}_{\mathrm{var}(\theta)} + \pi_{\theta, 1}(\eta_{\theta-1})\cdot {x}_{\mathrm{var}(\theta)}.
\]
Finally, the output of evaluation is $\mathsf{BP}(\mathbf{x})=1$ if $\eta_L =0$, otherwise $\mathsf{BP}(\mathbf{x})=0$.

We now let $\delta_{\kappa} =  \lceil\log_2 \kappa\rceil$ and note that each integer in $[0,\kappa-1]$ can be determined by $\delta_\kappa$ bits. In particular, for each $\theta \in [ L]$, let $d_{\theta,1}, \ldots, d_{\theta, \delta_\kappa}$ be the bits representing $\mathrm{var}(\theta)$. Then, we consider the following representation of $\mathsf{BP}$:
\begin{multline}\label{equation:z_BP}
%\nonumber
\hspace*{-12pt}  \mathbf{z}_{\mathsf{BP}} = \big(
d_{1,1}, \ldots, d_{1, \delta_\kappa}, \ldots, d_{L,1}, \ldots, d_{L, \delta_\kappa}, \pi_{1,0}(0), \ldots, \pi_{1,0}(4), \pi_{1,1}(0), \ldots, \\
%&& \hspace*{-25pt}
\pi_{1,1}(4),   \ldots,
\pi_{L,0}(0), \ldots, \pi_{L,0}(4), \pi_{L,1}(0), \ldots, \pi_{L,1}(4)
\big)^T \in [0,4]^{\zeta}, ~~~
\end{multline}
where $\zeta= L(\delta_\kappa +10)$.

\subsection{The OT-AC Protocol} \label{the-ot-ac}




We assume public parameters $\pp$
consisting of a modulus $q$, integers $n$, $m$ such that $m = 2n \lceil \log q \rceil$,  a public matrix $\bar{\mathbf{A}} \in \Zq^{n \times m}$,
the maximal length $L \in \mathsf{poly}(n)$ of branching programs and their desired input length $\kappa \in \mathsf{poly}(n)$.
\smallskip

\begin{description}
  \item[\textsf{ISetup}$\big(\pp     \big)$:] Given public parameters $\pp=\{ q,n,m, \bar{\mathbf{A}}, L,\kappa\}$, first generate a key pair $(PK_{I},SK_{I})\gets \mathsf{Keygen}(\pp,1)$ for the signature scheme
     in Section \ref{se:gs-lwe-sigep} in order to sign single-block messages (i.e., $N_b=1$) of length $m_I = n \cdot \lceil \log q \rceil + \kappa$. %$m=2 n \lceil \log q \rceil$.
    Letting $\ell_I = \mathcal{O}(n)$, this key pair contains $SK_{I}=\mathbf{T}_{\mathbf{A}_I}
    \in \ZZ^{m \times m}$ and
    $${PK}_{I}:=\big( \mathbf{A}_I, ~
    \{\mathbf{A}_{I,j} \}_{j=0}^{\ell_{I}}, ~\mathbf{D}_I, ~ \{ \mathbf{D}_{I,0}, \mathbf{D}_{I,1}\} , ~\mathbf{u}_I \big).$$
  \item[\textsf{Issue}$\big( \mathsf{I}(\pp,SK_I,PK_I,P_\USR,\mathbf{x}) \leftrightarrow \mathsf{U}(\pp,\mathbf{x},st_\USR)     \big)$:]
    On  common input $\mathbf{x} \in \{0,1\}^\kappa$, the issuer
    $\mathsf{I}$ and the user $\USR$ interact in the following way: \smallskip
    \begin{itemize}
      \item[1.] If $st_{\USR} = \emptyset$,   $\USR$ creates a pseudonym $P_\USR= \bar{\mathbf{A}} \cdot \mathbf{e}_{\USR} \in \Zq^n$, for a randomly chosen    $\mathbf{e}_{\USR} \sample U(\{0,1\}^m)$, which is sent to $\mathsf{I}$. It sets
        $st_{\USR}=(\mathbf{e}_\USR, P_\USR, 0, \emptyset ,\emptyset)$.  Otherwise, $\USR$ parses its state $st_\USR$ as $(\mathbf{e}_\USR,P_{\USR},f_{DB},C_\USR,\mathsf{Cred}_{\USR})$.
      \item[2.] The issuer $\mathsf{I}$  defines the message $\mathfrak{m}_{\USR,\mathbf{x}} = (\mathsf{vdec}_{n,q-1}(P_{\USR})^T|\mathbf{x}^T )^T \in \{0,1\}^{m_I}$.
        Then, it runs the signing algorithm of Section    \ref{se:gs-lwe-sigep}  to obtain  and return
        $\crt_{\USR,\mathbf{x}} = \big(\tau_{\USR},\mathbf{v}_{\USR},\mathbf{r}_{\USR} \big) \leftarrow \mathsf{Sign}(SK_I,\mathfrak{m}_{\USR,\mathbf{x}}) \in \{0,1\}^{\ell_{I}} \times \ZZ^{2m} \times \ZZ^{m}$, which binds $\USR$'s pseudonym $P_\USR$
        to the attribute string $\mathbf{x} \in \{0,1\}^\kappa$.
      \item[3.] $\USR$ checks that $\crt_{\USR,\mathbf{x}}$
        satisfies \eqref{ver-eq-block} and that $\|\mathbf{v}_\USR\| \leq \sigma \sqrt{2m},\mathbf{r}_\USR \leq \sigma \sqrt{m}$. If so, $\USR$ sets
        $C_\USR := C_{\USR} \cup \{\mathbf{x}\}$, $\mathsf{Cred}_\USR := \mathsf{Cred}_\USR \cup \{\crt_{\USR,\mathbf{x}}\}$ and updates its state $st_\USR=(\mathbf{e}_\USR,P_\USR,f_{DB},C_\USR,\mathsf{Cred}_\USR)$. If $\crt_{\USR,\mathbf{x}}$  does not properly verify, $\USR$ aborts the interaction and leaves $st_{\USR}$ unchanged. \smallskip
    \end{itemize}
  \item[\textsf{DBSetup}$\big(PK_I, \mathsf{DB}=\{(M_i,\BPR_i)\}_{i=1}^N \big)$:] The sender % \textsf{DB}
    has $\mathsf{DB}=\{(M_i,\BPR_i)\}_{i=1}^N $ which is a database  of $N$ pairs made of a   message
    $M_i \in \{0,1\}^{t}$ and a   policy realized by a length-$L$
    branching program $\BPR_i = \{\var_i(\theta),\pi_{i,\theta,0},\pi_{i,\theta,1}\}_{\theta=1}^L$.  %.of length $L \in \mathsf{poly}(n)$,
    \smallskip \smallskip
    \begin{itemize}
      \item[1.] Choose a random matrix $\mathbf{A}_{\mathrm{HBP}} \sample U \big(\Zq^{n \times \zeta } \big)$ which will be used to hash the description of
        branching programs.
      \item[2.] Generate a key pair for the signature scheme of Section \ref{RMA-sec} in order to sign $Q=N$ messages of length $m_d = (2n+t) \cdot \lceil \log q \rceil$ each.
        This key pair consists of $SK_{sig}=\mathbf{T}_{\mathbf{A}} \in \ZZ^{m \times m}$ and
        ${PK}_{sig}:=\big( \mathbf{A},
        \{\mathbf{A}_j \}_{j=0}^{\ell},   \mathbf{D}, \mathbf{u} \big),$ where $\ell=\lceil \log N \rceil$ and $\mathbf{A},\mathbf{A}_0,\ldots,\mathbf{A}_{\ell} \in U(\Zq^{n \times m})$, $\mathbf{D} \in U(\Zq^{n \times m_d})$ with
        $m = 2n \lceil \log q \rceil$, $m_d = (2n+t) \lceil \log q \rceil$. The counter is initialized to $\tau=0$.

      \item[3.] Sample  $\mathbf{S} \sample \chi^{n \times t}$ which will serve as a secret key  for an $\LWE$-based encryption scheme.
        Then, sample   $\mathbf{F} \sample U(\Zq^{n \times m})$, $\mathbf{E} \sample \chi^{m \times t  }$ to compute
        \begin{eqnarray} \label{PK-gen-ac}
          \mathbf{P} = [\mathbf{p}_1 | \ldots | \mathbf{p}_t]  =  \mathbf{F}^T \cdot \mathbf{S}  + \mathbf{E} ~\in \Zq^{m \times t}
        \end{eqnarray}
        so that $(\mathbf{F},\mathbf{P})  $  forms a public key for a $t$-bit variant of Regev's system.
      \item[4.]
        Sample    vectors $\mathbf{a}_1,\ldots ,\mathbf{a}_N \sample
        U(\Zq^n)$ and $\mathbf{x}_1,\ldots,\mathbf{x}_{N} \sample \chi^{t}$ to
        compute
        \begin{eqnarray} \label{init-db-ac}
          (\mathbf{a}_i,\mathbf{b}_i)= \bigl( \mathbf{a}_i, ~ \mathbf{a}_i^T \cdot \mathbf{S} + \mathbf{x}_i + M_i \cdot \lfloor q/2 \rfloor  \bigr) \in \Zq^n \times \Zq^{t} \qquad  \forall i \in [N]
          \qquad
        \end{eqnarray}

      \item[5.] For each $i=1$ to $N$, $ (\mathbf{a}_i,\mathbf{b}_i)$ is bound to $\BPR_i$ as follows. \smallskip  \begin{itemize} \item[a.]
            Let $\mathbf{z}_{\BPR,i}  \in [0,4]^\zeta $ be the binary representation of the branching program.
            Compute its digest $\mathbf{h}_{\BPR,i} = \mathbf{A}_{\mathrm{HBP}} \cdot \mathbf{z}_{\BPR,i} \in \Zq^n$.
						 % via the matrix $\mathbf{A}_{\mathrm{HBP}} \in \Zq^{n \times \zeta} $.
          \item[b.]  Using $SK_{sig}$, generate a signature $(\tau_i,\mathbf{v}_i ) \leftarrow \mathsf{Sign}(SK_{sig},\tau,\mathfrak{m}_i)$ on the message
            $\mathfrak{m}_i=\mathsf{vdec}_{2n+t,q-1}(\mathbf{a}_i|\mathbf{b}_i|\mathbf{h}_{\BPR,i}) \in \{0,1\}^{m_d}$ obtained by decomposing $(\mathbf{a}_i^T | \mathbf{b}_i^T | \mathbf{h}_{\BPR,i}^T )^T \in \Zq^{2n+t}$.
        \end{itemize}
      \item[6.] The database's public key is defined as
        $ PK_{\mathrm{DB}}= \bigl(  PK_{sig} ,~(\mathbf{F},\mathbf{P}),~\mathbf{A}_\mathrm{HBP}\bigr) $
        while the encrypted database is
        $  \{ER_i=\big(\mathbf{a}_i,\mathbf{b}_i,(\tau_i,\mathbf{v}_i ) \big), \BPR_i \}_{i=1}^N.  $
        The   sender $\mathsf{DB}$ outputs
        $  \bigl(  PK_{\mathrm{DB}} ,\{ER_i, \BPR_i \}_{i=1}^N \bigr) $
        and keeps   $SK_{\mathsf{DB}}=\big(SK_{sig},\mathbf{S} \big)$.\smallskip
        \end{itemize}

  \item[\textsf{Transfer}$\big(\mathsf{DB}(SK_{\mathsf{DB}},PK_{\mathsf{DB}},PK_I),\USR(\rho,st_\USR,PK_I,PK_\mathsf{DB},ER_\rho,\BPR_\rho) \big)$:]
    From an index $\rho \in [N]$, a record
    $ER_\rho =\big(\mathbf{a}_\rho,\mathbf{b}_\rho,(\tau_\rho,\mathbf{v}_\rho ) \big) $ and a policy $\BPR_{\rho}$, the user $\USR$ parses
    $st_\USR$ as $(\mathbf{e}_\USR,P_{\USR},f_{DB},C_\USR,\mathsf{Cred}_{\USR})$. If $C_\USR$ does not contain any $\mathbf{x} \in \{0,1\}^\kappa$ s.t.
    $\BPR_{\rho}(\mathbf{x})=1$ and $\mathsf{Cred}_{\USR}$ contains the corresponding   $\crt_{\USR,\mathbf{x}}$, $\USR$ outputs $\perp$. Otherwise, he
    selects  such a pair $(\mathbf{x},\crt_{\USR,\mathbf{x}})$ and interacts with $\mathsf{DB}$: \smallskip
    \begin{itemize}
      \item[1.] If $f_{DB}=0$, $\USR$ interacts with $\mathsf{DB}$ for the first time and requires $\mathsf{DB}$ to prove knowledge of small-norm   $\mathbf{S} \in \ZZ^{n \times t}$, $\mathbf{E} \in \ZZ^{m \times t}$,   $\{\mathbf{x}_i\}_{i=1}^N$ and
$t$-bit messages $\{M_i\}_{i=1}^N$ satisfying~\eqref{PK-gen-ac}-\eqref{init-db-ac}. To do this, $\mathsf{DB}$ uses the  ZK argument     in Section~\ref{subsection:ZK-protocol-1}.
       % to  prove knowledge of  short matrices $\mathbf{S} \in \ZZ^{n \times t}$ and $\mathbf{E} \in \chi^{m \times t}$ and
       % $t$-bit messages $\{M_i\}_{i=1}^N$                              -
        %satisfying (\ref{PK-gen-ac})-(\ref{init-db-ac}). To this end, $\mathsf{DB}$ does the following.  \smallskip \smallskip
        %\begin{itemize}
         % \item[a.]
          %  Define  $\mathbf{A}_{\mathsf{DB}}=[\mathbf{a}_1 | \ldots | \mathbf{a}_N] \in \Zq^{n \times N}$, $\mathbf{B}_{\mathsf{DB}}=[\mathbf{b}_1 | \ldots | \mathbf{b}_N] \in \Zq^{t \times N}$, $\mathbf{M}=[M_1 | \ldots | M_N]
           % \in \{0,1\}^{t \times N}$,
            %$\mathbf{X}=[\mathbf{x}_1 | \ldots | \mathbf{x}_N] \in \chi^{ t \times N}$
            %and parse $\mathbf{S}$ and $\mathbf{E}$ as $\mathbf{S}=[\mathbf{s}_1 | \ldots | \mathbf{s}_t] \in \chi^{n \times t}$,
            %$\mathbf{E}=[\mathbf{e}_1 | \ldots | \mathbf{e}_t] \in \chi^{m \times t}$.
          %\item[b.] For each $j \in [t]$, define $\bar{M}_j \in \{0,1\}^N$ to be the $j$-th column  of  $\mathbf{M}^T$. Likewise,
           % let $\bar{\mathbf{b}}_j \in \Zq^N$ (resp. $\bar{\mathbf{x}}_j \in \chi^N$) be the $j$-th column of $\mathbf{B}_{\mathsf{DB}}^T \in \Zq^{N \times t}  $
            %(resp.  $\mathbf{X}^T  $).  Note that (\ref{init-db-ac}) can be written
            %\begin{eqnarray*}
             % \mathbf{B}_{\mathsf{DB}}^T = \mathbf{A}_{\mathsf{DB}}^T \cdot \mathbf{S} +  \mathbf{X}^T + \mathbf{M}^T \cdot \lfloor q/2 \rfloor .
            %\end{eqnarray*}
            %For each $j \in [t]$, $\mathsf{DB}$ argues knowledge
            %of $\mathbf{s}_j \in \chi^n$, $\mathbf{e}_j \in \chi^m$, $\bar{\mathbf{x}}_j \in \chi^N$, $\bar{M}_j \in \{0,1\}^N$ such that
            %\begin{eqnarray} \label{sender-proof-ac}
             % \left[ \begin{array}{c|c|c|c} ~ \mathbf{F}^T  ~ & ~ \mathbf{I}_m  ~ & ~  & ~ ~\\ \hline
              %    ~\mathbf{A}_{\mathsf{DB}}^T  ~ & ~  ~ & ~ \mathbf{I}_N  ~ &  ~ \lfloor q/2 \rfloor \cdot \mathbf{I}_N  ~
              %\end{array} \right]
              %\cdot  \begin{bmatrix} \mathbf{s}_j \\ \hline \mathbf{e}_j \\ \hline \bar{\mathbf{x}}_j \\ \hline   \bar{{M}}_j  \end{bmatrix}  = \begin{bmatrix}
              %  \mathbf{p}_j \\ \hline
               % \bar{\mathbf{b}}_j
              %\end{bmatrix}
            %\end{eqnarray}
          %\item[c.]
        If there exists $i \in [N]$ such that $(\tau_i,\mathbf{v}_i)$ is an invalid signature
            on $\mathsf{vdec}_{2n+t,q-1} (\mathbf{a}_i^T|\mathbf{b}_i^T|\mathbf{h}_{\BPR,i}^T)^T   $ or if the ZK argument  does not verify, $\USR$ aborts. Otherwise, $\USR$ updates  $st_\USR$ and sets $f_{DB}=1$.
        %\end{itemize}
\end{itemize}
%\vspace*{-0.05cm}
\begin{itemize}
\item[2.] $\USR$ re-randomizes the pair $(\mathbf{a}_\rho,\mathbf{b}_\rho )$ contained in  $ER_\rho$. It samples vectors $\mathbf{e} \sample U(\{-1,0,1\}^m)$, $\mu \sample U(\{0,1\}^t)$ and  $\nu \sample U([-B,B]^t)$ to compute
\begin{eqnarray} \label{rand-CT-ac}
(\mathbf{c}_0,\mathbf{c}_1) = \big( \mathbf{a}_{\rho} + \mathbf{F} \cdot \mathbf{e} , ~\mathbf{b}_{\rho} + \mathbf{P}^T \cdot \mathbf{e} + \mu \cdot \lfloor q/2 \rfloor  + \nu \big) \in \Zq^n \times \Zq^t,
 \qquad
\end{eqnarray}
which is sent to $\mathsf{DB}$ as a re-randomization of $(\mathbf{a}_{\rho},\mathbf{b}_{\rho} + \mu \cdot \lfloor q/2 \rfloor   )$. Then, $\USR$ provides an interactive \textsf{WI} argument that   $(\mathbf{c}_0,\mathbf{c}_1)$ is  a re-randomization of some $(\mathbf{a}_{\rho},\mathbf{b}_{\rho})$ associated
with a policy $\BPR_\rho$ for which  $\USR$ has a credential $\crt_{\USR,x}$ for some $\mathbf{x} \in \{0,1\}^\kappa$ such that $\BPR_\rho (\mathbf{x})=1$.
%To this end, $\USR$ uses the technique of Section \ref{ineff-method}.
In addition, $\USR$
demonstrates possession  of: (i) a preimage $\mathbf{z}_{\BPR,\rho} \in [0,4]^\zeta $ of
$\mathbf{h}_{\BPR,\rho} = \mathbf{A}_{\mathrm{HBP}} \cdot \mathbf{z}_{\BPR,\rho} \in \Zq^n$; (ii) a credential $\mathsf{Cred}_{\USR,\mathbf{x}}$ for the corresponding $\mathbf{x} \in \{0,1\}^\kappa$ and the private key $\mathbf{e}_\USR \in \{0,1\}^m$ for the pseudonym $P_\USR$ to which $\mathbf{x}$ is bound; (iii)  the  coins leading to the randomization of some
$(\mathbf{a}_{\rho},\mathbf{b}_{\rho})$.
Then entire step is conducted
 by arguing knowledge of
\begin{eqnarray*}
\left\{
\begin{array}{l}
  \mathbf{e}_{\USR} \in \bit^m, \mathfrak{m}_{\USR,\mathbf{x}}  \in \{0,1\}^{m_I}  ,~\mathbf{x} \in \{0,1\}^\kappa,~\widehat{\mathfrak{m}}_{\USR,\mathbf{x}} \in \{0,1\}^{m/2}
 \\
\tau_{\USR} \in \{0,1\}^{\ell_I},~\mathbf{v}_{\USR}=(\mathbf{v}_{\USR,1}^T | \mathbf{v}_{\USR,2}^T)^T \in [-\beta,\beta]^{2m}, ~\mathbf{r}_{\USR} \in [-\beta,\beta]^m  \\  \qquad
	\qquad \qquad \quad    ~~~~~~~~~~~~~~  \text{ \scriptsize //   signature on $\mathfrak{m}_{\USR,\mathbf{x}}=(\mathsf{vdec}_{n,q-1}(P_\USR)^T| \mathbf{x}^T)^T $ } \\
\mathbf{z}_{\BPR,\rho} \in [0,4]^\zeta \qquad ~~~~~~~~~~~~\text{\scriptsize  // representation of $\BPR_{\rho}$  } \\
	\mathfrak{m}  \in \{0,1\}^{m_d},  ~\tau \in \{0,1\}^{\ell},~ \mathbf{v} =(\mathbf{v}_1^T | \mathbf{v}_2^T)^T \in \ZZ^{2m} \\  \qquad
	\qquad \qquad \quad ~~~~~~~~~~~~~~  \text{ \scriptsize //   signature on $\mathfrak{m}=\mathsf{vdec}_{2n+t,q-1}(\mathbf{a}_i^T| \mathbf{b}_i^T|\mathbf{h}_{\BPR,\rho}^T)^T $ } \\
	 ~\mathbf{e} \in \{-1,0,1\}^t, ~\mu \in \{0,1\}^t, ~
\nu \in [-B,B]^t,\\
	\qquad \qquad \qquad  \quad  ~~~~~~~~~~~~~~~  \text{\scriptsize // coins allowing the re-randomization of $(\mathbf{a}_{\rho},\mathbf{b}_\rho) $ }
\end{array}
 \right.
\end{eqnarray*}
satisfying the relations (modulo $q$)
%\begin{eqnarray} \label{statement-rand-un-ac}
%\mathbf{H}_{2n+t,q-1} \cdot \mathfrak{m} +
 %\left[ \begin{array}{c|c|c|c}
 %~  \mathbf{F} ~& ~ &~ & ~     \\  \hline \rule{0pt}{2.6ex}
 % ~\mathbf{P}^{T}~ & ~ \mathbf{I}_t   \lfloor q/2 \rfloor  ~ & ~\mathbf{I}_t~ & ~ \\ \hline
	 %& & & - \mathbf{A}_{\mathrm{HBP}}
 %\end{array} \right] \cdot  \begin{bmatrix}  \mathbf{e} \\ \hline  \mu  \\ \hline  \nu  \\ \hline
 % \mathbf{z}_{\BPR,\rho}
 %\end{bmatrix} &=& \begin{bmatrix} \mathbf{c}_0 \\ \hline \mathbf{c}_1 \\ \hline \mathbf{0}^n \end{bmatrix}   \qquad \quad
%\end{eqnarray}
%(recall that $(\mathbf{a}_\rho^T | \mathbf{b}_{\rho}^T | \mathbf{h}_{\BPR,\rho}^T )^T = \mathbf{H}_{2n+t,q-1} \cdot \mathfrak{m}   $)
%and
%\begin{eqnarray} \label{statement-rand-deux-ac}
%\mathbf{A}\cdot \mathbf{v}_1 + \mathbf{A}_0 \cdot \mathbf{v}_2 + \sum_{j=1}^\ell \mathbf{A}_j \cdot (\tau[j]\cdot \mathbf{v}_2) - \mathbf{D}\cdot \mathfrak{m} = \mathbf{u},
%\end{eqnarray}
{\footnotesize
  \begin{eqnarray}\label{statement-rand-trois-ac}
    \begin{cases}
      \mathbf{H}_{2n+t,q-1} \cdot \mathfrak{m} +
      \left[ \begin{array}{c|c|c|c}
          ~  \mathbf{F} ~& ~ &~ & ~     \\  \hline \rule{0pt}{2.6ex}
          ~\mathbf{P}^T ~ & ~ \mathbf{I}_t  \cdot \lfloor q/2 \rfloor  ~ & ~\mathbf{I}_t~ & ~ \\ \hline
          & & & - \mathbf{A}_{\mathrm{HBP}}
      \end{array} \right] \cdot  \begin{bmatrix}  \mathbf{e} \\ \hline  \mu  \\ \hline  \nu  \\ \hline
        \mathbf{z}_{\BPR,\rho}
      \end{bmatrix} = \begin{bmatrix} \mathbf{c}_0 \\ \hline \mathbf{c}_1 \\ \hline \mathbf{0}^n \end{bmatrix} \\ \qquad \quad \smallskip
      \text{{\scriptsize // (recall that $(\mathbf{a}_\rho^T | \mathbf{b}_{\rho}^T | \mathbf{h}_{\BPR,\rho}^T )^T = \mathbf{H}_{2n+t,q-1} \cdot \mathfrak{m}   $)}} \\[2.5pt]
      \mathbf{A}\cdot \mathbf{v}_1 + \mathbf{A}_0 \cdot \mathbf{v}_2 + \sum_{j=1}^\ell \mathbf{A}_j \cdot (\tau[j]\cdot \mathbf{v}_2) - \mathbf{D}\cdot \mathfrak{m} = \mathbf{u} \\[2.5pt]
      \mathbf{A}_{I}\cdot \mathbf{v}_{\mathsf{U},1} + \mathbf{A}_{I,0}\cdot \mathbf{v}_{\mathsf{U},2} +
      \sum_{j=1}^{\ell_I}\mathbf{A}_{I, j}\cdot (\tau_{\mathsf{U}}[j]\cdot \mathbf{v}_{\mathsf{U},2}) -  \mathbf{D}_I\cdot \widehat{\mathfrak{m}}_{\mathsf{U}, \mathbf{x}}  = \mathbf{u}_I \\[2.5pt]
      \mathbf{D}_{I,0}\cdot \mathbf{r}_{\mathsf{U}} + \mathbf{D}_{I,1}\cdot \mathfrak{m}_{\mathsf{U}, \mathbf{x}} - \mathbf{H}_{n,q-1}\cdot \widehat{\mathfrak{m}}_{\mathsf{U}, \mathbf{x}}  = \mathbf{0} \\[2.5pt]
      \left[
        \begin{array}{c|c}
          \mathbf{H}_{n,q-1} & \mathbf{0} \\
          \hline \rule{0pt}{2.6ex}
          \mathbf{0} & \mathbf{I}_\kappa \\
        \end{array}
      \right]\cdot {\mathfrak{m}}_{\USR,\mathbf{x}} + \left[
        \begin{array}{c}
          -\bar{\mathbf{A}} \\
          \mathbf{0} \\
        \end{array}
      \right]\cdot \mathbf{e}_{\mathsf{U}} + \left[
        \begin{array}{c}
          \mathbf{0} \\
          -\mathbf{I}_\kappa \\
        \end{array}
      \right]\cdot \mathbf{x} = \mathbf{0}
    \end{cases}
  \end{eqnarray}
}
and such that $\mathbf{z}_{\BPR,\rho} \in [0,4]^\zeta$ encodes  $\BPR_\rho$ such that  $\BPR_\rho (\mathbf{x})=1$.
This is done by running the argument system described in Section~\ref{subsection:ZK-Protocol4-BP}.

\item[3.] If the ZK argument of step 2 verifies, $\mathsf{DB}$ decrypts $(\mathbf{c}_0,\mathbf{c}_1) \in \Zq^n \times \Zq^t$ to
obtain  $M' = \lfloor (\mathbf{c}_1 - \mathbf{S}^T \cdot \mathbf{c}_0) / ( q/2 ) \rceil \in \{0,1\}^t,$
which is returned to $\USR$. Then, $\mathsf{DB}$ argues knowledge of
 $\mathbf{y}= \mathbf{c}_1 - \mathbf{S}^T \cdot \mathbf{c}_0 - M' \cdot \lfloor q/2 \rfloor \in \ZZ^t$
of norm $\| \mathbf{y} \|_{\infty} \leq q/5$ and small-norm  $\mathbf{E}\in \ZZ^{m \times t}$, $\mathbf{S} \in \ZZ^{n \times t}$ satisfying (modulo $q$)
\begin{eqnarray*}
\mathbf{P} &=& \mathbf{F}^T \cdot \mathbf{S} + \mathbf{E} ~  , \qquad \mathbf{c}_0^T \cdot \mathbf{S} + \mathbf{y}^T = \mathbf{c}_1^T - {M'}^T \cdot \lfloor q/2 \rfloor .
\end{eqnarray*}
To this end, $\mathsf{DB}$ uses the ZK argument system of Section~\ref{subsection:ZK-protocol-2}.

\item[4.] If the ZK argument produced by $\mathsf{DB}$ does not  verify, $\USR$   outputs $\perp$. Otherwise, $\USR$ recalls
the string $\mu \in \{0,1\}^t$   and outputs $M_{\rho_i}=M' \oplus  \mu$.
\end{itemize}
\end{description}

 Like our construction of Section \ref{OT-scheme}, the above  protocol requires the $\mathsf{DB}$ to repeat a ZK proof of communication complexity
$\Omega(N)$ with each user $\USR$ during the initialization phase. By applying the Fiat-Shamir heuristic as in Appendix~\ref{optimized}, the cost of the initialization phase
can be made independent of the number of users: the sender   can publicize $ \bigl(  PK_{\mathrm{DB}} ,\{ER_i, \BPR_i \}_{i=1}^N \bigr) $ along
   with a with a universally verifiable non-interactive proof of well-formedness.


The security of the above protocol against static corruptions is proved in~\cite{LLM+17}, under the $\SIS$ and $\LWE$ assumptions and is similar to the previous proofs.

\section{Zero-Knowledge Subprotocols for Stern Protocol}

\subsection{Our Strategy and Basic Techniques, In a Nutshell}\label{subsection:ZK-strategy}
Before going into the details of our protocols, we first  summarize our governing strategy and the  techniques that will be used in the next subsections.

In each   protocol, we prove knowledge of (possibly one-dimensional) integer vectors $\{\mathbf{w}_i\}_i$
that have   various constraints (e.g., smallness, special arrangements of coordinates, or  correlation with one another) and satisfy a system
\begin{eqnarray}\label{eq:big-system}
   \displaystyle \Big\{\sum_i\mathbf{M}_{i,j}\cdot \mathbf{w}_i = \mathbf{v}_j \Big\}_j,
\end{eqnarray}
where $\{\mathbf{M}_{i,j}\}_{i,j}$, $\{\mathbf{v}_j\}_{j}$ are public matrices (which are possibly zero or identity matrices) and   vectors. Our strategy consists in transforming this entire system into one equivalent equation $\mathbf{M}\cdot \mathbf{w} = \mathbf{v}$, where matrix $\mathbf{M}$ and vector $\mathbf{v}$ are public, while the constraints of the secret vector $\mathbf{w}$ capture those of witnesses $\{\mathbf{w}_i\}_i$ and they are provable in zero-knowledge via random permutations. For this purpose, the Stern-like protocol from \cref{sse:stern} comes in
handy.

A typical transformation step is of the form $\mathbf{w}_i \rightarrow \bar{\mathbf{w}}_i$, where there exists public matrix $\mathbf{P}_{i,j}$ such that $\mathbf{P}_{i,j}\cdot \bar{\mathbf{w}}_i = \mathbf{w}_i$. This subsumes the decomposition and extension mechanisms which  first appeared in~\cite{LNSW13}.
\begin{itemize}
    \item \textbf{Decomposition:} Used when $\mathbf{w}_i$ has infinity norm bound larger than $1$ and we want to work more conveniently with $\bar{\mathbf{w}}_i$ whose norm bound is exactly~$1$. In this case, $\mathbf{P}_{i,j}$ is a decomposition matrix.
    \item \textbf{Extension:} Used when we insert ``dummy'' coordinates to $\mathbf{w}_i$ to obtain $\bar{\mathbf{w}}_i$ whose coordinates are somewhat balanced. In this case,  $\mathbf{P}_{i,j}$ is a $\{0,1\}$-matrix with zero-columns corresponding to positions of insertions.
\end{itemize}
Such a step transforms the term $\mathbf{M}_{i,j}\cdot \mathbf{w}_i$ into $\overline{\mathbf{M}}_{i,j}\cdot \bar{\mathbf{w}}_i$, where $\overline{\mathbf{M}}_{i,j} = \mathbf{M}_{i,j}\cdot \mathbf{P}_{i,j}$ is a public matrix.
Also, using the commutativity property of addition, we often group together secret vectors having the same constraints.



After a number of transformations, we will reach a system equivalent to~\eqref{eq:big-system}:
\begin{eqnarray}\label{eq:big-system-derived}
    \begin{cases}
       \mathbf{M}'_{1,1}\cdot \mathbf{w}'_1 + \mathbf{M}'_{1,2}\cdot \mathbf{w}'_2 + \cdots + \mathbf{M}'_{1,k} \cdot \mathbf{w}'_{k} =  \mathbf{v}_1, \\
        %\hdotsfor{0} \\
     \hfill \vdots \hfill \\
        \mathbf{M}'_{t,1}\cdot \mathbf{w}'_1 + \mathbf{M}'_{t,2}\cdot \mathbf{w}'_2 + \cdots + \mathbf{M}'_{t,k} \cdot \mathbf{w}'_{k} =  \mathbf{v}_t,
    \end{cases}
\end{eqnarray}
where integers $t,k$ and matrices $\mathbf{M}'_{i,j}$ are public.  Defining
\[
\mathbf{M} = \left(
  \begin{array}{c|c|c|c}
    \mathbf{M}'_{1,1} & \mathbf{M}'_{1,2} & \cdots & \mathbf{M}'_{1,k} \\
    \hline
    \rule{0pt}{3ex}
    %\mathbf{M}''_{2,1} & \mathbf{M}''_{2,2} & \ldots & \mathbf{M}''_{2,15} \\
    %\hline
    %\rule{0pt}{3ex}
   \vdots & \vdots & \ddots & \vdots \\
    \hline
    \rule{0pt}{3ex}
    \mathbf{M}'_{t,1} & \mathbf{M}'_{t,2} & \cdots & \mathbf{M}'_{t,k} \\
  \end{array}
\right); \hspace*{10pt} \mathbf{w} = \left(
                \begin{array}{c}
                  \mathbf{w}'_1 \\[2.5pt]
                  %\mathbf{w}'_2 \\[2.5pt]
                  \vdots \\[2.5pt]
                  \mathbf{w}'_{k} \\
                \end{array}
              \right);
\hspace*{10pt}
\mathbf{v} = \left(
                \begin{array}{c}
                  \mathbf{v}_1 \\[2.5pt]
                 % \mathbf{v}_2 \\
                  \vdots \\[2.5pt]
                  \mathbf{v}_{t} \\
                \end{array}
              \right),
\]
we obtain the unified equation $\mathbf{M}\cdot \mathbf{w} = \mathbf{v} \bmod q$. At this stage, we will use a properly defined composition of random permutations to prove the constraints of~$\mathbf{w}$. We remark that  the crucial aspect of the above process is in fact the manipulation of witness  vectors, while the transformations of public matrices/vectors just follow accordingly. To ease the presentation of the next subsections, we will thus  only focus on the secret vectors.


In the process, we will employ various extending and permuting techniques which require introducing some notations. The most frequently used ones are given in Table~\ref{table:ZK-notations-techniques}. Some of these techniques appeared (in slightly different forms) in previous works~\cite{LNSW13,LNW15,LLNW16,LLM+16,LLM+16a}. The  last three parts of the table summarizes  newly-introduced techniques that will enable the  treatment of secret-and-correlated objects involved in the evaluation of hidden branching programs.

In particular, the intriguing technique of the last row will be used for proving knowledge of secret integer $z$ of the form $z = x\cdot y$ for some $(x,y) \in [0,4]\times \{0,1\}$ satisfying other relations. The following example  illustrates how it works.
\paragraph{Example.}
Let $(x,y) = (2,1)$ and $(c,b) = (4,1)$. Then we have:
\begin{eqnarray*}
\mathsf{ext}_{5 \times 2}(2,1) &=& \big(0,\hspace*{2.5pt}1,\hspace*{2.5pt}0,\hspace*{2.5pt}0,\hspace*{2.5pt}0,\hspace*{2.5pt}4,\hspace*{2.5pt}0,\hspace*{2.5pt}3,\hspace*{2.5pt}0,\hspace*{2.5pt}2\big)^T\\
T_{5\times 2}[4,1]\big(\mathsf{ext}_{5 \times 2}(2,1)\big) &=& \big(0,\hspace*{2.5pt}0,\hspace*{2.5pt}4,\hspace*{2.5pt}0,\hspace*{2.5pt}3,\hspace*{2.5pt}0,\hspace*{2.5pt}2,\hspace*{2.5pt}0,\hspace*{2.5pt}1,\hspace*{2.5pt}0\big)^T
\end{eqnarray*}
Note that: $T_{5\times 2}[4,1]\big(\mathsf{ext}_{5 \times 2}(2,1)\big) = \mathsf{ext}_{5 \times 2}(1,0) = \mathsf{ext}_{5 \times 2}(2 + 4 \bmod 5, 1 \oplus 1)$.

\begin{table}[htbp]
  \footnotesize
  \hspace{-13pt}
\begin{tabular}{|c|c|}
  \hline
  % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
  \textbf{Notation} & \textbf{Meaning/Property/Usage/Technique} \\
  %\hline
  %\rule{0pt}{2.6ex}
 % $\mathcal{S}_{\mathfrak{m}}$ & The set of all permutations of~$\mathfrak{m}$ elements \\
  \hline
  \rule{0pt}{3.6ex}
  $\mathsf{B}^2_{\mathfrak{m}}$ &
  \begin{minipage}[t]{0.86\textwidth}
    \begin{itemize}
    \item The set of vectors in~$\{0,1\}^{2\mathfrak{m}}$ with Hamming weight~$\mathfrak{m}$.  
    \item $\forall \phi \in \mathcal{S}_{2\mathfrak{m}}, \mathbf{x}' \in \mathbb{Z}^{2\mathfrak{m}}: \mathbf{x}' \in \mathsf{B}^2_{\mathfrak{m}} \Leftrightarrow \phi(\mathbf{x}') \in \mathsf{B}^2_{\mathfrak{m}}$.  
    \item To prove $\mathbf{x} \in \{0,1\}^{\mathfrak{m}}$: Extend $\mathbf{x}$ to $\mathbf{x}' \in \mathsf{B}^2_{\mathfrak{m}}$, then permute $\mathbf{x}'$. 

    \end{itemize}
  \end{minipage}

   \\
  \hline
  \rule{0pt}{3.6ex}
  $\mathsf{B}^3_{\mathfrak{m}}$ &
  \begin{minipage}[t]{0.86\textwidth}
    \begin{itemize}
    \item The set of vectors in $\{-1,0,1\}^{3\mathfrak{m}}$ that have exactly~$\mathfrak{m}$ coordinates equal to~$j$, for every $j \in \{-1,0,1\}$.  
    \item $\forall \phi \in \mathcal{S}_{3\mathfrak{m}}, \mathbf{x}' \in \mathbb{Z}^{3\mathfrak{m}}: \mathbf{x}' \in \mathsf{B}^3_{\mathfrak{m}} \Leftrightarrow \phi(\mathbf{x}') \in \mathsf{B}^3_{\mathfrak{m}}$.  
    \item To prove $\mathbf{x} \in \{-1,0,1\}^{\mathfrak{m}}$: Extend $\mathbf{x}$ to $\mathbf{x}' \in \mathsf{B}^3_{\mathfrak{m}}$, then permute $\mathbf{x}'$. 

    \end{itemize}
  \end{minipage}
   \\
  \hline
  \rule{0pt}{3.6ex}


  \begin{minipage}[t]{0.1\textwidth}
  ~\\[5pt]
    $\mathsf{ext}_2(\cdot)$\\[2.5pt]
    ~~and \\[2.5pt]
    $T_2[\cdot](\cdot)$
  \end{minipage}


  &
  \begin{minipage}[t]{0.86\textwidth}
    \begin{itemize}
    \item For $c \in \{0,1\}: \mathsf{ext}_2(c) = (\bar{c}, c)^T \in \{0,1\}^2$.    
    \item For $b \in \{0,1\}$ and $\mathbf{x} = (x_0, x_1)^T \in \mathbb{Z}^2$: \hspace*{5pt}$T_2[b](\mathbf{x}) = (x_b, x_{\bar{b}})^T $.  
    \item Property: $\mathbf{x} = \mathsf{ext}_2(c) \Leftrightarrow T_2[b](\mathbf{x}) = \mathsf{ext}_2(c \oplus b)$.  
    \item To prove $c \in \{0,1\}$ simultaneously satisfies many relations: Extend it to $\mathbf{x} = \mathsf{ext}_2(c)$, then permute and use the \emph{same} $b$ at all appearances.  
    \end{itemize}
   % \vspace*{0.15cm}
  \end{minipage}


   \\
  \hline
   \rule{0pt}{3.6ex}

  \begin{minipage}[t]{0.1\textwidth}
  ~\\
    \hspace*{-3.5pt}$\mathsf{expand}(\hspace*{-1pt}\cdot, \hspace*{-1pt}\cdot\hspace*{-1pt})$\\[2.5pt]
    ~~and \\%[2.5pt]
    \hspace*{-3.5pt}$T_{\mathsf{exp}}[\cdot, \hspace*{-1pt}\cdot](\cdot)$
  \end{minipage}


  &
  \begin{minipage}[t]{0.86\textwidth}
    \begin{itemize}
    \item For $c \in \{0,1\}$ and $\mathbf{x} \in \mathbb{Z}^{\mathfrak{m}}$: \hspace*{5pt} $\mathsf{expand}(c, \mathbf{x}) = (\bar{c}\cdot \mathbf{x}^T  \mid  c\cdot \mathbf{x}^T )^T \in \mathbb{Z}^{\mathfrak{2m}}$.    
    \item For $b \in \{0,1\}, \phi \in \mathcal{S}_{m}$, $\mathbf{v} = \left(
                                                                         \begin{array}{c}
                                                                           \mathbf{v}_0 \\
                                                                           \mathbf{v}_1 \\
                                                                         \end{array}
                                                                       \right)
    \in \mathbb{Z}^{\mathfrak{2m}}$: \hspace*{5pt}$T_{\mathsf{exp}}[b, \phi](\mathbf{v}) =
    \left(
      \begin{array}{c}
        \phi(\mathbf{v}_b) \\
        \phi(\mathbf{v}_{\bar{b}})\\
      \end{array}
    \right).$    
    \item Property: $\mathbf{v} = \mathsf{expand}(c, \mathbf{x}) \Leftrightarrow T_{\mathsf{exp}}[b, \phi](\mathbf{v}) = \mathsf{expand}(c \oplus b, \phi(\mathbf{x}))$.  
    \end{itemize}
  \end{minipage}
  \\
  \hline
  \rule{0pt}{3.6ex}
  $[\cdot]_5$
    &
  For $k \in \mathbb{Z}$: $[k]_5$ denotes the integer $t \in \{0,1,2,3,4\}$, s.t. $t = k \bmod 5$.
  \\[5pt]
  \hline
  \rule{0pt}{3.6ex}

  \begin{minipage}[t]{0.1\textwidth}
    ~~\\[5pt]
    $\mathsf{ext}_5(\cdot)$\\[2.5pt]
    ~~and \\[2.5pt]
    $T_5[\cdot](\cdot)$
  \end{minipage}
  &
  \begin{minipage}[t]{0.86\textwidth}
    \begin{itemize}
    \item For $x \in [0,4]: \mathsf{ext}_5(x) = ([x+4]_5, [x+3]_5, [x+2]_5, [x+1]_5, x)^T \in [0,4]^5$.
    \item For $c \in [0,4]$ and $\mathbf{v} = (v_0, v_1, v_2, v_3, v_4)^T \in \mathbb{Z}^5$:\vspace*{-0.25cm}
    \[
    T_5[c](\mathbf{v}) = \big(
    v_{[-c]_5}, v_{[-c+1]_5}, v_{[-c+2]_5}, v_{[-c+3]_5}, v_{[-c+4]_5}
    \big)^T .
    \]
    \item Property: $\mathbf{v} = \mathsf{ext}_5(x) \Leftrightarrow T_5[c](\mathbf{v}) = \mathsf{ext}_5(x +c \bmod 5)$.  
    \item To prove $x \in [0,4]$ simultaneously satisfies many relations: Extend it to $\mathbf{v} = \mathsf{ext}_5(x)$, then permute and use the \emph{same} $c$ at all appearances.  
    \end{itemize}
  \end{minipage}
  \\
  \hline
  \rule{0pt}{3.6ex}

  $\mathsf{unit}_x$
  &
  \begin{minipage}[t]{0.86\textwidth}
    \begin{itemize}
    \item $\forall x \in [0,4]$: $\mathsf{unit}_x$ is the $5$-dim unit vector $(v_0, \ldots, v_4)^T $ with $v_x = 1$.  
    \item For $c \in [0,4], \mathbf{v}\in \mathbb{Z}^5$: $\mathbf{v} = \mathsf{unit}_x \Leftrightarrow T_5[c](\mathbf{v}) = \mathsf{unit}_{x + c \bmod 5}$.  

    \hspace*{-5pt}$\rightarrow$ Allow proving $\mathbf{v} = \mathsf{unit}_x$ for some $x \in [0,4]$ satisfying other relations.
    \end{itemize}
  \end{minipage}
   \\
  \hline
  \rule{0pt}{3.6ex}

  \begin{minipage}[t]{0.1\textwidth}
    ~~\\[5pt]
    \hspace*{-4.5pt}$\mathsf{ext}_{5\times 2}\hspace*{-1pt}(\cdot\hspace*{-1pt},\hspace*{-1pt}\cdot)$\\[2.5pt]
    ~~and \\[2.5pt]
    \hspace*{-4.5pt}$T_{5\times \hspace*{-1pt}2}[\cdot,\hspace*{-1pt}\cdot](\cdot)$
  \end{minipage}
  &
  \begin{minipage}[t]{0.86\textwidth}
    \begin{itemize}
    \item For $x \in [0,4]$ and $y \in \{0,1\}$: \vspace*{-0.15cm}
    \begin{eqnarray*}
    \hspace*{-10pt}
    \mathsf{ext}_{5\times 2}(x,y) &=& ([x+4]_5\hspace*{-1pt}\cdot\hspace*{-1pt} \bar{y}, [x+4]_5\hspace*{-1pt}\cdot\hspace*{-1pt} {y}, [x+3]_5\hspace*{-1pt}\cdot\hspace*{-1pt} \bar{y}, [x+3]_5\hspace*{-1pt}\cdot\hspace*{-1pt} {y}, [x+2]_5\hspace*{-1pt}\cdot\hspace*{-1pt} \bar{y}, \\&&[x+2]_5\hspace*{-1pt}\cdot\hspace*{-1pt} {y}, [x+1]_5\hspace*{-1pt}\cdot\hspace*{-1pt} \bar{y}, [x+1]_5\hspace*{-1pt}\cdot\hspace*{-1pt} {y}, x\hspace*{-1pt}\cdot\hspace*{-1pt} \bar{y}, x\hspace*{-1pt}\cdot\hspace*{-1pt} {y})^T \in [0,4]^{10}
    \end{eqnarray*}
    \item For $(c,b) \in [0,4] \times \{0,1\}$ and $\mathbf{v} = (v_{0,0}, v_{0,1}, \ldots, v_{4,0}, v_{4,1})^T \in \mathbb{Z}^{10}$: \vspace*{-0.15cm}
    \begin{eqnarray*}
    T_{5\times 2}[c,b](\mathbf{v})&=& \big(
v_{[-c]_5, b}, v_{[-c]_5, \overline{b}},
v_{[-c+1]_5, b}, v_{[-c+1]_5, \overline{b}},
v_{[-c+2]_5, b}, \\
&& v_{[-c+2]_5, \overline{b}},
v_{[-c+3]_5, b}, v_{[-c+3]_5, \overline{b}},
v_{[-c+4]_5, b}, v_{[-c+4]_5, \overline{b}}
\big)^T.
\end{eqnarray*}
    \item Property: $\mathbf{v} = \mathsf{ext}_{5\times 2}(x,y) \Leftrightarrow T_{5\times 2}[c,b](\mathbf{v}) = \mathsf{ext}_{5\times 2}(x +c \bmod 5, y\oplus b)$.

    $\rightarrow$ Allow proving $z = x\cdot y$ for some $(x,y) \in [0,4]\times \{0,1\}$ satisfying other relations: Extend $z$ to $\mathbf{v} = \mathsf{ext}_{5\times 2}(x,y)$, then permute and use the \emph{same} $c,b$ at all appearances of $x, y$, respectively.
    \end{itemize}
  \end{minipage}


  \\
 %  &  \\
  \hline
\end{tabular}
\vspace*{5pt}
\caption{Basic notations and extending/permuting techniques used in our protocols.}
\label{table:ZK-notations-techniques}
\end{table}

\subsection{Protocol 1}\label{subsection:ZK-protocol-1}
Let $n, m, q, N, t, B_\chi$ be the parameters defined in Section~\ref{OT-scheme}. The protocol allows the prover to prove knowledge of \textsf{LWE} secrets and the well-formedness of ciphertexts. It is summarized as follows.
\begin{description}
  \item[Common input:] $\mathbf{F} \in \mathbb{Z}_q^{n \times m}$, \hspace*{5pt}$\mathbf{P} \in \mathbb{Z}_q^{m \times t}$; \hspace*{5pt}
     $\{\mathbf{a}_i\in \mathbb{Z}_q^n, \hspace*{3.5pt}\mathbf{b}_i \in \mathbb{Z}_q^t\}_{i=1}^N$. \smallskip
  \item[Prover's goal] is to prove knowledge of $\mathbf{S} \in [-B_\chi,B_\chi]^{n \times t}$, $\mathbf{E} \in [-B_\chi,B_\chi]^{m \times t}$, $\{\mathbf{x}_i\in [-B_\chi,B_\chi]^t, M_i \in \{0,1\}^t\}_{i=1}^N$ such that the following equations hold:
\end{description}

\begin{eqnarray}\label{eq:protocol-1-original}
\begin{cases}
\mathbf{F}^T \cdot \mathbf{S} + \mathbf{E} = \mathbf{P} \bmod q \\
\forall i \in [N]:  \mathbf{S}^T \cdot \mathbf{a}_i  + \mathbf{x}_i + \lfloor q/2\rfloor \cdot M_i = \mathbf{b}_i \bmod q.
\end{cases}
\end{eqnarray}
For each $j \in [t]$, let $\mathbf{p}_j, \mathbf{s}_j, \mathbf{e}_j$ be the $j$-th column of matrices $\mathbf{P}, \mathbf{S}, \mathbf{E}$, respectively. For each $(i, j) \in [N]\times [t]$, let $\mathbf{b}_i[j], \mathbf{x}_i[j], M_i[j]$ denote the $j$-th coordinate of vectors $\mathbf{b}_i, \mathbf{x}_i, M_i$, respectively. Then, observe that \eqref{eq:protocol-1-original} can be rewritten as:
\begin{eqnarray}\label{eq:protocol-1-step-1}
\begin{cases}
\forall j \in [t]: \mathbf{F}^T \cdot \mathbf{s}_j + \mathbf{I}_m \cdot \mathbf{e}_j = \mathbf{p}_j \bmod q \\
\forall (i,j) \in [N]\times [t]: \mathbf{a}_i^T \cdot \mathbf{s}_j + 1 \cdot \mathbf{x}_i[j] + \lfloor q/2\rfloor \cdot M_i[j] = \mathbf{b}_i[j] \bmod q.
\end{cases}
\end{eqnarray}
%Observe further that, all equations in (\ref{eq:protocol-1-step-1}) can be combined in one equation of the form:
%\begin{eqnarray}\label{eq:protocol-1-step-2}
%\mathbf{M}_1 \cdot \mathbf{w}_1 + \mathbf{M}_2 \cdot \mathbf{w}_2 = \mathbf{v} \bmod q,
%\end{eqnarray}
%where matrices $\mathbf{M}_1 \in \mathbb{Z}_q^{(m + N)t \times (n+m+N)t}$, $\mathbf{M}_2 \in \{0,\lfloor q/2\rfloor\}^{(m+N)t \times Nt}$, together with vector $\mathbf{v} \in \mathbb{Z}_q^{(m+N)t}$ are built from the common input, and
%where matrices $\mathbf{M}_1, \mathbf{M}_2$ and vector $\mathbf{v}$ are built from the common input, and
Then, we form the following vectors:
\begin{eqnarray*}
\mathbf{w}_1 &=& \big(
\mathbf{s}_1^T \mid \ldots \mid \mathbf{s}_t^T \mid \mathbf{e}_1^T \mid \ldots \mid \mathbf{e}_t^T \mid ( \mathbf{x}_1[1], \ldots, \mathbf{x}_N[t]    )
\big)^T \in [-B_\chi,B_\chi]^{(n+m+N)t}; \\
\mathbf{w}_2 &=& (M_1[1], \ldots, M_N[t])^T \in \{0,1\}^{Nt}.
\end{eqnarray*}

Next, we run $\mathsf{vdec}'_{(n+m+N)t, B_\chi}$ to decompose $\mathbf{w}_1$ into $\bar{\mathbf{w}}_1$  and then extend $\bar{\mathbf{w}}_1$ to $\mathbf{w}_1^* \in \mathsf{B}_{(n+m+N)t\delta_{B_\chi}}^3$. We also extend $\mathbf{w}_2$ into $\mathbf{w}_2^* \in \mathsf{B}_{Nt}^2$ and we then form $\mathbf{w} = ((\mathbf{w}_1^*)^T \mid (\mathbf{w}_2^*)^T  )^T \in \{-1,0,1\}^D$, where $D = 3(n+m+N)t\delta_{B_\chi} + 2Nt$.

Observe that relations \eqref{eq:protocol-1-step-1} can be  transformed into \textit{one} equivalent  equation of the form
$\mathbf{M}\cdot \mathbf{w} = \mathbf{v} \bmod q,$
where   $\mathbf{M}$ and   $\mathbf{v}$ are built from the common input.

Having performed the above unification, we now define $\mathsf{VALID}$ as the set of all vectors $\mathbf{t} = (\mathbf{t}_1^T \mid \mathbf{t}_2^T)^T \in \{-1,0,1\}^D$, where $\mathbf{t}_1 \in \mathsf{B}_{(n+m+N)t\delta_{B_\chi}}^3$ and $\mathbf{t}_2 \in \mathsf{B}_{Nt}^2$. Clearly, our vector $\mathbf{w}$ belongs to the set $\mathsf{VALID}$.

Next, we specify the set $\mathcal{S}$ and permutations of $D$ elements $\{\Gamma_\phi: \phi \in \mathcal{S}\}$, for which the conditions in~\eqref{eq:zk-equivalence} hold.
\begin{itemize}
\item $\mathcal{S}: = \mathcal{S}_{3(n+m+N)t\delta_{B_\chi}} \times \mathcal{S}_{2Nt}$.
\item For $\phi = (\phi_1, \phi_2) \in \mathcal{S}$ and for $\mathbf{t} = (\mathbf{t}_1^T \mid \mathbf{t}_2^T)^T \in \mathbb{Z}^D$, where $\mathbf{t}_1 \in \mathbb{Z}^{3(n+m+N)t\delta_{B_\chi}}$ and $\mathbf{t}_2 \in \mathbb{Z}^{2Nt}$, we define $\Gamma_\phi(\mathbf{t}) = (\phi_1(\mathbf{t}_1)^T \mid \phi_2(\mathbf{t}_2)^T )^T $.
\end{itemize}
By inspection, it can be seen that the desired properties in \eqref{eq:zk-equivalence} are satisfied. As a result, we can obtain the required \textsf{ZKAoK} by running the protocol from \cref{sse:stern-abstraction} with common input $(\mathbf{M}, \mathbf{v})$ and prover's input $\mathbf{w}$.
The protocol has communication cost $\mathcal{O}(D\log q)= \widetilde{\mathcal{O}}(\lambda)\cdot \mathcal{O}(Nt)$ bits. 

While this protocol has linear complexity in $N$, it is only used in the initialization phase, where $\Omega(N)$ bits inevitably have to be transmitted anyway.





%\begin{eqnarray*}
%\mathbf{M} &=& \big[\mathbf{M}_1\cdot \widehat{\mathbf{H}}_{(n+m+N)t, B} \big|  \mathbf{M}_2 \big| \mathbf{0}^{(m+N)t \times Nt}\big] \in \mathbb{Z}_q^{K \times D}; \\
%\mathbf{w} &=& \big(\big(\mathsf{ThreeExt}(\mathsf{vdec}'_{(n+m+N)t, B}(\mathbf{w}_1))\big)^T \mid  \big(\mathsf{TwoExt}(\mathbf{w}_2)\big)^T \big)^T \in \{-1,0,1\}^D,
%\end{eqnarray*}
%then we obtain a unified equation: $\mathbf{M}\cdot \mathbf{w} = \mathbf{v} \bmod q$.

\subsection{Protocol 2}\label{subsection:ZK-protocol-2}
Let $n, m, q, N, t, B$ be system parameters. The protocol allows the prover to prove knowledge of \textsf{LWE} secrets and the correctness of decryption. % It is summarized as follows.
\begin{description}
  \item[Common input:] $\mathbf{F} \in \mathbb{Z}_q^{n \times m}$, \hspace*{5pt}$\mathbf{P} \in \mathbb{Z}_q^{m \times t}$; \hspace*{5pt} $\mathbf{c}_0 \in \mathbb{Z}_q^n, \hspace*{5pt} \mathbf{c}_1 \in \mathbb{Z}_q^t$, \hspace*{5pt} $M' \in \{0,1\}^t$.
      \smallskip
  \item[Prover's goal] is to prove knowledge of $\mathbf{S} \in [-B_\chi,B_\chi]^{n \times t}$, $\mathbf{E} \in [-B_\chi,B_\chi]^{m \times t}$ and $\mathbf{y} \in [-q/5, q/5]^{t}$ such that the following equations hold:
\end{description}

\begin{eqnarray}\label{eq:protocol-2-original}
\mathbf{F}^T \cdot \mathbf{S} + \mathbf{E} = \mathbf{P} \bmod q; \hspace*{10pt}
\mathbf{c}_0^T \cdot \mathbf{S} + \mathbf{y}^T = \mathbf{c}_1^T - M'^T \cdot \lfloor q/2\rfloor \bmod q.
\end{eqnarray}
For each $j \in [t]$, let $\mathbf{p}_j, \mathbf{s}_j, \mathbf{e}_j$ be the $j$-th column of matrices $\mathbf{P}, \mathbf{S}, \mathbf{E}$, respectively; and let $\mathbf{y}[j], \mathbf{c}_1[j], M'[j]$ be the $j$-th entry of vectors $\mathbf{y}, \mathbf{c}_1, M'$, respectively.
Then, observe that \eqref{eq:protocol-2-original} can be re-written as:
\begin{eqnarray}\label{eq:protocol-2-step-1}
\forall j \in [t]:
\begin{cases}
\mathbf{F}^T \cdot \mathbf{s}_j + \mathbf{I}_m \cdot \mathbf{e}_j = \mathbf{p}_j \bmod q \\
\mathbf{c}_0^T \cdot \mathbf{s}_j + 1\cdot \mathbf{y}[j] = \mathbf{c}_1[j]- M'[j]\cdot  \lfloor q/2\rfloor\bmod q.
\end{cases}
\end{eqnarray}
Next, we form vector $\mathbf{w}_1 = (\mathbf{s}_1^T \mid \ldots \mid \mathbf{s}_t^T \mid \mathbf{e}_1^T \mid \ldots \mid \mathbf{e}_t^T)^T \in [-B_\chi,B_\chi]^{(n+m)t}$, then decompose it to $\bar{\mathbf{w}}_1 \in \{-1,0,1\}^{(n+m)t\delta_{B_\chi}}$, and extend $\bar{\mathbf{w}}_1$ to $\mathbf{w}_1^* \in \mathsf{B}_{(n+m)t\delta_{B_\chi}}^3$.

At the same time, we decompose vector $\mathbf{y} = (\mathbf{y}[1], \ldots, \mathbf{y}[t])^T \in [-q/5, q/5]^{t}$ to $\bar{\mathbf{y}} \in \{-1,0,1\}^{t\delta_{q/5}}$, and then extend $\bar{\mathbf{y}}$ to $\mathbf{y}^* \in \mathsf{B}_{t\delta_{q/5}}^3$.

Defining the ternary  vector $\mathbf{w} = ((\mathbf{w}^*_1)^T \mid (\mathbf{y}^*)^T)^T \in \{-1,0,1\}^D$ of dimension  $D = 3(n+m)t\delta_{B_\chi} + 3t\delta_{q/5}$,   we finally  obtain the equation $\mathbf{M}\cdot \mathbf{w} = \mathbf{v} \bmod q$, for public matrix $\mathbf{M}$ and public vector $\mathbf{v}$. Using similar arguments as in Section~\ref{subsection:ZK-protocol-1}, we   can obtain the desired zero-knowledge argument system. The protocol has communication cost $\mathcal{O}(D\log q)= \widetilde{\mathcal{O}}(\lambda)\cdot \mathcal{O}(t)$ bits.

\subsection{Protocol 3}\label{subsection:ZK-protocol-3}
Let $n, m , m_d, q, t, \ell, B$ be the parameters defined in Section~\ref{OT-scheme}. The protocol allows the prover to argue that a given ciphertext is a correct randomization of some hidden ciphertext and that he knows a valid signature on that   ciphertext. Let $\beta$ be the infinity norm bound of these  valid signatures. % produced by the underlying signature.
\begin{description}
  \item[Common input:] It consists of matrices $\mathbf{F} \in \mathbb{Z}_q^{n \times m}$, \hspace*{2.5pt}$\mathbf{P} \in \mathbb{Z}_q^{m \times t}$, \hspace*{2.5pt} $\mathbf{A}, \hspace*{1pt}\mathbf{A}_0, \hspace*{1pt}\mathbf{A}_1,$ $ \ldots, \mathbf{A}_\ell \in \mathbb{Z}_q^{n \times m}$, \hspace*{2.5pt} $\mathbf{D} \in \mathbb{Z}_q^{n \times m_d}$ \hspace*{2.5pt}
    and vectors
           $\mathbf{c}_0 \in \mathbb{Z}_q^n, \hspace*{2.5pt}\mathbf{c}_1 \in \mathbb{Z}_q^t, \hspace*{2.5pt}\mathbf{u} \in \mathbb{Z}_q^n$. \smallskip
  \item[Prover's goal] is to prove knowledge of $\mathfrak{m} \in \{0,1\}^{m_d}$, $\mu \in \{0,1\}^t$, $\mathbf{e} \in \{-1,0,1\}^t$, $\nu \in [-B,B]^t$, $\tau = (\tau[1], \ldots, \tau[\ell])^T \in \{0,1\}^\ell$, $\mathbf{v}_1, \mathbf{v}_2 \in [-\beta, \beta]^m$  such that the following equations hold:
\end{description}
{\small
\begin{eqnarray}\label{eq:protocol-3-original}
\begin{cases}
  \mathbf{A}\cdot \mathbf{v}_1 + \mathbf{A}_0 \cdot \mathbf{v}_2 + \sum_{j=1}^\ell \mathbf{A}_j \cdot (\tau[j]\cdot \mathbf{v}_2) - \mathbf{D}\cdot \mathfrak{m} = \mathbf{u} \bmod q; \\
  \mathbf{H}_{n+t, q-1}\hspace*{-2pt}\cdot \hspace*{-2pt}\mathfrak{m} + \left(
    \begin{array}{c}
      \mathbf{F} \\
      \mathbf{P}^T \\
    \end{array}
  \right)\hspace*{-2pt}\cdot\hspace*{-2pt} \mathbf{e} + \left(
    \begin{array}{c}
      \mathbf{0}^{n \times t} \\
      \lfloor \frac{q}{2}\rfloor \hspace*{-2pt}\cdot\hspace*{-2pt} \mathbf{I}_t\\
    \end{array}
  \right) \hspace*{-2pt}\cdot\hspace*{-2pt} \mu +  \left(
    \begin{array}{c}
      \mathbf{0}^{n \times t} \\
      \mathbf{I}_t \\
    \end{array}
  \right) \hspace*{-2pt}\cdot\hspace*{-2pt} \nu = \left(
    \begin{array}{c}
      \mathbf{c}_0 \\
      \mathbf{c}_1 \\
    \end{array}
  \right) \bmod q. ~~~~~
\end{cases}
\end{eqnarray}}
For this purpose, we  perform the following transformations on the witnesses. \medskip


\noindent
\textbf{Decompositions. } Decompose vectors $\mathbf{v}_1, \mathbf{v}_2, \nu$ to vectors $\bar{\mathbf{v}}_1 \in \{-1,0,1\}^{m\delta_\beta}$, $\bar{\mathbf{v}}_2 \in \{-1,0,1\}^{m\delta_\beta}$, $\bar{\nu} \in \{-1,0,1\}^{t\delta_B}$, respectively.
\smallskip

\noindent
\textbf{Extensions/Combinations. }
\begin{itemize}
\item Let $\mathbf{w}_1 = (\mathfrak{m}^T \mid \mu^T )^T \in \{0,1\}^{m_d +t}$ and extend it into $\mathbf{w}_1^* \in \mathsf{B}_{m_d+t}^2$.
\item Let $\mathbf{w}_2 = (\bar{\mathbf{v}}_1^T \mid \bar{\nu}^T \mid \mathbf{e}^T)^T \in \{-1,0,1\}^{m\delta_\beta + t\delta_B + t}$ and extend it into the vector $\mathbf{w}_2^* \in \mathsf{B}_{m\delta_\beta + t\delta_B + t}^3$.
\item Extend $\bar{\mathbf{v}}_2$ into $\mathbf{s}_0 \in \mathsf{B}_{m\delta_\beta}^3$. Then, for each $j \in [\ell]$, define ${\mathbf{s}}_j = \mathsf{expand}(\tau[j], \mathbf{s}_0)$. (We refer to Table~\ref{table:ZK-notations-techniques} for details about $\mathsf{expand}(\cdot, \cdot)$.)
\end{itemize}


%At the same time, we extend the vector $\bar{\mathbf{v}}_2$ to $\mathbf{v}_2^* \in \mathsf{B}_{m\delta_\beta}^3$ and  $\tau$ into $\tau^* = (\tau[1], \ldots, \tau[\ell], \tau[\ell+1], \ldots, \tau[2\ell])^T \in \mathsf{B}_{2\ell}$, and then form vector $\mathbf{w}_3^* = \big((\mathbf{v}_2^*)^T  \mid (\tau[1]\cdot \mathbf{v}_2^*)^T \mid  \ldots \mid  (\tau[2\ell]\cdot \mathbf{v}_2^*)^T \big)^T \in \mathsf{Mix}_{\ell, m\delta_\beta}$.
\noindent
Now, we form vector $\mathbf{w} = \bigl({\mathbf{w}_1^*}^T \mid {\mathbf{w}_2^*}^T \mid \mathbf{s}_0^T \mid {\mathbf{s}}_1^T \mid \ldots \mid  {\mathbf{s}}_\ell^T \bigr)^T \in \{-1,0,1\}^D$, where $D = (2\ell+2)3m\delta_\beta + 3t\delta_B + 3t + 2(m_d+t)$. At this point, we observe that the equations in~\eqref{eq:protocol-3-original} can be equivalently transformed into $\mathbf{M}\cdot \mathbf{w} = \mathbf{v} \bmod q$, where the matrix $\mathbf{M}$ and the vector $\mathbf{v}$ are built from the public input.
\smallskip

Having performed the above transformations, we now define $\mathsf{VALID}$ as the set of all vectors $\mathbf{t} = (\mathbf{t}_1^T \hspace*{1.6pt}\mid \hspace*{1.6pt}\mathbf{t}_2^T \hspace*{1.6pt} \mid \hspace*{1.6pt} \mathbf{t}_{3,0}^T \hspace*{1.6pt} \mid \hspace*{1.6pt} \mathbf{t}_{3,1}^T \hspace*{1.6pt}\mid  \ldots \mid \hspace*{1.6pt} \mathbf{t}_{3,\ell}^T )^T \in \{-1,0,1\}^D$ for which there exists $\tau = (\tau[1], \ldots,  \tau[\ell])^T \in \{0,1\}^\ell$ such that:
\[
\mathbf{t}_1 \in \mathsf{B}_{m_d+t}^2; \hspace*{2.8pt}
\mathbf{t}_2 \in \mathsf{B}_{m\delta_\beta + t\delta_B + t}^3; \hspace*{2.8pt}
\mathbf{t}_{3,0} \in \mathsf{B}_{m\delta_\beta}^3; \hspace*{2.8pt}
\forall j\in [\ell]: \mathbf{t}_{3,j} = \mathsf{expand}(\tau[j], \mathbf{t}_{3,0}).
\]
It can be seen that $\mathbf{w}$ belongs to this tailored set.
Now, let us specify the set $\mathcal{S}$ and permutations of $D$ elements $\{\Gamma_\phi: \phi \in \mathcal{S}\}$ satisfying the conditions in~\eqref{eq:zk-equivalence}.
\begin{itemize}
\item $\mathcal{S}: = \mathcal{S}_{2(m_d+t)} \times \mathcal{S}_{3(m\delta_\beta + t\delta_B + t)} \times \mathcal{S}_{3m\delta_\beta} \times \{0,1\}^\ell$.
\item For $\phi = \big(\phi_1, \phi_2, \phi_{3}, (b[1], \ldots, b[\ell])^T \big) \in \mathcal{S}$, we define the permutation $\Gamma_\phi$ that transforms vector $\mathbf{t} = (\mathbf{t}_1^T \hspace*{1.6pt}\mid \hspace*{1.6pt}\mathbf{t}_2^T \hspace*{1.6pt}\mid \hspace*{1.6pt} \mathbf{t}_{3,0}^T \hspace*{1.6pt}\mid \hspace*{1.6pt} \mathbf{t}_{3,1}^T \hspace*{1.6pt}\mid \ldots \mid \hspace*{1.6pt} \mathbf{t}_{3,\ell}^T )^T \in \mathbb{Z}^D$ as follows:
    \begin{eqnarray*}
    \Gamma_\phi(\mathbf{t}) = \big(\phi_1(\mathbf{t}_1)^T \hspace*{1.6pt}\mid &&\phi_2(\mathbf{t}_2)^T \hspace*{1.6pt}\mid \hspace*{1.6pt} \phi_3(\mathbf{t}_{3,0})^T \hspace*{1.6pt}\mid  \\ &&T_{\mathsf{exp}}[b[1],\phi_3](\mathbf{t}_{3,1})^T \hspace*{2.8pt}\mid \ldots \mid \hspace*{2.8pt}T_{\mathsf{exp}}[b[\ell],\phi_3](\mathbf{t}_{3,\ell})^T  \big)^T.
    \end{eqnarray*}
\end{itemize}
By inspection, it can be seen that the properties in~\eqref{eq:zk-equivalence} are indeed satisfied. As a result, we can obtain the required argument of knowledge by running the protocol from \cref{sse:stern-abstraction} with common input $(\mathbf{M}, \mathbf{v})$ and prover's input $\mathbf{w}$.
The protocol has communication cost $\mathcal{O}(D\log q)= \widetilde{\mathcal{O}}(\lambda)\cdot \mathcal{O}(\log N + t)$ bits.

\subsection{Protocol 4: A Treatment of Hidden Branching Programs}\label{subsection:ZK-Protocol4-BP}
We now present the proof system run by the user in the OT-AC system of Section~\ref{OT-AC-scheme}. It allows arguing knowledge of an input $\mathbf{x} = (x_0, \ldots, x_{\kappa-1})^T \in \{0,1\}^\kappa$  satisfying a hidden branching program $\mathsf{BP}= \{(\var(\theta),\pi_{\theta,0},\pi_{\theta,1})\}_{\theta =1}^L$ of length for $L \in \mathsf{poly}(\lambda)$. The prover should additionally demonstrate that: (i) He has a valid credential for $\mathbf{x}$; (ii) The hashed encoding of $\mathsf{BP}$ is associated with some hidden ciphertext of the database (and he knows a signature guaranteeing this link); (iii) A given ciphertext is a re-randomization of that hidden ciphertext.

 Recall that, at each step $\theta \in [L]$ of the evaluation   of $\mathsf{BP}(\mathbf{x})$, we have to look up  the value $x_{\var(\theta)}$ in   $\mathbf{x}=(x_0, \ldots, x_{\kappa-1})^T$   to compute the $\theta$-th state~$\eta_\theta$ as per
\begin{eqnarray}\label{equation:ZK-BP-evaluation}
\eta_\theta = \pi_{\theta, x_{\mathrm{var}(\theta)}}(\eta_{\theta-1}) = \pi_{\theta, 0}(\eta_{\theta-1})\cdot \bar{x}_{\mathrm{var}(\theta)} + \pi_{\theta, 1}(\eta_{\theta-1})\cdot {x}_{\mathrm{var}(\theta)}.
\end{eqnarray}

To prove that each step is done correctly, it is necessary to provide evidence that the corresponding search is   honestly carried out without revealing ${x}_{\mathrm{var}(\theta)}$,  ${\mathrm{var}(\theta)}$ nor $\{ \pi_{\theta,b}\}_{b=0}^1$. To this end, a first idea is  to perform  a simple left-to-right search on $(x_0, \ldots, x_{\kappa-1})$: namely,
  \eqref{equation:ZK-BP-evaluation} is expressed in terms of a matrix-vector relation   where $\eta_\theta$ is encoded as a unit  vector of dimension $5$;  $\{ \pi_{\theta,b}\}_{b=0}^1$ are represented as permutation matrices; and $\mathbf{x}_{\mathrm{var}(\theta)} = \mathbf{M}_{\mathrm{var}(\theta)}  \cdot \mathbf{x} $ is computed
using a  matrix     $\mathbf{M}_{\mathrm{var}(\theta)}  \in \{0,1\}^{\kappa \times \kappa}$ containing exactly one $1$ per row.
While this approach can be handled using proofs for matrix-vector relations using the techniques of \cite{LLM+16a},   the expected complexity is $\mathcal{O}(\kappa)$ for each step, so that the total  complexity becomes
 $\mathcal{O}(L \kappa)$. Fortunately, a better  complexity can be achieved.

 If we instead perform a dichotomic search on $\mathbf{x}=(x_0, \ldots, x_{\kappa-1})^T$,   we can reduce the complexity of each step to   $\mathcal{O}(\log \kappa)$. To this end, we need to prove   a statement ``I performed a correct dichotomic search on my secret array $\mathbf{x}$''.

 In order to solve this problem, we will employ two existing lattice-based tools.
%(which we recall in Section~\ref{appendix:bit-commit+Merkle-tree} of Appendix, for the sake of completeness):
\begin{enumerate}[(i)]
\item A variant of the \textsf{SIS}-based computationally binding and statistically hiding commitment scheme from~\cite{KTX08}, which allows to commit to one-bit messages;
\item The \textsf{SIS}-based Merkle hash tree proposed in~\cite{LLNW16}.
\end{enumerate}

Let $\bar{\mathbf{A}} \hookleftarrow U(\mathbb{Z}_q^{n \times m})$ and $\mathbf{a}_{\mathsf{com}} \hookleftarrow U(\mathbb{Z}_q^{n})$. For each $i \in [0,\kappa-1]$, we let the receiver  commit to $x_i \in \{0,1\}$ as $\mathsf{com}_i = \mathbf{a}_{\mathsf{com}}\cdot x_i + \bar{\mathbf{A}}\cdot \mathbf{r}_{\mathsf{com},i}$, with $\mathbf{r}_{\mathsf{com},i} \hookleftarrow U(\{0,1\}^m)$, and reveal $\mathsf{com}_1,\ldots,\mathsf{com}_{\kappa-1}$ to the sender. We build a Merkle tree of depth $\delta_\kappa = \lceil \log \kappa \rceil$ on top of the  leaves $\mathsf{com}_0, \ldots, \mathsf{com}_{\kappa-1}$  using the $\mathsf{SIS}$-based hash function $h_{\bar{\mathbf{A}}}: \{0,1\}^{n\lceil \log q\rceil} \times \{0,1\}^{n\lceil \log q\rceil} \rightarrow \{0,1\}^{n\lceil \log q\rceil}$ of~\cite{LLNW16}. Our use of  Merkle trees is reminiscent of \cite{LLNW16} in that the content of the leaves is public. The Merkle tree will actually serve as a ``bridge'' ensuring that: (i) The same string $\mathbf{x} $ is used in all steps while enabling dichotomic searches; (ii) At each step, the prover indeed uses some coordinate of  $\mathbf{x}$ (without revealing which one),  the choice of which is dictated by a path in the tree determined by $\var(\theta)$. %Note that, under the \textsf{SIS} assumptions,  the commitment and the hash function are both secure.

 Since $\{ \mathsf{com}_i \}_{i=0}^{\kappa-1}$ are public,   both parties can deterministically compute the root $\mathbf{u}_{\mathsf{tree}} $ of the Merkle tree.  For each $\theta \in [L]$, we consider the binary representation $d_{\theta, 1}, \ldots, d_{\theta, \delta_\kappa}$ of $\var(\theta)$, which is part of  the encoding of $\mathsf{BP}$  defined in~\eqref{equation:z_BP}.
We then prove knowledge of a bit $y_\theta$ satisfying the statement
``From the root $\mathbf{u}_{\mathsf{tree}} \in \{0,1\}^{n\lceil \log q\rceil}$ of the   tree,  the path determined by the bits $d_{\theta, 1}, \ldots, d_{\theta, \delta_\kappa}$ leads to  the leaf associated with the commitment opened to $y_\theta$.''  If the Merkle tree and the commitment scheme are both secure,  it  should hold that $y_\theta = x_{\mathrm{var}(\theta)}$. Said otherwise, we can provably perform a ``dichotomic search'' for $x_{\mathrm{var}(\theta)} = y_\theta$. Moreover, the techniques from~\cite{LLNW16} can be adapted to do this  in zero-knowledge manner, i.e., without revealing the path nor the reached leaf.

Now, our task can be divided into $3$ steps: (i) Proving that the searches on Merkle tree yield  $y_{1}, \ldots, y_L$; (ii) Proving that the branching program evaluates to $\mathsf{BP}(\mathbf{x})=1$ if $y_{1}, \ldots, y_L$ are used in the evaluation; (iii) Proving all the other relations mentioned above, as well as the consistency of  $\{ \mathsf{com}_i \}_{i=0}^{\kappa-1}$ and the fact that they open to a certified $\mathbf{x} \in \{0,1\}^\kappa$. \\
\indent
Thanks to   dichotomic  searches, the  communication cost drops to $\mathcal{O}(L \delta_\kappa + \kappa)$.
These steps can be treated as explained below.

\subsubsection{The Merkle Tree Step.}

At each step $\theta \in [L]$, the prover demonstrates knowledge of a path consisting of $\delta_\kappa$ nodes $\mathbf{g}_{\theta,1}, \ldots, \mathbf{g}_{\theta, \delta_\kappa} \in \{0,1\}^{n\lceil \log q\rceil}$ determined by $d_{\theta, 1}, \ldots, d_{\theta, \delta_\kappa}$, as well as their sibling nodes $\mathbf{t}_{\theta, 1}, \ldots, \mathbf{t}_{\theta, \delta_\kappa} \in \{0,1\}^{n\lceil \log q\rceil}$.
Also, the prover argues knowledge of an opening $(y_\theta ,  \mathbf{r}_\theta) \in \{0,1\}  \times \{0,1\}^m $ for the commitment of which $\mathbf{g}_{\theta, \delta_\kappa}$ is a binary decomposition.
As shown in~\cref{sse:stern},
%(and  recalled in Appendix~\ref{appendix:bit-commit+Merkle-tree}),
it suffices to prove  the following relations (mod $q$):

\begin{eqnarray}  \label{Merkle-layer}
 \forall \theta\in [L]   \begin{cases}
  \bar{\mathbf{A}}\cdot \mathsf{expand}( {d}_{\theta,1}, \mathbf{g}_{\theta,1}) + \bar{\mathbf{A}}\cdot \mathsf{expand}( \bar{d}_{\theta,1}, \mathbf{t}_{\theta,1}) = \mathbf{H}_{n, q-1}\hspace*{-2.5pt}\cdot \hspace*{-2.5pt}\mathbf{u}_{\mathsf{tree}}, \\[2.5pt]
 \bar{\mathbf{A}}\cdot \mathsf{expand}( {d}_{\theta,2}, \mathbf{g}_{\theta,2})
+ \bar{\mathbf{A}}\cdot \mathsf{expand}( \bar{d}_{\theta,2}, \mathbf{t}_{\theta,2})\\
    \hspace*{.5\textwidth} - \mathbf{H}_{n, q-1}\cdot \mathbf{g}_{\theta, 1} = \mathbf{0}, \qquad    \\\smallskip
%\hspace*{35pt}\ldots \ldots \ldots \ldots \ldots \ldots \\
\hfill \vdots \hfill \\
\bar{\mathbf{A}}\cdot \mathsf{expand}( {d}_{\theta,\delta_\kappa}, \mathbf{g}_{\theta,\delta_\kappa})
+ \bar{\mathbf{A}}\cdot \mathsf{expand}( \bar{d}_{\theta,\kappa}, \mathbf{t}_{\theta,\kappa}) \\\smallskip
    \hspace*{.5\textwidth} - \mathbf{H}_{n, q-1}\cdot \mathbf{g}_{\theta, \delta_\kappa-1} = \mathbf{0}, \\
\mathbf{a}_{\mathsf{com}}\cdot y_\theta + \bar{\mathbf{A}}\cdot \mathbf{r}_\theta - \mathbf{H}_{n, q-1}\cdot \mathbf{g}_{\theta, \delta_\kappa}=\mathbf{0},
\end{cases}
\end{eqnarray}
where $\mathsf{expand}(\cdot, \cdot)$ is defined in Table~\ref{table:ZK-notations-techniques}. \smallskip

\paragraph{Extending.}
\begin{itemize}
\item For each $(\theta, i) \in [L] \times [\delta_\kappa]$: Extend $\mathbf{g}_{\theta,i}, \mathbf{t}_{\theta,i} \in \{0,1\}^{m/2}$ to $\widetilde{\mathbf{g}}_{\theta,i}, \widetilde{\mathbf{t}}_{\theta,i} \in \mathsf{B}_{m/2}^2$, respectively.  Then, let $\widehat{\mathbf{g}}_{\theta,i} = \mathsf{expand}(d_{\theta,i}, \widetilde{\mathbf{g}}_{\theta,i})$ and $\widehat{\mathbf{t}}_{\theta,i} = \mathsf{expand}(\bar{d}_{\theta,i}, \widetilde{\mathbf{t}}_{\theta,i})$. \smallskip
\item For each $\theta \in [L]$, extend the bit $y_\theta$ into the   vector $\mathbf{y}_\theta = \mathsf{ext}_2(y_\theta) \in \{0,1\}^2$. \smallskip
\item Let $\widetilde{\mathbf{r}} = (\mathbf{r}_1^T \mid  \ldots \mid  \mathbf{r}_L^T )^T \in \{0,1\}^{mL}$, then extend it into the vector $\widehat{\mathbf{r}} \in \mathsf{B}_{mL}^2$.
\end{itemize}

\paragraph{Combining.}
Next, we let $D_{\mathsf{tree}} = 5mL\delta_\kappa + 2L + 2mL$  and define
%  $\mathbf{w}_{\mathsf{tree}} \in \{0,1\}^{D_{\mathsf{tree}}}$ as:
\begin{eqnarray}\label{equation:w_tree}
\nonumber \hspace*{-8pt}
 \mathbf{w}_{\mathsf{tree}}  = \bigl(
\widetilde{\mathbf{g}}_{1,1}^T \mid
\widehat{\mathbf{g}}_{1,1}^T   \mid
\widehat{\mathbf{t}}_{1,1}^T   \mid
 \ldots \mid    
\widetilde{\mathbf{g}}_{1,\delta_\kappa}^T \mid
\widehat{\mathbf{g}}_{1,\delta_\kappa}^T \mid
\widehat{\mathbf{t}}_{1,\delta_\kappa}^T \mid
\ldots \mid
\widetilde{\mathbf{g}}_{L,1}^T \mid
\widehat{\mathbf{g}}_{L,1}^T   \mid
\widehat{\mathbf{t}}_{L,1}^T  \\ \mid
 \ldots \mid \widetilde{\mathbf{g}}_{L,\delta_\kappa}^T \mid \widehat{\mathbf{g}}_{L,\delta_\kappa}^T \mid
 \widehat{\mathbf{t}}_{L,\delta_\kappa}^T
\mid
 \mathbf{y}_1^T \mid
 \ldots \mid
  \mathbf{y}_L^T \mid
  \widehat{\mathbf{r}}^T
\bigr)^T  \in \{0,1\}^{D_{\mathsf{tree}}}. \qquad
\end{eqnarray}
Then, observe that, the above $L(\delta_\kappa +1)$ equations can be combined into one:
\begin{eqnarray}\label{equation:M_tree.w_tree}
\mathbf{M}_{\mathsf{tree}}\cdot \mathbf{w}_{\mathsf{tree}} = \mathbf{v}_{\mathsf{tree}} \bmod q,
\end{eqnarray}
where matrix $\mathbf{M}_{\mathsf{tree}}$ and vector $\mathbf{v}_{\mathsf{tree}}$ are built from the public input.

\subsubsection{The Branching Program Step.}

 The last three parts of Table~\ref{table:ZK-notations-techniques} describe the vector transformations that will be used to handle the secret vectors appearing in the evaluation of $\mathsf{BP}$. The following equations emulate the evaluation process. In particular, for each $\theta \in [2,L]$, we introduce an extra vector $\mathbf{e}_\theta = (c_{\theta,0}, \ldots, c_{\theta,4}) \in \{0,1\}^5$ to enable the extraction of the values $\pi_{\theta, 0}(\eta_{\theta-1})$, and $\pi_{\theta,1}(\eta_{\theta-1})$.
\begin{eqnarray}
\begin{cases}
%f_{1,0} - 1\cdot \pi_{1,0}(0) - \sum_{i=1}^4 0 \cdot \pi_{1,0}(i) = 0 ~~\text{\small{// meaning: $f_{1,0}= \pi_{1,0}(0) = \pi_{1,0}(\eta_0)$}}\\
%f_{1,1} - 1\cdot \pi_{1,1}(0) - \sum_{i=1}^4 0 \cdot \pi_{1,1}(i) = 0 ~~\text{\small{// meaning: $f_{1,1}= \pi_{1,1}(0) = \pi_{1,1}(\eta_0)$}}\\
\pi_{1,0}(0)\cdot \bar{y}_1 + \pi_{1,1}(0)\cdot y_1 - \eta_1 = 0, &\text{\scriptsize{// computing $\eta_1$ with $\eta_0=0$}}\\[2.6pt]

\mathbf{e}_2 - \sum_{i=0}^4 \mathsf{unit}_i \cdot c_{2,i} = (0,0,0,0,0)^T, &\text{\scriptsize{// we will also prove $\mathbf{e}_2 = \mathsf{unit}_{\eta_1}$}}\\[2.6pt]
f_{2,0} - \sum_{i=0}^4 \pi_{2,0}(i)\cdot c_{2,i} = 0, &\text{\scriptsize{// meaning: $f_{2,0}= \pi_{2,0}(\eta_1)$}}\\
f_{2,1} - \sum_{i=0}^4 \pi_{2,1}(i)\cdot c_{2,i} = 0, &\text{\scriptsize{// meaning:  $f_{2,1}= \pi_{2,1}(\eta_1)$}}\\
f_{2,0}\cdot \bar{y}_2 + f_{2,1}\cdot y_2 - \eta_2 = 0, &\text{\scriptsize{// computing $\eta_2$}}\\[2.6pt]
%\hspace*{26pt} \ldots \ldots \ldots \\[2.6pt]
\hfill \vdots \hfill & \\

\mathbf{e}_L - \sum_{i=0}^4 \mathsf{unit}_i \cdot c_{L,i} = (0,0,0,0,0)^T, &\text{\scriptsize{// we will also prove $\mathbf{e}_L = \mathsf{unit}_{\eta_{L-1}}$}}\\[2.6pt]
f_{L,0} - \sum_{i=0}^4 \pi_{L,0}(i)\cdot c_{L,i} = 0,  &\text{\scriptsize{// meaning: $f_{L,0}= \pi_{L,0}(\eta_{L-1})$}}\\
f_{L,1} - \sum_{i=0}^4 \pi_{L,1}(i)\cdot c_{L,i} = 0, &\text{\scriptsize{// meaning: $f_{L,1}= \pi_{L,1}(\eta_{L-1})$}}\\
f_{L,0}\cdot \bar{y}_L + f_{L,1}\cdot y_L = 0. &\text{\scriptsize{// final state $\eta_L=0$}}
\end{cases}
\end{eqnarray}

\noindent
\textbf{Extending.}
\begin{itemize}
\item For each $\theta \in [L-1]$, extend $\eta_\theta \in [0,4]$ to $5$-dimensional vector $\mathbf{s}_\theta = \mathsf{ext}_5(\eta_\theta)$. % \smallskip
\item For each $(\theta, j) \in [2, L] \times \{0,1\}$, extend $f_{\theta, j} \in [0,4]$ to $\mathbf{f}_{\theta, j} = \mathsf{ext}_5(f_{\theta, j})$. \smallskip
\item For each $(\theta, i) \in [2,L] \times [0,4]$, extend $c_{\theta, i} \in \{0,1\}$ to $\mathbf{c}_{\theta,i} = \mathsf{ext}_2(c_{\theta, i})$.  \smallskip
\item Extend the products $\pi_{1,0}(0)\cdot \bar{y}_1$ and $\pi_{1,1}(0)\cdot y_1$ into $10$-dimensional vectors $\mathbf{h}_{1,0}= \mathsf{ext}_{5 \times 2}(\pi_{1,0}(0), \bar{y}_1)$ and $\mathbf{h}_{1,1} = \mathsf{ext}_{5 \times 2}(\pi_{1,1}(0), y_1)$, respectively. \smallskip
\item For each $\theta \in [2, L]$, extend the products $f_{\theta, 0}\cdot \bar{y}_\theta$ and $f_{\theta, 1}\cdot {y}_\theta$ into $10$-dimensional vectors $\mathbf{h}_{\theta,0}= \mathsf{ext}_{5 \times 2}(f_{\theta, 0}, \bar{y}_\theta)$ and $\mathbf{h}_{\theta,1} = \mathsf{ext}_{5 \times 2}(f_{\theta, 1}, y_\theta)$. \smallskip
\item For $(\theta, i) \in [2,L] \times [0,4]$, extend the products $\pi_{\theta, 0}(i)\cdot c_{\theta, i}$ and $\pi_{\theta, 1}(i)\cdot c_{\theta, i}$ into  $\mathbf{z}_{\theta, 0, i} = \mathsf{ext}_{5 \times 2}(\pi_{\theta, 0}(i), c_{\theta, i})$ and $\mathbf{z}_{\theta, 1, i} = \mathsf{ext}_{5 \times 2}(\pi_{\theta, 1}(i), c_{\theta, i})$, respectively. \smallskip
\end{itemize}

\noindent
\textbf{Combining. } Let $D_{\mathsf{BP}}= 150L - 130$, and form $\mathbf{w}_{\mathsf{BP}} \in [0,4]^{D_{\mathsf{BP}}}$ of the form:
\begin{eqnarray}\label{equation:w_BP}
\nonumber
\big(
\mathbf{s}_1^T \hspace*{1.6pt}\mid \hspace*{1.6pt}
 \ldots \hspace*{1.6pt}\mid \hspace*{1.6pt}
  &&\mathbf{s}_{L-1}^T \hspace*{1.6pt}\mid \hspace*{1.6pt}
   \mathbf{e}_2^T \hspace*{1.6pt}\mid \hspace*{1.6pt} \ldots \hspace*{1.6pt}\mid \hspace*{1.6pt}
    \mathbf{e}_L^T \hspace*{1.6pt}\mid \hspace*{1.6pt}
     \mathbf{c}_{2,0}^T \hspace*{1.6pt}\mid \hspace*{1.6pt}
      \ldots \hspace*{1.6pt}\mid \hspace*{1.6pt}
       \mathbf{c}_{L,4}^T \hspace*{1.6pt}\mid \hspace*{1.6pt}
        \mathbf{z}_{2,0,0}^T \hspace*{1.6pt}\mid \hspace*{1.6pt}
         \ldots \hspace*{1.6pt}\mid \hspace*{1.6pt}
          \mathbf{z}_{L,1,4}^T \hspace*{1.6pt}\mid  \\
&&\mathbf{f}_{2,0}^T \hspace*{1.6pt}\mid \hspace*{1.6pt}
 \ldots \hspace*{1.6pt}\mid \hspace*{1.6pt}
  \mathbf{f}_{L,1}^T \hspace*{1.6pt}\mid \hspace*{1.6pt}
 \mathbf{h}_{1,0}^T \hspace*{1.6pt}\mid \hspace*{1.6pt}
 \mathbf{h}_{1,1}^T \hspace*{1.6pt}\mid \hspace*{1.6pt}
 \mathbf{h}_{2,0}^T \hspace*{1.6pt}\mid \hspace*{1.6pt}
  \mathbf{h}_{2,1}^T \hspace*{1.6pt}\mid \hspace*{1.6pt}
   \ldots \hspace*{1.6pt}\mid \hspace*{1.6pt}
    \mathbf{h}_{L,0}^T \hspace*{1.6pt}\mid \hspace*{1.6pt}
     \mathbf{h}_{L,1}^T
\big)^T. \qquad~
\end{eqnarray}
Then, observe that  the vector  $\mathbf{w}_{\mathsf{BP}} $ of~\eqref{equation:w_BP} satisfies \textit{one} equation of the form:
\begin{eqnarray}\label{equation:M_BP.w_BP-over-Z}
\mathbf{M}_{\mathsf{BP}}\cdot \mathbf{w}_{\mathsf{BP}} = \mathbf{v}_{\mathsf{BP}},
\end{eqnarray}
where matrix $\mathbf{M}_{\mathsf{BP}}$ and vector $\mathbf{v}_{\mathsf{BP}}$ are obtained from the common input. Note that we work with integers in $[0,4]$, which are much smaller than $q$. As a result, \begin{eqnarray}\label{equation:M_BP.w_BP-mod-q}
\mathbf{M}_{\mathsf{BP}}\cdot \mathbf{w}_{\mathsf{BP}} = \mathbf{v}_{\mathsf{BP}} \bmod q.
\end{eqnarray}
Conversely, if we can prove that~\eqref{equation:M_BP.w_BP-mod-q} holds for a well-formed vector $\mathbf{w}_{\mathsf{BP}}$, then that vector should also satisfy~\eqref{equation:M_BP.w_BP-over-Z}.

\subsubsection{The Third Step.}

In the third layer, we have to prove knowledge of:
\begin{eqnarray} \label{3rd-layer}
\begin{cases}
  d_{1,1}, \ldots, d_{L, \delta_\kappa} \in \{0,1\}, \pi_{1,0}(0), \ldots, \pi_{L,1}(4) \in [0,4],\hspace*{2.5pt}\mathfrak{m} \in \{0,1\}^{m_d}, \\[2.6pt]
  \mathbf{x} = (x_0, \ldots, x_{\kappa-1})^T \in  \{0,1\}^\kappa, \hspace*{2.5pt}
  \mathfrak{m}_{\mathsf{U}, \mathbf{x}} \in \{0,1\}^{\frac{m}{2} + \kappa},  \hspace*{2.5pt} \widehat{\mathfrak{m}}_{\mathsf{U}, \mathbf{x}} \in \{0,1\}^{\frac{m}{2}}, \\[2.6pt]
  \mathbf{e}_{\mathsf{U}} \in \{0,1\}^m, \hspace*{2.5pt}
\mathbf{r}_{\mathsf{com},0}, \ldots, \mathbf{r}_{\mathsf{com},\kappa-1} \in \{0,1\}^m,   \hspace*{2.5pt} \mu \in \{0,1\}^t, \hspace*{2.5pt}\tau \in \{0,1\}^\ell, \hspace*{2.5pt}\\[2.6pt]
\tau_{\mathsf{U}} \hspace*{-1pt}\in\hspace*{-1pt} \{0,1\}^{\ell_I}, \hspace*{-1pt} \mathbf{v}_1, \hspace{-1pt} \mathbf{v}_2, \hspace{-1pt} \mathbf{v}_{\mathsf{U},1}, \hspace{-1pt} \mathbf{v}_{\mathsf{U},2},\hspace{-1pt}  \mathbf{r}_{\mathsf{U}} \hspace*{-1pt} \in \hspace*{-1pt} [-\beta,\beta]^m, \hspace*{-1pt}
\mathbf{e} \hspace{-1pt} \in \hspace{-1pt} \{-1,0,1\}^t,  \hspace*{-1pt} \nu \hspace*{-1pt} \in \hspace{-1pt} [-B,B]^t,
\end{cases}
\end{eqnarray}
which satisfy the equations of~\eqref{statement-rand-trois-ac}  for $\mathbf{z}_{\BPR, \rho} = (d_{1,1}, \ldots, d_{L, \delta_\kappa}, \pi_{1,0}(0), \ldots, \pi_{L,1}(4))^T$  and,  $\forall i \in [0,\kappa-1]$, the bit $x_i$ is committed in $\mathsf{com}_i$ with randomness~$\mathbf{r}_{\mathsf{com},i}$:
\[
\left[
  \begin{array}{ccc}
    \mathbf{a}_{\mathsf{com}} &  &  \\
     & \ddots &  \\
     &  &  \mathbf{a}_{\mathsf{com}} \\
  \end{array}
\right]\cdot \mathbf{x} +
\left[
  \begin{array}{ccc}
    \bar{\mathbf{A}} &  &  \\
     & \ddots &  \\
     &  &  \bar{\mathbf{A}} \\
  \end{array}
\right]\cdot
\left(
  \begin{array}{c}
    \mathbf{r}_{\mathsf{com},0} \\
    \vdots \\
    \mathbf{r}_{\mathsf{com},\kappa-1} \\
  \end{array}
\right)
= \left(
                            \begin{array}{c}
                              \mathsf{com}_0 \\
                              \vdots \\
                              \mathsf{com}_{\kappa-1} \\
                            \end{array}
                          \right) \bmod q.
\]

\noindent
\textbf{Decomposing. } We use   $\mathsf{vdec}'_{m, \beta}(\cdot)$ to decompose   $\mathbf{v}_1, \mathbf{v}_2, \mathbf{v}_{\mathsf{U},1}, \mathbf{v}_{\mathsf{U},2}, \mathbf{r}_{\mathsf{U}} \in [-\beta, \beta]^m$ into   $\bar{\mathbf{v}}_1, \bar{\mathbf{v}}_2, \bar{\mathbf{v}}_{\mathsf{U},1}, \bar{\mathbf{v}}_{\mathsf{U},2}, \bar{\mathbf{r}}_{\mathsf{U}} \in \{-1,0,1\}^{m\delta_\beta}$, respectively. Similarly, we decompose vector $\nu \in [-B,B]^t$ into vector $\bar{\nu} = \mathsf{vdec}'_{t,B}(\nu) \in \{-1,0,1\}^{t\delta_B}$. \smallskip

\noindent
\textbf{Extending and Combining. } Next, we perform the following steps:

\begin{itemize}
\item For each $(\theta, i) \in [L] \times [\delta_\kappa]$, extend $d_{\theta, i}$ to $\mathbf{d}_{\theta,i} = \mathsf{ext}_2(d_{\theta,i})$.

\item For each $(\theta, j,i) \in [L] \times \{0,1\} \times [0,4]$, extend $\pi_{\theta, j}(i)$ to $\Pi_{\theta, j,i} = \mathsf{ext}_5(\pi_{\theta, j}(i))$. %\smallskip

\item Let $\overline{\mathbf{w}}_{3,1} = \big(\mathbf{x}^T |  \mathbf{r}_{\mathsf{com},0}^T |  \ldots |  \mathbf{r}_{\mathsf{com},\kappa-1}^T  |  \mathfrak{m}_{\mathsf{U}, \mathbf{x}}^T |   \widehat{\mathfrak{m}}_{\mathsf{U}, \mathbf{x}}^T |  \mathfrak{m}^T \mid \mathbf{e}_{\mathsf{U}}^T |  \mu^T\big)^T \in \{0,1\}^{D_{3,1}}$, where $D_{3,1} = \kappa(m +2) + 2m + m_d + t$. Then extend $\overline{\mathbf{w}}_{3,1}$ to ${\mathbf{w}}_{3,1} \in \mathsf{B}_{D_{3,1}}^2$.

\item Define the vector $\overline{\mathbf{w}}_{3,2} = (\bar{\mathbf{v}}_1^T |  \bar{\mathbf{v}}_{\mathsf{U},1}^T |  \bar{\mathbf{r}}_{\mathsf{U}}^T |  \bar{\nu}^T |  \mathbf{e}^T)^T \in \{-1,0,1\}^{D_{3,2}}$ of dimension $D_{3,2} = 3m\delta_\beta + t(\delta_B+1)$  and extend  it into
% $3D_{3,2}$-dimensional vectors
${\mathbf{w}}_{3,2} \in \mathsf{B}_{D_{3,2}}^3$.

\item Extend $\bar{\mathbf{v}}_2$ to $\mathbf{s}_0 \in \mathsf{B}_{m\delta_\beta}^3$. Then for $j \in [\ell]$, form vector
      $\mathsf{s}_j = \mathsf{expand}\big(\tau[j], \mathbf{s}_0\big)$.  %\smallskip
\item Extend $\bar{\mathbf{v}}_{\mathsf{U},2}$ to $\mathbf{s}_{\mathsf{U},0} \in \mathsf{B}_{m\delta_\beta}^3$. Then for $j \in [\ell_I]$, form $\mathsf{s}_{\mathsf{U},j} = \mathsf{expand}\big(\tau_{\mathsf{U}}[j], \mathbf{s}_{\mathsf{U},0}\big)$.

    %Extend $\tau, \tau_{\mathsf{U}}$ to $\tau^* \in \mathsf{B}_{\ell}^2$ and $\tau^*_{\mathsf{U}} \in  \mathsf{B}_{\ell_I}^2$.
    %\begin{eqnarray*}
    %\tau^* &=& (\tau[1], \ldots, \tau[\ell], \tau[\ell+1], \ldots, \tau[2\ell])^T \in \mathsf{B}_{\ell}^2 \\
    %\tau^*_{\mathsf{U}}&=& (\tau_{\mathsf{U}}[1], \ldots, \tau_{\mathsf{U}}[\ell_I], \tau[\ell_I+1], \ldots, \tau_{\mathsf{U}}[2\ell_I])^T \in \mathsf{B}_{\ell_I}^2.
    %\end{eqnarray*}
   % Then form the ``mixing'' vectors:

\end{itemize}

Given the above transformations, let $D_3 = 2L(\delta_\kappa+25) + 2D_{3,1} + 3D_{3,2} + 3m\delta_\beta(2\ell+1) + 3m\delta_\beta(2\ell_I+1)$  and construct vector $\mathbf{w}_3 \in [-1,4]^{D_3}$ of the form:
\begin{eqnarray}\label{equation:w_3}
  \nonumber
  \big(
    \mathbf{d}_{1,1}^T \mid 
    \ldots \mid 
    \mathbf{d}_{L, \delta_\kappa}^T
    && \hspace*{-1.3em} \mid 
    \Pi_{1,0,0}^T \mid  \ldots
    \mid 
    \Pi_{L,1,4}^T \mid 
    \mathbf{w}_{3,1}^T \mid 
    \mathbf{w}_{3,2}^T \mid  \\
    &&
    \mathbf{s}_0^T \mid 
    \mathbf{s}_1^T \mid 
    \ldots \mid 
    \mathbf{s}_\ell^T \mid 
    \mathbf{s}_{\mathsf{U},0}^T \mid 
    \mathbf{s}_{\mathsf{U},1}^T \mid 
    \ldots \mid 
    \mathbf{s}_{\mathsf{U},\ell_I}^T \mid 
  \big)^T. \qquad
\end{eqnarray}
Observe that  the given five equations can be combined into one of the form:
\begin{eqnarray}\label{equation:M_3.w_3}
\mathbf{M}_3 \cdot \mathbf{w}_3 = \mathbf{v}_3 \bmod q,
\end{eqnarray}
where matrix $\mathbf{M}_3$ and vector $\mathbf{v}_3$ can be built from the public input.

\subsubsection{Putting Pieces Altogether.}

 At the final stage of the process,  we connect  the three aforementioned steps.
Indeed, all the equations involved in our process are captured by~\eqref{equation:M_tree.w_tree}, \eqref{equation:M_BP.w_BP-mod-q}, and~\eqref{equation:M_3.w_3} - which in turn can be combined into:
\begin{eqnarray}\label{equation:final}
\mathbf{M}\cdot \mathbf{w} = \mathbf{v} \bmod q,
\end{eqnarray}
where $\mathbf{w} = (\mathbf{w}_{\mathsf{tree}}^T \hspace*{1.8pt}\mid \hspace*{1.8pt} \mathbf{w}_{\mathsf{BP}}^T \hspace*{1.8pt}\mid \hspace*{1.8pt} \mathbf{w}_3^T)^T \in [-1,4]^D$, for

\[ D = D_{\mathsf{tree}} + D_{\mathsf{BP}} + D_3 = \widetilde{\mathcal{O}}(\lambda)\cdot (L\cdot \log \kappa + \kappa) + \widetilde{\mathcal{O}}(\lambda)\cdot(\log N + \lambda) + \widetilde{\mathcal{O}}(1)\cdot t. \]

The components  of   $\mathbf{w}$ all have constraints listed in Table~\ref{table:ZK-notations-techniques}. By construction, these blocks either belong to the special sets $\mathsf{B}_{\mathfrak{m}}^2$, $\mathsf{B}_{\mathfrak{m}}^3$ or they have the special forms $\mathsf{expand}(\cdot, \cdot)$, $\mathsf{ext}_2(\cdot)$, $\mathsf{ext}_5(\cdot)$, $\mathsf{ext}_{5\times 2}(\cdot, \cdot)$, which are invariant under the permutations defined in Table~\ref{table:ZK-notations-techniques}. As a result, we can specify suitable sets $\mathsf{VALID}$, $\mathcal{S}$ and permutations of $D$ elements $\{\Gamma_\phi: \phi \in \mathcal{S}\}$, for which the conditions of~\eqref{eq:zk-equivalence} are satisfied.% The   description of $\mathsf{VALID}$, $\mathcal{S}$ and $\Gamma_\phi$ is detailed in Appendix~\ref{appendix:ZK-Merkle}.
The description of the elements $\mathsf{VALID}$, $\mathcal{S}$ and $\Gamma_\phi$ is detailed as follows.

Let $\mathsf{VALID}$ be the set of all vectors in $[-1,4]^D$ having the form $(\mathbf{w}_{\mathsf{tree}}^T \| \mathbf{w}_{\mathsf{BP}}^T \| \mathbf{w}_3^T)^T$, where $\mathbf{w}_{\mathsf{tree}}, \mathbf{w}_{\mathsf{BP}}, \mathbf{w}_3$ have the form~\eqref{equation:w_tree}, \eqref{equation:w_BP}, and~\eqref{equation:w_3}, respectively, and the following conditions hold:
\begin{itemize}
    \item For each $(\theta, i) \in [L] \times [\delta_\kappa]$: There exists $d_{\theta,i} \in \{0,1\}$ and $\widetilde{\mathbf{g}}_{\theta,i}, \widetilde{\mathbf{t}}_{\theta,i}\in \mathsf{B}_{m/2}^2$ such that $\mathbf{d}_{\theta,i} = \mathsf{ext}_2(d_{\theta,i})$ and
      \begin{align*}
        \widehat{\mathbf{g}}_{\theta, i} &= \mathsf{expand}(d_{\theta,i}, \widetilde{\mathbf{g}}_{\theta,i}); &
        \widehat{\mathbf{t}}_{\theta, i} &= \mathsf{expand}(\bar{d}_{\theta,i}, \widetilde{\mathbf{t}}_{\theta,i}).
      \end{align*}


    \item There exist $y_1 \in \{0,1\}$ and $\pi_{1,0}(0), \pi_{1,1}(0) \in [0,4]$ such that
    \[
    \begin{cases}
      \begin{aligned}
        \mathbf{y}_1 &= \mathsf{ext}_2(y_1);
        &
        \mathbf{h}_{1,0} &= \mathsf{ext}_{5 \times 2}(\pi_{1,0}(0), \bar{y}_1);
        &
        \mathbf{h}_{1,1} &= \mathsf{ext}_{5 \times 2}(\pi_{1,1}(0), {y}_1); 
      \end{aligned} \\
      \begin{aligned}
        \Pi_{1,0,0} &= \mathsf{ext}_5(\pi_{1,0}(0)); &
        \Pi_{1,1,0} &= \mathsf{ext}_5(\pi_{1,1}(0)).
      \end{aligned}
    \end{cases}
    \]

    \item For all $(j,i) \in \{0,1\} \times [1,4]$: $\Pi_{1, j, i} = \mathsf{ext}_5(\pi_{1,j}(i))$, for \emph{some} $\pi_{1,j}(i) \in [0,4]$. (Note that these $\pi_{1,j}(i)$ do \emph{not} participate in the evaluation of the $\mathsf{BP}$.)


    \item For $\theta \in [2,L]$: There exist $y_\theta \in \{0,1\}$, $f_{\theta, 0}, f_{\theta, 1} \in [0,4]$ such that $\mathbf{y}_\theta = \mathsf{ext}_2(y_\theta)$ and
     \[
    \begin{cases}
      \begin{aligned}
        \mathbf{f}_{\theta, 0} &= \mathsf{ext}_5(f_{\theta, 0}); &
        \mathbf{f}_{\theta, 1} &= \mathsf{ext}_5(f_{\theta, 1}); \\
        \mathbf{h}_{\theta,0} &= \mathsf{ext}_{5 \times 2}(f_{\theta, 0}, \bar{y}_\theta);
        &
        \mathbf{h}_{\theta,1} &= \mathsf{ext}_{5 \times 2}(f_{\theta, 1}, y_\theta).
      \end{aligned}
    \end{cases}
    \]



  %$\mathbf{f}_{\theta, 0} = \mathsf{ext}_5(f_{\theta, 0})$, $\mathbf{f}_{\theta, 1} = \mathsf{ext}_5(f_{\theta, 1})$, $\mathbf{h}_{\theta,0}= \mathsf{ext}_{5 \times 2}(f_{\theta, 0}, \bar{y}_\theta)$, $\mathbf{h}_{\theta,1} = \mathsf{ext}_{5 \times 2}(f_{\theta, 1}, y_\theta)$. \medskip


    \item For $(\theta, j, i) \in [2,L]\times \{0,1\} \times [0,4]$: there exist $\pi_{\theta,j}(i) \in [0,4]$, $c_{\theta,i} \in \{0,1\}$ such that
      \begin{align*}
        \Pi_{\theta,j,i} &= \mathsf{ext}_5(\pi_{\theta,j}(i));
        &
        \mathbf{c}_{\theta,i} &= \mathsf{ext}_2(c_{\theta,i});
        &
        \mathbf{z}_{\theta, j, i} &= \mathsf{ext}_{5 \times 2}(\pi_{\theta, j}(i), c_{\theta, i}).
      \end{align*}


    \item There exist $\eta_1, \ldots, \eta_{L-1} \in [0,4]$ such that the following hold. \smallskip
    \begin{enumerate}
        \item For all $\theta = 1, \ldots, L-1$: $\mathbf{s}_\theta = \mathsf{ext}_5(\eta_\theta)$. \medskip
        \item For all $\theta = 2, \ldots, L$: $\mathbf{e}_\theta = \mathsf{unit}_{\eta_{\theta-1}}$.
    \end{enumerate}
      \medskip


    \item $\widehat{\mathbf{r}} \in \mathsf{B}_{mL}^2$; \quad ${\mathbf{w}}_{3,1} \in \mathsf{B}_{D_{3,1}}^2$; \hspace*{6.8pt} ${\mathbf{w}}_{3,2} \in \mathsf{B}_{D_{3,2}}^3$; \medskip
    \item  $\mathbf{s}_0 \in \mathsf{B}_{m\delta_\beta}^3$, and there exists $\tau = (\tau[1], \ldots, \tau[\ell])^T \in \{0,1\}^\ell$ such that for all $j \in [\ell]$:
      $\mathsf{s}_j = \mathsf{expand}\big(\tau[j], \mathbf{s}_0\big)$. \medskip
    %$\mathbf{w}_{3,3} \in \mathsf{Mix}_{\ell, m\delta_\beta}$;

     %   \hspace*{6.8pt} $\mathbf{w}_{3,4} \in \mathsf{Mix}_{\ell_I, m\delta_\beta}$.


\item $\mathbf{s}_{\mathsf{U},0} \in \mathsf{B}_{m\delta_\beta}^3$, and there exists $\tau_{\mathsf{U}} = (\tau_{\mathsf{U}}[1], \ldots, \tau_{\mathsf{U}}[\ell_I])^T \in \{0,1\}^{\ell_I}$ such that for all $j \in [\ell_I]$:  $\mathsf{s}_{\mathsf{U},j} = \mathsf{expand}\big(\tau_{\mathsf{U}}[j], \mathbf{s}_{\mathsf{U},0}\big)$.
\end{itemize}

By construction, we have $\mathbf{w} \in \mathsf{VALID}$. Let us now specify the set $\mathcal{S}$ and permutations of $D$ elements $\{\Gamma_\phi: \phi \in \mathcal{S}\}$, for which the conditions in~\eqref{eq:zk-equivalence} hold. Again, we refer to the notations and techniques from Table~\ref{table:ZK-notations-techniques}, which we will apply here. Let
\begin{eqnarray*}
&&\mathcal{S} = \{0,1\}^{L\delta_\kappa} \times \{0,1\}^L \times [0,4]^{10L} \times [0,4]^{L-1}\times \{0,1\}^{5(L-1)} \times [0,4]^{2(L-1)} \times \\
&& \big((\mathcal{S}_m)^{2L\delta_\kappa} \times \mathcal{S}_{2mL}\big) \hspace*{-1.5pt}\times \hspace*{-1.5pt}(\mathcal{S}_{2D_{3,1}} \times \mathcal{S}_{3D_{3,2}} \hspace*{-1.5pt}\times \hspace*{-1.5pt} (\mathcal{S}_{3m\delta_\beta}\times \{0,1\}^\ell)\hspace*{-1.5pt} \times\hspace*{-1.5pt} (\mathcal{S}_{3m\delta_\beta}\times \{0,1\}^{\ell_I})).
\end{eqnarray*}
For each $\phi = (\mathbf{b}_d, \mathbf{b}_y, \mathbf{b}_p, \mathbf{b}_c, \mathbf{b}_f, \Sigma_{\mathsf{tree}}, \Sigma_3) \in \mathcal{S}$, where:
\[
\begin{cases}
\mathbf{b}_d = (b_{d,1,1}, \ldots, b_{d,L,\delta_\kappa})^T, \hspace*{10pt} \mathbf{b}_y = (b_{y,1}, \ldots, b_{y, L})^T,
\\
\mathbf{b}_\eta = (b_{\eta, 1}, \ldots, b_{\eta, L-1})^T, \hspace*{5pt}
\mathbf{b}_c = (b_{c,2,0}, \ldots, b_{c,L,4})^T, \hspace*{5pt}
\mathbf{b}_f = (b_{f, 2,0}, \ldots, b_{f, L, 1})^T, \\
\mathbf{b}_p = (b_{\pi, 1,0,0}, \ldots, b_{\pi, L,1,4})^T, \hspace*{5pt}\Sigma_{\mathsf{tree}} = (\sigma_{g,1,1}, \ldots, \sigma_{g,\theta, \delta_\kappa}, \sigma_{t,1,1}, \ldots, \sigma_{t, \theta, \delta_\kappa}, \sigma_r),   \\
\Sigma_3 = (\sigma_{3,1}, \hspace*{1.8pt}
\sigma_{3,2}, \hspace*{1.8pt}
\sigma_{3,3,1}, \hspace*{1.8pt}
b_{\tau}[1]\ldots b_{\tau}[\ell], \hspace*{1.8pt}
\sigma_{3,3,2}, \hspace*{1.8pt}
b_{\tau,\mathsf{U}}[1]\ldots b_{\tau,\mathsf{U}}[\ell_I]),
\end{cases}
\]
let $\Gamma_\phi$ be the permutation that, when applying to vector $\mathbf{s}$ of the form  $(\mathbf{w}_{\mathsf{tree}}^T \| \mathbf{w}_{\mathsf{BP}}^T \| \mathbf{w}_3^T)^T \in \mathbb{Z}^D$,
where $\mathbf{w}_{\mathsf{tree}}, \mathbf{w}_{\mathsf{BP}}, \mathbf{w}_3$ have the form~\eqref{equation:w_tree}, \eqref{equation:w_BP}, and~\eqref{equation:w_3}, respectively, transforms the block-vectors as follows:
\begin{itemize}
\item For each $(\theta, i) \in [L] \times [\delta_\kappa]$: $\widetilde{\mathbf{g}}_{\theta,i} \mapsto \sigma_{g, \theta, i}(\widetilde{\mathbf{g}}_{\theta,i})$ and
  \begin{align*}
 \widehat{\mathbf{g}}_{\theta,i} &\mapsto T_{\mathsf{exp}}[b_{d, \theta, i}, \sigma_{g_, \theta, i}](\widehat{\mathbf{g}}_{\theta,i}); &
\widehat{\mathbf{t}}_{\theta,i} &\mapsto T_{\mathsf{exp}}[{b}_{d, \theta, i}, \sigma_{t_, \theta, i}](\widehat{\mathbf{t}}_{\theta,i}).
\end{align*}

\item For each $\theta \in [L]$: $\mathbf{y}_\theta \mapsto T_2[b_{y,\theta}](\mathbf{y}_{\theta})$;
$\widehat{\mathbf{r}} \mapsto \sigma_r(\widehat{\mathbf{r}})$.

\item For each $\theta = 1, \ldots, L-1$: $\mathbf{s}_\theta \mapsto T_5[b_{\eta, \theta}](\mathbf{s}_\theta)$.

\item For each $\theta = 2, \ldots, L$: $\mathbf{e}_\theta \mapsto T_5[b_{\eta, \theta-1}](\mathbf{e}_\theta)$.

\item For each $(\theta, i) \in [2,L]\times [0,4]$: $\mathbf{c}_{\theta, i} \mapsto T_2[b_{c,\theta, i}](\mathsf{c}_{\theta,i})$.

\item For each $(\theta, j,i) \in [2,L] \times \{0,1\}\times [0,4]$: $\mathbf{z}_{\theta, j,i} \mapsto T_{5\times 2}[b_{\pi, \theta, j, i}, b_{c, \theta, i}](\mathbf{z}_{\theta, j,i})$.

\item For each $(\theta, j) \in [2,L] \times \{0,1\}$: $\mathbf{f}_{\theta, j} \mapsto T_5[b_{f,\theta,j}](\mathbf{f}_{\theta,j})$.

\item $\mathbf{h}_{1,0} \mapsto T_{5\times 2}[b_{\pi, 1,0,0}, b_{y,1}](\mathbf{h}_{1,0})$; $\mathbf{h}_{1,1} \mapsto T_{5\times 2}[b_{\pi, 1,1,0}, b_{y,1}](\mathbf{h}_{1,1})$.

\item For each $(\theta, j) \in [2,L] \times \{0,1\}$: $\mathbf{h}_{\theta,j} \mapsto T_{5\times 2}[b_{f,\theta,j}, b_{y,\theta}](\mathbf{h}_{\theta,j})$.

  \item For each $(\theta, i) \in [L]\times [\delta_\kappa]$: $\mathbf{d}_{\theta, i} \mapsto T_2[b_{d,\theta, i}](\mathbf{d}_{\theta, i})$.

 \item For each $(\theta, j, i) \in [L] \times \{0,1\} \times [0,4]$: $\Pi_{\theta, j,i} \mapsto T_5[b_{\pi, \theta, j, i}](\Pi_{\theta, j,i})$.

    \item For each $i \in [1,2]$: $\mathbf{w}_{3,i} \mapsto \sigma_{3,i}(\mathbf{w}_{3,i})$.

    \item $\mathsf{s}_0 \mapsto \sigma_{3,3,1}(\mathsf{s}_0)$. For each $j \in [\ell]$: $\mathbf{s}_j \mapsto T_{\mathsf{exp}}[b_{\tau}[j],\sigma_{3,3,1}](\mathbf{s}_j)$.

    \item $\mathsf{s}_{\mathsf{U},0} \mapsto \sigma_{3,3,2}(\mathsf{s}_{\mathsf{U},0})$. For each $j \in [\ell_I]$: $\mathsf{s}_{\mathsf{U},j} \mapsto T_{\mathsf{exp}}[b_{\tau,\mathsf{U}}[j],\sigma_{3,3,2}](\mathsf{s}_{\mathsf{U},j})$.
\end{itemize}
\medskip
Based on the equivalences observed in Table~\ref{table:ZK-notations-techniques}, it can be checked that the conditions of~\eqref{eq:zk-equivalence} hold, namely:
\begin{eqnarray*}
\begin{cases}
\mathbf{w} \in \mathsf{VALID} \hspace*{2.5pt} \Longleftrightarrow \hspace*{2.5pt} \Gamma_\phi(\mathbf{w}) \in \mathsf{VALID}, \\
\text{If } \mathbf{w} \in \mathsf{VALID} \text{ and } \phi \text{ is uniform in } \mathcal{S}, \text{ then }  \Gamma_\phi(\mathbf{w}) \text{ is uniform in } \mathsf{VALID}.
\end{cases}
\end{eqnarray*}


Our desired argument system then works as follows. At the beginning of the interaction, the prover computes commitments $\mathsf{com}_0, \ldots, \mathsf{com}_{\kappa - 1} \in \mathbb{Z}_q^n$ and send them once to the verifier. Both parties construct matrix $\mathbf{M}$ and vector~$\mathbf{v}$ based on the public input as well as $\mathsf{com}_0, \ldots, \mathsf{com}_{\kappa - 1}$, while the prover prepares vector $\mathbf{w}$, as described. Finally, they
run the protocol of \cref{sse:stern-abstraction},
which has communication cost $\mathcal{O}(D \log q)= \mathcal{O}(L\cdot \log \kappa + \kappa)$.

\section{Reducing the Communication Complexity in the Random Oracle Model} \label{optimized}
One limitation of our basic adaptive OT protocol is that it requires the sender to repeat the zero-knowledge proofs of the initialization phase
for each user. In total, the communication cost of the initialization phase thus amounts to $\Omega(\lambda N U)$, which is even more expensive
than the $O(\lambda (N+U))$ complexities of \cite{CNS07,GH07,CDN09,JL09}. As pointed out by Green and Hohenberger \cite{GH11}, decreasing the
cost of the initialization phase to be independent of the number of users  is highly
desirable: ideally, one would certainly prefer a  non-interactive initialization phase where the Sender can publicize a $O(\lambda N)$-size
commitment to the database, which can subsequently  be used by arbitrarily many receivers.

In the random oracle model, we show that our protocols can both be modified to obtain this optimized communication complexity.
 This can be achieve by the simple expedient of making
the sender's zero-knowledge proofs non-interactive via the Fiat-Shamir heuristic. \\
\indent  By removing interaction from \textit{all} the sender's proof
(i.e., even those of the transfer phase), we also minimize the number of communication rounds since we only need
 the verifier's arguments to be witness indistinguishable and we can thus safely repeat them in parallel.
%One of the reasons why such an optimization is possible is that, in the security proofs, the
%zero-knowledge arguments produced by the sender at each transfer phase never have to be rewound by the simulator: indeed, they only serve as
%proofs of membership rather than proofs of knowledge.
 Relying on the random oracle model thus allows the sender to publicize the entire
database and proofs on a public repository so as to avoid repeating these proofs for each receiver.



\subsection{Description}

The   description hereunder relies on the same parameters as in sections \ref{OT-scheme}   and \ref{OT-AC-scheme}.
  Namely, we use $m= 2 n \lceil \log q \rceil$,  a modulus $q$ for which the noise distribution $\chi$ is $\alpha q$-bounded, for some $0<\alpha <1$, and
	also define an integer $B$ as a randomization parameter
such that $(m+1) \alpha q / B $ is negligible and choosing $\alpha$ such that $(m+1) \alpha \leq 1/5$ ensures decryption correctness.

We assume two random oracles $H_F:\{0,1\}^\ast \rightarrow \Zq^{n \times m}$ and
$H_{\mathsf{FS}} : \{0,1\}^\ast \rightarrow \{1,2,3\}^\varsigma$, for some $\varsigma \in \omega(\log n)$. The former will be used to derive the sender's public matrix $\mathbf{F} \in \Zq^{n \times m} $
while the latter will  provide the verifier's challenges when we apply the Fiat-Shamir heuristic.


\begin{description}
\item[\textsf{Initialization}$\big(\mathsf{S}_\mathsf{I}(1^\lambda,\textsf{DB}),\mathsf{R}_{\mathsf{I}}(1^\lambda) \big)$:] In this protocol, the sender $\mathsf{S}_\mathsf{I}$   has a database $\textsf{DB}=(M_1,\ldots,M_N)$ of $N$ messages, where $M_i \in \{0,1\}^{t}$ for each $i \in [N]$,
for some $t \in \mathsf{poly}(\lambda)$. It  interacts with the receiver $\mathsf{R}_\mathsf{I}$ as follows. \smallskip \smallskip
\begin{itemize}
\item[1.] Generate a key pair for the signature scheme of Section \ref{RMA-sec} in order to sign $Q=N$ messages of length $m_d = (n+t) \cdot \lceil \log q \rceil$ each.
This key pair consists of $SK_{sig}=\mathbf{T}_{\mathbf{A}} \in \ZZ^{m \times m}$ and
$${PK}_{sig}:=\big( \mathbf{A},
  \{\mathbf{A}_j \}_{j=0}^{\ell},   \mathbf{D}, \mathbf{u} \big),$$ where $\ell=\log N$ and $\mathbf{A},\mathbf{A}_0,\ldots,\mathbf{A}_{\ell} \in U(\Zq^{n \times m})$, $\mathbf{D} \in U(\Zq^{n \times m_d})$ with
	 $m = 2n \lceil \log q \rceil$, $m_d = (n+t) \lceil \log q \rceil$. The counter is initialized to $\tau=0$.
	\item[2.] Choose a  matrix $\mathbf{S} \sample \chi^{n \times t}$ that will serve as a secret key  for an $\LWE$-based encryption scheme.
	Then, define the  matrix $\mathbf{F} =H_{F}(\varepsilon) \in \Zq^{n \times m}$ and sample a matrix $\mathbf{E} \sample \chi^{m \times t  }$ to compute
		\begin{eqnarray} \label{PK-gen-app}
		 \mathbf{P} = \left[ \mathbf{p}_1 \mid \ldots \mid \mathbf{p}_t \right]  =  \mathbf{F}^T \cdot \mathbf{S}  + \mathbf{E} ~\in \Zq^{m \times t}
		\end{eqnarray}
		so that $(\mathbf{F},\mathbf{P}) \in \Zq^{n \times m} \times \Zq^{m  \times t }$  forms a public key for a $t$-bit variant of Regev's encryption scheme \cite{Reg05}
		 (or, equivalently,
		a set of $m$ encryptions of the all-zeroes $t$-bit string).
	\item[3.]
	Sample    vectors $\mathbf{a}_1,\ldots ,\mathbf{a}_N \sample
	 U(\Zq^n)$ and $\mathbf{x}_1,\ldots,\mathbf{x}_{N} \sample \chi^{t}$ to
	compute
	\begin{eqnarray} \label{init-db-app}
	 (\mathbf{a}_i,\mathbf{b}_i)= \bigl( \mathbf{a}_i, ~ \mathbf{S}^T \cdot \mathbf{a}_i + \mathbf{x}_i + M_i \cdot \lfloor q/2 \rfloor  \bigr) \in \Zq^n \times \Zq^{t} \qquad  \forall i \in [N]
	 \qquad
	\end{eqnarray}

\item[4.] For each $i=1$ to $N$, generate a signature $(\tau_i,\mathbf{v}_i ) \leftarrow \mathsf{Sign}(SK_{sig},\tau,\mathfrak{m}_i)$ on the message
 $\mathfrak{m}_i=\mathsf{vdec}_{n+t,q-1}(\mathbf{a}_i|\mathbf{b}_i) \in \{0,1\}^{m_d}$ obtained by decomposing $(\mathbf{a}_i^T | \mathbf{b}_i^T)^T \in \Zq^{n+t}$.
\item[5.] $\mathsf{S}_\mathsf{I}$ sends $\mathsf{R}_\mathsf{I}$ the initialization data
\begin{eqnarray} \label{init-data}
  R_0= \bigl(  PK_{sig} ,~(\mathbf{F},\mathbf{P}),~\{(\mathbf{a}_i,\mathbf{b}_i),(\tau_i,\mathbf{v}_i )\}_{i=1}^N , ~\pi_K  \bigr),
	\end{eqnarray}
 which
includes a NIZK argument of knowledge $\pi_K$ of   small-norm matrices $\mathbf{S} \in \ZZ^{n \times t}$ and $\mathbf{E} \in \chi^{m \times t}$ and
$t$-bit messages $\{M_i\}_{i=1}^N$
that are consistent with \eqref{PK-gen-app}-\eqref{init-db-app}. The argument $\pi_K$ is built by taking the following steps: \smallskip \smallskip \smallskip
\begin{itemize}
\item[a.] Define   $\mathbf{A}_{\textsf{DB}}=[\mathbf{a}_1 | \ldots | \mathbf{a}_N] \in \Zq^{n \times N}$, $\mathbf{B}_{\textsf{DB}}=[\mathbf{b}_1 | \ldots | \mathbf{b}_N] \in \Zq^{t \times N}$, $\mathbf{M}=[M_1 | \ldots | M_N]
\in \{0,1\}^{t \times N}$,
$\mathbf{X}=[\mathbf{x}_1 | \ldots | \mathbf{x}_N] \in \chi^{ t \times N}$
 and parse $\mathbf{S}$ and $\mathbf{E}$ as $\mathbf{S}=[\mathbf{s}_1 | \ldots | \mathbf{s}_t] \in \chi^{n \times t}$,
$\mathbf{E}=[\mathbf{e}_1 | \ldots | \mathbf{e}_t] \in \chi^{m \times t}$.
\item[b.] For each $j \in [t]$,   define  $\bar{M}_j \in \{0,1\}^N$ to be the $j$-th column  of  $\mathbf{M}^T = [ \bar{M}_1 | \ldots | \bar{M}_t ]$. Likewise,
let $\bar{\mathbf{b}}_j \in \Zq^N$ (resp. $\bar{\mathbf{x}}_j \in \chi^N$) be the $j$-th column of $\mathbf{B}_{\textsf{DB}}^T=[\bar{\mathbf{b}}_1 | \ldots | \bar{\mathbf{b}}_t ] \in \Zq^{N \times t}  $
(resp.  $\mathbf{X}^T=[\bar{\mathbf{x}}_1 | \ldots | \bar{\mathbf{x}}_t ]   $) and generate a signature of knowledge
of $\mathbf{s}_j \in \chi^n$, $\mathbf{e}_j \in \chi^m$, $\bar{\mathbf{x}}_j \in \chi^N$, $\bar{M}_j \in \{0,1\}^N$, for $j \in [t]$,  such that
\begin{eqnarray} \label{sender-proof-app}
  \left[ \begin{array}{c|c|c|c} ~ \mathbf{F}^T  ~ & ~ \mathbf{I}_m  ~ & ~  & ~ ~\\ \hline
      \rule{0pt}{2.5ex}~\mathbf{A}_{\textsf{DB}}^T  ~ & ~  ~ & ~ \mathbf{I}_N  ~ &  ~ \lfloor q/2 \rfloor \cdot \mathbf{I}_N  ~
     \end{array} \right]
     \cdot  \begin{bmatrix} \mathbf{s}_j \\ \hline \mathbf{e}_j \\ \hline \bar{\mathbf{x}}_j \\ \hline \rule{0pt}{2.5ex}  \bar{{M}}_j  \end{bmatrix}  = \begin{bmatrix}
\mathbf{p}_j \\ \hline
\bar{\mathbf{b}}_j
 \end{bmatrix}
\end{eqnarray}
Let the NIZK proof be  $\pi_K=(
\{\mathsf{Comm}_{K,j}\}_{j=1}^\varsigma,\mathsf{Chall}_K,\{\mathsf{Resp}_{K,j}\}_{j=1}^\varsigma)$,
where $\mathsf{Chall}_K = H_{\mathsf{FS}}\big( (\mathbf{F},\mathbf{P}, \mathbf{A}_{\textsf{DB}},  \mathbf{B}_{\textsf{DB}}),
\{ \mathsf{Comm}_{K,j}\}_{j=1}^\varsigma \big) \in \{1,2,3\}^\varsigma$.
\item[c.] If the proof of knowledge $\pi_K$ does not verify
  or if there exists $i \in [N]$ such that $(\tau_i,\mathbf{v}_i)$ is an invalid signature on
 $\mathsf{vdec}_{n+t,q-1}\big((\mathbf{a}_i^T|\mathbf{b}_i^T)^T \big)^T $, then $\mathsf{R}_\mathsf{I}$ aborts.
\end{itemize}
\item[6.] Finally $\mathsf{S}_\mathsf{I}$ defines $S_0= \big( (\mathbf{S},\mathbf{E}) ,(\mathbf{F},\mathbf{P}),PK_{sig}  \big)$, which it keeps to itself. \medskip \smallskip
\end{itemize}

\item[\textsf{Transfer}$\big(\mathsf{S}_\mathsf{T}(S_{i-1}),\mathsf{R}_{\mathsf{T}}(R_{i-1},\rho_i) \big)$:] At the $i$-th transfer, the receiver $\mathsf{R}_\mathsf{T}$ has state $R_{i-1}$ and
an index $\rho_i \in [1,N]$. It interacts as follows with the sender $\mathsf{S}_\mathsf{T}$ that has state $S_{i-1}$ in order to obtain $M_{\rho_i}$ from $\textsf{DB}$.  \smallskip \smallskip \smallskip
\begin{itemize}
\item[1.] $\mathsf{R}_\mathsf{T}$ samples vectors $\mathbf{e} \sample U(\{-1,0,1\}^m)$, $\mu \sample U(\{0,1\}^t)$ and a random $\nu \sample U([-B,B]^t)$ to compute
\begin{eqnarray} \label{rand-CT-app}
(\mathbf{c}_0,\mathbf{c}_1) = \big( \mathbf{a}_{\rho_i} + \mathbf{F} \cdot \mathbf{e} , ~\mathbf{b}_{\rho_i} + \mathbf{P}^T \cdot \mathbf{e} + \mu \cdot \lfloor q/2 \rfloor  + \nu \big) \in \Zq^n \times \Zq^t,
 \qquad
\end{eqnarray}
which is a re-randomization of $(\mathbf{a}_{\rho_i},\mathbf{b}_{\rho_i} + \mu \cdot \lfloor q/2 \rfloor  )$. The resulting ciphertext $(\mathbf{c}_0,\mathbf{c}_1)$ is sent to
$\mathsf{S}_\mathsf{T}$. In addition,  $\mathsf{R}_\mathsf{T}$ provides an interactive \textsf{WI} argument that   $(\mathbf{c}_0,\mathbf{c}_1)$ is indeed a re-randomization of $(\mathbf{a}_{\rho_i},\mathbf{b}_{\rho_i})$ for some index $\rho_i \in [N]$.
To this end, $\mathsf{R}_\mathsf{T}$ argues knowledge of short vectors $\mathfrak{m} = \mathsf{vdec}_{n+1,q-1}(\mathbf{a}_i| \mathbf{b}_i) \in \{0,1\}^{m_d}$, $\mathbf{e} \in \{-1,0,1\}^t$, $\mu \in \{0,1\}^t$,
$\nu \in [-B,B]^t$, $\tau \in \{0,1\}^{\ell}$ and $\mathbf{v} =(\mathbf{v}_1^T | \mathbf{v}_2^T)^T \in \ZZ^{2m}$ such that
\begin{eqnarray} \label{statement-rand-un-app}
 \left[ \begin{array}{cc|c|c|c}
\mathbf{H}_{n,q-1}  ~ &  ~  ~ & ~  \mathbf{F} ~& ~ &~      \\  \hline
&   ~\mathbf{H}_{t,q-1}~  & \rule{0pt}{2.5ex} ~\mathbf{P}^{T}~ & ~ \mathbf{I}_t  \cdot \lfloor q/2 \rfloor  ~ & ~\mathbf{I}_t~
 \end{array} \right] \cdot  \begin{bmatrix} \mathfrak{m}  \\  \hline \mathbf{e} \\ \hline  \mu  \\ \hline  \nu  \end{bmatrix} = \begin{bmatrix} \mathbf{c}_0 \\ \hline \mathbf{c}_1 \end{bmatrix}
\end{eqnarray}
and
\begin{eqnarray} \label{statement-rand-deux-app}
\left[ \begin{array}{c|c|c|c}
\mathbf{A}   ~ & ~ \mathbf{A}_0  ~& ~ \cdots ~ & ~ \mathbf{A}_\ell \end{array} \right] \cdot \begin{bmatrix} \mathbf{v}_1 \\ \hline \mathbf{v}_2 \\ \hline \rule{0pt}{2.5ex} \tau[1] \cdot \mathbf{v}_2 \\ \hline
\vdots \\ \hline \rule{0pt}{2.5ex} \tau[\ell] \cdot \mathbf{v}_2 \end{bmatrix} = \mathbf{u} + \mathbf{D} \cdot \mathfrak{m} ~\bmod q
\end{eqnarray}

\item[2.] If the \textsf{WI} argument of step 1 verifies, $\mathsf{S}_\mathsf{T}$ uses $\mathbf{S} \in \chi^{n \times t}$ to decrypt $(\mathbf{c}_0,\mathbf{c}_1) \in \Zq^n \times \Zq^t$ and
obtain $$M' = \lfloor (\mathbf{c}_1 - \mathbf{S}^T \cdot \mathbf{c}_0) / ( q/2 ) \rceil \in \{0,1\}^t,$$
which is sent back to $\mathsf{R}_\mathsf{T}$. In addition, $\mathsf{S}_\mathsf{T}$ provides a NIZK argument $\pi_T$ of knowledge of $\mathbf{y}= \mathbf{c}_1 - \mathbf{S}^T \cdot \mathbf{c}_0 - M' \cdot \lfloor q/2 \rfloor \in \ZZ^t$
of norm $\| \mathbf{y} \|_{\infty} \leq q/5$ and $\mathbf{E}=[\mathbf{e}_1|\ldots | \mathbf{e}_t] \in \chi^{m \times t}$ satisfying (modulo $q$)
\begin{eqnarray} \label{test-fin-trans}
\mathbf{P} &=& \mathbf{F}^T \cdot \mathbf{S} + \mathbf{E} ~  , \qquad \mathbf{c}_0^T \cdot \mathbf{S} + \mathbf{y}^T = \mathbf{c}_1^T - {M'}^T \cdot \lfloor q/2 \rfloor .
\end{eqnarray}
Given $\mathbf{y}=(\mathbf{y}[1],\ldots,\mathbf{y}[t])^T \in \ZZ^t$ and $\mathbf{S}=[\mathbf{s}_1| \ldots | \mathbf{s}_t]$,  this amounts to proving, for each $j \in [t]$,   knowledge
of $\mathbf{s}_j \in \chi^n$, $\mathbf{y}[j] \in \ZZ$ such that $|\mathbf{y}[j] | < q/4$ and  $\mathbf{e}_j \in \chi^m$,   such that
\begin{align} \label{sender-proof-two-app}
 \left[ \begin{array}{c|c|c}
 ~ \mathbf{F}^T  ~ & ~ \mathbf{I}_m  ~ & ~~   \\ \hline
 \rule{0pt}{2.5ex} \mathbf{c}_0^T ~ & & 1
\end{array} \right]
 \cdot  \begin{pmatrix} \mathbf{s}_j \\ \hline \mathbf{e}_j  \\ \hline \mathbf{y}[j]  \end{pmatrix}  &=
 \begin{pmatrix}
\mathbf{p}_j \\ \hline
\rule{0pt}{2.5ex} \mathbf{c}_1[j] - M'[j] \cdot \lfloor q/2 \rfloor
 \end{pmatrix} & \forall j \in [t],
\end{align}
where $\mathbf{c}_1=(\mathbf{c}_1[1],\ldots,\mathbf{c}_1[t])^T $ and $M' = (M'[1],\ldots,M'[t])^T$. Let the NIZK argument be  $\pi_T=(
\{\mathsf{Comm}_{T,j}\}_{j=1}^\varsigma,\mathsf{Chall}_T,\{\mathsf{Resp}_{T,j}\}_{j=1}^\varsigma)$,
where $\mathsf{Chall}_T = H_{\mathsf{FS}}\big( (\mathbf{F},\mathbf{P}, \mathbf{c}_0,  \mathbf{c}_{1}),
\{ \mathsf{Comm}_{T,j}\}_{j=1}^\varsigma \big) \in \{1,2,3\}^\varsigma$.
\item[3.] If th  argument $\pi_T$ produced by $\mathsf{S}_\mathsf{T}$ does not properly verify, $\mathsf{R}_\mathsf{T}$ halts and outputs $\perp$. Otherwise, $\mathsf{R}_\mathsf{T}$ recalls
the random string $\mu \in \{0,1\}^t$ that was chosen at step 1 and computes $M_{\rho_i}=M' \oplus  \mu$. The transfer ends with $\mathsf{S}_\mathsf{T}$ and $\mathsf{R}_\mathsf{T}$
outputting $S_i=S_{i-1}$ and $R_i=R_{i-1}$, respectively.
\end{itemize}
\end{description}

\subsection{Security}

For simplicity, our   proofs are given in the single-receiver setting but they readily carry over to the multi-receiver setting,
as defined in \cite[Appendix B]{GH11}.

\begin{theorem} \label{sender-sec-optimized}
The above $\OTA$ protocol provides receiver security under the $\SIS$ assumption in the random oracle model.
\end{theorem}

\begin{proof}
  We show how to map any real-world cheating sender $\hat{\mathsf{S}}$  to an ideal-world cheating sender $\hat{\mathsf{S}}'$ such that, under the $\SIS$ assumption,
  the  distributions $\REAL_{\hat{\mathsf{S}},{\mathsf{R}}}$ and $\IDEAL_{\hat{\mathsf{S}}',{\mathsf{R}}'}$ under common input $(N,k,M_1,\ldots,M_N,\rho_1,\ldots,\rho_k)$ are computationally indistinguishable.

  We consider a sequence of hybrid experiments with binary outputs.
  In each experiment $\textsf{Exp}_i$,  a distinguisher $\ddv$ inputs  the states $(S_k,R_k)$ produced by $\hat{\mathsf{S}}$ and $\mathsf{R}'$ at the end of $\textsf{Exp}_i$ and outputs a bit.
  We  define $W_i$ to be the event that the output of  $\textsf{Exp}_i$ is $1$.
  The first experiment outputs whatever the distinguisher $\ddv$ outputs and corresponds to the real interaction between the cheating sender $\hat{\mathsf{S}}$ and the
  receiver $\mathsf{R}$.
  \smallskip
  \begin{description}
    \item[\textsf{Exp}$_0$:]  This experiment  involves a real execution of $\hat{\mathsf{S}}$ in interaction with a honest receiver $\mathsf{R}$ which queries the index $\rho_i \in [N]$ at
      the $i$-th transfer for each $i \in [k]$. The output of  $\textsf{Exp}_0$
      is  exactly the output of the distinguisher $\ddv$ on input of $X=(S_k,R_k)  \leftarrow \REAL_{\mathsf{S},\hat{\mathsf{R}}} $, so that
      we have
      $$\Pr[W_0]=\Pr[    \ddv (X) =1 \mid X \leftarrow \REAL_{\hat{\mathsf{S}},{\mathsf{R}}} ].$$

    \item[\textsf{Exp}$_1$:]  This experiment is like $\textsf{Exp}_0$ except that  $\mathsf{R}'$ programs the random oracle $H_F : \{0,1\}^\ast \rightarrow \Zq^{n \times m}$ in the following way. It runs the trapdoor generation algorithm
      $(\mathbf{F},\mathbf{T}_{\mathbf{F}}) \leftarrow \mathsf{TrapGen}(1^n,1^m,q)$ of \cite{AP09} so as to obtain a statistically uniform matrix $\mathbf{F} \in \Zq^{n \times m}$ and a small-norm $\mathbf{T}_{\mathbf{F}} \in \ZZ^{m \times m}$ basis of $\Lambda_q^{\perp}(\mathbf{F})$. It then programs the
      random oracle so as to have $H_F(\varepsilon) = \mathbf{F} \in \Zq^{n \times m} $.  Clearly, this change leaves the adversary's view statistically
      unchanged: we have $| \Pr[W_1]-\Pr[W_0] | \in \mathsf{negl}(\lambda)$. \smallskip

    \item[\textsf{Exp}$_2$:]    is as $\textsf{Exp}_1$ but, at step 5 of the initialization phase, $\mathsf{R}'$ uses the short basis
      $\mathbf{T}_{\mathbf{F}} \in \ZZ^{m \times m}$ of $\Lambda_q^{\perp}(\mathbf{F})$ (which satisfies $\mathbf{F} \cdot \mathbf{T}_{\mathbf{F}} = \mathbf{0}^n \bmod q$)  to
      extract witnesses   $\mathbf{s}_j \in \chi^n$, $\mathbf{e}_j \in \chi^m$ from the columns $\mathbf{p}_j = \mathbf{F}^T \cdot \mathbf{s}_j + \mathbf{e}_j \in \ZZ^m$  of the
      matrix $\mathbf{P}= \left[\mathbf{p}_1 \mid \ldots \mid \mathbf{p}_t\right] \in \Zq^{m \times t}$
%and
% $\bar{\mathbf{x}}_j \in \chi^N$, $\bar{M}_j \in \{0,1\}^N$,
      for each $j \in [t]$. Note that this can be done by inverting the $\LWE$ function (see, e.g., \cite[Section 2.3]{GKV10}).
      At this point,
      $\mathsf{R}'$ aborts the interaction in the event that one of the following conditions holds: \smallskip
      \begin{itemize}
        \item[E.1:] The $\LWE$-inversion   algorithm
          fails to compute small-norm vectors  $\mathbf{s}_j \in \chi^n$, $\mathbf{e}_j \in \chi^m$ such that   $\mathbf{p}_j = \mathbf{F}^T \cdot \mathbf{s}_j + \mathbf{e}_j \in \Zq^m$ for some $j \in [t]$. %(which happens if $\mathbf{T}_{\mathbf{F}}^T  \cdot \mathbf{p}_j $ is not small)

        \item[E.2:]  The
          columns of $\mathbf{S} = \left [\mathbf{s}_1 \mid \ldots \mid \mathbf{s}_t \right] \in \chi^{n \times t}$ are successfully extracted but there exists $i \in [N]$ such that  one of the coordinates of
          $\mathbf{b}_i -  \mathbf{S}^T \cdot \mathbf{a}_i  \bmod q$ is neither close to $0$ nor $\lfloor q/2 \rfloor$ (i.e., the inequalities $  |\mathbf{b}_i -  \mathbf{S}^T \cdot \mathbf{a}_i  \bmod q | > \alpha q$ and $ |(\mathbf{b}_i -  \mathbf{S}^T \cdot \mathbf{a}_i  \bmod q) - \lfloor q/2 \rfloor |  > \alpha q $ are both satisfied). \smallskip
      \end{itemize}
      In either of the above situations, $\mathsf{R}'$  infers that  $\hat{\mathsf{S}}$ managed to create a convincing argument for a false statement and   aborts the interaction. In such a situation,  however, $\mathsf{R}'$ can be turned into an algorithm that breaks the binding property
      of the commitment scheme used in the ZK argument (which contradicts the $\SIS$ assumption if the statistically hiding commitment of \cite{KTX08}  is used) by replaying the adversary with the same random tape but a different random oracle $H_{\mathsf{FS}}$. According to the General Forking Lemma of \cite{BPVY00},
      replaying $\hat{\mathsf{S}}$ up to $32 \cdot Q_H / (\varepsilon - 3^{-t})$ times (where $Q_H$ is the  number of queries to $H_{\mathsf{FS}}$ is sufficient to extract
      a breach in the binding property of the commitment).
      Otherwise (i.e., if $\mathsf{R}'$ does not fail), the
      matrix $\mathbf{S}   \in \chi^{n \times t}$   allows
      $\mathsf{R}'$ to decode the messages $M_1,\ldots,M_N \in \{0,1\}^t$ from
      the encrypted database $\{(\mathbf{a}_i,\mathbf{b}_i)\}_{i=1}^N$.
      Under the
      $\SIS$ assumption, it follows that  $\textsf{Exp}_1$ returns $1$ with about the same probability as $\textsf{Exp}_0$. In the random oracle model, the $\SIS$
      assumption thus implies  that
      $ | \Pr[W_2] -\Pr[W_1] | \in \mathsf{negl} (\lambda). $ \smallskip


    \item[\textsf{Exp}$_3$:]  is identical to  \textsf{Exp}$_2$ except that  the    receiver $\mathsf{R}'$ makes use of the matrix $\mathbf{S} \in \chi^{n \times t}$, which   was extracted at step 5 of the initialization phase. At step 2 of each transfer, $\mathsf{R}'$ uses
      $\mathbf{S}$ to determine if the NIZK argument $\pi_T$ really  proves a true statement or if $\hat{\mathsf{S}}$ managed
      to break its  soundness. Namely, upon receiving $\hat{\mathsf{S}}$'s response $M ' \in \{0,1\}^t$  at step 2, $\mathsf{R}'$
      uses the previously extracted $\mathbf{S} \in \chi^{n \times t}$ to determine if there exists  $\mathbf{y} \in \ZZ^t$ of norm $\| \mathbf{y} \|_{\infty}
      \leq q/5$ such that
      \begin{eqnarray} \label{test-trois}
        \mathbf{c}_0^T \cdot \mathbf{S} + \mathbf{y}^T = \mathbf{c}_1^T - {M'}^T \cdot \lfloor q/2 \rfloor .
      \end{eqnarray}
      If  such vector $\mathbf{y}$ turns out not to exist, $\mathsf{R}'$ deduces $\mathsf{R}'$  that  $\hat{\mathsf{S}}$ was able to fake a convincing argument for a false statement and   aborts the interaction. However, $\mathsf{R}'$ can then be turned into a PPT adversary against the binding property
      of the commitment scheme used in the ZK argument (and thus the $\SIS$ assumption if the commitment of \cite{KTX08}  is used) by replaying the adversary  according to the General Forking technique  \cite{BPVY00}. The result of \cite{BPVY00} tells us that
      replaying $\hat{\mathsf{S}}$ up to $32 \cdot Q_H / (\varepsilon - 3^{-t})$ times (where $Q_H$ is the  number of queries to $H_{\mathsf{FS}}$)   suffices to break the binding property of the commitment.
      Under
      the $\SIS$ assumption, we  have $ | \Pr[W_3] -\Pr[W_2] | \in \mathbf{negl} (\lambda)  $.
      \smallskip

    \item[\textsf{Exp}$_4$:] This experiment is like $\textsf{Exp}_3$ with the difference that, at each transfer, the receiver $\mathsf{R}'$ chooses the index $\rho_i=1$ and thus always requests
      the first message of the encrypted database.  In more details, at each transfer, $\mathsf{R}'$
      samples vectors $\mathbf{e} \sample U(\{-1,0,1\}^m)$, $\mu \sample U(\{0,1\}^t)$ and  $\nu \sample U([-B,B]^t)$ to compute and send
      \begin{eqnarray*}
        (\mathbf{c}_0,\mathbf{c}_1) = \big( \mathbf{a}_{1} + \mathbf{F} \cdot \mathbf{e} , ~\mathbf{b}_{1} + \mathbf{P}^T \cdot \mathbf{e} + \mu \cdot \lfloor q/2 \rfloor  + \nu \big) \in \Zq^n \times \Zq^t,
      \end{eqnarray*}
      which is a re-randomization of $(\mathbf{a}_{1},\mathbf{b}_{1} + \mu \cdot \lfloor q/2 \rfloor   )$. Moreover,   $\mathsf{R}_\mathsf{T}'$ uses the witness $\rho_i=1$ to faithfully generate an interactive \textsf{WI} argument that
      $(\mathbf{c}_0,\mathbf{c}_1)$ is a re-randomization of $(\mathbf{a}_{\rho_i},\mathbf{b}_{\rho_i})$.
      It thus generates a \textsf{WI} argument of knowledge of vectors $\mathfrak{m} = \mathsf{vdec}_{n+t,q-1}(\mathbf{a}_1| \mathbf{b}_1) \in \{0,1\}^{m_d}$, $\mathbf{e} \in \{-1,0,1\}^t$, $\mu \in \{0,1\}^t$,
      $\nu \in [-B,B]^t$, $\tau \in \{0,1\}^{\ell}$ and $(\mathbf{v}_1^T | \mathbf{v}_2^T)^T \in \ZZ^{2m}$ satisfying relations~\eqref{eq:protocol-3-original}.
%(\ref{statement-rand-un})-(\ref{statement-rand-deux}).
      By the statistically \textsf{WI} of the interactive argument system, this modification has no noticeable impact on the output distribution of a cheating sender $\hat{\mathsf{S}}$ whatsoever.
      We have  $ | \Pr[W_4] -\Pr[W_3] | \in \mathsf{negl}(\lambda). $ \smallskip
  \end{description}
  In $\textsf{Exp}_4$, we  define the  ideal-world cheating sender $\hat{\mathsf{S}}'$ in the following way. It programs the random oracle $H_F : \{0,1\}^\ast
  \rightarrow \Zq^{n \times m}$ in such a way that $H_F(\varepsilon) =\mathbf{F} \in \Zq^{n \times m}$ for some statistically random
  matrix produced as $(\mathbf{F},\mathbf{T}_{\mathbf{F}}) \leftarrow \mathsf{TrapGen}(1^n,1^m,q)$.  At the initialization
  phase,  $\hat{\mathsf{S}}'$ uses the small-norm basis $\mathbf{T}_{\mathbf{F}}$ of $\Lambda_q^{\perp}(\mathbf{F})$ to  extract the small-norm matrices $\mathbf{S} = [\mathbf{s}_1|\ldots|\mathbf{s}_t] \in \chi^{n \times t}$
  and $\mathbf{E}=[\mathbf{e}_1| \ldots |\mathbf{e}_t] \in \chi^{m \times t}$  satisfying \eqref{PK-gen-app} and   decrypt $\{(\mathbf{a}_i,\mathbf{b}_i)\}_{i=1}^N$ into
  messages $M_1,\ldots,M_N \in \{0,1\}^N$. If the extraction fails because one of the events E.1 and E.2 (as defined in $\textsf{Exp}_2$) comes about,
  $\hat{\mathsf{S}}'$  aborts. Otherwise, it then submits  $M_1,\ldots,M_N \in \{0,1\}^N$ to the trusted party $\mathsf{TT}$. As in $\textsf{Exp}_2$, during each transfer phase,  $\hat{\mathsf{S}}'$ computes $(\mathbf{c}_0,\mathbf{c}_1)$ as
  a re-randomization of $(\mathbf{a}_1,\mathbf{b}_1) \in \Zq^n \times \Zq^t$ and faithfully generates the receiver's argument of knowledge using the witness $\rho_i=1$ at step 1.
  At step 2 of each transfer,  $\hat{\mathsf{S}}'$ aborts if it realizes that  $\hat{\mathsf{S}}$ created a convincing NIZK argument $\pi_T$ for a false statement. If $\pi_T$ correctly verifies and indeed relates to a true statement (which $\hat{\mathsf{S}}'$ can detect by applying the test \eqref{test-trois} using the matrix $\mathbf{S} \in \chi^{n \times t}$ extracted
  in the initialization phase),    $\hat{\mathsf{S}}'$ sends $1$ to the trusted party $\mathsf{TT}$ so as to authorize the transfer in the ideal world. Otherwise,  $\hat{\mathsf{S}}'$ sends $0$ to  $\mathsf{TT}$.
  At the end of the $k$-th transfer phase,  $\hat{\mathsf{S}}'$ outputs whatever  $\hat{\mathsf{S}}$ outputs as its final state $S_k$. \\
  \indent In $\textsf{Exp}_4$, it is easy to see that
  $$ \Pr[W_4] =  \Pr[    \ddv (X) =1 \mid X \leftarrow \IDEAL_{\hat{\mathsf{S}}',{\mathsf{R}}'} ] .$$
  Putting the above altogether, we find that the  $\SIS$ assumption implies   such that
  \begin{eqnarray*}
    |  \Pr[    \ddv (X) =1 \mid X \leftarrow \REAL_{\hat{\mathsf{S}},{\mathsf{R}}} ]   -  \Pr[    \ddv (X) =1 \mid X \leftarrow \IDEAL_{\hat{\mathsf{S}}',{\mathsf{R}}'} ] | \in \mathsf{negl}(\lambda) .
  \end{eqnarray*}
\end{proof}

The proof of security against a dishonest receiver is almost identical to the proof of Theorem \ref{rec-sec}.  The only difference is that, from
experience $\textsf{Exp}_3$ onwards,
the sender's ZK arguments are non-interactive and can be simulated by programming the random oracle $H_{\mathsf{FS}} : \{0,1\}^\ast
 \rightarrow \{1,2,3\}^{\varsigma}$ in the standard way.   The detailed proof of the following theorem is thus omitted.

\begin{theorem} \label{sender-sec-app}
The above $\OTA$ protocol provides sender security under the $\SIS$ assumption in the random oracle model.
\end{theorem}


As mentioned in \cite{GH11}, extending the simulation-based  definitions   to the multi-receiver setting is rather
straightforward (see \cite[Appendix B]{GH11} for details).  \\
\indent
 Analogously to the Green-Hohenberger protocol \cite[Section 4]{GH11},
our proof of sender security goes through in the multi-receiver setting as long as  the  receivers  interact with the
sender in a sequential manner. This restriction is important since
 the simulator has to rewind the receiver's zero-knowledge arguments at step 1 of each transfer, which would not be possible in concurrent sessions.


\section{Comparison of Oblivious Transfer Schemes} \label{sec-comp}

\begin{table}[h]
  \centering
  \scriptsize
  \begin{tabular}{|ccccc|}
    \hline
    Protocol & \begin{minipage}{\widthof{Initialization}}\vspace{3pt}\centering Initialization Cost \vspace{3pt}\end{minipage} & Transfer Cost & Assumptions & Security \\
    \hline \hline
    Folklore & $\cdot$ & $\bigO(\lambda N)$ & general & Full Sim \\ \hline
    %KN~\cite{KN06} & $\bigO(\lambda(N+U))$ & $\bigO(\lambda N)$ & Decisional $n$-th residuosity + DDH & Full Sim \\ \hline
    NP~\cite{NP99} & $\cdot$ & $\bigO(\lambda \cdot \log(N))$ & DDH + $\OT_1^2$ & Half Sim \\ \hline
    KPN~\cite{KPN10} & $\bigO(\lambda (N \cdot U))$ & $\bigO(\lambda)$ & DDH & Full Sim \\ \hline
    CNS~\cite{CNS07} & $\bigO(\lambda (N + U))$ & $\bigO(\lambda)$ & $q$-type & Full Sim \\
    GH08~\cite{GH08} & $\bigO(\lambda (N + U))$ & $\bigO(\lambda)$ & DLIN + $q$-type & UC \\
    JL~\cite{JL09} & $\bigO(\lambda (N + U))$ & $\bigO(\lambda)$ & Comp. Dec. Residuosity + $q$-type & Full Sim \\
    %RKP~\cite{RKP09} & $\bigO(\lambda (N + U))$ & $\bigO(\lambda)$ & DLIN + $q$-Hidden SDH + $q$-TDH & UC \\
    GH11~\cite{GH11} & $\bigO(\lambda (N+U))$ & $\bigO(\lambda)$ & Decision 3-Party DH & Full Sim \\ \hline
    GH11~\cite{GH11} & $\bigO(\lambda N)$ & $\bigO(\lambda)$ & 3-Party DDH + DLIN & Full Sim \\ \hline \hline
    Ours, §\ref{sec:def-OT} & $\bigO(\lambda (N \cdot U))$ & $\bigO(\lambda \cdot \log N)$ & LWE + SIS & Full Sim \\
    Ours, App \ref{optimized} & $\bigO(\lambda N)$ & $\bigO(\lambda \cdot \log N)$ & LWE + SIS & Full Sim  (ROM)\\ \hline
  \end{tabular}
  \medskip
  \caption[Comparison of the different adaptive OT protocols secure in the standard model]{Overview of the different adaptive OT (without access control) protocols secure in the standard model (except for our scheme in Section~\ref{optimized} of this Supplementary Material). In this table, $\lambda$ denotes the security parameter, $N$ the size of the database and $U$ the number of receivers. The horizontal lines separate the different schemes into categories based of their efficiency. We note that, like those of \cite{KPN11}, the KPN~\cite{KPN10} scheme is secure  in a strictly weaker model than ours. In particular, the sender detects if the same record is obtained twice, as pointed out in \cite{GH11}.
	%We also note that, while the proceedings version of \cite{KPN11} claims a construction based on $\LWE$, this claim was removed from the revised
	%ePrint version in August 2014.
	}
  \label{tab:comparison}
\end{table}


In this section, we present, in Tables~\ref{tab:comparison} and \ref{tab:AC-comparison}, comparisons between existing adaptive oblivious transfer protocols and ours. These results are to be taken carefully, as the existing schemes are mostly designed in the pairing-based cryptography setting.
The communication complexities thus take into account the number of underlying mathematical objects exchanged during each interactive protocols, which are group elements in the previous constructions, and vectors in our case.

Another remark is that the other schemes which support access control, shown in Table~\ref{tab:AC-comparison}, manage access policy in the fashion of Camenisch \textit{et al.}~\cite{CDN09}. In their work, they model the \textit{access policy} as access categories bounded to users (like their role, or their permission) which are delivered by the issuer. A given message in the database is made available for a \textit{conjunction} of access categories: meaning that to access a given file, a user has to be in \textit{all} the categories the message in linked to. To handle disjunctions, the file is duplicated. The number of messages in the database $N$ in these schemes is then dependent of the access policy, and a cost for duplications is to take into account, as the database has to prove that encryption of the same message with different access policy is indeed the encryption of the same message.

By handling access control through branching programs, we avoid the hidden cost of disjunctions, while enabling access control for attribute's language in $\mathsf{NC}1$.

\begin{table}[h]
  \centering
  \scriptsize
  \begin{tabular}{|ccccccc|}
    \hline
    Protocol & \begin{minipage}{\widthof{Initialization}}\centering\vspace{3pt} Initialization Cost\vspace{3pt}\end{minipage} & Transfer Cost & Assumptions & Policies & \begin{minipage}{\widthof{Policies}}Private Policies\end{minipage} & Security \\
    \hline \hline
    CDN~\cite{CDN09} &  $\bigO(\lambda \cdot N)$ & $\bigO(\lambda) \cdot \poly[\lambda]$ & $q$-type & Conj. & \nocross & Full Sim \\
    %ZAWHMCY~\cite{ZA+10} & $\bigO(\lambda N)$ & $\bigO(\lambda)$ & ABE & Full Sim \\
    CDNZ~\cite{CDNZ11} & $\bigO(\lambda \cdot N)$ & $\bigO(\lambda) \cdot \poly[\lambda]$ & $q$-type + XDDH & Conj. & \okcross &  Full Sim   \\
    ACDN~\cite{ACDN13} & $\bigO(\lambda \cdot N)$ & $\bigO(\lambda) \cdot \poly[\lambda]$ & DLIN + SXDH& Conj. & \nocross & UC \\ \hline
    ZAW+~\cite{ZAW+10} & $\bigO(\lambda \cdot N)$ & $\bigO(\lambda)$ & CP-ABE + $q$-type & $\mathsf{NC}1$ & \nocross  & Full-Sim \\ \hline
    CDEN~\cite{CDEN12} & $\bigO(\lambda \cdot N)$ & $\bigO(\lambda \log N) + \poly[\lambda]$ & CP-ABE + GGM & $\mbox{CNF}^{-}$ & \okcross & Full-Sim \\ \hline \hline
    Ours, §\ref{OT-AC-scheme} & $\bigO(\lambda \cdot N) $ & $\widetilde{\bigO}(\lambda \log N) + \poly[\lambda]$ & LWE + SIS & $\mathsf{NC}1$ & \nocross & Full Sim \\ \hline
\end{tabular}
\medskip
\caption[Comparison of the different adaptive OT-AC schemes secure in the standard model]{Overview of the different adaptive OT-AC protocols secure in the standard model. Here $N$ denotes the size of the database. The polynomial $\poly[\lambda]$ in transfer costs captures the expense of access policies. In CDEN, GGM stands for generic group model, and $\mbox{CNF}^{-}$ means a restricted version of conjunctive normal form formulas, namely a user has to possess \textit{all} attributes in its access credentials, and to do so, it is able to provides a disjunction of its accesses. Finally ``Conj.'' means ``Conjunctions'', meaning that the user has to possess all the credential for a given message, and disjunctions can be achieved at the expense of duplications of database entries.}
  \label{tab:AC-comparison}
\end{table}