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.

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

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 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.

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

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

$(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$.

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:

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:

\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.

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

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.

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 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.

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.

\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$.

\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 \times2m}$, 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

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

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)}}\neq0\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:

\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.

\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)}\}$.

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:

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

The signature scheme of Section~\ref{RMA-sec} is secure against Type II attacks if $\SIS_{n,m,q,\beta''}$ holds, with $\beta'' =\sqrt2(\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$.

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''$.

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)}$.

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}\\

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

with $h_{\tau^{(i)}}= h_0+\sum\tau^{(i)}[j]\cdot h_j \neq0$ 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:

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}.

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:

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

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}

is an integer vector of $\Lambda_q^\perp(\mathbf{A})$, with norm bounded by $\|\mathbf v' \|\leq\sqrt2(\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}

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

(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

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})$.

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).

$ 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

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

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$)

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}.

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

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

\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}

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

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$,

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$.