1451 lines
120 KiB
TeX
1451 lines
120 KiB
TeX
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
|
|
%\chapter{Lattice-Based Oblivious Transfer with Access Control} \label{ch:ac-ot}
|
|
%\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}
|
|
|
|
Kiayias, Tsiounis and Yung~\cite{KTY07} presented group encryption ($\mathsf{GE}$) as the encryption analogue of group signatures~\cite{CVH91}, which allow users to anonymously sign messages on behalf of an entire group they belong to.
|
|
While group signatures aim at hiding the source of some message within a crowd administered by some group manager, group encryption rather seeks to hide its destination within a group of legitimate receivers.
|
|
In both cases, a verifier should be convinced that the anonymous signer/receiver indeed belongs to a purported population.
|
|
In order to keep users accountable for their actions, an opening authority ($\mathsf{OA}$) is further empowered with some information allowing it to un-anonymize signatures/ciphertexts.
|
|
|
|
Kiayias, Tsiounis and Yung~\cite{KTY07} formalized $\mathsf{GE}$ schemes as a primitive allowing the sender to generate publicly verifiable guarantees that:
|
|
(1) The ciphertext is well-formed and intended for some registered group member who will be able to decrypt;
|
|
(2) the opening authority will be able identify the receiver if necessary; (3) The plaintext satisfies certain properties such as being a witness for some
|
|
public relation or the private key that underlies a given public key. In the model of Kiayias \textit{et al.}~\cite{KTY07}, the message secrecy and anonymity
|
|
properties are required to withstand active adversaries, which are granted access to decryption oracles in all security experiments.
|
|
|
|
As a natural application, group encryption allows a firewall to filter all incoming encrypted emails except those intended for some certified organization
|
|
member and the content of which is additionally guaranteed to satisfy certain requirements, like the absence of malware.
|
|
|
|
$\mathsf{GE}$~schemes are also motivated by natural privacy applications such as anonymous trusted third parties, key recovery mechanisms or oblivious retriever
|
|
storage systems. In optimistic protocols, $\mathsf{GE}$ allows verifiably encrypting messages to \emph{anonymous} trusted third parties which mostly remain off-line
|
|
and only come into play to sort out conflicts. In order to protect privacy-sensitive information such as users' citizenship, group encryption
|
|
makes it possible to hide the identity of users' preferred trusted third parties within a set of properly certified trustees.
|
|
|
|
In cloud storage services, $\mathsf{GE}$ enables privacy-preserving asynchronous transfers of encrypted datasets. Namely, it allows users to archive encrypted datasets
|
|
on remote servers while convincing those servers that the data is indeed intended for some anonymous certified client who paid a subscription to the storage
|
|
provider. Moreover, a judge should be able to identify the archive's recipient in case a misbehaving server is found guilty of hosting suspicious
|
|
transaction records or any other illegal content.
|
|
|
|
As pointed out by Kiayias \textit{et al.}~\cite{KTY07}, group encryption also implies a form of hierarchical group signatures~\cite{TW05}, where signatures can only be opened by a set of eligible trustees operating in a very specific manner determiner by the signer.
|
|
|
|
The design of numerous privacy-preserving cryptographic protocols crucially relies on zero-knowledge proofs~\cite{GMR85} to prove properties about encrypted or committed values so as to enforce honest behavior on behalf of participants or protect the privacy of users.
|
|
In the lattice settings, efficient zero-knowledge proofs are non-trivial to construct due to the limited amount of algebraic structure.
|
|
While natural methods of proving knowledge of secret keys \cite{MV03,Lyu08,KTX08,LNSW13} are available, they are only known to work for specific languages.
|
|
When it comes to proving circuit satisfiability, the best known methods are designed for the $\mathsf{LPN}$ setting~\cite{JKPT12} or take advantage of the extra structure available in the ring $\LWE$
|
|
setting~\cite{XXW13,BKLP15}.
|
|
Hence, these methods are not known to readily carry over to standard (i.e., non-ideal) lattices.
|
|
In the standard model, the problem
|
|
is even trickier as we do not have a lattice-based counterpart of Groth-Sahai proofs~\cite{GS08} and efficient non-interactive proof systems are only available
|
|
for specific problems~\cite{PV08}.
|
|
|
|
The difficulty of designing efficient zero-knowledge proofs for lattice-related languages makes it highly non-trivial to adapt privacy-preserving cryptographic
|
|
primitives in the lattice setting. In spite of these technical hurdles, a recent body of work successfully designed anonymity-enabling mechanisms like ring
|
|
signatures \cite{KTX08,ABB+13}, blind signatures \cite{Ruec10}, group signatures \cite{GKV10,LLLS13,LLNW14,BCK+14,NZZ15,LNW15,LLNW16}
|
|
or, more recently, signature schemes with companion zero-knowledge protocols~\cite{LLM+16}. A common feature of all these works is that the zero-knowledge
|
|
layer of the proposed protocols only deals with linear equations, where witnesses are only multiplied by public values.
|
|
|
|
In this chapter, motivated by the design of advanced privacy-preserving protocols in the lattice setting, we construct zero-knowledge arguments for non-linear
|
|
statements among witnesses consisting of vectors and matrices. For suitable parameters $q,n,m \in \ZZ$, we consider zero-knowledge argument systems whereby a
|
|
prover can demonstrate knowledge of secret matrices $\mathbf{X} \in \ZZ_q^{m \times n}$ and vectors $\mathbf{s} \in \ZZ_q^n$, $\mathbf{e} \in \ZZ^m$ such that:
|
|
(i) $\mathbf{e} \in \ZZ^m$ has small norm;
|
|
(ii) A public vector $\mathbf{b} \in \ZZ_q^n$ equals $\mathbf{b} = \mathbf{X}\cdot \mathbf{s} + \mathbf{e} \bmod q$;
|
|
(iii) The underlying pair $(\mathbf{X},\mathbf{s})$ satisfies additional algebraic relations: for instance, it should be possible to prove possession of a signature on some representation of the matrix $\mathbf{X}$.
|
|
In particular, our zero-knowledge argument makes it possible to prove that a given ciphertext is a well-formed $\LWE$-based encryption with respect to some
|
|
hidden, but certified public key. This protocol comes in handy in the design of \textit{group encryption} schemes~\cite{KTY07}, where such languages naturally
|
|
arise.
|
|
Using these advances, we thus construct, in this chapter, the first construction of group encryption under lattice assumptions.
|
|
|
|
\paragraph{Related work.}
|
|
Kiayias, Tsiounis and Yung (KTY) \cite{KTY07} formalized the notion of group encryption and provided a modular design using
|
|
zero-knowledge proofs, digital signatures, anonymous CCA-secure public-key encryption and commitment schemes. They also gave an efficient instantiation using
|
|
Paillier's cryptosystem~\cite{Pail99} and Camenisch-Lysyanskaya signatures \cite{CL02}.
|
|
|
|
Cathalo, Libert and Yung \cite{CLY09}
|
|
designed a non-interactive system in the standard model under non-interactive pairing-related assumptions. El~Aimani and Joye \cite{EJ13} suggested various
|
|
efficiency improvements with both interactive and non-interactive proofs.
|
|
|
|
Libert \textit{et al.}~\cite{LYJP14} empowered the $\GE$ primitive with a refined traceability mechanism akin to that of traceable signatures~\cite{KTY04}. Namely,
|
|
by releasing a user-specific trapdoor, the opening authority can allow anyone to publicly trace ciphertexts encrypted for this specific group member without
|
|
affecting the privacy of other users. Back in 2010, Izabachène, Pointcheval and Vergnaud~\cite{IPV10} considered the problem of eliminating subliminal
|
|
channels in a different form of traceable group encryption.
|
|
|
|
As a matter of fact, all existing realizations of group encryption or similar primitives rely on traditional number theoretic assumptions like the hardness of
|
|
factoring or computing discrete logarithms. In particular, all of them are vulnerable to quantum attacks. For the sake of not putting all one's eggs in the
|
|
same basket, it is highly desirable to have instantiations based on alternative, quantum-resistant foundations.
|
|
\bigskip
|
|
|
|
In the next sections, we first present the definitions of a group encryption schemes and the required building block.
|
|
Then, we describe the zero-knowledge protocol we use to handle these quadratic relations before finally describing our scheme.
|
|
|
|
\section{Syntax and Definitions of Group Encryption} \label{GE-model}
|
|
\index{Group Encryption}
|
|
|
|
We use the syntax and the security model of Kiayias, Tsiounis and Yung \cite{KTY07}.
|
|
The group encryption (\textsf{GE}) primitive involves a sender, a verifier, a group manager~(\textsf{GM}) that manages the group of receivers and an opening
|
|
authority~(\textsf{OA}) which is capable of identifying ciphertexts' recipients.
|
|
|
|
In the syntax of \cite{KTY07}, a $\mathsf{GE}$ scheme is specified by the description of a
|
|
relation $R$ as well as a tuple
|
|
$\mathsf{GE}=\bigl(\mathsf{SETUP},\mathsf{JOIN},\langle
|
|
\mathcal{G}_r,R,\mathsf{sample}_{R}
|
|
\rangle,\mathsf{ENC},\mathsf{DEC},\mathsf{OPEN},\langle
|
|
\mathcal{P},\mathcal{V} \rangle \bigr)$ of algorithms or protocols.
|
|
In details, $\mathsf{SETUP}$ is a set of initialization procedures that all take (implicitly or explicitly) a security parameter $1^\lambda$ as input. We call them
|
|
$\mathsf{SETUP}_{\mathsf{init}}(1^\lambda)$,
|
|
$\mathsf{SETUP}_{\mathsf{GM}}(\param)$ and
|
|
$\mathsf{SETUP}_{\mathsf{OA}}(\param)$. The first one of these procedures
|
|
generates a set of public parameters $\param$ (like the KTY construction \cite{KTY07}, we rely on a common reference string even when using interaction between
|
|
provers and verifiers). The latter two procedures are used to produce key pairs
|
|
$(\pk_{\GM},\sk_{\GM})$, $(\pk_{\OA},\sk_{\OA})$ for the $\GM$ and the
|
|
$\OA$. In the following, $\param$ is incorporated in the inputs of all algorithms although we sometimes omit to explicitly write it.
|
|
|
|
$\mathsf{JOIN}=(\mathsf{J}_{\mathsf{user}},\mathsf{J}_{\GM})$ is an interactive protocol between the $\GM$ and the prospective user.
|
|
After the execution of $\mathsf{JOIN}$, the $\GM$ stores the public key $\pk$ and its certificate $\crt_{\pk}$ in a public directory
|
|
$\mathsf{database}$.
|
|
As in \cite{KY05}, we will restrict this
|
|
protocol to have minimal interaction and consist of only two messages: the first one is the user's public key $\pk$ sent by $\mathsf{J}_{\mathsf{user}}$ to $\mathsf{J}_{\GM}$
|
|
and the latter's response is a certificate $\crt_{\pk}$ for $\pk$ that makes the user's group membership effective. We do not require the user to prove
|
|
knowledge of his private key $\sk$ or anything else about it. In our construction, valid keys will be publicly recognizable and users will not have to prove
|
|
their validity. By avoiding proofs of knowledge of private keys, the security proof never has to
|
|
rewind the adversary to extract those private keys, which allows supporting concurrent joins as
|
|
advocated by Kiayias and Yung \cite{KY05}. If applications demand it, it is possible to add
|
|
proofs of knowledge of private keys in a modular way but our security proofs do not require
|
|
rewinding the adversary in executions of $\mathsf{JOIN}$.
|
|
|
|
Algorithm $\mathsf{sample}_{R}$ allows sampling pairs $(x,w)\in R$ (made of a public value $x$ and a witness $w$) using keys $(\pk_{R},\sk_{R})$ produced by
|
|
$\mathcal{G}_r(1^\lambda)$ which samples public/secret parameters for the relation $R$. Depending on the relation, $\sk_{R}$ may be the empty string (as in the scheme \cite{KTY07} and ours which both involve publicly samplable relations). The testing procedure $R(x,w)$ uses $\pk_{R}$ to
|
|
return $1$ whenever $(x,w)\in R$. To encrypt a witness $w$ such that $(x,w) \in R$ for some public $x$, the sender fetches the pair $(\pk,\crt_{\pk})$
|
|
from $\mathsf{database}$ and runs the randomized encryption algorithm. The latter takes as input $w$, a label $L$, the receiver's pair $(\pk,\crt_{\pk})$ as
|
|
well as public keys $\pk_{\GM}$ and $\pk_{\OA}$. Its output is a ciphertext
|
|
$\Psi \gets \mathsf{ENC}(\pk_{\GM},\pk_{\OA},\pk,\crt_{\pk},w,L)$.
|
|
On input of the same elements, the certificate $\crt_{\pk}$, the ciphertext $\Psi$ and the random coins $coins_{\Psi}$ that were used to produce $\Psi$, the
|
|
non-interactive algorithm $\mathsf{PP}$ generates a proof $\pi_{\Psi}$ that there exists a certified receiver whose public key was registered in $\mathsf{database}$ and
|
|
who is able to decrypt $\Psi$ and obtain a witness $w$ such that $(x,w) \in R$. The verification algorithm $\mathcal{V}$ takes as input $\Psi$, $\pk_{\GM}$,
|
|
$\pk_{\OA}$, $\pi_{\Psi}$ and the description of $R$ and outputs $0$ or $1$. Given $\Psi$, $L$ and the receiver's private key $\sk$, the output of
|
|
$\mathsf{DEC}$ is either a witness $w$ such that $(x,w) \in R$ or a rejection symbol $\bot$. Finally,
|
|
$\mathsf{OPEN}$ takes as input a ciphertext/label pair $(\Psi,L)$ and the OA's secret key $\sk_{\OA}$ and returns a receiver's public key $\pk$.
|
|
|
|
The model of \cite{KTY07} considers four properties termed correctness, message security, anonymity and soundness.
|
|
In the security definitions, stateful oracles capture the adversary's
|
|
interaction with the system. In the soundness game, the KTY model requires
|
|
that pk belongs to the language of valid public keys. Here, we are implicitly assuming that the space
|
|
of valid public keys is dense (all matrices are valid keys, as is the case in our scheme).
|
|
|
|
In the upcoming definitions, we sometimes use the notation
|
|
\[ \langle \mathsf{output}_A |\mathsf{output}_B \rangle \allowbreak \gets \langle A(\mathsf{input}_A),B(\mathsf{input}_B) \rangle (\mathsf{common\textrm{-}input}) \]
|
|
to denote the execution of a protocol between $A$ and $B$ obtaining their own outputs from their respective inputs.
|
|
\medskip
|
|
|
|
\paragraph{Correctness.}
|
|
The correctness property
|
|
requires that the following experiment returns $1$ with overwhelming
|
|
probability.
|
|
|
|
\begin{center}
|
|
\procedure{Experiment $\Expt^{\mathrm{correctness}}(\lambda)$}{
|
|
\mathsf{param} \gets
|
|
\mathsf{SETUP}_{\mathsf{init}}(1^\lambda); (\pk_{R},\sk_{R})
|
|
\gets \mathcal{G}_r (\lambda); (x,w) \leftarrow \mathsf{sample}_{R}
|
|
(\pk_{R},\sk_{R}); \\
|
|
(\pk_{\GM},\sk_{\GM}) \leftarrow \mathsf{SETUP}_{\GM}(\mathsf{param}); (\pk_{\OA},\sk_{\OA}) \leftarrow \mathsf{SETUP}_{\OA}(\mathsf{param}); \\
|
|
\langle \pk,\sk,\crt_{\pk} | \pk,\crt_{\pk} \rangle \leftarrow \langle \mathsf{J}_{\mathsf{user}},\mathsf{J}_{\GM}(\sk_{\GM}) \rangle (\pk_{\GM}); \\
|
|
\Psi \leftarrow
|
|
\mathsf{ENC}(\pk_{\GM},\pk_{\OA},\pk,\crt_{\pk},w,L);\\
|
|
\pi_{\Psi} \leftarrow \mathcal{P}(\pk_{\GM},\pk_{\OA},\pk,\crt,w,L,\Psi,coins_{\Psi}); \\
|
|
\pcif \bigl( (w \neq \mathsf{DEC}(\sk,\Psi,L)) \vee ( \pk \neq
|
|
\mathsf{OPEN}(\sk_{\OA},\Psi,L )) \\ \quad \qquad \vee (\mathcal{V}(\Psi,L,\pi_{\Psi},\pk_{\GM},\pk_{\OA})=0)
|
|
\bigr) \pcthen\\
|
|
\pcind \pcreturn 0\\
|
|
\pcelse\\
|
|
\pcind \pcreturn 1;
|
|
}
|
|
\end{center}
|
|
|
|
\paragraph{Message Secrecy.}
|
|
The message secrecy property is defined by an experiment where the adversary has access to oracles
|
|
that may be stateful (and maintain a state across queries) or
|
|
stateless:
|
|
%These oracles are the following:
|
|
\begin{itemize}
|
|
\item[-] $\mathsf{DEC}(\sk)$: is a stateless oracle for the user decryption function
|
|
$\mathsf{DEC}$. When this oracle is restricted not to decrypt a
|
|
ciphertext-label pair $(\Psi,L)$, we denote it by
|
|
$\mathsf{DEC}^{\neg \langle \Psi, L \rangle}$.
|
|
\item[-] $\mathsf{CH}_{\mathsf{ror}}^b(\lambda,\pk,w,L)$: is a
|
|
real-or-random challenge oracle which is called \textit{once}. It
|
|
returns $(\Psi,coins_{\Psi})$ such that $\Psi \leftarrow
|
|
\mathsf{ENC}(\pk_{\GM},\pk_{\OA},\pk,\crt_{\pk},w,L)$ if $b=1$
|
|
whereas, if $b=0$, $\Psi \leftarrow
|
|
\mathsf{ENC}(\pk_{\GM},\pk_{\OA},\pk,\crt_{\pk},w',L)$ encrypts a
|
|
random plaintext of
|
|
length $O(\lambda)$ uniformly sampled in the plaintext space. In both cases, $coins_{\Psi}$ denote the random
|
|
coins used to generate $\Psi$.
|
|
\item[-]
|
|
$\mathsf{PROVE}_{\mathsf{PP},\mathsf{PP}'}^b(\pk_{\GM},\pk_{\OA},\pk,\crt_{\pk},\pk_{R},x,w,\Psi,L,coins_{\Psi})$:
|
|
is a stateful oracle that can be invoked a polynomial number times. If $b=1$, it replies by running the real prover $\mathsf{PP}$ on the inputs to
|
|
create an actual proof $\pi_{\Psi}$. If $b=0$, the oracle runs a
|
|
simulator $\mathsf{PP}'$ that uses the same inputs as $\mathsf{PP}$ except witness
|
|
$w,coins_{\Psi}$ and generates a simulated proof.
|
|
\end{itemize}
|
|
These oracles are used in an experiment where the adversary controls
|
|
the $\GM$, the $\OA$ and all members except the honest receiver. The
|
|
adversary $\adv$ embodies the dishonest $\GM$ that certifies the honest
|
|
receiver in an execution of $\mathsf{JOIN}$. It is granted access to an oracle $\mathsf{DEC}$ which decrypts on behalf of that receiver. In the
|
|
challenge phase, it transmits a state information $\mathsf{aux}$ to itself and invokes the challenge oracle for a label and a
|
|
pair $(x,w) \in R$ of its choice. After the challenge phase, it
|
|
can also query the $\mathsf{PROVE}$ oracle many times
|
|
and finally attempts to guess the challenger's bit $b$.
|
|
|
|
As pointed out in \cite{KTY07,CLY09}, designing an efficient
|
|
simulator $\mathsf{PP}'$ (for executing $\mathsf{PROVE}_{\mathsf{PP},\mathsf{PP}'}^b(.)$
|
|
when $b=0$) is part of the security proof.
|
|
\begin{definition} \label{security-def}
|
|
A $\mathsf{GE}$ scheme satisfies \textit{message security}
|
|
if, for any PPT adversary $\adv$, the experiment below returns $1$
|
|
with probability at most $1/2 + \mathsf{negl}(\lambda)$.
|
|
|
|
\begin{center}
|
|
\procedure{Experiment $\Expt_{\adv}^{\mathrm{sec}}(\lambda)$}{
|
|
\param \leftarrow \mathsf{SETUP}_{\mathsf{init}}(1^\lambda); (\mathsf{aux},\pk_{\GM},\pk_{\OA}) \leftarrow \adv(\param); \\
|
|
\langle \pk,\sk,\crt_{\pk} | \mathsf{aux} \rangle
|
|
\leftarrow \langle \mathsf{J}_{\mathsf{user}},\adv(\mathsf{aux}) \rangle
|
|
(\pk_{\GM}); \\
|
|
(\mathsf{aux},x,w,L,\pk_{R}) \leftarrow
|
|
\adv^{\mathsf{DEC}(\sk,.)}(\mathsf{aux});\\
|
|
\pcif (x,w) \not\in R \pcthen\\
|
|
\pcind\pcreturn 0;\\
|
|
b\sample \{0,1\}; ( \Psi,coins_{\Psi} ) \leftarrow \mathsf{CH}_{\mathsf{ror}}^b(\lambda,\pk,w,L) ; \\
|
|
b' \leftarrow
|
|
\adv^{\mathsf{PROVE}_{\mathsf{PP},\mathsf{PP}'}^b(\pk_{\GM},\pk_{\OA},\pk,\crt_{\pk},\pk_{R},x,w,\Psi,L,coins_{\Psi}),\mathsf{DEC}^{\neg
|
|
\langle \Psi, L \rangle}(\sk,.)}(\mathsf{aux},\Psi) ; \\
|
|
\pcif b=b' \pcthen\\ \pcind\pcreturn 1 \\\pcelse\\ \pcind \pcreturn 0;
|
|
}
|
|
\end{center}
|
|
\end{definition}
|
|
|
|
\paragraph{Anonymity.}
|
|
In the experiment modeling the anonymity property, the adversary
|
|
controls the entire system except the opening authority and two well-behaved users.
|
|
The challenger thus introduces two honest users' public keys $\pk_0,\pk_1$ in $\mathsf{database}$ and thus obtains certificate for both $\pk_0,\pk_1$ from the adversarially-controlled $\GM$.
|
|
For a pair $(x,w) \in R$ of its choice, the adversary obtains an encryption of $w$ under $\pk_b$ for some $b\in \bit$ chosen by the challenger.
|
|
The adversary is provided with decryption oracles w.r.t. both keys $\pk_0,\pk_1$. In addition, it has the following oracles at disposal:
|
|
\begin{itemize}
|
|
\item[-] $\mathsf{CH}_{\mathsf{anon}}^b(\pk_{\GM},\pk_{\OA},\pk_0,\pk_1,w,L)$: is a
|
|
challenge oracle that is only queried once by the adversary. It
|
|
returns a pair $(\Psi,coins_{\Psi})$ consisting of a ciphertext
|
|
$\Psi \leftarrow
|
|
\mathsf{ENC}(\pk_{\GM},\pk_{\OA},\pk_b,\crt_{\pk_b},w,L)$ and the
|
|
coin tosses $coins_{\Psi}$ that were used to generate $\Psi$.
|
|
\item[-]
|
|
$\mathsf{USER}(\pk_{\GM})$: is a stateful oracle that obtains certificates from the adversary by simulating two
|
|
executions of $\mathsf{J}_{\mathsf{user}}$ to introduce two honest users
|
|
in the group. It uses a string $\mathsf{keys}$ where the outputs $(\pk_0,\sk_0,\crt_{\pk_0})$, $(\pk_1,\sk_1,\crt_{\pk_1})$ of honest users
|
|
are written as long as the adversarially-supplied certificates $\{\crt_{\pk_d}\}_{d=0}^1$ are valid w.r.t. $\pk_{\GM}$ (i.e., invalid certificates are ignored
|
|
by the oracle and no entry is introduced in $\mathsf{keys}$ for them).
|
|
\item[-]
|
|
$\mathsf{OPEN}(\sk_{\OA},.)$: is a stateless oracle that simulates
|
|
the opening algorithm and, on input of a $\mathsf{GE}$
|
|
ciphertext, returns the receiver's public key.
|
|
\end{itemize}
|
|
|
|
The reason why
|
|
the $\mathsf{USER}$ oracle is needed is that both honest users' public keys $\pk_0, \pk_1$ must have been properly
|
|
certified by the adversarially-controlled $\mathsf{GM}$ before the challenge phase because the adversary subsequently obtains
|
|
proofs generated using $(\pk_b,\crt_{\pk_b})$.
|
|
|
|
\begin{definition} \label{anonymity-def}
|
|
A $\mathsf{GE}$ scheme satisfies \textit{anonymity} if, for any PPT adversary $\adv$, the experiment below returns $1$
|
|
with a probability not exceeding $1/2 + \mathsf{negl}(\lambda)$.
|
|
\begin{center}
|
|
\procedure{Experiment $\Expt_{\adv}^{\mathrm{anon}}(\lambda)$}{
|
|
\param \leftarrow
|
|
\mathsf{SETUP}_{\mathsf{init}}(1^\lambda); (\pk_{\OA},\sk_{\OA})
|
|
\leftarrow \mathsf{SETUP}_{\mathsf{OA}}( \param); \\
|
|
(\mathsf{aux},\pk_{\GM}) \leftarrow \adv(\param,\pk_{\OA});
|
|
\mathsf{aux} \leftarrow
|
|
\adv^{\mathsf{USER}(\pk_{\GM}),\mathsf{OPEN}(\sk_{\OA},.)}
|
|
(\mathsf{aux}) ; \\
|
|
\pcif \mathsf{keys} \neq (\pk_0,\sk_0,\crt_{\pk_0},\pk_1,\sk_1,\crt_{\pk_1})(\mathsf{aux}) \pcthen\\
|
|
\pcreturn 0;\\
|
|
(\mathsf{aux},x,w,L,\pk_{R}) \leftarrow
|
|
\adv^{\mathsf{OPEN}(\sk_{\OA},.),
|
|
\mathsf{DEC}(\sk_0,.),\mathsf{DEC}(\sk_1,.)}(\mathsf{aux}); \\
|
|
\pcif (x,w) \not\in R \pcthen\\
|
|
\pcind \pcreturn 0; \\
|
|
b\sample \{0,1\}; ( \Psi,coins_{\Psi} ) \leftarrow \mathsf{CH}_{\mathsf{anon}}^b(\pk_{\GM},\pk_{\OA},\pk_0,\pk_1,w,L) ; \\
|
|
b' \leftarrow
|
|
\adv^{\mathcal{P}(\pk_{\GM},\pk_{\OA},\pk_b,\crt_{\pk_b},x,w,\Psi,L,coins_{\Psi},}
|
|
\\ ^{\mathsf{OPEN}^{\neg \langle \Psi,L \rangle
|
|
}(\sk_{\OA},.),\mathsf{DEC}^{\neg \langle \Psi, L
|
|
\rangle}(\sk_0,.),\mathsf{DEC}^{\neg
|
|
\langle \Psi, L \rangle}(\sk_1,.))}(\mathsf{aux},\Psi) ; \\
|
|
\pcif b=b' \pcthen\\
|
|
\pcind \pcreturn 1\\
|
|
\pcelse\\
|
|
\pcind \pcreturn 0;
|
|
}
|
|
\end{center}
|
|
\end{definition}
|
|
|
|
\paragraph{Soundness.}
|
|
Here, the adversary creates the group of receivers by interacting with the honest GM.
|
|
Its goal is to produce a ciphertext $\Psi$ and a convincing proof
|
|
that $\Psi$ is valid w.r.t. a relation $R$ of its choice but
|
|
either: (1) The opening of $\Psi$ reveals a receiver's public key $\pk$ that
|
|
does not belong to any group member; (2) The output $\pk$ of
|
|
$\mathsf{OPEN}$ is not a valid public key (\textit{i.e.}, $\pk \not\in
|
|
\mathcal{PK}$, where $\mathcal{PK}$ is the language of valid public keys); (3) The ciphertext $C$ is not in the space
|
|
$\mathcal{C}^{x,L,\pk_{R},\pk_{\GM},\pk_{\OA},\pk}$ of valid
|
|
ciphertexts. This notion is formalized by a game where the adversary
|
|
is given access to a user registration oracle
|
|
$\mathsf{REG}(\sk_{\GM},.)$ that simulates $\mathsf{J}_{\GM}$. This oracle
|
|
maintains a list $\mathsf{database}$ where registered public keys and
|
|
their certificates are stored.
|
|
|
|
\begin{definition} \label{soundness-def}
|
|
A $\mathsf{GE}$ scheme is \textit{sound} if, for any PPT adversary $\adv$, the experiment below returns $1$
|
|
with negligible probability.
|
|
\begin{center}
|
|
\procedure{Experiment $\Expt_{\adv}^{\mathrm{soundness}}(\lambda)$}{
|
|
\param \leftarrow
|
|
\mathsf{SETUP}_{\mathsf{init}}(1^\lambda); (\pk_{\OA},\sk_{\OA})
|
|
\leftarrow \mathsf{SETUP}_{\OA}( \param); \\
|
|
(\pk_{\GM},\sk_{\GM}) \leftarrow \mathsf{SETUP}_{\GM}( \param); \\
|
|
(\pk_{R},x,\Psi,\pi_{\Psi},L,\mathsf{aux}) \leftarrow
|
|
\adv^{\mathsf{REG}(\sk_{\GM},.)}(\param,\pk_{\GM},\pk_{\OA},\sk_{\OA});
|
|
\\
|
|
\pcif \mathcal{V}( \Psi,L,\pi_{\Psi},\pk_{\GM},\pk_{\OA})=0 \pcthen\\
|
|
\pcind \pcreturn 0; \\
|
|
\pk \leftarrow \mathsf{OPEN}(\sk_{\OA},\Psi,L); \\
|
|
\pcif \big( (\pk \not\in \mathsf{database} ) \vee (\pk \not \in \mathcal{PK})
|
|
\vee (\Psi \not \in
|
|
\mathcal{C}^{x,L,\pk_{R},\pk_{\GM},\pk_{\OA},\pk}) \big)\pcthen\\
|
|
\pcind \pcreturn 1\\
|
|
\pcelse \\
|
|
\pcind \pcreturn 0;
|
|
}
|
|
\end{center}
|
|
\end{definition}
|
|
|
|
The model of Kiayias \textit{et al.} \cite{KTY07} requires
|
|
that $\pk$ belongs to the language of valid public keys, so that the adversary is considered to defeat the soundness property when
|
|
$(\Psi,L)$ opens to a key outside the language (i.e.,
|
|
$\pk \not \in \mathcal{PK}$). In our scheme, we will assume that the space
|
|
of valid public keys is dense in that all matrices of a given dimension are valid public keys, which have an underlying private key.
|
|
We nevertheless use the same definition as \cite{KTY07} in order to emphasize that we are not relaxing the model in any way.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
\section{Building Blocks}
|
|
|
|
|
|
|
|
|
|
\subsection{The Agrawal-Boneh-Boyen IBE Scheme} \label{ap:ABB-IBE}
|
|
\index{Identity-Based Encryption!Agrawal-Boneh-Boyen}
|
|
|
|
\subsubsection{Identity-Based Encryption.} \label{ap:IBE}
|
|
|
|
An IBE scheme is a tuple of efficient algorithms $(\mathsf{Setup}, \mathsf{Extract}_\mathsf{PP}, \mathsf{Encrypt}_\mathsf{PP},$ $\mathsf{Decrypt}_\mathsf{PP})$ such that
|
|
\begin{description}
|
|
\item[\textsf{Setup}$(1^\lambda)$:] On security parameter $\lambda$, this algorithm outputs public parameters $\mathsf{PP}$ and a master secret key $\textsf{msk}$.
|
|
\item[\textsf{Extract}$_\mathsf{PP}(\textsf{msk}, \ID)$:] Takes as input a master secret key $\textsf{msk}$ and an identity $\ID$ and outputs a secret key $\sk_\ID$.
|
|
\item[\textsf{Encrypt}$_\mathsf{PP}(\ID, M)$:] Given an identity $\ID$ and a message $M$, it outputs a ciphertext $C$.
|
|
\item[\textsf{Decrypt}$_\mathsf{PP}(\sk_\ID, C)$:] Given a secret key $\sk_\ID$ and a ciphertext $C$, outputs either a decryption error symbol $\bot$, or a message $M$.
|
|
\end{description}
|
|
|
|
Correctness requires that, for any pair $(\mathsf{PP}, \textsf{msk}) \gets \Setup(1^\lambda)$, any $\ID$ and any message $M$, we have
|
|
$\mathsf{Decrypt}_\mathsf{PP}\bigl(\textsf{Extract}_\mathsf{PP}(\textsf{msk}, \ID), \mathsf{Encrypt}_\mathsf{PP}(\ID, M)\bigr) = M.$
|
|
Our proofs rely on the semantic security of the scheme against selective adversaries (\textsf{IND-sID-CPA})
|
|
but also on the stronger property of ciphertext pseudo-randomness. %in Lemma~\ref{ABB-deux}.
|
|
Informally, this notions demands that the adversary be unable to distinguish an
|
|
encryption of a message of its choice from a random element of the ciphertext space $\mathcal{C}$. Notice that this property implies \textsf{IND-sID-CPA} security.
|
|
|
|
\begin{definition}
|
|
\label{de:pseudorand-cipher}
|
|
An IBE scheme has pseudo-random-ciphertexts if no PPT adversary $\adv$ with access to private key extraction oracle \textsf{Extract$_\mathsf{PP}(\textsf{msk}, \cdot)$} has non-negligible advantage
|
|
$ \advantage{\mathrm{ROR}}{\adv}{\lambda} = | \Pr\bigl[ \mathbf{Expt}_{\adv}^\mathrm{ROR} = 1 \bigr] - \frac 1 2 | $ in the game described in Figure~\ref{fig:expt-ror}
|
|
|
|
\begin{figure}
|
|
\centering
|
|
\procedure{Experiment $\Expt^{\mathrm{ROR}}_{\adv}(\lambda)$}{
|
|
\ID^\star \gets \adv(\textsf{id}, \lambda); (\mathsf{PP}, \textsf{msk}) \gets \mathsf{Setup}(1^\lambda);~\\
|
|
M \gets \adv^{\mathsf{Extract}_\mathsf{PP}(\textsf{msk}, \cdot)}_\textsf{Ch}(\mathsf{PP});\\
|
|
b \sample \U(\bit);\\
|
|
\pcif b = 1 \pcthen\\
|
|
\pcind C^\star \gets \mathsf{Encrypt}_\mathsf{PP}(M, \ID^\star) \\
|
|
\pcelse\\
|
|
\pcind C^\star \sample \U(\mathcal{C});\\
|
|
b' \gets \adv^{\mathsf{Extract}_\mathsf{PP}(\textsf{msk}, \cdot)}(\textsf{guess},C^\star);\\
|
|
\pcif b = b' \pcthen\\
|
|
\pcind \pcreturn 1\\
|
|
\pcelse \\
|
|
\pcind \pcreturn 0
|
|
}
|
|
\caption{Security experiment for the pseudo-random-ciphertext property for an IBE}
|
|
\label{fig:expt-ror}
|
|
\end{figure}
|
|
\end{definition}
|
|
|
|
|
|
\subsubsection{The ABB System.} \label{ap:ABB-desc}
|
|
|
|
Agrawal, Boneh and Boyen described~\cite{ABB10} a compact IBE scheme in the standard model which allows encrypting multi-bit messages.
|
|
%In
|
|
%the description hereunder, algorithms \textsf{Extract}, \textsf{Encrypt} and \textsf{Decrypt} have implicit access to the public param
|
|
%eters $\mathsf{PP}$ defined in the \textsf{Setup} algorithm.
|
|
|
|
\begin{description}
|
|
\item[\textsf{Setup}$(1^\lambda)$:] Given a security parameter $\lambda$, choose parameters
|
|
$q, n, \sigma, \alpha$ and define $k =\lfloor \log q \rfloor$, $\bar{m}= nk$, $m = 2 \bar{m}$ and choose a noise distribution $\chi$ for $\LWE$.
|
|
\begin{enumerate}
|
|
\item Compute $(\bar{\mathbf A}, \mathbf{T}_{\bar{\mathbf{A}}}) \gets \TrapGen(1^n, 1^m, q)$.
|
|
\item Define $\mathbf{G} = \mathbf{I}_n \otimes [1|2|\ldots |2^{k-1}] \in \ZZ_q^{n \times \bar{m}}$. Sample matrices $\mathbf B \sample \U(\ZZ_q^{ n \times \bar{m}}) $,
|
|
$ \mathbf U \sample \U(\Zq^{n \times m})$.
|
|
\item Let $\mathsf{FRD}: \Zq^n \to \Zq^{n \times n}$ be the full-rank difference mapping from~\cite{ABB10}.
|
|
\end{enumerate} Output
|
|
$
|
|
\mathsf{PP}= \bigl(\bar{\mathbf A}, \mathbf B, \mathbf U \bigr)$ and $\textsf{msk} = \mathbf{T}_{\bar{\mathbf A}}$.
|
|
|
|
\item[\textsf{Extract}$_\mathsf{PP}(\textsf{msk}, \ID)$:] Given $\textsf{msk} = \mathbf{T}_{\bar{\mathbf A}}$ and an identity $\ID \in \Zq^n$, do as follows: \smallskip
|
|
\begin{enumerate}
|
|
\item Define the matrix $\mathbf B_\ID = \mathbf B + \mathsf{FRD}(\ID) \cdot \mathbf G \in \Zq^{n \times \bar{m}}$.
|
|
%\item Use $\mathbf T_A$ to compute a delegated basis $\mathbf T_\ID$ for the dual lattice of the matrix $\mathbf B_{\mathbf A, \ID} = \left[ \mathbf A \mid \mathbf B_\ID \right]$.
|
|
\item Let $\mathbf B_{\mathbf A, \ID} = \left[ \mathbf A \mid \mathbf B_\ID \right] \in \ZZ_q^{n \times (m + \bar{m})}$, use $\mathbf T_A$ to compute a delegated basis $\mathbf T_\ID$ for the lattice $\Lambda^\perp(\mathbf B_{\mathbf A, \ID})$.
|
|
\item Use $\mathbf T_\ID$ to sample a small-norm matrix $\mathbf E_\ID \in \ZZ^{(m+ \bar{m}) \times m}$ satisfying the equality $\mathbf B_{\mathbf A, \ID} \cdot \mathbf E_\ID = \mathbf U \bmod q$.
|
|
\item Output $\sk_\ID = \mathbf E_\ID \in \ZZ^{(m+ \bar{m}) \times m}$. \smallskip \smallskip
|
|
\end{enumerate}
|
|
\item[\textsf{Encrypt}$_\mathsf{PP}(\ID,\mathbf m)$:] Given an identity $\ID$ and a message $\mathbf m \in \bit^m$, \smallskip
|
|
\begin{enumerate}
|
|
\item Compute the matrix $\mathbf B_\ID = \mathbf B + \mathsf{FRD}(\ID) \cdot \mathbf G \in \Zq^{n \times \bar{m}}$.
|
|
Sample vectors $\mathbf s \sample \U(\Zq^n), \mathbf x, \mathbf y \sample \chi^m$, $\mathbf R \sample D_{\ZZ,\sigma}^{m \times \bar{m}}$ and compute
|
|
$\mathbf z = \mathbf R^T \cdot \mathbf y \in \ZZ^m$.
|
|
\item Compute
|
|
\begin{equation} \label{eq:ABB-c}
|
|
\begin{cases}
|
|
\mathbf c^{(1)} = \bar{\mathbf A}^T \cdot \mathbf s + \mathbf y \bmod q,\\
|
|
\mathbf c^{(2)} = \mathbf B_\ID^T \cdot \mathbf s + \mathbf z \bmod q,\\
|
|
\mathbf c^{(3)} = \mathbf U^T \cdot \mathbf s + \mathbf x + \mathbf m \cdot \left\lfloor \dfrac{q}{2} \right\rfloor.
|
|
\end{cases}
|
|
\end{equation}
|
|
\item Output $\mathbf c = \bigl(\mathbf c^{(1)},\mathbf c^{(2)},\mathbf c^{(3)}\bigr) \in \ZZ_q^m \times \ZZ_q^{\bar{m}} \times \ZZ_q^m$. \smallskip \smallskip
|
|
\end{enumerate}
|
|
\item[\textsf{Decrypt}$_\mathsf{PP}(\sk_\ID, \mathbf c)$:] Given $\sk_\ID = \mathbf E_\ID$ and $\mathbf c=\bigl(\mathbf c^{(1)},\mathbf c^{(2)},\mathbf c^{(3)}\bigr) \in \ZZ_q^m \times \ZZ_q^{\bar{m}} \times \ZZ_q^m$, compute and output
|
|
% \begin{equation} \label{eq:ABB-dec}
|
|
$ \mathbf m' = \left\lfloor \left( \mathbf c^{(3)} - \mathbf E_\ID \cdot \begin{bmatrix} \mathbf c^{(1)} \\ \mathbf c^{(2)} \end{bmatrix} \right) \cdot \left\lfloor \dfrac{q}{2} \right\rfloor^{-1} \right\rceil \in \bit^m .$
|
|
% \end{equation}
|
|
\end{description}
|
|
\smallskip
|
|
|
|
|
|
|
|
\begin{theorem}[{\cite[Th. 23]{ABB10}}] \label{ABB-pseudorand-prop}
|
|
The ABB IBE scheme has pseudo-random ciphertexts if the $\LWE_{n,q,\chi}$ assumption holds.
|
|
\end{theorem}
|
|
|
|
\section{Warm-up: Decompositions, Extensions, Permutations}
|
|
\label{se:decomposition-extensions-permutations}
|
|
|
|
This section introduces the notations and techniques that will be used throughout the chapter. It details Stern-like protocols that have been introduced in~\cref{sse:stern}. The techniques that will be employed for handling quadratic relations (double-bit extension $\mathsf{ext}(\cdot, \cdot)$, expansion $\expandtimes(\cdot, \cdot)$ of matrix-vector product and the associated permuting mechanisms) are novel contributions.
|
|
\subsection{Decompositions}\label{subsection:decomposition}
|
|
For any $B \in \ZZ_+$, define the number $\delta_B:=\lfloor \log_2 B\rfloor +1 = \lceil \log_2(B+1)\rceil$ and the sequence $B_1, \ldots, B_{\delta_B}$, where $B_j = \lfloor\frac{B + 2^{j-1}}{2^j} \rfloor$, $\forall j \in [1,\delta_B]$. As observed in~\cite{LNSW13}, the sequence satisfies $\sum_{j=1}^{\delta_B} B_j = B$ and
|
|
any integer $v \in [0, B]$ can be decomposed into a binary vector $\mathsf{idec}_B(v) \hspace*{-1pt}= \hspace*{-1pt}(v^{(1)}, \ldots, v^{(\delta_B)})^T \hspace*{-2pt}\in \hspace*{-1pt}\{0,1\}^{\delta_B}$ such that $\sum_{j=1}^{\delta_B}B_j \cdot v^{(j)} \hspace*{-1pt}=\hspace*{-1pt} v$. We describe this decomposition procedure in a deterministic manner:
|
|
\begin{enumerate}
|
|
\item $v': = v$
|
|
\item For $j=1$ to $\delta_B$ do:
|
|
\begin{enumerate}[(i)]
|
|
\item If $v' \geq B_j$ then $v^{(j)}: = 1$, else $v^{(j)}: = 0$;
|
|
\item $v': = v' - B_j\cdot v^{(j)}$.
|
|
\end{enumerate}
|
|
\item Output $\mathsf{idec}_B(v) = (v^{(1)}, \ldots, v^{(\delta_B)})^T$.
|
|
\end{enumerate}
|
|
|
|
Next, for any positive integers $\mathfrak{m}, B$, we define the decomposition matrix:
|
|
\begin{eqnarray}
|
|
\mathbf{H}_{\mathfrak{m},B}: = \begin{bmatrix} B_1 \ldots B_{\delta_B} & & & & \\
|
|
& B_1 \ldots B_{\delta_B} & & & \\
|
|
& & & \ddots & \\
|
|
& & & & B_1 \ldots B_{\delta_B} \\
|
|
\end{bmatrix} \in \mathbb{Z}^{\mathfrak{m} \times \mathfrak{m}\delta_B},
|
|
\end{eqnarray}
|
|
and the following injective functions:
|
|
\begin{enumerate}[(i)]
|
|
\item $\mathsf{vdec}_{\mathfrak{m}, B}: [0,B]^{\mathfrak{m}} \rightarrow \{0,1\}^{\mathfrak{m}\delta_B}$ that maps vector $\mathbf{v} = (v_1, \ldots, v_{\mathfrak{m}})^T$ to vector $\big(\mathsf{idec}_B(v_1)^T \| \ldots \| \mathsf{idec}_B(v_{\mathfrak{m}})^T\big)^T$. Note that $\mathbf{H}_{\mathfrak{m}, B} \cdot \mathsf{vdec}_{\mathfrak{m}, B}(\mathbf{v}) = \mathbf{v}$. \smallskip
|
|
\item $\mathsf{vdec}'_{\mathfrak{m}, B}: [-B,B]^{\mathfrak{m}} \rightarrow \{-1,0,1\}^{\mathfrak{m}\delta_B}$ that maps vector
|
|
$\mathbf{w} = (w_1, \ldots, w_{\mathfrak{m}})^T$ to vector
|
|
$\big(\sigma(w_1)\cdot\mathsf{idec}_B(w_1)^T \| \ldots \| \sigma(w_{\mathfrak{m}})\cdot\mathsf{idec}_B(w_{\mathfrak{m}})^T\big)^T$, where for each $i=1, \ldots, \mathfrak{m}$: $\sigma(w_i) = 0$ if $w_i =0$; $\sigma(w_i) = -1$ if $w_i <0$; $\sigma(w_i) = 1$ if $w_i >0$. Note that $\mathbf{H}_{\mathfrak{m}, B} \cdot \mathsf{vdec}'_{\mathfrak{m}, B}(\mathbf{w}) = \mathbf{w}$.
|
|
\end{enumerate}
|
|
|
|
We also define the following matrix decomposition procedure. For positive integers $n,m,q$, define the injective function $\mathsf{mdec}_{n,m,q}: \mathbb{Z}_q^{m \times n} \rightarrow \{0,1\}^{mn\delta_{q-1}}$ that maps matrix $\mathbf{X} = [\mathbf{x}_1 | \ldots | \mathbf{x}_n] \in \mathbb{Z}_q^{m \times n}$, where $\mathbf{x}_1, \ldots, \mathbf{x}_n \in \mathbb{Z}_q^m$, to vector
|
|
\begin{align*}
|
|
\mathsf{mdec}_{n,m,q}(\mathbf{X}) &= \big(\mathsf{vdec}_{m, q-1}(\mathbf{x}_1)^T \| \ldots \|\ \mathsf{vdec}_{m,q-1}(\mathbf{x}_n)^T\big)^T \\
|
|
&= (x_{1,1}, \ldots, x_{1, mk}, x_{2,1}, \ldots, x_{2,mk}, \ldots, x_{n,1}, \ldots, x_{n,mk})^T \\
|
|
& \hspace{.6\textwidth}\in \{0,1\}^{nm \delta_{q-1}},
|
|
\end{align*}
|
|
where, for each $(i,j) \in [n] \times [m \delta_{q-1}]$, $x_{i,j} \in \{0,1\}$ denotes the $j$-th bit of the decomposition of the $i$-th column of $\mathbf{X}$. \\ \indent Looking ahead,
|
|
when proving
|
|
knowledge of witnesses $(\mathbf{X},\mathbf{s}) \in \ZZ_q^{m \times n} \times \ZZ_q^{n}$ satisfying $\mathbf{b} = \mathbf{X} \cdot \mathbf{s} + \mathbf{e} \bmod q$, we will have to consider terms of the form $x_{i,j} \cdot s_{i,t}$, where $\mathbf{s}=(s_1,\ldots,s_n)^T \in \ZZ_q^n$ and
|
|
$(s_{i,1},\ldots,s_{i,\delta_{q-1}})^T=\mathsf{idec}_{q-1}(s_i)$ for each
|
|
$i \in [n]$.
|
|
|
|
\subsection{Extensions and Permutations}\label{subsection:warm-up-ext-perm}
|
|
We now introduce the extensions and permutations which will be essential for proving quadratic relations.
|
|
\begin{itemize}
|
|
\item For each $c \in \{0,1\}$, denote by $\overline{c}$ the bit $1-c \in \{0,1\}$.
|
|
\item For $c_1,c_2 \in \{0,1\}$, define the vector $$\mathsf{ext}(c_1,c_2) = (\overline{c}_1\cdot \overline{c}_2, \overline{c}_1\cdot {c}_2, {c}_1\cdot \overline{c}_2, c_1\cdot c_2)^T \in \{0,1\}^4.$$
|
|
\item For $b_1,b_2 \in \{0,1\}$, define the permutation $T_{b_1,b_2}$ that transforms vector $\mathbf{v} = (v_{0,0}, v_{0,1}, v_{1,0}, v_{1,1})^T \in \mathbb{Z}_q^4$ to vector $(v_{{b}_1, {b}_2}, v_{{b}_1, \overline{b}_2}, v_{ \overline{b}_1,{b}_2}, v_{\overline{b}_1, \overline{b}_2})^T$.
|
|
|
|
Note that, for all $c_1, c_2, b_1, b_2 \in \{0,1\}$, we have the following:
|
|
\begin{eqnarray}
|
|
\mathbf{z} = \mathsf{ext}(c_1, c_2) \hspace*{5pt}\Longleftrightarrow \hspace*{5pt} T_{b_1, b_2}(\mathbf{z}) = \mathsf{ext}(c_1 \oplus b_1, c_2 \oplus b_2),
|
|
\end{eqnarray}
|
|
|
|
\end{itemize}
|
|
where $\oplus$ denotes the bit-wise addition modulo $2$.
|
|
|
|
Now, for positive integers $n,m,k$, and for vectors $$\mathbf{x} = (x_{1,1}, \ldots, x_{1, mk}, x_{2,1}, \ldots, x_{2,mk}, \ldots, x_{n,1}, x_{n,mk})^T \in \{0,1\}^{nmk}$$
|
|
and $\mathbf{s}_0 = (s_{1,1}, \ldots, s_{1,k}, s_{2,1}, \ldots, s_{2,k}, \ldots, s_{n,1}, \ldots, s_{n,k})^T \in \{0,1\}^{nk}$, we define the vector $ \expandtimes (\mathbf{x}, \mathbf{s}_0) \in \{0,1\}^{4nmk^2}$ as
|
|
\begin{align*}
|
|
\expandtimes (\mathbf{x}, \mathbf{s}_0) =
|
|
&\bigl( \mathsf{ext}^T(x_{1,1}, s_{1,1}) \| \mathsf{ext}^T(x_{1,1}, s_{1,2}) \| \ldots \| \mathsf{ext}^T(x_{1,1}, s_{1,k}) \| \\
|
|
&\| \mathsf{ext}^T(x_{1,2}, s_{1,1}) \| \mathsf{ext}^T(x_{1,2}, s_{1,2}) \| \ldots \| \mathsf{ext}^T(x_{1,2}, s_{1,k}) \| \ldots \\
|
|
&\| \mathsf{ext}^T(x_{1,mk}, s_{1,1}) \| \mathsf{ext}^T(x_{1,mk}, s_{1,2}) \| \ldots \| \mathsf{ext}^T(x_{1,mk}, s_{1,k}) \| \\
|
|
&\| \mathsf{ext}^T(x_{2,1}, s_{2,1}) \| \mathsf{ext}^T(x_{2,1}, s_{2,2}) \| \ldots \| \mathsf{ext}^T(x_{2,1}, s_{2,k}) \| \ldots \\
|
|
&\| \mathsf{ext}^T(x_{2,mk}, s_{2,1}) \| \mathsf{ext}^T(x_{2,mk}, s_{2,2}) \| \ldots \| \mathsf{ext}^T(x_{2,mk}, s_{2,k}) \| \ldots \\
|
|
&\| \mathsf{ext}^T(x_{n,1}, s_{n,1}) \| \mathsf{ext}^T(x_{n,1}, s_{n,2}) \| \ldots \| \mathsf{ext}^T(x_{n,1}, s_{n,k}) \| \ldots \\
|
|
&\| \mathsf{ext}^T(x_{n,mk}, s_{n,1}) \| \mathsf{ext}^T(x_{n,mk}, s_{n,2}) \| \ldots \| \mathsf{ext}^T(x_{n,mk}, s_{n,k})
|
|
\bigr)^T\hspace*{-2.5pt}.
|
|
\end{align*}
|
|
That is, $ \expandtimes (\mathbf{x}, \mathbf{s}_0)$ is obtained by applying $\mathsf{ext}$ to all pairs of the form $(x_{i,j},s_{i,t})$ for $(i,j,t) \in [n] \times [mk] \times [k]$.
|
|
|
|
|
|
Now, for $\mathbf{b} = (b_{1,1}, \ldots, b_{1, mk}, b_{2,1}, \ldots, b_{2,mk}, \ldots, b_{n,1}, b_{n,mk})^T \in \{0,1\}^{nmk}$ and $\mathbf{d} = (d_{1,1}, \ldots, d_{1,k}, d_{2,1}, \ldots, d_{2,k}, \ldots, d_{n,1}, \ldots, d_{n,k})^T \in \{0,1\}^{nk}$, we define the permutation $P_{\mathbf{b}, \mathbf{d}}$ that transforms
|
|
vector
|
|
\begin{align*}
|
|
\mathbf{v} = &\big( (\mathbf{v}_{1,1,1}^T \| \ldots \| \mathbf{v}_{1,1, k}^T ) \| ( \mathbf{v}_{1,2,1}^T \| \ldots \| \mathbf{v}_{1,2,k}^T ) \| \ldots \| ( \mathbf{v}_{1,mk,1}^T \| \ldots \| \mathbf{v}_{1,mk,k}^T ) \| \\
|
|
&~ (\mathbf{v}_{2,1,1}^T \| \ldots \| \mathbf{v}_{2,1, k}^T ) \| (\mathbf{v}_{2,2,1}^T \| \ldots \| \mathbf{v}_{2,2,k}^T ) \| \ldots \| ( \mathbf{v}_{2,mk,1}^T \| \ldots \| \mathbf{v}_{2,mk,k}^T ) \| \\
|
|
&~ \hspace*{-25pt} (\mathbf{v}_{n,1,1}^T \| \ldots \| \mathbf{v}_{n,1, k}^T ) \| ( \mathbf{v}_{n,2,1}^T \| \ldots \| \mathbf{v}_{n,2,k}^T ) \| \ldots \| ( \mathbf{v}_{n,mk,1}^T \| \ldots \| \mathbf{v}_{n,mk,k}^T )
|
|
\big)^T \hspace*{-3.5pt}\in \hspace*{-1.5pt}\mathbb{Z}^{4nmk^2},
|
|
\end{align*}
|
|
consisting of $nmk^2$ blocks of length $4$, to the vector $P_{\mathbf{b}, \mathbf{d}}(\mathbf{v})$ of the form
|
|
\begin{align*}
|
|
\big(~& (\mathbf{w}_{1,1,1}^T \| \ldots \| \mathbf{w}_{1,1, k}^T ) \| ( \mathbf{w}_{1,2,1}^T \| \ldots \| \mathbf{w}_{1,2,k}^T ) \| \ldots \| ( \mathbf{w}_{1,mk,1}^T \| \ldots \| \mathbf{w}_{1,mk,k}^T ) \| \\
|
|
& ( \mathbf{w}_{2,1,1}^T \| \ldots \| \mathbf{w}_{2,1, k}^T ) \| ( \mathbf{w}_{2,2,1}^T \| \ldots \| \mathbf{w}_{2,2,k}^T ) \| \ldots \| ( \mathbf{w}_{2,mk,1}^T \| \ldots \| \mathbf{w}_{2,mk,k}^T ) \| \\
|
|
& (\mathbf{w}_{n,1,1}^T \| \ldots \| \mathbf{w}_{n,1, k}^T ) \| (\mathbf{w}_{n,2,1}^T \| \ldots \| \mathbf{w}_{n,2,k}^T ) \| \ldots \| (\mathbf{w}_{n,mk,1}^T \| \ldots \| \mathbf{w}_{n,mk,k}^T )
|
|
~ \big)^T,
|
|
\end{align*}
|
|
where for each $(i,j,t) \in [n]\times [mk] \times [k]$: \hspace*{2.5pt}$\mathbf{w}_{i,j,t} = T_{b_{i,j}, d_{i,t}}(\mathbf{v}_{i,j,t})$.
|
|
\smallskip
|
|
|
|
Observe that, for all $\mathbf{b} \in \{0,1\}^{nmk}, \mathbf{d} \in \{0,1\}^{nk}$, we have:
|
|
\begin{eqnarray}\label{eq:expand-permuting}
|
|
\mathbf{z} = \expandtimes (\mathbf{x}, \mathbf{s}_0) \hspace*{5pt}\Longleftrightarrow \hspace*{5pt} P_{\mathbf{b},\mathbf{d}}(\mathbf{z}) = \expandtimes (\mathbf{x} \oplus \mathbf{b}, \mathbf{s}_0 \oplus \mathbf{d}).
|
|
\end{eqnarray}
|
|
\smallskip
|
|
|
|
\noindent
|
|
Next, we recall the notations, extensions and permutations used in previous Stern-like protocols~\cite{LNSW13,LNW15,ELL+15,LLM+16} for proving linear relations.
|
|
|
|
For any positive integer $t$, denote by $\permutations_t$ the symmetric group of all permutations of~$t$ elements, by $\mathsf{B}_{2t}$ the set of all vectors in $\{0,1\}^{2t}$ having Hamming weight~$t$, and by $\mathsf{B}_{3t}$ the set of all vectors in $\{-1,0,1\}^{3t}$ having exactly $t$ coordinates equal to $j$, for each $j \in \{-1,0,1\}$.
|
|
Note that for any $\phi \in \permutations_{2t}$ and $\psi\in \permutations_{3t}$, we have the following equivalences:
|
|
\begin{eqnarray}\label{eq:permuting-B_2t_B_3t}
|
|
\mathbf{x} \in \mathsf{B}_{2t} \Longleftrightarrow \phi(\mathbf{x}) \in \mathsf{B}_{2t} \hspace*{7.5pt}\text{ and }\hspace*{7.5pt} \mathbf{y} \in \mathsf{B}_{3t} \Longleftrightarrow \psi(\mathbf{y}) \in \mathsf{B}_{3t}.
|
|
\end{eqnarray}
|
|
The following extending procedures are defined for any positive integers $t$.
|
|
\begin{itemize}
|
|
\item $\mathsf{ExtendTwo}_t: \{0,1\}^{t} \rightarrow \mathsf{B}_{2t}$. On input vector $\mathbf{x}$ with Hamming weight $w$, it outputs
|
|
\[\mathbf{x}' = (\mathbf{x}^T \| \mathbf{1}^{t-w} \| \mathbf{0}^{w})^T. \]
|
|
\item $\mathsf{ExtendThree}_t: \{-1,0,1\}^{t} \rightarrow \mathsf{B}_{3t}$. On input vector $\mathbf{y}$ containing $n_j$ coordinates equal to $j$ for $j \in \{-1,0,1\}$, this procedure outputs the vector
|
|
\[\mathbf{y}' = (\mathbf{y}^T \| \mathbf{1}^{t-n_1}
|
|
\| \mathbf{0}^{t-n_0} \| \mathbf{(-1)}^{t-n_{-1}}).\]
|
|
\end{itemize}
|
|
We also use the following encoding and permutation to achieve fine-grained control over coordinates of binary witness-vectors.
|
|
\begin{itemize}
|
|
\item For any positive integer $t$, define the function $\mathsf{encode}_t$ that encodes vector $\mathbf{x} = (x_1, \ldots, x_t)^T\in \{0,1\}^t$ to vector $\mathsf{encode}_t(\mathbf{x}) = (\bar{x}_1, x_1, \ldots, \bar{x}_t, x_t)^T \in \{0,1\}^{2t}$.
|
|
\item For any positive integer $t$ and any vector $\mathbf{c} = (c_1, \ldots, c_t)^T \in \{0,1\}^t$, define the permutation $F_{\mathbf{c}}^{(t)}$ that transforms vector $\mathbf{v} = (v_1^{(0)}, v_1^{(1)}, \ldots, v_t^{(0)}, v_t^{(1)})^T \in \ZZ^{2t}$ into vector $F_{\mathbf{c}}^{(t)}(\mathbf{v}) = (v_1^{(c_1)}, v_1^{(\bar{c}_1)}, \ldots, v_t^{(c_t)}, v_t^{(\bar{c}_t)})^T$.
|
|
\end{itemize}
|
|
Note that the following equivalence holds for all $t, \mathbf{c}$:
|
|
\begin{eqnarray}\label{eq:equivalence-encoding}
|
|
\mathbf{y} = \mathsf{encode}_t(\mathbf{x}) \hspace*{7.5pt}\Longleftrightarrow \hspace*{7.5pt} F_{\mathbf{c}}^{(t)}(\mathbf{y}) = \mathsf{encode}_t(\mathbf{x} \oplus \mathbf{c}).
|
|
\end{eqnarray}
|
|
|
|
To close this warm-up section, we remark that the equivalences observed in~\eqref{eq:expand-permuting}, \eqref{eq:permuting-B_2t_B_3t} and~\eqref{eq:equivalence-encoding} will play crucial roles in our zero-knowledge layer.
|
|
|
|
\section{The Supporting Zero-Knowledge Layer} \label{groupenc-zk-layer}
|
|
|
|
In this section, we first demonstrate how to prove in zero-knowledge that a given vector $\mathbf{b}$ is a correct \textsf{LWE} evaluation, i.e., $\mathbf{b} = \mathbf{X}\cdot \mathbf{s} + \mathbf{e} \bmod q$, where the hidden matrix $\mathbf{X}$ and vector $\mathbf{s}$ may satisfy additional conditions.
|
|
|
|
This sub-protocol, which we believe will have other applications, is one of the major challenges in our road towards the design of lattice-based group encryption. We then plug this building block into the big picture as described in~\cref{sse:stern}, and construct the supporting zero-knowledge argument of knowledge (\textsf{ZKAoK}) for our group encryption scheme (Section~\ref{groupenc-scheme}).
|
|
|
|
\subsection{Proving the LWE Relation With Hidden Matrices}\label{subsection:quadratic-relation}
|
|
Let $n,m,q, \beta$ be positive integers where $\beta \ll q$, and let $k = \delta_{q-1}= \lceil \log_2 q\rceil$. We identify $\Zq$ as the set $\{0,1, \ldots, q-1\}$.
|
|
We consider a zero-knowledge argument system allowing prover $\mathcal{P}$ to convince verifier $\mathcal{V}$ on input $\mathbf{b} \in \Zq^m$ that $\mathcal{P}$ knows secret matrix $\mathbf{X} \in \Zq^{m \times n}$, and vectors $\mathbf{s} \in \Zq^n$, $\mathbf{e} \in [-\beta, \beta]^m$ such that:
|
|
\begin{eqnarray}\label{eq:quadratic-LWE-original}
|
|
\mathbf{b} = \mathbf{X}\cdot \mathbf{s} + \mathbf{e} \bmod q.
|
|
\end{eqnarray}
|
|
Moreover, the argument system should be readily extended to proving that $\mathbf{X}$ and $\mathbf{s}$ satisfy additional conditions, such as:
|
|
\begin{itemize}
|
|
\item The bits representing $\mathbf{X}$ are certified by an authority, and the prover also knows that secret signature-certificate.
|
|
\item The (secret) hash of $\mathbf{X}$ is correctly encrypted to a given ciphertext.
|
|
\item The \textsf{LWE} secret $\mathbf{s}$ is involved in other linear equations.
|
|
\end{itemize}
|
|
|
|
Let $q_1, \ldots, q_k \in \Zq$ be the sequence of integers obtained by decomposing $q-1$ using the technique recalled in
|
|
Section \ref{subsection:decomposition}, and define the row vector $\mathbf{g} = (q_1, \ldots, q_k)$.
|
|
Let $\mathbf{X} = [\mathbf{x}_1 | \ldots | \mathbf{x}_n] \in \Zq^{m \times n}$ and $\mathbf{s}= (s_1, \ldots, s_n)^T$.
|
|
For each index $i \in [n]$, let us consider $\mathsf{vdec}_{m,q-1}(\mathbf{x}_i) = (x_{i,1}, \ldots, x_{i,mk})^T \in \{0,1\}^{mk}$.
|
|
Let
|
|
\[ \mathsf{vdec}_{n,q-1}(\mathbf{s})= (s_{1,1}, \ldots, s_{1,k}, s_{2,1}, \ldots, s_{2,k}, \ldots, s_{n,1}, \ldots s_{n,k})^T \in \{0,1\}^{nk} \]
|
|
and observe that $s_i = \mathbf{g} \cdot \mathsf{idec}_{q-1}(s_i)= \mathbf{g}\cdot (s_{i,1}, \ldots, s_{i,k})^T$ for each $i \in [n]$.
|
|
We have:
|
|
\begin{eqnarray*}
|
|
\mathbf{X}\cdot \mathbf{s} &=& \sum_{i=1}^n \mathbf{x}_i\cdot s_i = \sum_{i=1}^n \mathbf{H}_{m,q-1}\cdot \mathsf{vdec}_{m,q-1}(\mathbf{x}_i)\cdot s_i \\
|
|
&=& \mathbf{H}_{m,q-1}\cdot \Big(\sum_{i=1}^n (x_{i,1}\cdot s_i, \ldots, x_{i,mk}\cdot s_i)^T\Big) \bmod q.
|
|
\end{eqnarray*}
|
|
Observe that, for each $i \in [n]$ and each $j \in [mk]$, we have
|
|
\begin{align*}
|
|
x_{i,j}\cdot s_i &= x_{i,j}\cdot \mathbf{g} \cdot (s_{i,1}, \ldots, s_{i,k})^T \\
|
|
&= (q_1, \ldots, q_k) \cdot (x_{i,j}\cdot s_{i,1}, \ldots, x_{i,j}\cdot s_{i,k})^T.
|
|
\end{align*}
|
|
We now extend vector $(q_1, q_2, \ldots, q_k)$ to $\mathbf{g}' \hspace*{-1.5pt}=\hspace*{-1.5pt} (0,0,0,q_1, 0,0,0, q_2, \ldots, 0,0,0,q_k) \in \Zq^{4k}$.
|
|
For all $(i,j) \in [n]\times [mk]$, we have:
|
|
$$
|
|
x_{i,j}\cdot s_i = \mathbf{g}' \cdot (\mathsf{ext}^T(x_{i,j}, s_{i,1}) \| \ldots \| \mathsf{ext}^T(x_{i,j},s_{i,k}))^T.
|
|
$$
|
|
Let us define the matrices
|
|
\begin{eqnarray} \label{Q0-def}
|
|
\mathbf{Q}_0: = \mathbf{I}_{mk}\otimes \mathbf{g}' = \begin{bmatrix} \mathbf{g}' & & & & \\
|
|
& \mathbf{g}' & & & \\
|
|
& & & \ddots & \\
|
|
& & & & \mathbf{g}' \\
|
|
\end{bmatrix} \in \Zq^{mk \times 4mk^2},
|
|
\end{eqnarray}
|
|
and $\widehat{\mathbf{Q}} = [\overbrace{\mathbf{Q}_0 | \ldots | \mathbf{Q}_0}^{n \text{ times }}] \in \Zq^{mk \times 4nmk^2}$. For each $i \in [n]$, define
|
|
\begin{align*}
|
|
\mathbf{y}_i = \bigl( &\mathsf{ext}^T(x_{i,1}, s_{i,1}) \| \ldots \| \mathsf{ext}^T(x_{i,1},s_{i,k}))^T \| \mathsf{ext}^T(x_{i,2},s_{i,1}) \| \ldots \| \mathsf{ext}^T(x_{i,2}, s_{i,k}) \\
|
|
& \| \ldots \|\mathsf{ext}^T(x_{i,mk},s_{i,1} \| \ldots \| \mathsf{ext}^T(x_{i,mk}, s_{i,k}) \bigr)^T \in \{0,1\}^{4mk^2}.
|
|
\end{align*}
|
|
Then, for all $i \in [n]$, we have:
|
|
$
|
|
(x_{i,1}\cdot s_i, \ldots, x_{i,mk}\cdot s_i)^T = \mathbf{Q}_0 \cdot \mathbf{y}_i.
|
|
$
|
|
Now, we note that $$(\mathbf{y}_1^T \| \ldots \| \mathbf{y}_n^T)^T = \expandtimes \bigl(\mathsf{mdec}_{n,m,q}(\mathbf{X}), \mathsf{vdec}_{n,q-1}(\mathbf{s})\bigr),$$
|
|
and
|
|
\begin{multline} \label{almost}
|
|
\sum_{i=1}^n (x_{i,1}\cdot s_i, \ldots, x_{i,mk}\cdot s_i)^T \\ = \sum_{i=1}^n \mathbf{Q}_0 \cdot \mathbf{y}_i = \widehat{\mathbf{Q}}\cdot \expandtimes \bigl(\mathsf{mdec}_{n,m,q}(\mathbf{X}), \mathsf{vdec}_{n,q-1}(\mathbf{s}) \bigr). \qquad
|
|
\end{multline}
|
|
|
|
Letting $\mathbf{Q}= \mathbf{H}_{m,q-1}\cdot \widehat{\mathbf{Q}} \in \Zq^{m \times 4nmk^2}$ and left-multiplying~\eqref{almost} by $ \mathbf{H}_{m,q-1}$, we obtain the equation:
|
|
\[
|
|
\mathbf{X} \cdot \mathbf{s} = \mathbf{Q}\cdot
|
|
\expandtimes \bigl(\mathsf{mdec}_{n,m,q}(\mathbf{X}), \mathsf{vdec}_{n,q-1}(\mathbf{s})\bigr) \bmod q.
|
|
\]
|
|
\begin{comment}
|
|
\begin{table}
|
|
\centering
|
|
\begin{tabular}{|c|c|c|c|c|c|c|c|c|}
|
|
\hline
|
|
$x_1$ & $x_2$ & $b_1$ & $b_2$ & ~$\mathsf{ext}(x_1,x_2)$~ & ~$T_{b_1,b_2}(\mathsf{ext}(x_1,x_2))$~ & ~$x_1 \oplus b_1$~& ~$x_2 \oplus b_2$~ &~$\mathsf{ext}(x_1 \oplus b_1, x_2 \oplus b_2)$~\\
|
|
\hline
|
|
\rule{0pt}{3ex}
|
|
$0$ & $0$ & $0$ & $0$ & $(1000)^T$ & $(1000)^T$ & $0$ & $0$ & $(1000)^T$ \\[5pt]
|
|
|
|
$0$ & $0$ & $0$ & $1$ & $(1000)^T$ & $(0100)^T$ & $0$ & $1$ & $(0100)^T$ \\[5pt]
|
|
|
|
$0$ & $0$ & $1$ & $0$ & $(1000)^T$ & $(0010)^T$ & $1$ & $0$ & $(0010)^T$ \\[5pt]
|
|
|
|
\hline
|
|
\end{tabular}
|
|
\end{table}
|
|
\end{comment}
|
|
|
|
This means that the task of proving knowledge of $(\mathbf{X},\mathbf{s},\mathbf{e}) \in \Zq^{m \times n} \times \Zq^n \times [-\beta,\beta]^m$ such that $\mathbf{b}=\mathbf{X} \cdot \mathbf{s} + \mathbf{e} \bmod q$
|
|
boils down to proving knowledge of $\mathbf{z} \in \{0,1\}^{4nmk^2}$, $\mathbf{x} \in \{0,1\}^{nmk}$, $\mathbf{s}_0 \in \{0,1\}^{nk}$ and a short $\mathbf{e} \in \ZZ^m$ such that
|
|
\[
|
|
\mathbf{b} = \mathbf{Q}\cdot \mathbf{z} + \mathbf{I}_m \cdot \mathbf{e} \bmod q
|
|
\qquad \mbox{ and } \qquad
|
|
\mathbf{z} = \expandtimes (\mathbf{x},\mathbf{s}_0).
|
|
\]
|
|
|
|
As the knowledge of small-norm vector $\mathbf{e}$ can easily be proven with Stern-like protocol (e.g.,~\cite{LNSW13}), the challenging part is to prove in zero-knowledge the constraint ``$\mathbf{z} = \expandtimes (\mathbf{x},\mathbf{s}_0)$''.
|
|
To this end, we will use the following permuting technique inspired by the equivalence of equation~\eqref{eq:expand-permuting}.
|
|
We sample uniformly random $\mathbf{d}_x \in \{0,1\}^{n{m}k}$ and $\mathbf{d}_s \in \{0,1\}^{nk}$, send $\mathbf{x}' = \mathbf{x} \oplus \mathbf{d}_x$ and $\mathbf{s}' = \mathbf{s}_0 \oplus \mathbf{d}_s$ to the verifier, and let the latter check that $P_{\mathbf{d}_x, \mathbf{d}_s}(\mathbf{z}) = \expandtimes(\mathbf{x}', \mathbf{s}')$.
|
|
This will be sufficient to convince the verifier that the original vector $\mathbf{z}$ satisfies the required constraint.
|
|
The crucial point is that no additional information about $\mathbf{x}$ and $\mathbf{s}_0$ is leaked, since these binary vectors are perfectly hidden under the ``one-time pad'' $\mathbf{d}_x$ and $\mathbf{d}_s$, respectively.
|
|
|
|
In the framework of Stern's protocol, the idea of using ``one-time-pad'' permutations further allows us to prove that $\mathbf{x}$ and $\mathbf{s}_0$ satisfy additional conditions, i.e., they appear in other equations.
|
|
This is done by first setting up an equivalence similar to~\eqref{eq:expand-permuting} in the places where these objects appear, and then, using the same ``one-time pad'' for each of them in all appearances.
|
|
We will explain in detail how this technique can be realized in the next subsection.
|
|
|
|
%**************************************************
|
|
\section{Our Lattice-Based Group Encryption Scheme} \label{groupenc-scheme}
|
|
|
|
To build a $\mathsf{GE}$ scheme using our zero-knowledge argument system, we need to choose a specific key-private CCA2-secure encryption scheme.
|
|
The first idea is to use the CCA2-secure public-key cryptosystem which is implied by the Agrawal-Boneh-Boyen identity-based encryption (IBE) scheme \cite{ABB10} (which is
|
|
recalled in \cref{ap:ABB-IBE}) via the Canetti-Halevi-Katz (CHK) transformation \cite{CHK04}.
|
|
The ABB scheme is a natural choice since it has pseudo-random ciphertexts (which implies the key-privacy \cite{BBDP01} when the CHK paradigm
|
|
is applied) and provides
|
|
one of the most efficient CCA2 cryptosystem based on the hardness of $\LWE$ in the standard model.
|
|
One difficulty is that the Kiayias-Tsiounis-Yung model \cite{KTY07} requires
|
|
that certified public keys be valid public keys (i.e., which have a matching secret key).
|
|
When new group members join the system and request a certificate for their
|
|
public key $\mathbf{B}_{\mathsf{U}} \in \Zq^{n \times \bar{m}}$, a direct use of the ABB/CHK technique would incur of proof
|
|
of existence of a GPV trapdoor \cite{GPV08} corresponding to $\mathbf{B}_{\mathsf{U}}$ (i.e., a small-norm matrix $\mathbf{T}_{\mathbf{B}_{\mathsf{U}}} \in \ZZ^{\bar{m} \times \bar{m} } $ s.t.
|
|
$\mathbf{B} \cdot \mathbf{T}_{\mathbf{B}_{\mathsf{U}}}= \mathbf{0}^n \bmod q$).
|
|
While the techniques of Peikert and Vaikuntanathan
|
|
\cite{PV08} would provide a solution to this problem (as they allow proving that $\mathbf{T}_{\mathbf{B}_{\mathsf{U}}} \in \ZZ^{\bar{m} \times \bar{m}} $ has full-rank),
|
|
we found it simpler to rely on the trapdoor mechanism
|
|
of Micciancio and Peikert \cite{MP12}.
|
|
|
|
If we assume public parameters containing a random matrix $\bar{\mathbf{A}} \in \Zq^{n \times m}$, each user's public key
|
|
can consist of a matrix $\mathbf{B}_{\mathsf{U}} = \bar{\mathbf{A}} \cdot \mathbf{T}_{\mathsf{U}} \in \Zq^{n \times \bar{m}}$, where $\mathbf{T}_{\mathsf{U}} \in \ZZ^{m \times \bar{m}}$ is a
|
|
small-norm matrix whose calms are sampled from a discrete Gaussian distribution. Note that, if $\bar{\mathbf{A}} \in \Zq^{n \times m}$ is uniformly distributed, then
|
|
\cite[Lemma 5.1]{GPV08} ensures that, with overwhelming probability, any
|
|
matrix $\mathbf{B}_{\mathsf{U}} \in \Zq^{n \times \bar{m}}$ has an underlying small-norm matrix satisfying $\mathbf{B}_{\mathsf{U}} = \bar{\mathbf{A}} \cdot \mathbf{T}_{\mathsf{U}} \bmod q $. This simplifies
|
|
the joining procedure by eliminating the need for proofs of public key validity.
|
|
|
|
In the encryption algorithm, the sender computes a dual Regev encryption~\cite{GPV08} of the witness $\mathbf{w} \in \{0,1\}^m$ using a matrix
|
|
$[\bar{\mathbf{A}} ~|~ \mathbf{B}_\mathsf{U} + \mathsf{FRD}(\vk) \cdot \mathbf{G} ] \in \Zq^{n \times (m + \bar{m})}$ such that: (i) $\vk \in \Zq^n$ is the verification key of a one-time signature; (ii)
|
|
$\mathsf{FRD} : \Zq^n \rightarrow \Zq^{n \times n}$ is the full-rank difference\footnote{This means that, for any two distinct one-time verification keys $\vk ,\vk' \in \Zq^n$, the difference
|
|
$\mathsf{FRD}(\vk) - \mathsf{FRD}(\vk') \in \Zq^{n \times n}$ is invertible over $\Zq$.} function of \cite{ABB10};
|
|
(iii) $\mathbf{G} = \mathbf{I}_n \otimes [1|2| \ldots |2^{k-1}] \in \Zq^{n \times \bar{m}}$ is the gadget matrix of \cite{MP12}. Given that $\mathbf{G} $ has a publicly known
|
|
trapdoor allowing to sample short vectors in $\Lambda_q^{\perp}(\mathbf{G})$, the user can use his private key $\mathbf{T}_{\mathsf{U}} \in \ZZ^{m \times \bar{m}}$ to decrypt
|
|
by running the $\mathsf{SampleRight}$ algorithm of Lemma \ref{lem:sampler}.
|
|
|
|
Having encrypted the witness $\mathbf{w} \in \{0,1\}^m$ by running the ABB encryption algorithm, the sender proceeds by encrypting a hash value of $\mathbf{B}_{\mathsf{U}} \in \Zq^{n \times \bar{m}}$ under the public key $\mathbf{B}_{\OA} = \bar{\mathbf{A}} \cdot \mathbf{T}_{\OA} \in \Zq^{n \times \bar{m}}$ of the opening authority. The latter hash value
|
|
is obtained as a bit-wise decomposition of $\mathbf{F} \cdot \mathsf{mdec}_{n,m,q}(\mathbf{B}_{\mathsf{U}}^T) \in \Zq^{2n}$, where $\mathbf{F} \in \Zq^{2n \times n \bar{m} \lceil \log q \rceil}$
|
|
is a random public matrix and $\mathsf{mdec}_{n,m,q}(\mathbf{B}_{\mathsf{U}}^T) \in \{0,1\}^{n \bar{m} \lceil \log q \rceil}$ denotes an entry-wise binary decomposition of the matrix $\mathbf{B}_{\mathsf{U}} \in \Zq^{n \times \bar{m}}$.
|
|
|
|
By combining our new argument for quadratic relations and the extensions of Stern's protocol suggested in \cite{LNW15,LLM+16},
|
|
we are able to prove that some component of the ciphertext is of the form $\mathbf{c}=\mathbf{B}_{\mathsf{U}}^{T} \cdot \mathbf{s} + \mathbf{e} \in \Zq^{\bar{m}}$, for some $\mathbf{s} \in \Zq^n$
|
|
and a small-norm $\mathbf{e} \in \ZZ^{\bar{m}}$ while also arguing possession of a signature on the binary decomposition
|
|
$\mathsf{mdec}_{n,m,q}(\mathbf{B}_{\mathsf{U}}^T) \in \{0,1\}^{n \bar{m} \lceil \log q \rceil}$ of $\mathbf{B}_{\mathsf{U}}^T$. For this purpose, we use a variant of a signature scheme
|
|
due to B\"ohl \textit{et al.}'s
|
|
signature \cite{BHJ+15} which was described in \cref{ch:gs-lwe}
|
|
(and of which a description is given in \cref{se:gs-lwe-sigep}).
|
|
At the same time, the prover $\mathcal{P}$ can also
|
|
argue that a hash value of $\mathsf{mdec}_{n,m,q}(\mathbf{B}_{\mathsf{U}}^T) $ is properly
|
|
encrypted under the $\OA$'s public key using the ABB encryption scheme.
|
|
|
|
|
|
|
|
|
|
\subsection{Description of the Scheme}
|
|
|
|
Our $\mathsf{GE}$ scheme allows encrypting witnesses for the \ISIS relation (as in \cref{de:sis}) $ \mathrm{R}_{\ISIS}(n,m,q,1)$, which
|
|
consists of pairs $((\mathbf{A}_R, \mathbf{u}_R), \mathbf{w}) \in (\Zq^{n \times m} \times \Zq^n) \times \{0,1\}^m $ satisfying $\mathbf{u}_R=\mathbf{A}_R \cdot \mathbf{w} \bmod q$.
|
|
This relation is in the same spirit as the one of Kiayias, Tsiounis and Yung \cite{KTY07}, who consider the verifiable encryption of discrete logarithms. While the construction of
|
|
\cite{KTY07} allow verifiably encrypting discrete-logarithm-type secret keys under the public key of some anonymous trusted third party, our construction makes it possible to encrypt GPV-type secret keys \cite{GPV08}. \smallskip
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
\begin{description}
|
|
\item[$\mathsf{SETUP_{init}}(1^\lambda)$:] This algorithm performs the following: \smallskip
|
|
\begin{itemize}
|
|
\item[1.] Choose integers $n = \mathcal{O}(\lambda)$, prime $q = \widetilde{\mathcal{O}}(n^4)$, and let $k = \lceil \log_2 q\rceil$, $\bar{m}=nk$ and $m =2\bar{m}= 2nk$. Choose a $B$-bounded distribution
|
|
$\chi$ over $\ZZ$ for some $B= \sqrt{n}\omega(\log n)$.
|
|
\item[2.] Choose a Gaussian parameter $\sigma = \Omega(\sqrt{n \log q}\log n)$. Let $\beta = \sigma\omega(\log n)$ be the upper bound of samples from $D_{\mathbb{Z}, \sigma}$.
|
|
\item[3.] Select integers $\ell = \ell(\lambda)$ which determines the maximum expected group size $2^\ell$, and $\kappa = \omega(\log \lambda)$ (the number of protocol repetitions).
|
|
% \item Pick $3$ hash functions to be modelled as random oracles: $$\mathcal{H}_1: \{0,1\}^* \rightarrow \mathbb{Z}_q^{n \times L}, \mathcal{H}_2: \{0,1\}^* \rightarrow \mathbb{Z}_q^{n \times n}, \mathcal{H}_\textsf{FS}: \{0,1\}^* \rightarrow \{1,2,3\}^\kappa.$$
|
|
\item[4.] Select a strongly unforgeable one-time signature $\mathcal{OTS} = (\mathsf{Gen}, \mathsf{Sig}, \mathsf{Ver})$. We assume that the verification keys live in $\mathbb{Z}_q^n$.
|
|
\item[5.] Select public parameters $\compar$ for a statistically-hiding commitment scheme like \cite{KTX08}. This commitment will serve as a building block for the zero-knowledge argument
|
|
system used in $\langle \mathcal{P}, \mathcal{V} \rangle $.
|
|
\item[6.] Let $\mathsf{FRD}: \mathbb{Z}_q^{n} \rightarrow \mathbb{Z}_q^{n \times n}$ be the full-rank difference mapping from~\cite{ABB10}.
|
|
\item[7.] Pick a random matrix $\mathbf{F} \leftarrow \mathbb{Z}_q^{2n \times n \bar{m}k}$, which will be used to hash users' public keys from $\Zq^{n \times \bar{m}}$ to $\mathbb{Z}_q^n$.
|
|
% \item[7.] Pick matrices $\mathbf{A}_0,\mathbf{A}_1,\ldots,\mathbf{A}_{\ell}, \mathbf{D}_1 \xleftarrow{\$} \Zq^{n \times m}$, $\mathbf{D}, \mathbf{D}_0 \xleftarrow{\$} \mathbb{Z}_q^{n \times %nk}$ and vector $\mathbf{u} \xleftarrow{\$} \Zq^n$. These objects will be used for verifying the membership certificates issued by GM.
|
|
\item[8.] Let $\mathbf{G} \in \Zq^{n \times \bar{m}}$ be the gadget matrix $\mathbf{G}= \mathbf{I}_n \otimes \begin{bmatrix} 1 & 2 & \ldots & 2^{k-1} \end{bmatrix}$ of \cite{MP12}. Pick matrices $\bar{\mathbf{A}}, \mathbf{U} \sample \U(\mathbb{Z}_q^{n \times m})$ and $\mathbf{V} \sample \U(\mathbb{Z}_q^{n \times m})$. Looking ahead, $\mathbf{U}$ will be used to encrypt for the receiver while $\mathbf{V}$ will be used
|
|
to encrypt the user's public key under the $\OA$'s public key. As for $\bar{\mathbf{A}}$, it will be used in two instances of the ABB encryption scheme \cite{ABB10}. \smallskip \smallskip
|
|
\end{itemize}
|
|
Output
|
|
\begin{eqnarray*} %\label{eq:param}
|
|
\param &=& \big\{\lambda, n, q, k, m, B, \chi, \sigma, \beta, \ell, \kappa, \mathcal{OTS}, \compar, \mathsf{FRD}, \bar{\mathbf{A}}, \mathbf{G}, \mathbf{F}, \mathbf{U}, \mathbf{V} \big\}.
|
|
%\\ & & ~ \mathbf{F}, \{\mathbf{A}_i\}_{i=0}^\ell,\mathbf{D}, \mathbf{D}_0, \mathbf{D}_1,\mathbf{u}, \mathbf{B}_0, \mathbf{B}_1, \mathbf{G}_{re}, \mathbf{G}_{op} \big\}.
|
|
\end{eqnarray*}
|
|
\item[$\langle
|
|
\mathcal{G}_r, \mathsf{sample}_{R}
|
|
\rangle$:] Algorithm $\mathcal{G}_r(1^\lambda,1^n,1^m)$ proceeds by sampling a random matrix $\mathbf{A}_R \sample \U(\Zq^{n \times m})$ and outputting
|
|
$(\pk_{R},\sk_{R})=(\mathbf{A}_R,\varepsilon)$. On input of a public key
|
|
$\pk_{R}=\mathbf{A}_R \in \Zq^{n \times m}$ for the relation $\mathrm{R}_{\ISIS}$, algorithm
|
|
$\mathsf{sample}_{R}$ picks $\mathbf{w} \sample \U(\{0,1\}^m)$ and outputs a pair $((\mathbf{A}_R,\mathbf{u}_R),\mathbf{w})$, where $\mathbf{u}_R =\mathbf{A}_R \cdot \mathbf{w} \in \Zq^n$.
|
|
|
|
|
|
\item[$\mathsf{SETUP_{\GM}}(\param)$:] The $\GM$ generates $(\sk_\GM,\pk_\GM) \leftarrow \mathsf{Keygen}(1^\lambda,q,n,m,\ell,\sigma)$ as a key pair for the $\SIS$-based signature scheme of \cite{LLM+16} (as recalled in \cref{se:gs-lwe-sigep}). This key pair
|
|
consists of $\sk_{\GM}:=
|
|
\mathbf{T}_{\mathbf{A}} $ and
|
|
\begin{eqnarray} \label{PK-GM}
|
|
\hspace*{-25pt} \pk_{\GM}:=\Bigl( \mathbf{A}, \mathbf{A}_0,\ldots, \mathbf{A}_{\ell} \in \Zq^{n \times m},
|
|
~ \mathbf{D}_0 , \mathbf{D}_1 \in \Zq^{n \times m}, \mathbf{D} \in \Zq^{n \times \bar{m}}, \mathbf{u} \in \Zq^n \Bigr).
|
|
\end{eqnarray}
|
|
|
|
|
|
\item[$\mathsf{SETUP_{\OA}}(\param)$:] The $\OA$ samples a small-norm matrix $\mathbf{T}_{\OA} \leftarrow D_{\ZZ^m,\sigma}^{\bar{m}}$ in $\ZZ^{m \times \bar{m}}$ to obtain a statistically uniform $\mathbf{B}_{\OA} = \bar{\mathbf{A}}
|
|
\cdot \mathbf{T}_{\OA}
|
|
\in \Zq^{n \times \bar{m}}$. The $\OA$'s key pair consists of
|
|
$(\sk_{\OA},\pk_{\OA})=(\mathbf{T}_{\OA},\mathbf{B}_{\OA})$.
|
|
\medskip
|
|
|
|
\item[$\mathsf{JOIN}$:] The prospective user $\mathsf{U}$ and the $\GM$ interact in the following protocol. \smallskip \smallskip
|
|
\begin{itemize}
|
|
\item[1.]
|
|
$\mathsf{U}$ first samples $\mathbf{T}_{\mathsf{U}} \leftarrow D_{\ZZ^m,\sigma}^{\bar{m}} $ in $\ZZ^{m \times \bar{m}}$ to compute a statistically uniform matrix $\mathbf{B}_{\mathsf{U}} = \bar{\mathbf{A}} \cdot \mathbf{T}_{\mathsf{U}} \in \Zq^{n \times \bar{m}}$.
|
|
The prospective user defines his key pair as
|
|
$(\pk_{\mathsf{U}},\sk_{\mathsf{U}})=(\mathbf{B}_{\mathsf{U}},\mathbf{T}_{\mathsf{U}})$ and sends $\pk_{\mathsf{U}}=\mathbf{B}_{\mathsf{U}}$ to the $\GM$.
|
|
%In addition, $\mathsf{U}$ proves to $\GM$ that $\mathbf{B}_{\mathsf{U}} \in \Zq^{n \times m} $ is
|
|
% a valid public key by demonstrating possesion of a short basis of $\Lambda_q^{\perp}(\mathbf{B}_{\mathsf{U}})$. This can be achieved via \cite{PV08}.
|
|
\smallskip
|
|
\item[2.] Upon receiving a public key $\mathsf{pk}_{\mathsf{U}} = \mathbf{B}_{\mathsf{U}} \in \mathbb{Z}_q^{n \times \bar{m}}$ from the user, the $\GM$ certifies $\pk_U$ via the following steps:
|
|
\smallskip
|
|
\begin{enumerate}
|
|
\item[a.] Compute $\mathbf{h}_{\mathsf{U}} = \mathbf{F}\cdot \mathsf{mdec}_{n,\bar{m},q}(\mathbf{B}_{\mathsf{U}}^T) \in \mathbb{Z}_q^{2n}$ as a hash value
|
|
of the public key $\pk_{\mathsf{U}}=\mathbf{B}_{\mathsf{U}} \in \Zq^{n \times \bar{m}}$. \smallskip %and let $\mathbf{e_M} = \mathsf{encode}(\mathsf{bin}(\mathbf{h_M})) \in \{0,1\}^{m}$.
|
|
\item[b.] Use the trapdoor $\sk_{\GM} = \mathbf{T_A}$ to generate a signature
|
|
\begin{eqnarray}\label{eq:cert-description}
|
|
\crt_{\mathsf{U}} = \big( \tau, \mathbf{d}, \mathbf{r} \big) \in \{0,1\}^\ell \times [-\beta,\beta]^{2m} \times [-\beta,\beta]^m,
|
|
\end{eqnarray}
|
|
satisfying
|
|
\begin{multline}\label{eq:cert-verification}
|
|
\big[\mathbf{A} ~|~ \sum_{j=1}^\ell \tau[j]\mathbf{A}_j\big] \cdot \mathbf{d} \\ = \mathbf{u} +
|
|
\mathbf{D}\cdot \mathsf{vdec}_{n,q-1}( \mathbf{D}_0 \cdot \mathbf{r} + \mathbf{D}_1 \cdot \mathsf{vdec}_{n,q-1}(\mathbf{h}_{\mathsf{U}}) ) \bmod q,
|
|
\end{multline}
|
|
where $\tau= \tau[1] \ldots \tau[\ell] \in \{0,1\}^{\ell}$, as in the scheme of \cref{se:gs-lwe-sigep}. \smallskip
|
|
\end{enumerate}
|
|
$\mathsf{U}$ verifies that $\crt_{\mathsf{U}}$ is tuple of the form (\ref{eq:cert-description}) satisfying (\ref{eq:cert-verification}) and returns~$\perp$ if it is not the case.
|
|
The $\GM$ stores $(\pk_{\mathsf{U}},\crt_\mathsf{U})$ in the user database $\mathsf{database}$ and returns the certificate $\crt_\mathsf{U}$ to the new user $\mathsf{U}$. \medskip
|
|
% \begin{eqnarray}\label{eq:cert-pk}
|
|
%\mathsf{cert}_{\mathsf{pk}} = (\mathbf{h_M}, sig_{\mathbf{M}}).
|
|
%\end{eqnarray}
|
|
\end{itemize}
|
|
|
|
\item[$\mathsf{ENC}(\pk_{\GM}, \pk_{\OA}, \pk_\mathsf{U}, \crt_\mathsf{U}, \mathbf{w}, L)$:] To encrypt a witness $\mathbf{w} \in \{0,1\}^m$
|
|
for $((\mathbf{A}_R, \mathbf{u}_R), \mathbf{w})$ in relation $\mathrm{R}_{\mathsf{ISIS}}(n,m,q,1)$ (i.e., $\mathbf{A}_R \cdot \mathbf{w} = \mathbf{u}_R \bmod q$), parse $\pk_{\GM}$
|
|
as in (\ref{PK-GM}), $\pk_{\OA}$ as $\mathbf{B}_{\OA} \in \Zq^{n \times \bar{m}}$, $\pk_{\mathsf{U}}$ as $\mathbf{B}_\mathsf{U} \in \Zq^{n \times \bar{m}}$ and $\crt_{\mathsf{U}}$ as in~(\ref{eq:cert-description}). \smallskip \smallskip
|
|
\begin{enumerate}
|
|
\item[1.] Generate a one-time key-pair $(\sk, \vk) \leftarrow \mathsf{Gen}(1^\lambda)$, where $\vk \in \mathbb{Z}_q^n$.
|
|
\item[2.] Compute a full-rank-difference hash $\mathbf{H}_{\vk}= \mathsf{FRD}(\vk) \in \mathbb{Z}_q^{n \times n}$ of the one-time verification key $\vk \in \Zq^n$.
|
|
%Define $\mathbf{B}_{\vk} = \mathbf{B}_\mathsf{U} + \mathbf{H}_{\vk}\cdot \mathbf{G} \in \mathbb{Z}_q^{n \times m}$.
|
|
\item[3.] Encrypt the witness $\mathbf{w} \in \{0,1\}^m$ under $\mathsf{U}$'s public key $\mathbf{B}_\mathsf{U} \in \Zq^{n \times \bar{m}}$ using the tag $\vk$ by taking the following steps: \smallskip
|
|
\begin{enumerate}
|
|
\item[a.] Sample $\mathbf{s}_{\rec} \leftarrow \U(\mathbb{Z}_q^n)$, $\mathbf{R}_{\rec} \leftarrow D_{\ZZ,\sigma}^{m \times \bar{m}} $ and
|
|
$\mathbf{x}_{\rec}, \mathbf{y}_{\rec} \leftarrow \chi^m$. Compute $\mathbf{z}_{\rec} = \mathbf{R}_{\rec}^T\cdot \mathbf{y}_{\rec} \in \mathbb{Z}^{\bar{m}}$.
|
|
\item[b.] Compute
|
|
\begin{eqnarray}\label{eq:c-recipient}
|
|
\begin{cases}
|
|
\mathbf{c}_{\rec}^{(1)} = \bar{\mathbf{A}}^T\cdot \mathbf{s}_{\rec} + \mathbf{y}_{\rec} \bmod q \\
|
|
\mathbf{c}_{\rec}^{(2)} %= \mathbf{B}_{\vk}^T \cdot \mathbf{s}_{\rec} + \mathbf{z}_{\rec} \bmod q
|
|
= (\mathbf{B}_\mathsf{U} + \mathbf{H}_{\vk} \cdot \mathbf{G})^T \cdot \mathbf{s}_{\rec} + \mathbf{z}_{\rec} \bmod q ; \\
|
|
\mathbf{c}_{\rec}^{(3)} = \mathbf{U}^T \cdot \mathbf{s}_{\rec} + \mathbf{x}_{\rec} + \mathbf{w}\cdot \Big\lfloor\frac{q}{2}\Big\rfloor,
|
|
\end{cases}
|
|
\end{eqnarray}
|
|
and let $\mathbf{c}_{\rec} = \big(\mathbf{c}_{\rec}^{(1)}, \mathbf{c}_{\rec}^{(2)}, \mathbf{c}_{\rec}^{(3)}\big)
|
|
\in \mathbb{Z}_q^m \times \mathbb{Z}_q^{\bar{m}} \times \mathbb{Z}_q^m$, which forms an ABB ciphertext \cite{ABB10} for the tag $\vk \in \Zq^n$.
|
|
|
|
\end{enumerate}
|
|
\medskip
|
|
|
|
\item[4.] Encrypt the decomposition $\mathsf{vdec}_{n,q-1}(\mathbf{h_\mathsf{U}}) \in \{0,1\}^{m}$ of the hashed $\pk_\mathsf{U}$ under
|
|
the $\OA$'s public key $\mathbf{B}_{\OA} \in \Zq^{n \times \bar{m}}$ w.r.t. the tag $\vk \in \Zq^n$. Namely, conduct the following steps: \smallskip
|
|
\begin{enumerate}
|
|
\item[a.] Sample $\mathbf{s}_{\mathsf{oa}} \leftarrow \U( \mathbb{Z}_q^n)$, $\mathbf{R}_{\mathsf{oa}} \leftarrow D_{\ZZ,\sigma}^{m \times \bar{m}}$,
|
|
$\mathbf{x}_{\mathsf{oa}} \leftarrow \chi^{m}, \mathbf{y}_{\mathsf{oa}} \leftarrow \chi^m$. Set $\mathbf{z}_{\mathsf{oa}} = \mathbf{R}_{\mathsf{oa}}^T\cdot \mathbf{y}_{\mathsf{oa}} \in \ZZ^{\bar{m}}$.
|
|
\item[b.] Compute
|
|
\begin{eqnarray}\label{eq:c-open}
|
|
\begin{cases}
|
|
\mathbf{c}_{\mathsf{oa}}^{(1)} = \bar{\mathbf{A}}^T \cdot \mathbf{s}_{\mathsf{oa}} + \mathbf{y}_{\mathsf{oa}} \bmod q; \\
|
|
\mathbf{c}_{\mathsf{oa}}^{(2)} = (\mathbf{B}_\OA + \mathbf{H}_{\vk} \cdot \mathbf{G})^T \cdot \mathbf{s}_{\mathsf{oa}} + \mathbf{z}_{\mathsf{oa}} \bmod q; \\
|
|
\mathbf{c}_{\mathsf{oa}}^{(3)} = \mathbf{V}^T \cdot \mathbf{s}_{\mathsf{oa}} + \mathbf{x}_{\mathsf{oa}} + \mathsf{vdec}_{n,q-1}(\mathbf{h_\mathsf{U}})\cdot \Big\lfloor\frac{q}{2}\Big\rfloor,
|
|
\end{cases}
|
|
\end{eqnarray}
|
|
and let $\mathbf{c}_{\mathsf{oa}} = \big(\mathbf{c}_{\mathsf{oa}}^{(1)}, \mathbf{c}_{\mathsf{oa}}^{(2)}, \mathbf{c}_{\mathsf{oa}}^{(3)}\big) \in \mathbb{Z}_q^m \times \mathbb{Z}_q^{\bar{m}} \times \mathbb{Z}_q^{m}$.
|
|
|
|
\end{enumerate}
|
|
\medskip
|
|
|
|
\item[5.] Compute a one-time signature $\Sigma = \mathsf{Sig}(\sk, (\mathbf{c}_{\rec}, \mathbf{c}_{\mathsf{oa}},L))$. \medskip
|
|
|
|
\end{enumerate}
|
|
|
|
Output the ciphertext
|
|
\begin{eqnarray}\label{eq:final-ciphertext}
|
|
\mathbf{\Psi} = (\vk,\mathbf{c}_{\rec}, \mathbf{c}_{\mathsf{oa}}, \Sigma).
|
|
\end{eqnarray}
|
|
and the state information $coins_{\mathbf{\Psi}}=\big( \mathbf{s}_{\rec}, \mathbf{R}_{\rec} , \mathbf{x}_{\rec}, \mathbf{y}_{\rec}, \mathbf{s}_{\mathsf{oa}}, \mathbf{R}_{\mathsf{oa}} ,\mathbf{x}_{\mathsf{oa}}, \mathbf{y}_{\mathsf{oa}} \big) $.
|
|
\medskip
|
|
|
|
\item[$\mathsf{DEC}(\mathsf{sk}_\mathsf{U}, \mathbf{\Psi},L)$]: The decryption algorithm proceeds as follows: \smallskip \smallskip
|
|
\begin{enumerate}
|
|
\item[1.] If $\mathsf{Ver}\big(\vk, \Sigma, ( \mathbf{c}_{\rec}, \mathbf{c}_{\mathsf{oa}},L)\big) = 0$, return $\bot$. Otherwise, parse the secret key $\mathsf{sk}_\mathsf{U}$ as $\mathbf{T}_\mathsf{U} \in \ZZ^{m \times \bar{m}}$ and the ciphertext $\mathbf{\Psi}$ as in~(\ref{eq:final-ciphertext}).
|
|
Define the matrix $\mathbf{B}_{\vk} = \mathbf{B}_\mathsf{U} +
|
|
\mathsf{FRD}(\vk) \cdot \mathbf{G} \in \mathbb{Z}_q^{n \times \bar{m}}$.
|
|
\item[2.]
|
|
Decrypt $\mathbf{c}_{\rec}$ using a decryption key for the tag $\vk \in \ZZ^n$. Namely, \smallskip
|
|
\begin{itemize}
|
|
\item[a.] Define $\mathbf{B}_{\mathsf{U},\vk} = [ \bar{\mathbf{A}} | \mathbf{B}_\vk ] = [ \bar{\mathbf{A}} | \bar{\mathbf{A}} \cdot \mathbf{T}_{\mathsf{U}} + \mathsf{FRD}(\vk) \cdot \mathbf{G} ] \in \Zq^{n \times (m+\bar{m})} $. Using $\mathbf{T}_\mathsf{U}$ and the publicly known trapdoor $\mathbf{T}_{\mathbf{G}}$ of $\mathbf{G}$,
|
|
compute a small-norm matrix $\mathbf{E}_{\vk} \in \ZZ^{(m+ \bar{m}) \times m} $ such that $\mathbf{B}_{\mathsf{U},\vk} \cdot \mathbf{E}_{\vk} = \mathbf{U} \bmod q$ by running the $\mathsf{SampleRight}$
|
|
algorithm of Lemma \ref{lem:sampler}.
|
|
\item[b.] Compute
|
|
\begin{eqnarray*}
|
|
\mathbf{w} = \left\lfloor \Bigl( \mathbf{c}_{\rec}^{(3)} - \mathbf{E}_{\vk}^T \cdot \begin{bmatrix} \mathbf{c}_{\rec}^{(1)} \\ \mathbf{c}_{\rec}^{(2)} \end{bmatrix} \Bigr) / \left\lfloor \frac{q}{2} \right\rfloor \right\rceil \in \ZZ^m
|
|
\end{eqnarray*}
|
|
and return the obtained $\mathbf{w} \in \{0,1\}^m$.
|
|
\end{itemize}
|
|
\end{enumerate}
|
|
|
|
\medskip
|
|
\item[$\mathsf{OPEN}(\mathsf{sk}_{\OA}, \mathbf{\Psi},L)$]:
|
|
The opening algorithm proceeds as follows: \smallskip \smallskip
|
|
\begin{enumerate}
|
|
\item[1.] If $\mathsf{Ver}\big(\vk, \Sigma, (\mathbf{c}_{\rec}, \mathbf{c}_{\mathsf{oa}}),L\big) = 0$, then return $\bot$. Otherwise, parse $\mathsf{sk}_{\OA}$ as $\mathbf{T}_\OA \in \ZZ^{m \times \bar{m}}$ and the ciphertext $\mathbf{\Psi}$ as in~(\ref{eq:final-ciphertext}).
|
|
\item[2.] Decrypt $\mathbf{c}_{\mathsf{oa}}$ using a decryption key for the tag $\vk \in \Zq^n$ in the same way as in the decryption algorithm.
|
|
That is, do the following: \smallskip
|
|
\begin{itemize}
|
|
\item[a.] Define the matrix $\mathbf{B}_{\OA,\vk} = [ \bar{\mathbf{A}} | \mathbf{B}_\OA + \mathsf{FRD}(\vk) \cdot \mathbf{G} ] \in \Zq^{n \times (m+\bar{m})} $. Use $\mathbf{T}_\OA$ to
|
|
compute
|
|
a small-norm $\mathbf{E}_{\OA,\vk} \in \ZZ^{(m+\bar{m}) \times m} $ satisfying $\mathbf{B}_{\OA,\vk} \cdot \mathbf{E}_{\OA,\vk} = \mathbf{V} \bmod q$.
|
|
\item[b.] Compute
|
|
\begin{eqnarray*}
|
|
\mathbf{h} = \left\lfloor \Bigl( \mathbf{c}_{\mathsf{oa}}^{(3)} - \mathbf{E}_{\OA,\vk}^T \cdot \begin{bmatrix} \mathbf{c}_{\mathsf{oa}}^{(1)} \\ \mathbf{c}_{\mathsf{oa}}^{(2)} \end{bmatrix} \Bigr) /
|
|
\left\lfloor \frac{q}{2} \right\rfloor \right\rceil \in \{0,1\}^{m}
|
|
\end{eqnarray*}
|
|
and $\mathbf{h}_\mathsf{U}'=\mathbf{H}_{2n,q-1} \cdot \mathbf{h} \in \Zq^{2n}$.
|
|
\end{itemize}
|
|
|
|
\item[3.] Look up $\mathsf{database}$ to find a public key $\pk_\mathsf{U}=\mathbf{B}_\mathsf{U} \in \Zq^{n \times \bar{m}}$ that hashes
|
|
to $\mathbf{h}_\mathsf{U}' \in \Zq^{2n}$ (i.e., such that $\mathbf{h}_\mathsf{U}'= \mathbf{F} \cdot \mathsf{mdec}_{n,\bar{m},q}(\mathbf{B}_\mathsf{U}^T)$). If more than one such key exists, return
|
|
$\perp$.
|
|
If only one key $\pk_\mathsf{U}=\mathbf{B}_{\mathsf{U}} \in \Zq^{n \times \bar{m}}$ satisfies $\mathbf{h}_\mathsf{U}'= \mathbf{F} \cdot \mathsf{mdec}_{n,\bar{m},q}(\mathbf{B}_\mathsf{U}^T)$, return that key $\pk_\mathsf{U}$.
|
|
In any other situation, return $\bot$.
|
|
\end{enumerate}
|
|
|
|
|
|
|
|
|
|
\bigskip
|
|
\item[$\langle \mathcal{P}, \mathcal{V}\rangle$:] The common input consists of $\param$ and $\mathsf{pk}_{\GM} $ as specified above, and $(\mathbf{A}_R, \mathbf{u}_R)$ in $\mathbb{Z}_q^{n \times m} \times \mathbb{Z}_q^n$, $\mathsf{pk}_{\OA} = \mathbf{B}_{\OA} \in \Zq^{n \times \bar{m}}$,
|
|
and a ciphertext $\mathbf{\Psi}$ as in~(\ref{eq:final-ciphertext}).
|
|
Both parties compute $ \mathbf{B}_{\OA,\vk} = [ \bar{\mathbf{A}} | \mathbf{B}_\OA + \mathsf{FRD}(\vk) \cdot \mathbf{G} ] $ as specified above.
|
|
The prover's secret input consists of a witness $\mathbf{w} \in \{0,1\}^m$,
|
|
$\mathsf{pk}_\mathsf{U}= \mathbf{B}_\mathsf{U}$, $\crt_\mathsf{U} = (\tau,\mathbf{d},\mathbf{r}) \in \{0,1\}^\ell \times \ZZ^{2m} \times \ZZ^m$, and the random coins
|
|
$coins_{\mathbf{\Psi}}=\big( \mathbf{s}_{\rec}, \mathbf{R}_{\rec} , \mathbf{x}_{\rec}, \mathbf{y}_{\rec}, \mathbf{s}_{\mathsf{oa}}, \mathbf{R}_{\mathsf{oa}} ,\mathbf{x}_{\mathsf{oa}}, \mathbf{y}_{\mathsf{oa}} \big) $ used to generate $\mathbf{\Psi}$. \smallskip
|
|
|
|
The prover's goal is to convince the verifier in zero-knowledge that his secret input satisfies the following: \smallskip
|
|
\begin{enumerate}
|
|
\item $\mathbf{A}_R \cdot \mathbf{w} = \mathbf{u}_R \bmod q$.
|
|
\item $\mathbf{h_M} = \mathbf{F}\cdot \mathsf{mdec}_{n,m,q}(\mathbf{M}) \bmod q$.
|
|
\item Conditions (\ref{eq:cert-description}) and (\ref{eq:cert-verification}) hold.
|
|
\item Vectors $\mathbf{x}_{\rec}, \mathbf{y}_{\rec}, \mathbf{x}_{\mathsf{oa}}, \mathbf{y}_{\mathsf{oa}}$ have infinity norms bounded by $B$, and vectors $\mathbf{z}_{\rec}, \mathbf{z}_{\mathsf{oa}}$ have infinity norms bounded by $\beta mB$.
|
|
\item Equations in (\ref{eq:c-recipient}) and (\ref{eq:c-open}) hold.
|
|
\end{enumerate}
|
|
|
|
\medskip \smallskip
|
|
To this end $\mathcal{P}$ conducts the following steps. \medskip \smallskip \smallskip
|
|
\begin{itemize}
|
|
\item[1.] Decompose the matrix $\mathbf{B}_\mathsf{U} \in \Zq^{n \times \bar{m}}$ into $\mathbf{b}_{\mathsf{U}} = \mathsf{mdec}_{n,\bar{m},q}(\mathbf{B}_{\mathsf{U}}^T) \in \{0,1\}^{n\bar{m}k}$ and the vectors $\mathbf{s}_{\rec} ,\mathbf{s}_{\mathsf{oa}} \in \Zq^n$ into $\mathbf{s}_{0,\rec} = \mathsf{vdec}_{n,q-1}(\mathbf{s}_{\rec}) \in \{0,1\}^{nk}$ and $\mathbf{s}_{0,\mathsf{oa}} = \mathsf{vdec}_{n,q-1}(\mathbf{s}_{\mathsf{oa}}) \in \{0,1\}^{nk}$. Combine the first two binary vectors into $\mathbf{z}_{\mathbf{\Psi}} = \expandtimes (\mathbf{b}_{\mathsf{U}},\mathbf{s}_{0,\rec}) \in \{0,1\}^{4n \bar{m} k^2}
|
|
$. Define
|
|
$$\mathbf{Q} = \mathbf{H}_{\bar{m},q-1} \cdot [\overbrace{\mathbf{Q}_0 | \ldots | \mathbf{Q}_0}^{n \text{ times }}] \in \Zq^{\bar{m} \times 4n \bar{m} k^2} ,$$ where
|
|
$\mathbf{Q}_0 = \mathbf{I}_{\bar{m} k} \otimes \mathbf{g}' \in \Zq^{\bar{m}k \times 4 \bar{m} k^2}$ is the matrix defined as in (\ref{Q0-def}).
|
|
\smallskip
|
|
\item[2.] Generate a zero-knowledge argument of knowledge of
|
|
\begin{eqnarray*}
|
|
\left\{
|
|
\begin{array}{l}
|
|
\tau \in \{0,1\}^\ell, ~\mathbf{d}=[\mathbf{d}_1^T | \mathbf{d}_2^T ]^T \in [-\beta,\beta]^{2m},~\mathbf{r} \in [-\beta,\beta]^m \\
|
|
\mathbf{t}_{\mathsf{U}} \in \{0,1\}^{m},~\mathbf{w}_{\mathsf{U}} \in \{0,1\}^{\bar{m}} \\
|
|
\mathbf{b}_{\mathsf{U}} \in \{0,1\}^{n \bar{m} k}, ~\mathbf{s}_{0,\rec} \in \{0,1\}^{nk}, ~
|
|
\mathbf{z}_{\mathbf{\Psi}} = \expandtimes (\mathbf{b}_{\mathsf{U}},\mathbf{s}_{0,\rec})
|
|
\\
|
|
\mathbf{x}_{\rec}, ~\mathbf{y}_{\rec} \in [-B,B]^m, ~ \mathbf{z}_{\rec} \in [-\beta mB, \beta mB]^{\bar{m}} , ~\mathbf{w} \in \{0,1\}^m, \\
|
|
\mathbf{s}_{0,\mathsf{oa}} \in \{0,1\}^{nk},~\mathbf{x}_{\mathsf{oa}}, ~\mathbf{y}_{\mathsf{oa}} \in [-B,B]^m, ~\mathbf{z}_{\mathsf{oa}} \in [-\beta mB,\beta mB]^{\bar{m}}
|
|
\end{array}
|
|
\right.
|
|
\end{eqnarray*}
|
|
|
|
\end{itemize}
|
|
\end{description}
|
|
|
|
\begin{comment}
|
|
\begin{eqnarray} \label{rel-un}
|
|
\left[ \begin{array}{c|c|c|c|c} \mathbf{A} ~& ~\mathbf{A}_0 ~&~ \mathbf{A}_1 ~ & ~\ldots & \mathbf{A}_\ell \end{array} \right] \cdot \begin{bmatrix} \mathbf{d}_1 \\ \hline
|
|
\mathbf{d}_2 \\ \hline \tau[1] \cdot \mathbf{d}_2 \\ \hline \vdots \\ \hline \tau[\ell] \cdot \mathbf{d}_2 \end{bmatrix} &=& \mathbf{u} + \mathbf{D} \cdot \mathbf{w}_\mathsf{U} \bmod q \qquad \qquad \\ \nonumber
|
|
\mathbf{H}_{n,q-1} \cdot \mathbf{w}_\mathsf{U} &=& \mathbf{D}_0 \cdot \mathbf{r} + \mathbf{D}_1 \cdot \mathbf{t}_{\mathsf{U}} \\ \nonumber
|
|
\mathbf{H}_{2n,q-1} \cdot \mathbf{t}_{\mathsf{U}} & =& \mathbf{F} \cdot \mathbf{b}_{\mathsf{U}} \bmod q
|
|
\end{eqnarray}
|
|
as well as
|
|
\begin{eqnarray} \nonumber
|
|
\mathbf{c}_{\rec}^{(1)} &=& \left[ \begin{array}{c|c} \bar{\mathbf{A}}^T \cdot \mathbf{H}_{n,q-1} ~ &~ \mathbf{I}_m \end{array} \right] \cdot \begin{bmatrix} \mathbf{s}_{0,\rec} \\ \hline \mathbf{y}_{\rec} \end{bmatrix} , \qquad \quad \\ \label{rel-deux}
|
|
\mathbf{z}_{\mathbf{\Psi}} &= & \expandtimes (\mathbf{b}_{\mathsf{U}},\mathbf{s}_{0,\rec}) \qquad \qquad \\ \nonumber
|
|
\mathbf{c}_{\rec}^{(2)} &=&
|
|
\left[ \begin{array}{c|c|c} \mathbf{Q} ~&~ \mathbf{G}^T \cdot \mathbf{H}_\vk^T \cdot \mathbf{H}_{n,q-1} ~& ~ \mathbf{I}_{\bar{m}}
|
|
\end{array} \right] \cdot \begin{bmatrix} \mathbf{z}_{\mathbf{\Psi}} \\ \hline \mathbf{s}_{0,\rec} \\ \hline \mathbf{z}_{\rec} \end{bmatrix} , \qquad \quad \\ \nonumber
|
|
\mathbf{c}_{\rec}^{(3)} &=&
|
|
\left[ \begin{array}{c|c|c} ~ \mathbf{U}^T \cdot \mathbf{H}_{n,q-1} ~~& ~~ \mathbf{I}_m ~~& ~~\mathbf{I}_m \cdot \lfloor \frac{q}{p} \rfloor ~
|
|
\end{array} \right] \cdot \begin{bmatrix} \mathbf{s}_{0,\rec} \\ \hline \mathbf{x}_{\rec} \\ \hline \mathbf{w} \end{bmatrix} , \\ \nonumber
|
|
\mathbf{u}_R &=& \mathbf{A}_R \cdot \mathbf{w} \bmod q
|
|
\end{eqnarray}
|
|
and
|
|
\begin{eqnarray} \nonumber
|
|
\mathbf{c}_{\mathsf{oa}}^{(1)} &=& \left[ \begin{array}{c|c} \bar{\mathbf{A}}^T \cdot \mathbf{H}_{n,q-1} ~& ~ \mathbf{I}_m
|
|
\end{array} \right] \cdot \begin{bmatrix} \mathbf{s}_{0,\mathsf{oa}} \\ \hline \mathbf{y}_{\mathsf{oa}} \end{bmatrix} , \qquad \quad \\ \label{rel-trois}
|
|
\mathbf{c}_{\mathsf{oa}}^{(2)} &=&
|
|
\left[ \begin{array}{c|c} (\mathbf{B}_\OA + \mathbf{H}_\vk \cdot \mathbf{G} )^T \cdot \mathbf{H}_{n,q-1} ~& ~ \mathbf{I}_{\bar{m}}
|
|
\end{array} \right] \cdot \begin{bmatrix} \mathbf{s}_{0,\mathsf{oa}} \\ \hline \mathbf{z}_{\mathsf{oa}} \end{bmatrix} , \qquad \quad \\ \nonumber
|
|
\mathbf{c}_{\mathsf{oa}}^{(3)} &=&
|
|
\left[ \begin{array}{c|c|c} ~ \mathbf{V}^T \cdot \mathbf{H}_{n,q-1} ~~& ~ ~ \mathbf{I}_m~~& ~~\mathbf{I}_m \cdot \lfloor \frac{q}{2} \rfloor ~
|
|
\end{array} \right] \cdot \begin{bmatrix} \mathbf{s}_{0,\mathsf{oa}} \\ \hline \mathbf{x}_{\mathsf{oa}} \\ \hline \mathbf{t}_{\mathsf{U}} \end{bmatrix} .
|
|
\end{eqnarray}
|
|
The protocol is repeated $\kappa$ times to make the soundness error negligibly small.
|
|
\end{itemize}
|
|
|
|
|
|
\end{description}
|
|
\medskip
|
|
\end{comment}
|
|
such that the following system of $10$ equations holds:
|
|
\begin{eqnarray}\label{eq:big-system-main-scheme}
|
|
\begin{cases}
|
|
\mathbf{u}= [\mathbf{A} | \mathbf{A}_0 | \mathbf{A}_1 | \ldots | \mathbf{A}_\ell]\cdot \left(
|
|
\begin{array}{c}
|
|
\mathbf{d}_1 \\
|
|
\mathbf{d}_2 \\
|
|
\tau[1]\cdot \mathbf{d}_2 \\
|
|
\vdots \\ \tau[\ell]\cdot \mathbf{d}_2\\
|
|
\end{array}
|
|
\right)
|
|
+ (-\mathbf{D})\cdot\mathbf{w}_\textsf{U} \bmod q, \\[5pt]
|
|
\mathbf{0} = \mathbf{H}_{n, q-1}\cdot \mathbf{w}_\textsf{U} + (-\mathbf{D}_0)\cdot \mathbf{r} + (-\mathbf{D}_1)\cdot \mathbf{t}_\textsf{U} \bmod q, \\[5pt]
|
|
\mathbf{0} = \mathbf{H}_{2n,q-1}\cdot \mathbf{t}_\textsf{U} + (-\mathbf{F})\cdot\mathbf{b}_\textsf{U}\bmod q, \\[5pt]
|
|
\mathbf{c}_{\rec}^{(1)} = (\bar{\mathbf{A}}^T\cdot \mathbf{H}_{n,q-1}) \cdot \mathbf{s}_{0,\rec} + \mathbf{I}_m\cdot \mathbf{y}_{\rec} \bmod q, \\[5pt]
|
|
\mathbf{c}_{\rec}^{(2)} = \mathbf{Q}\cdot \mathbf{z}_{\mathbf{\Psi}} + (\mathbf{G}^T\cdot \mathbf{H}_{\vk}^T \cdot \mathbf{H}_{n,q-1})\cdot \mathbf{s}_{0,\rec} + \mathbf{I}_{\bar{m}} \cdot \mathbf{z}_{\rec} \bmod q, \\[5pt]
|
|
\mathbf{c}_{\rec}^{(3)} = (\mathbf{U}^T\cdot \mathbf{H}_{n,q-1})\cdot \mathbf{s}_{0,\rec} + \mathbf{I}_m\cdot \mathbf{x}_{\rec} + (\lfloor \frac{q}{2}\rfloor\cdot \mathbf{I}_m)\cdot \mathbf{w} \bmod q, \\[5pt]
|
|
\mathbf{u}_R = \mathbf{A}_R\cdot \mathbf{w} \bmod q, \\[5pt]
|
|
\mathbf{c}_{\mathsf{oa}}^{(1)} = (\bar{\mathbf{A}}^T \cdot \mathbf{H}_{n,q-1})\cdot \mathbf{s}_{0,\mathsf{oa}} + \mathbf{I}_m\cdot \mathbf{y}_{\mathsf{oa}} \bmod q, \\[5pt]
|
|
\mathbf{c}_{\mathsf{oa}}^{(2)} = [(\mathbf{B}_{\OA} + \mathbf{H}_{\vk}\cdot \mathbf{G})^T\cdot \mathbf{H}_{n,q-1}]\cdot \mathbf{s}_{0,\mathsf{oa}} + \mathbf{I}_{\bar{m}}\cdot \mathbf{z}_{\mathsf{oa}} \bmod q, \\[5pt]
|
|
\mathbf{c}_{\mathsf{oa}}^{(3)} = (\mathbf{V}^T\cdot \mathbf{H}_{n,q-1})\cdot \mathbf{s}_{0, \mathsf{oa}} + \mathbf{I}_m\cdot \mathbf{x}_{\mathsf{oa}} + (\lfloor \frac{q}{2}\rfloor\cdot \mathbf{I}_m)\cdot \mathbf{t}_{\mathsf{U}} \bmod q.
|
|
\end{cases}
|
|
\end{eqnarray}
|
|
Let $\mathbf{w}_1 = \mathbf{b}_{\mathsf{U}}$, $\mathbf{w}_2 = \mathbf{s}_{0,\rec}$, $\mathbf{w}_3 = \mathbf{z}_{\mathbf{\Psi}} = \expandtimes (\mathbf{b}_{\mathsf{U}},\mathbf{s}_{0,\rec})$, $\mathbf{w}_4 = \mathbf{w}_{\mathsf{U}}$, $\mathbf{w}_5 = \mathbf{t}_{\mathsf{U}}$,
|
|
$\mathbf{w}_6 = \mathbf{s}_{0,\mathsf{oa}}$, $\mathbf{w}_7 = \mathbf{w}$, $\mathbf{w}_8 = \mathbf{x}_{\rec}$, $\mathbf{w}_9 = \mathbf{y}_{\rec}$, $\mathbf{w}_{10} = \mathbf{z}_{\rec}$, $\mathbf{w}_{11} = \mathbf{r}$, $\mathbf{w}_{12} = \mathbf{x}_{\mathsf{oa}}$, $\mathbf{w}_{13} = \mathbf{y}_{\mathsf{oa}}$, $\mathbf{w}_{14}= \mathbf{z}_{\mathsf{oa}}$ and $$\mathbf{w}_{15}= \big(\hspace*{1.5pt}\mathbf{d}_1^T \hspace*{1.5pt}\|\hspace*{1.5pt} \mathbf{d}_2^T \hspace*{1.5pt}\|\hspace*{1.5pt} \tau[1]\hspace*{-1.5pt}\cdot\hspace*{1.5pt}\mathbf{d}_2^T \hspace*{1.5pt}\| \ldots \|\hspace*{1.5pt} \tau[\ell]\hspace*{-1.5pt}\cdot\hspace*{1.5pt}\mathbf{d}_2^T\hspace*{1.5pt}\big)^T.$$
|
|
Then system (\ref{eq:big-system-main-scheme}) can be rewritten as:
|
|
\begin{eqnarray}\label{eq:big-system-main-scheme-2}
|
|
\begin{cases}
|
|
\mathbf{v}_1 = \mathbf{M}_{1,1}\cdot \mathbf{w}_1 + \mathbf{M}_{1,2}\cdot \mathbf{w}_2 + \ldots + \mathbf{M}_{1,15} \cdot \mathbf{w}_{15} \bmod q, \\[2.5pt]
|
|
\mathbf{v}_2 = \mathbf{M}_{2,1}\cdot \mathbf{w}_1 + \mathbf{M}_{2,2}\cdot \mathbf{w}_2 + \ldots + \mathbf{M}_{2,15} \cdot \mathbf{w}_{15} \bmod q, \\
|
|
\hspace{.35\textwidth}\vdots\\
|
|
%\hdotsfor{0} \\
|
|
\mathbf{v}_{10} = \mathbf{M}_{10,1}\cdot \mathbf{w}_1 + \mathbf{M}_{10,2}\cdot \mathbf{w}_2 + \ldots + \mathbf{M}_{10,15} \cdot \mathbf{w}_{15}\bmod q,
|
|
\end{cases}
|
|
\end{eqnarray}
|
|
where $\{\mathbf{M}_{i,j}\}_{(i,j) \in [10] \times [15]}$, $\{\mathbf{v}_i\}_{i \in [10]}$ are public matrices and vectors (which are possibly zero).
|
|
|
|
The argument system is obtained by invoking the protocol from \cref{sse:stern}. The protocol is repeated $\kappa$ times to make the soundness error negligibly small.
|
|
|
|
\subsection{Efficiency and Correctness} \label{correctness}
|
|
|
|
\paragraph{Efficiency.}
|
|
It can be seen that the given group encryption scheme can be implemented in polynomial time. We now will evaluate the bit-sizes of keys and ciphertext, as well as the communication cost of the protocol $\langle \mathcal{P}, \mathcal{V}\rangle$.
|
|
\begin{itemize}
|
|
\item The public key of \textsf{GM}, as in~\eqref{PK-GM}, has bit-size $\mathcal{O}(\ell n^2 \log^2 q) = \widetilde{\mathcal{O}}(\ell \lambda^2)$.
|
|
\item The public keys of \textsf{OA} and each user both have bit-size $n\bar{m}\lceil\log_2 q\rceil = \widetilde{\mathcal{O}}(\lambda^2)$.
|
|
\item The secret key of each party in the scheme is a trapdoor of bit-size $\widetilde{\mathcal{O}}(\lambda^2)$. The user's certificate $\mathsf{cert}_{\USR}$ has bit-size $\widetilde{\mathcal{O}}(\lambda)$.
|
|
\item The ciphertext $\mathbf{\Psi}$ consists of $\vk \in \ZZ_q^n$, two ABB ciphertexts of total size $2(2m + \bar{m})\lceil\log_2 q\rceil$ and a one-time signature $\Sigma$. Thus, its bit-size is $\widetilde{\mathcal{O}}(\lambda) + \big|\Sigma\big|$.
|
|
\item The communication cost of the protocol $\langle \mathcal{P}, \mathcal{V}\rangle$ is largely dominated by the bit-size of the witness $\mathbf{z}_{\mathbf{\Psi}} = \expandtimes (\mathbf{b}_{\USR},\mathbf{s}_{0,\rec}) \in \{0,1\}^{4n \bar{m} k^2}$. The total cost is $\kappa\cdot \mathcal{O}(n^2 \log^4 q) = \widetilde{\mathcal{O}}(\lambda^2)$ bits.
|
|
\end{itemize}
|
|
|
|
|
|
|
|
\paragraph{Correctness.}
|
|
The given group encryption scheme is correct with overwhelming probability.
|
|
We first remark that the scheme parameters are set up so that the two instances of the ABB identity-based encryption~\cite{ABB10} are correct. Indeed, during the decryption procedure of $\mathsf{DEC}(\mathsf{sk}_\USR, \mathbf{\Psi},L)$, we have:
|
|
\[
|
|
\mathbf{c}_{\rec}^{(3)} - \mathbf{E}_{\vk}^T \cdot \begin{bmatrix} \mathbf{c}_{\rec}^{(1)} \\ \mathbf{c}_{\rec}^{(2)} \end{bmatrix} = \mathbf{x}_{\rec} - \mathbf{E}_{\vk}^T \cdot \begin{bmatrix} \mathbf{y}_{\rec} \\ \mathbf{z}_{\rec} \end{bmatrix} + \mathbf{w}\cdot \left\lfloor \frac{q}{2} \right\rfloor.
|
|
\]
|
|
Note that $\|\mathbf{x}_{\rec}\|_\infty$ and $\|\mathbf{y}_{\rec}\|_\infty$ are bounded by $B$, and $\|\mathbf{z}_{\rec}\|_\infty = \|\mathbf{R}_{\rec}^T\cdot \mathbf{y}_{\rec}\|_\infty \leq \beta m B = \widetilde{\mathcal{O}}(n^2)$. Furthermore, the entries of the discrete Gaussian matrix $\mathbf{E}_{\vk}^T$ are bounded by $\widetilde{\mathcal{O}}(\sqrt{n})$. Hence, the error term $\mathbf{x}_{\rec} - \mathbf{E}_{\vk}^T \cdot \begin{bmatrix} \mathbf{y}_{\rec} \\ \mathbf{z}_{\rec} \end{bmatrix}$ is bounded by $\widetilde{\mathcal{O}}(n^{3.5})$ which is much smaller than $q/4 = \widetilde{\mathcal{O}}(n^4)$. As a result, the decryption algorithm returns $\mathbf{w}$ with overwhelming probability. The correctness of algorithm $\mathsf{OPEN}(\mathsf{sk}_{\OA}, \mathbf{\Psi},L)$ also follows from a similar argument.
|
|
|
|
Finally, we note that if a certified group user honestly follows all the prescribed algorithms, then he should be able to compute valid witness-vectors to be used in the protocol $\langle \mathcal{P}, \mathcal{V}\rangle$, and he should be accepted by the verifier, thanks to the perfect completeness of the argument system in \cref{sse:stern}.
|
|
|
|
\subsection{Security} \label{security}
|
|
|
|
Our scheme is proven secure under the $\SIS$ and $\LWE$ assumptions using classical reduction techniques.
|
|
The security results are explicited in the following theorems.
|
|
%, for which some proofs have been deferred to Appendix~\ref{proofs-GE}.
|
|
|
|
\subsubsection{Anonymity}
|
|
|
|
\begin{theorem} \label{anon-thm}
|
|
The scheme provides anonymity if the $\LWE$ assumption holds and if $\mathcal{OTS}$ is a strongly unforgeable one-time signature.
|
|
% \textnormal{(The proof is given in Appendix~\ref{proof-anon-thm}.)}
|
|
\end{theorem}
|
|
|
|
%%%%%%%%%
|
|
% Proof %
|
|
%%%%%%%%%
|
|
\begin{proof}
|
|
We consider a sequence of games where the first game is the real experiment of definition \ref{anonymity-def} while, in the final game, the adversary $\adv$ is essentially an adversary against the anonymity of the Agrawal-Boneh-Boyen IBE scheme \cite{ABB10}.
|
|
In Game $i$, we call $W_i$ the event that the challenger outputs $1$.
|
|
\smallskip \smallskip
|
|
|
|
\noindent \textbf{Game $1$:} The challenger $\bdv$ generates public parameters $\param$, which include matrices $ \bar{\mathbf{A}}, \mathbf{U}, \mathbf{V} \in \ZZ_q^{n \times m} $ and
|
|
$\mathbf{F} \in \ZZ_q^{2n \times n \bar{m} k} $. The opening authority's public
|
|
key $\pk_{\OA} = \mathbf{B}_{\OA} \in \ZZ_q^{n \times \bar{m}}$ is given to $\adv$ who generates a group manager's public key
|
|
$\pk_{\GM}$ of its own. By invoking the $\mathsf{USER}$ oracle, $\adv$
|
|
registers two distinct receivers' public keys
|
|
$\pk_{\USR,0}=\mathbf{B}_{\USR,0} \in \ZZ_q^{n \times \bar{m}}$, $\pk_{\USR,1}=\mathbf{B}_{\USR,1} \in \ZZ_q^{n \times \bar{m}}$
|
|
chosen by the challenger. It also makes a number of opening queries and decryption
|
|
queries, which the challenger handles using $\sk_{\OA}=\mathbf{T}_{\OA}$ and $\sk_{\USR,0}=\mathbf{T}_{\USR,0} $, $\sk_{\USR,1}=\mathbf{T}_{\USR,1}$,
|
|
respectively. After a while, the adversary outputs $((\mathbf{A}_R,\mathbf{u}_R),\mathbf{w},L)$ such
|
|
that $\mathbf{u}_R= \mathbf{A}_R \cdot \mathbf{w} \bmod q$, with $\mathbf{A}_R \in \ZZ_p^{n \times m}$, $\mathbf{u}_R \in \ZZ_q^n$ and $\mathbf{w} \in \{0,1\}^m$. In return, $\adv$ obtains, as a challenge, a
|
|
group encryption
|
|
$\Psi^\star= (\vk^\star,\mathbf{c}_{\rec}^\star, \mathbf{c}_{\oa}^\star, \Sigma^\star).$
|
|
of the witness $\mathbf{w}$ under $\pk_{\USR,b} =\mathbf{B}_{\USR,b}$, for some random bit $b \leftarrow \U( \{0,1\})$ of the challenger's
|
|
choice. Then, the adversary obtains proofs $\pi_{\Psi^\star}^\star$ for
|
|
$\Psi^\star$ and makes further opening and decryption queries under the
|
|
natural restrictions of Definition \ref{anonymity-def}. When the adversary $\adv$ halts, it
|
|
outputs a bit $b' \in \{0,1\}$ and the challenger outputs $1$ if and only if $b'=b$. % We call $W_1$ the latter event.
|
|
\smallskip \smallskip
|
|
|
|
\noindent \textbf{Game $2$:} This game is like Game $1$ except the challenger aborts in
|
|
the event that the adversary $\adv$ queries the opening of a ciphertext
|
|
$\Psi= (\vk,\mathbf{c}_{\rec}, \mathbf{c}_{\oa}, \Sigma)$ such that $\vk=\vk^\star$ and $\sigma$ is valid (we
|
|
assume w.l.o.g. that $\vk^\star$ is generated ahead of time). If
|
|
this event occurs, the adversary $\adv$ is necessarily able to break the strong unforgeability
|
|
of $\mathcal{OTS}$ (note that, if the query occurs before the challenge phase, it means that
|
|
$\adv$ has forged a signature without seeing a signature at all). There thus exist a one-time signature forger $\bdv$ such that
|
|
$|\Pr[W_2]-\Pr[W_1]| \leq \mathbf{Adv}_\bdv^{\mathrm{ots}}(\lambda)$, which means that Game $2$ is identical to Game $1$
|
|
so long as $\mathcal{OTS}$ is a strongly unforgeable one-time signature. \smallskip \smallskip
|
|
|
|
\noindent \textbf{Game $3$:} In this game, we modify the generation of proofs $\pi_{\Psi^\star}^\star$:
|
|
instead of generating proofs using the real witnesses, we appeal to the zero-knowledge simulator of the argument system of \cref{sse:stern-abstraction} at each invocation
|
|
of $\mathcal{P}$ after the challenge phase. Note that, since we assume public parameters generated by a trusted party, the statistical ZK simulator is allowed to use
|
|
a trapdoor embedded in $\param$ to generate simulated proofs (using, e.g., Damg\aa rd's technique \cite{Dam00}).
|
|
The statistical zero-knowledge property of the argument system ensures that $\adv$'s view remains statistically close to that of Game $2$: we have
|
|
$|\Pr[W_3]-\Pr[W_2] | \leq \mathsf{negl}(\lambda)$. \smallskip \smallskip
|
|
|
|
\noindent \textbf{Game $4$:} We now modify the generation of the challenge ciphertext $\Psi^\star$.
|
|
In this game, the challenger computes the ciphertext
|
|
$\mathbf{c}_{\oa}^\star$ as an ABB encryption under the identity $\vk^\star$ of a random $m$-bit string instead of a decomposition
|
|
$\mathsf{vdec}_{n,q-1}(\mathbf{h}_{\USR,b}) \in \{0,1\}^m$ of $\mathbf{h}_{\USR,b} = \mathbf{F} \cdot \mathsf{mdec}_{n,\bar{m},q}(\mathbf{B}_{\USR,b}^T) \in \ZZ_q^{2n}$. Since
|
|
the random encryption coins $\mathbf{s}_{\oa}^\star, \mathbf{R}_{\oa}^\star ,\mathbf{x}_{\oa}^\star, \mathbf{y}_{\oa}^\star $ are no longer used to generate proofs
|
|
$\pi_{\Psi^\star}$, we can show that any noticeable change in $\adv$'s output distribution implies
|
|
a selective adversary against the ABB IBE, as established by Lemma \ref{ABB-un}, which would contradict the $\LWE$ assumption.
|
|
The result of Agrawal \textit{et al.}~\cite[Theorem~23]{ABB10} (recalled in Theorem~\ref{ABB-pseudorand-prop}) indeed implies
|
|
$|\Pr[W_4]-\Pr[W_3]| \leq \mathbf{Adv}^{\mathsf{LWE}}(\lambda) $. \smallskip \smallskip
|
|
|
|
In Game $4$, we can show that, if the adversary $\adv$ has noticeable advantage in the anonymity game, we can break the anonymity of the ABB IBE system, as shown
|
|
in the proof of Lemma \ref{ABB-deux}.
|
|
From the result of \cite[Theorem 23]{ABB10}, we deduce that $|\Pr[W_4]-1/2| \leq \mathbf{Adv}^{\mathsf{LWE}}(\lambda)$,
|
|
which implies the announced result.
|
|
\end{proof}
|
|
|
|
\begin{lemma}\label{ABB-un}
|
|
Any PPT adversary such that $\Pr[W_4]$ is noticeably different from $\Pr[W_3]$ implies a selective adversary against the ABB IBE scheme.
|
|
\end{lemma}
|
|
|
|
\begin{proof}
|
|
Let $\adv$ be a PPT adversary for which $\left| \Pr[W_4] - \Pr[W_3] \right| = \varepsilon$ is non-negligible. We use $\adv$ to build a selective adversary against the ABB IBE system.
|
|
|
|
At the outset of the game, the reduction $\bdv$ generates a one-time signature key pair $(\vk^\star, \sk^\star)$ and declares
|
|
$\vk^\star$ as the target identity to its challenger for the selective security game, and obtains in return the IBE public parameters
|
|
$$\mathsf{PP} = \big(\bar{\mathbf A}, \mathbf B, \mathbf V \big) \in \Zq^{n \times m} \times \Zq^{n \times \bar{m}} \times \Zq^{n \times m}.$$
|
|
|
|
Next, the reduction runs the appropriate steps of the actual $\textsf{SETUP}_\textsf{init}$ algorithm to obtain
|
|
$\mathsf{COM}_{\mathsf{par}}$, $\mathbf{F} \in \ZZ_q^{2n \times n\bar{m}k}$ and $\mathbf{U} \in \ZZ_q^{n \times m}$.
|
|
Namely, $\bdv$ samples $\mathbf F \sample \U(\Zq^{2m\times n \bar{m} k})$ and $\mathbf U \sample \U(\Zq^{n \times m})$ like in the $\mathsf{SETUP}_\mathsf{init}$ algorithm and sends
|
|
$$ \param = \big\{\lambda, n, q, k, m, B, \chi, \sigma, \beta, \ell, \kappa, \mathcal{OTS}, \compar, \mathsf{FRD}, \bar{\mathbf{A}}, \mathbf{G}, \mathbf{F}, \mathbf{U}, \mathbf{V} \big\} $$
|
|
along with $\pk_\OA = \mathbf B \in \ZZ_q^{n \times \bar{m}}$ to the adversary $\adv$.
|
|
|
|
In return, the adversary $\adv$ chooses $\pk_\GM$, which allows it to enroll two users for whom $\bdv$ faithfully
|
|
generates $(\pk_{\USR, i}, \sk_{\USR, i})_{i \in \bit}$. Knowing both private keys $\{\sk_{\USR,i} = \mathbf{T}_{\USR,i} \}_{i \in \bit}$, $\bdv$ is able to perfectly simulate the $\mathsf{DEC}(\cdot)$
|
|
oracle.% Further decryption queries will use $\pk_{\USR, i}$ to decrypt $\mathbf c_\rec$.
|
|
\medskip
|
|
|
|
\noindent \paragraph{Open Queries.} To answer opening queries for ciphertexts $\mathbf{\Psi} = (\vk, \mathbf c_\rec, \mathbf c_\OA, \Sigma)$ and labels $L$, $\bdv$
|
|
first checks that $\mathsf{Ver}(\vk, \Sigma, (\mathbf c_\rec, \mathbf c_\OA, L)) = 1$. If this test fails, $\bdv$ returns $\bot$. Otherwise, $\bdv$ queries its IBE challenger
|
|
to obtain a IBE private key $\mathbf T_{\OA, \vk} \in \ZZ^{(m+ \bar{m}) \times m}$ for identity $\vk \neq \vk^\star$. The IBE challenger's response allows $\bdv$ to decrypt $\mathbf c_\OA$ and figure out the identity of the receiver by looking up $\mathsf{database}$.
|
|
The result of the opening operation is then returned to~$\adv$.
|
|
\medskip
|
|
|
|
After a number of queries, $\adv$ decides to move to the challenge phase and sends a challenge query $\big( (\mathbf{A}_R,\mathbf{u}_R), \mathbf w^\star, L^\star \big)$ such that
|
|
$\mathbf{u}_R=\mathbf{A}_R \cdot \mathbf{w}^\star \bmod q$. The reduction
|
|
handles this query by requesting a challenge ciphertext for the IBE security game with the messages $\mathbf{m}_0=\mathsf{vdec}_{n,q-1}(\mathbf h_{\mathsf U,b})$, for some random bit $b \sample \U(\bit)$
|
|
and $\mathbf{m}_1 \sample \U(\{0,1\}^m)$. In return, $\bdv$ obtains
|
|
a challenge ciphertext $\mathbf c^\star_\OA$ under identity $\vk^\star$, which is embedded in $\adv$'s challenge ciphertext. Namely,
|
|
$\mathbf{\Psi}^\star = (\vk^\star, \mathbf c_\rec^\star, \mathbf c_\OA^\star, \Sigma^\star)$ is obtained by computing $\mathbf c_\rec^\star$ as an ABB encryption
|
|
of the witness $\mathbf w^\star$ using the matrix $\mathbf{B}_{\mathsf U,b} \in \ZZ_q^{n \times \bar{m}}$ as in~\eqref{eq:c-recipient}
|
|
and $\Sigma^\star = \Sign(\sk^\star, (\mathbf c_\rec^\star, \mathbf c_\OA^\star, L^\star))$.
|
|
All queries to the proving oracle $\mathcal{P}$ are replied by returning a simulated ZK argument as in Game $3$.
|
|
|
|
When $\adv$ halts, it outputs a bit $b' \in \{0,1\}$. If $b = b'$, $\bdv$ returns the bit $0$ as a guess that the selective security challenger encrypted $\mathbf{m}_0=\mathsf{vdec}_{n,q-1}(\mathbf h_{\mathsf U,b})$.
|
|
Otherwise, $\bdv$ outputs $1$ meaning that the IBE challenger chose to encrypt $\mathbf{m}_1$, which was chosen independently of the value of $b \in \{0,1\}$.
|
|
If we call \textsf{Random} (resp. \textsf{Real}) the event that the IBE challenger chooses to encrypt $\mathbf{m}_1$ (resp. $\mathbf{m}_0$),
|
|
we can assess % corresponds to \SFGame 3.
|
|
the advantage of the reduction $\bdv$ as
|
|
\begin{align*}
|
|
\mathbf{Adv}_{\bdv}^{\textrm{sID-CPA}}(\lambda) &= \left|\Pr[b=b'\mid \textsf{Random}] - \Pr[b=b' \mid\textsf{Real}]\right|\\
|
|
&= \left|\Pr[W_4] - \Pr[W_3]\right|\\
|
|
&= \varepsilon,
|
|
\end{align*}
|
|
which proves the result.
|
|
\end{proof}
|
|
|
|
\begin{lemma} \label{ABB-deux}
|
|
In Game $4$, the adversary's advantage is negligible assuming that the ABB IBE has pseudo-random ciphertexts.
|
|
\end{lemma}
|
|
|
|
\begin{proof}
|
|
Let us assume the existence of a PPT adversary $\adv$ with non negligible advantage $\varepsilon$ in Game $4$. From $\adv$,
|
|
we construct a selective adversary $\bdv$ that can distinguish ABB ciphertexts from random elements of the ciphertext space with non-negligible advantage in the game described in Definition~\ref{de:pseudorand-cipher}.
|
|
|
|
First, $\bdv$ generates $(\sk^\star, \vk^\star)$ via the key generation algorithm of the one-time-signature \textsf{OTS} and hands $\vk^\star$ to its pseudo-randomness challenger. In return,
|
|
$\bdv$ receives
|
|
\[ \mathsf{PP} = \big(\bar{\mathbf A}, \mathbf B, \mathbf U \big) \in \Zq^{n \times m} \times \Zq^{n \times \bar{m}} \times \Zq^{n \times m} \]
|
|
from its real-or-random (ROR) challenger.
|
|
|
|
Our reduction uses $\mathsf{PP}$ to compute public parameters for our $\mathsf{GE}$ scheme. To this end, it samples $\mathbf F \sample \U(\Zq^{2n \times n \bar{m}k})$,
|
|
$\mathbf V \sample \U(\Zq^{n\times m})$ as in the real $\mathsf{SETUP}_\mathsf{init}$ algorithm.
|
|
The reduction $\bdv$ also computes $\mathbf B_\OA =\bar{\mathbf{A}} \cdot \mathbf T_\OA \bmod q $,
|
|
where the small-norm matrix $\mathbf{T}_\OA$ is sampled from $D_{\ZZ,\sigma}^{m \times \bar{m}}$, and sends $\adv$ the parameters
|
|
\[ \mathsf{param}= \big\{\lambda, n, q, k, m, \sigma, \beta, \ell, \kappa, \mathcal{OTS}, \compar, \mathsf{FRD}, \bar{\mathbf{A}}, \mathbf{G}, \mathbf{F}, \mathbf{U}, \mathbf{V} \big\}, \]
|
|
where $\bar{\mathbf{A}}$ is taken from $\mathsf{PP}$,
|
|
along with $\pk_\OA = \mathbf B_\OA$. The rest of the keys are generated as in Game $4$.
|
|
|
|
The reduction $\bdv$ then tosses a coin $b \sample \U(\bit)$. When the adversary $\adv$ triggers an execution of the join protocol,
|
|
$\bdv$ generates the public keys $(\pk_i)_{i\in \bit}$ by defining $\pk_{\USR,b} = \mathbf B$ using the matrix $\mathbf B \in \ZZ_q^{n \times \bar{m}}$ supplied by
|
|
the ROR challenger as part of $\mathsf{PP}$ and generates $(\pk_{\USR,1-b},\sk_{1-b}) =(\mathbf{B}_{\USR,1-b} = \bar{\mathbf{A}} \cdot \mathbf T_{1-b}, \mathbf{T}_{1-b})$ for
|
|
a secret key $\mathbf{T}_{1-b} \sample D_{\ZZ^m,\sigma}^{\bar{m}}$ of its own.
|
|
The two public keys $(\pk_{\USR,i})_{i\in \bit}$ are then certified by the adversarially-controlled $\GM$.
|
|
Notice that in the adversary's view, both public keys $\pk_{\USR,b}$ and $\pk_{\USR,1-b}$ are identically distributed.
|
|
|
|
To answer decryption queries $(\mathbf{\Psi} = (\vk, \mathbf c_\rec, \mathbf c_\OA, \Sigma),L)$, for any query pertaining to $\pk_{\USR,b}$, the reduction invokes its ROR challenger to obtain an IBE
|
|
private key for the identity $\vk \neq \vk^\star$ and uses the result to decrypt $\mathbf c_\rec$. For any decryption query involving
|
|
$\pk_{\USR,1-b}$, the reduction can faithfully run the actual decryption algorithm using its trapdoor $\mathbf T_{1-b}$.
|
|
Open queries are answered using $\mathbf T_\OA$ as in the real \textsf{Open} algorithm.
|
|
|
|
When the adversary $\adv$ decides to do so, it queries a challenge for a triple $((\mathbf A_R, \mathbf{u}_R), \mathbf w, L)$ of its choice subject to the constraint
|
|
$\mathbf{u}_R = \mathbf A_R \cdot \mathbf{w}$. At this point, $\bdv$ queries a challenge to
|
|
its own challenger for the message $\mathbf w$ and obtains a ciphertext $\mathbf c$, which is embedded in
|
|
$\mathbf{\Psi}^\star=(\vk^\star, \mathbf c, \mathbf c_\OA^\star, \Sigma^\star)$ while $\mathbf c_\OA^\star$ and $\Sigma^\star$ are generated as
|
|
in Game $3$ (in particular, $\mathbf c_\OA^\star$ encrypts a random string instead of a hash value of $\pk_{\USR,b}$). After the challenge phase, all queries to the proving oracle $\mathcal{P}$ are replied by returning a simulated ZK argument as in Game $3$.
|
|
|
|
When $\adv$ ends, it outputs a bit $b' \in \{0,1\}$. If $b' = b$, the reduction outputs \textsf{Real}. Otherwise, it outputs \textsf{Random}.
|
|
Indeed, if the ROR challenger is playing the real game, we are exactly in Game $4$: we have $\Pr[b'=b | \mathsf{Real}] = \Pr[W_4]$.
|
|
Otherwise, the challenge ciphertext $\mathbf{\Psi}^\star$ is completely independent of $b \in \{0,1\}$
|
|
so that we can only have $b'=b$ with probability $\Pr[b'=b| \mathsf{Random}]=1/2$. It follows that $\advantage{\mathrm{ROR}}{\bdv}(\lambda) \geq | \Pr[W_4] -1/2 |$.
|
|
\end{proof}
|
|
|
|
\subsubsection{Message Secrecy}
|
|
|
|
\begin{theorem} \label{secrecy-thm}
|
|
The scheme provides message secrecy assuming that the $\LWE$ assumption holds and that $\mathcal{OTS}$ is a strongly unforgeable one-time signature.
|
|
% \textnormal{(The proof is presented in Appendix~\ref{proof-secrecy-thm}.)}
|
|
\end{theorem}
|
|
|
|
\begin{proof}
|
|
We proceed via a sequence of games. The first one corresponds to the experiment of Definition \ref{security-def} when the challenger's bit $b$ is $1$ and the
|
|
adversary obtains an actual encryption of the witness $\mathbf{w} \in \{0,1\}^m$ and real proofs at each invocation of the $\mathsf{PROVE}(.)$ oracle. In the last
|
|
game, the adversary $\adv$ is given an encryption of some random plaintext whereas $\mathsf{PROVE}(.)$ returns simulated zero-knowledge arguments which are
|
|
generated a simulator $\mathcal{P}'$ that does not use any witness. In Game $i$, $W_i$ stands for the event that the adversary $\adv$ outputs the bit $b'=1$.
|
|
\smallskip \smallskip
|
|
|
|
\noindent \textbf{Game} $1$: This is the real game, where the challenger feeds $\adv$ with
|
|
public parameters $\param$ containing $ \bar{\mathbf{A}}, \mathbf{U}, \mathbf{V} \in \ZZ_q^{n \times m} $ and
|
|
$\mathbf{F} \in \ZZ_q^{2n \times n \bar{m}k} $. The adversary produces public
|
|
keys $\pk_{\OA} = \mathbf{B}_{\OA} \in \ZZ_q^{n \times \bar{m}}$
|
|
and $\pk_{\GM}= ( \mathbf{A}, \{\mathbf{A}_i\}_{i=0}^{\ell},
|
|
\mathbf{D}_0 , \mathbf{D}_1, \mathbf{D}, \mathbf{u} )$ on behalf of the opening authority and the group manager which are both under its control.
|
|
The challenger and $\adv$ run an execution of the $\mathsf{JOIN}$ protocol
|
|
which allows $\adv$ to register and certify the public key $\pk_{\USR}=\mathbf{B}_{\USR} \in \ZZ_q^{n \times \bar{m}}$ of some
|
|
honest receiver chosen by the challenger. Then, the adversary $\adv$ makes a polynomial number of
|
|
decryption queries which the challenger faithfully handles using the private key $\sk_{\USR} = \mathbf{T}_{\USR} \in \ZZ^{m \times \bar{m}} $
|
|
for which $\mathbf{B}_{\USR} \cdot \mathbf{T}_{\USR} = \mathbf{0}^{n \times \bar{m}} $. At some point, the adversary $\adv$ outputs a triple $((\mathbf{A}_R,\mathbf{u}_R),\mathbf{w},L)$ such
|
|
that $\mathbf{u}_R= \mathbf{A}_R \cdot \mathbf{w} \bmod q$, with $\mathbf{A}_R \in \ZZ_p^{n \times m}$, $\mathbf{u}_R \in \ZZ_q^n$ and $\mathbf{w} \in \{0,1\}^m$.
|
|
At this point, the challenger generates a challenge ciphertext
|
|
$\Psi^\star= (\vk^\star,\mathbf{c}_{\rec}^\star, \mathbf{c}_{\oa}^\star, \Sigma^\star)$ consisting of a group encryption of
|
|
the real witness $\mathbf{w}$ under $\pk_{\USR} =\mathbf{B}_{\USR}$. Then, the adversary obtains a polynomial number of proofs $\pi_{\Psi^\star}^\star$ related to the
|
|
challenge ciphertext
|
|
$\Psi^\star$ and is granted further access to the decryption oracle under the obvious
|
|
restrictions. When $\adv$ halts, it
|
|
outputs a bit $b' \in \{0,1\}$. % and we call $W_1$ the event that $b'=1$.
|
|
\smallskip \smallskip
|
|
|
|
\noindent \textbf{Game} $2$: In this game, we modify the $\mathsf{DEC}(.)$ oracle and have the challenger reject any ciphertext of the form
|
|
$\Psi= (\vk,\mathbf{c}_{\rec}, \mathbf{c}_{\oa}, \Sigma)$
|
|
such that $\vk=\vk^\star$
|
|
(note that $\vk^\star$ can be generated at the outset of the game w.l.o.g.).
|
|
Clearly Game $2$ is identical to Game $1$ until the event that the challenger rejects a ciphertext that would not have been rejected in Game $1$.
|
|
This can only occur if $\adv$ is able to break the strong unforgeability of the one-time signature $\mathcal{OTS}$.
|
|
As in the proof of Theorem~\ref{anon-thm}, we have $|\Pr[W_2]-\Pr[W_1]| \leq \mathbf{Adv}^{\mathrm{ots}}(\lambda)$, which is negligible
|
|
if $\mathcal{OTS}$ is strongly unforgeable.
|
|
\smallskip \smallskip
|
|
|
|
\noindent \textbf{Game} $3$: We now modify the generation of proofs
|
|
$\pi_{\Psi^\star}^\star$. Instead of generating them using the witnesses used in the generation of $\Psi^\star$, we rely on
|
|
the zero-knowledge simulator of the argument system of \cref{sse:stern-abstraction} at each invocation
|
|
of $\mathsf{PROVE}^b_{\mathcal{P},\mathcal{P}'}$ after the challenge phase (note that, since we assume trusted public parameters, the simulator can use techniques \cite{Dam00} to achieve statistically
|
|
perfect simulation without increasing the number of rounds). The statistical ZK property of the argument system ensures that this change will remain unnoticed, even in the
|
|
view of an all powerful adversary: we have
|
|
$|\Pr[W_3]-\Pr[W_2] | \in \mathsf{negl}(\lambda)$. From now onwards, the random coins $coins_{\mathbf{\Psi}}^\star=\big( \mathbf{s}_{\rec}^\star, \mathbf{R}_{\rec}^\star , \mathbf{x}_{\rec}^\star, \mathbf{y}_{\rec}^\star, \mathbf{s}_{\oa}^\star, \mathbf{R}_{\oa}^\star ,\mathbf{x}_{\oa}^\star, \mathbf{y}_{\oa}^\star \big) $ are no longer used by the $\mathsf{PROVE}$ oracle.
|
|
\smallskip \smallskip
|
|
|
|
\noindent \textbf{Game} $4$: In the generation of $\Psi^\star$, we
|
|
set $\mathbf{c}_{\rec}^\star$ as an encryption of a random element of $\ZZ_p^m$. Since
|
|
the random encryption coins $ \mathbf{s}_{\rec}^\star, \mathbf{R}_{\rec}^\star , \mathbf{x}_{\rec}^\star, \mathbf{y}_{\rec}^\star $ are not used in Game $3$, Lemma \ref{ABB-simple} gives a
|
|
simple
|
|
reduction showing that
|
|
any
|
|
significant change in $\adv$'s behavior would imply a selective adversary against the ABB identity-based encryption scheme.
|
|
The result of
|
|
\cite{ABB10} tells us that, under the $\LWE$ assumption, Game $4$ is computationally indistinguishable from Game $3$ in the adversary's view: we have
|
|
$|\Pr[W_4]-\Pr[W_3]| \leq
|
|
\mathbf{Adv}^{\mathsf{LWE}}(\lambda) $.
|
|
\smallskip \smallskip
|
|
|
|
\noindent \textbf{Game} $5$: We bring a last modification to the $\mathsf{DEC}(.)$
|
|
oracle and now refrain from applying the rejection rule of Game $2$. If
|
|
$\mathcal{OTS}$ is strongly unforgeable, the distance $|\Pr[W_5]-\Pr[W_4]|
|
|
\leq \mathbf{Adv}^{\mathrm{ots}}(\lambda) $ must be negligible.
|
|
\medskip
|
|
|
|
In the last game, the oracle $\mathsf{PROVE}(.)$
|
|
does not need to know any witness. It thus mirrors the experiment of Definition \ref{security-def} where the
|
|
challenger's bit is $b=0$. Putting everything altogether, we get
|
|
$|\Pr[W_5]-\Pr[W_1]| \in \mathsf{negl}(\lambda) $, which yields the claimed result.
|
|
\end{proof}
|
|
|
|
\begin{lemma} \label{ABB-simple}
|
|
Any PPT adversary that can distinguish Game $4$ from Game $3$ implies a selective adversary against the ABB IBE scheme.
|
|
\end{lemma}
|
|
|
|
\begin{proof}
|
|
Let us assume a $\ppt$ adversary $\adv$ such that $\varepsilon = \bigl| \Pr[W_4] - \Pr[W_3] \bigr|$ is noticeable. We use $\adv$ to construct a PPT
|
|
adversary $\bdv$ that breaks the IND-sID-CPA security
|
|
%(as defined in Definition~\ref{de:IND-sID-CPA})
|
|
of the ABB scheme, which would contradict the $\LWE$ assumption, as established
|
|
in~\cite[Th. 23]{ABB10}.
|
|
|
|
At the very beginning of the IND-sID-CPA game, the reduction $\bdv$ generates a one-time signature key pair $(\sk^\star, \vk^\star)$ and hands $\vk^\star$ to its selective security challenger as the target identity under which the challenge ciphertext will later be computed. In response, $\bdv$ receives the public parameters
|
|
$$\mathsf{PP} = (\bar{\mathbf A}, \mathbf B, \mathbf U) \in \Zq^{n \times m} \times \Zq ^{n \times \bar m} \times \Zq^{n \times m}$$ from its IBE challenger.
|
|
|
|
The reduction then runs the missing steps of the actual $\Setup_{\mathsf{init}}$ algorithm: namely, $\bdv$ samples $\mathbf F \sample \U(\Zq^{2m \times n\bar{m}k}), \mathbf V \sample \U(\Zq^{n \times m})$ and generates $\compar$ before sending the common public parameters
|
|
$$\param = \bigl\{\lambda, n, q, k, m, B, \chi, \sigma, \beta, \ell, \kappa, \mathcal{OTS}, \compar, \mathsf{FRD}, \bar{\mathbf{A}}, \mathbf{G}, \mathbf{F}, \mathbf{U}, \mathbf{V} \bigr\}$$
|
|
to the adversary $\adv$.
|
|
|
|
At this point, the adversary $\adv$ chooses the public keys $\pk_\OA = \mathbf B_\OA \in \Zq^{n \times \bar{m}}$ and $\pk_\GM = (\mathbf A, \{ \mathbf A_i \}_{i=0}^\ell, \mathbf D_0, \mathbf D_1, \mathbf D, \mathbf{u})$ on
|
|
behalf of the opening authority and the group manager. It also starts an execution of the joining protocol in which the reduction $\bdv$
|
|
defines $\pk_\USR = \mathbf B \in \Zq^{n \times \bar m}$ as the honest receiver's public key, where $\mathbf B \in \ZZ_q^{n \times \bar{m}}$ is taken from the public parameters
|
|
$\mathsf{PP}$ supplied by its IBE challenger. Note that $\pk=\mathbf{B} \in \ZZ_q^{n \times \bar{m}}$ is distributed as a real key in $\adv$'s view.
|
|
This public key is certified by $\mathbf A$ which controls the $\GM$.
|
|
|
|
In the next stage, $\adv$ makes a number of decryption queries for ciphertexts of the form $\mathbf{\Psi} = (\vk, \mathbf c_\rec, \mathbf c_\OA, \Sigma)$. To answer these,
|
|
the reduction invokes its IBE challenger so as to obtain an IBE private key $\mathbf E_\vk \in \ZZ^{(m+\bar m) \times m}$ for the identity
|
|
$\vk \neq \vk^\star$. The resulting $\mathbf E_\vk$ is used it to IBE-decrypt $\mathbf c_\rec$ and return the corresponding witness $\mathbf w$ to $\mathbf A$ .
|
|
|
|
At some point, the adversary $\adv$ queries a challenge ciphertext by outputting a triple $((\mathbf A_R, \mathbf u_R), \mathbf w, L)$ such that $\mathbf{w} \in \{0,1\}^m$ satisfies
|
|
$\mathbf u_R = \mathbf A_R \cdot \mathbf{w} \bmod q$. Then, the reduction $\bdv$ requests a challenge ciphertext $\mathbf c^\star_\rec$ to its IBE
|
|
challenger by sending it the messages $\mathbf m_1 = \mathbf{w} \in \{0,1\}^m$ and $\mathbf m_0 \sample \U(\{0,1\}^m)$. The resulting ciphertext $\mathbf c^\star_\rec$
|
|
is embedded in $\mathbf{\Psi}^\star = (\vk^\star, \mathbf c_\rec^\star, \mathbf c_\OA^\star, \Sigma^\star)$ by faithfully computing
|
|
$\mathbf c_\OA^\star$ and $\Sigma^\star$ as in the actual $\textsf{Enc}$ algorithm.
|
|
|
|
After the challenge phase, $\adv$ keeps sending decryption queries for ciphertexts $\Psi^\star$ containing one-time verification keys
|
|
$\vk \neq \vk^\star$ and these decryption queries are answered as before. In addition, $\adv$ is granted access to the stateful oracle $\mathsf{PROVE}^b_{\mathcal{P},\mathcal{P}'}$.
|
|
Recall that, from Game $3$ onwards, all these queries are answered by returning simulated zero-knowledge arguments.
|
|
%The following proof queries are answered as in Game~3, meaning that they are simulated by the zero-knowledge simulator of the underlying argument system.
|
|
Eventually $\adv$ outputs a bit $b' \in \{0,1\}$ which is also returned by $\bdv$ to its own challenger.
|
|
|
|
If the IBE challenger provides a challenge $\mathbf c^\star_\rec$ that encrypts a random message (i.e., by encrypting $\mathbf{m}_0$), then we are exactly in the setting of Game $4$.
|
|
In the even that $\mathbf c^\star_\rec$ rather encrypts $\mathbf{m}_1=\mathbf{w} \in \{0,1\}^m$, $\adv$'s view is exactly the same as in Game $3$. If we denote by
|
|
\textsf{Random} (resp. \textsf{Real}) the event that the IBE challenger chooses to encrypt $\mathbf m_0$ (resp. $\mathbf m_1$), the advantage of the reduction $\bdv$ as an IND-sID-CPA
|
|
adversary is
|
|
\begin{align*}
|
|
\advantage{\textrm{sID-CPA}}{\bdv}(\lambda) &= \left| \Pr[b'=1 | \textsf{Real}] - \Pr[b'=1 | \mathsf{Random}] \right| = \left|\Pr[W_3] - \Pr[W_4] \right|\\
|
|
&= \varepsilon,
|
|
\end{align*}
|
|
which concludes our proof.
|
|
\end{proof}
|
|
|
|
|
|
|
|
|
|
%\subsection{ Soundness (Proof of Theorem~\ref{soundness-thm})} \label{proof-soundness-thm}
|
|
|
|
|
|
|
|
\subsubsection{Soundness}
|
|
|
|
|
|
\begin{theorem} \label{soundness-thm}
|
|
The scheme provides soundness under the $\SIS$ assumption.
|
|
%\textnormal{(The proof is detailed in Appendix~\ref{proof-soundness-thm}.)}
|
|
\end{theorem}
|
|
|
|
|
|
\begin{proof}
|
|
To prove the result, we observe that, in order to break the soundness property, the adversary must come up with a relation
|
|
$\pk_{\mathcal{R}}=(\mathbf{A}_{{R}},\mathbf{u}_{R}) \in \ZZ_q^{n \times m} \times \ZZ_q^n$, a ciphertext
|
|
$\Psi^\star= (\vk^\star,\mathbf{c}_{\rec}^\star, \mathbf{c}_{\oa}^\star, \Sigma^\star)$, a label $L$ and produce a convincing proof $\pi_{\Psi^\star}$ such that either
|
|
\begin{enumerate}
|
|
\item $\mathbf{c}_{\oa}^\star$ does not decrypt to a string $\mathbf{h} \in \{0,1\}^m$ such that $\mathbf{h}_{\USR} = \mathbf{H}_{2n,q-1} \cdot \mathbf{h} \in \ZZ_q^{2n}$ coincides
|
|
with $\mathbf{h}_{\USR} = \mathbf{F} \cdot \mathsf{mdec}_{n,m,q}(\mathbf{B}_{\USR}^T)$ for some $\pk_{\USR}=\mathbf{B}_{\USR} \in \ZZ_q^{n \times \bar{m}}$ appearing in $\mathsf{database}$.
|
|
\item $\mathbf{c}_{\oa}^\star$ opens to a certified public key $\pk_{\USR}=\mathbf{B}_{\USR} \in \ZZ_q^{n \times \bar{m}}$, which belongs to $\mathsf{database}$ (and for which a certificate
|
|
was issued), but $\mathbf{B}_{\USR} $ is outside the language $\mathcal{PK}$ of valid public keys. This case is immediately ruled out
|
|
by the density of the public key space.
|
|
Namely, all matrices
|
|
$\mathbf{B}_{\USR} \in \ZZ_q^{n \times \bar{m}} $ are potentially valid public keys as there always exist a small-norm matrix $\mathbf{T}_{\USR} \in \ZZ^{m \times \bar{m}}$
|
|
such that $\mathbf{B}_{\USR} = \bar{\mathbf{A}} \cdot \mathbf{T}_{\USR} \bmod q$.
|
|
\item $\mathbf{c}_{\oa}^\star$ opens to a certified key $\pk_{\USR}=\mathbf{B}_{\USR}$ for which
|
|
$\Psi^\star= (\vk^\star,\mathbf{c}_{\rec}^\star, \mathbf{c}_{\oa}^\star, \Sigma^\star)$ is not a valid encryption of $\mathbf{w} \in \{0,1\}^m$ such that
|
|
$\mathbf{u}_R= \mathbf{A}_R \cdot \mathbf{w} \bmod q$.
|
|
\item The opening algorithm fails to uniquely identify the receiver. This occurs if $\mathbf{c}_{\oa}^\star$ decrypts to a string $\mathbf{h} \in \{0,1\}^m$ such that $\mathbf{h}_{\USR}' = \mathbf{H}_{2n,q-1} \cdot \mathbf{h} \in \ZZ_q^{2n}$ corresponds to
|
|
at least two distinct public keys $\mathbf{B}_{\USR,0} ,\mathbf{B}_{\USR,1} \in \ZZ_q^{n \times \bar{m}}$ which satisfy
|
|
$$\mathbf{h}_{\USR}' = \mathbf{F} \cdot \mathsf{mdec}_{n ,\bar{m},q}(\mathbf{B}_{\USR,0}^T ) \bmod q=\mathbf{F} \cdot \mathsf{mdec}_{n ,\bar{m},q}(\mathbf{B}_{\USR,1}^T ) \bmod q. $$
|
|
Since $\mathsf{mdec}_{n,\bar{m},q}(.) : \ZZ_q^{\bar{m} \times n} \rightarrow \{0,1\}^{n \bar{m} k}$ is an injective function, the above equality necessarily implies a
|
|
collision for the $\mathsf{SIS}$-based hash function built upon $\mathbf{F} \in \ZZ_q^{2n \times n \bar{m} k}$: namely,
|
|
$$ \mathsf{mdec}_{n ,\bar{m},q}(\mathbf{B}_{\USR,0}^T ) - \mathsf{mdec}_{n ,\bar{m},q}(\mathbf{B}_{\USR,1}^T ) ~~\in \{-1,0,1\}^{n\bar{m} k} $$
|
|
is a short non-zero vector of $\Lambda_q^\perp (\mathbf{F})$.
|
|
\end{enumerate}
|
|
Having shown that cases \textit{b} and \textit{d} cannot occur if the $\mathsf{SIS}$ assumption holds, we only need to consider cases \textit{a} and \textit{c}. The computational soundness of the argument system ensures that, by replaying
|
|
the soundness adversary a sufficient number of times,
|
|
the knowledge extractor will be able to extract either:
|
|
(i) A breach in the computational soundness of the argument system and thus the binding property of the commitment scheme $\mathsf{COM}$ (which relies on the $\mathsf{SIS}$ assumption with the commitment scheme of \cite{KTX08}). Note that this situation covers case (\textit{c}.) above.
|
|
(ii) A set of witnesses
|
|
\begin{eqnarray*}
|
|
\left\{
|
|
\begin{array}{l}
|
|
\tau \in \{0,1\}^\ell, ~\mathbf{d}=[\mathbf{d}_1^T | \mathbf{d}_2^T ]^T \in [-\beta,\beta]^{2m},~\mathbf{r} \in [-\beta,\beta]^m \\
|
|
\mathbf{t}_{\USR} \in \{0,1\}^{m},~\mathbf{w}_{\USR} \in \{0,1\}^{\bar{m}} \\
|
|
\mathbf{b}_{\USR} \in \{0,1\}^{n \bar{m} k}, ~\mathbf{s}_{0,\rec} \in \{0,1\}^{nk}, ~
|
|
\mathbf{z}_{\mathbf{\Psi}} \in \{0,1\}^{4n \bar{m} k^2}
|
|
\\
|
|
\mathbf{x}_{\rec}, ~\mathbf{y}_{\rec} \in [-B,B]^m, ~ \mathbf{z}_{\rec} \in [-\beta mB,\beta mB]^{\bar{m}} , ~\mathbf{w} \in \{0,1\}^m, \\
|
|
\mathbf{s}_{\oa} \in \{0,1\}^{nk},~\mathbf{x}_{\oa}, ~\mathbf{y}_{\oa} \in [-B,B]^m, ~\mathbf{z}_{\oa} \in [-\beta mB,\beta mB]^{\bar{m}}
|
|
\end{array}
|
|
\right.
|
|
\end{eqnarray*}
|
|
satisfying relations \eqref{eq:big-system-main-scheme}.
|
|
%(\ref{rel-un})-(\ref{rel-trois}).
|
|
Given that witnesses $\tau \in \{0,1\}^\ell$, $\mathbf{d} \in [-\beta,\beta]^{2m}$, $\mathbf{r} \in [- \beta,\beta]^m$ and $\mathbf{t}_{\USR} \in \{0,1\}^m$ satisfy \eqref{eq:big-system-main-scheme}, %(\ref{rel-un}),
|
|
it comes that $(\tau,\mathbf{d},\mathbf{r})$ form a valid signature for the message $\mathbf{t}_{\USR} \in \{0,1\}^m$. At this point, case \textit{a} implies that no matrix
|
|
$\mathbf{B}_{\USR} \in \ZZ_q^{n \times \bar{m}} $ of
|
|
$\mathsf{database}$ decomposes to a string $\mathbf{h}_\USR \in \{0,1\}^{n\bar{m}k}$ such that $\mathbf{t}_{\USR} = \mathsf{vdec}_{n,q-1}(\mathbf{F} \cdot \mathbf{h}_{\USR} \bmod q )$ was
|
|
signed by the reduction during an execution of $\mathsf{JOIN}$. This implies that
|
|
the pair
|
|
$\big(\mathbf{t}_{\USR} , (\tau,\mathbf{d},\mathbf{r}) \big)$ forms a forgery for the $\mathsf{SIS}$-based signature scheme of Section~\ref{se:gs-lwe-sigep}. The reduction is straightforward
|
|
and omitted.
|
|
\end{proof}
|
|
|