text:
\section{Introduction}

\IEEEPARstart{P}{ublic-key} encryption with keyword search (PEKS), introduced by Boneh \emph{et al.} in \cite{BCO04}, has the advantage that anyone who knows the receiver's public key can upload keyword-searchable ciphertexts to a server. The receiver can delegate the keyword search to the server. More
specifically, each sender separately encrypts a file and its extracted keywords and sends the resulting ciphertexts to a server; when the receiver wants to retrieve the files containing a specific keyword, he delegates a keyword search trapdoor to the server; the server finds the encrypted files containing the queried keyword without knowing the original files or the keyword itself, and returns the corresponding encrypted files to the receiver; finally, the receiver decrypts these encrypted files\footnote{Since the encryption of the original files can be separately processed with an independent public-key encryption scheme as in \cite{BCO04}, we only describe the encryption of the keywords (unless otherwise
clearly stated in the paper).}. The authors of PEKS \cite{BCO04} also presented semantic security against chosen keyword attacks (SS-CKA) in the sense that the server cannot distinguish the ciphertexts of the keywords of its choice before observing the corresponding keyword search trapdoors. It seems an appropriate security notion, especially if the keyword space has no high min-entropy. Existing semantically secure PEKS schemes take search time linear with the total number of all ciphertexts. This makes retrieval from large-scale databases prohibitive. Therefore, more efficient searchable public-key encryption is crucial for practically deploying PEKS schemes.

One of the prominent works to accelerate the search over encrypted keywords in the public-key setting is deterministic
encryption introduced by Bellare \emph{et al}. in \cite{BBN07}. An encryption scheme is deterministic if the encryption algorithm is deterministic. Bellare \emph{et al}. \cite{BBN07} focus on enabling search over encrypted keywords to be
as efficient as the search for unencrypted keywords, such that a ciphertext containing a given keyword can be retrieved
in time complexity logarithmic in the total number of all ciphertexts. This is reasonable because the encrypted keywords
can form a tree-like structure when stored according to their binary values. However, deterministic encryption has two inherent limitations. First, keyword privacy can be guaranteed only
for keywords that are \emph{a priori} hard-to-guess by the adversary (\emph{i.e.}, keywords with high
min-entropy to the adversary); second, certain information of a message leaks inevitably via the ciphertext of
the keywords since the encryption is deterministic. Hence, deterministic encryption is only applicable in special scenarios.

\subsection{Our Motivation and Basic Ideas}

We are interested in providing highly efficient search performance without
sacrificing semantic security in PEKS. Observe that a keyword space is usually of no high min-entropy in many
scenarios. Semantic security is crucial to guarantee keyword privacy in such
applications. Thus the linear search complexity of existing schemes is the major obstacle to their adoption.
Unfortunately, the linear complexity seems to be inevitable because the server has to scan and test each ciphertext, due to the fact that these ciphertexts (corresponding to the same keyword or not) are indistinguishable to the server.

\begin{figure}
\centering
\includegraphics [width=0.48\textwidth,height=0.25\textheight]{Mainidea}
\caption{Hidden star-like structure formed by keyword searchable ciphertexts.
(The dashed arrows denote the hidden relations. $Enc(W_i)$ denotes the searchable ciphertext of keyword $W_i$.)}\label{F.Mainidea}
\end{figure}

A closer look shows that there is still space to improve search performance in PEKS without sacrificing semantic security if one can organize the ciphertexts with elegantly designed but hidden relations. Intuitively, if the keyword-searchable ciphertexts have a hidden star-like structure, as shown in Figure \ref{F.Mainidea}, then search over ciphertexts containing a specific keywords may be accelerated. Specifically, suppose all ciphertexts of the same keyword form a chain by the correlated hidden relations, and also a hidden relation exists from a public \emph{Head} to the first ciphertext of each chain. With a keyword search trapdoor and the \emph{Head}, the server seeks out the first matching ciphertext via the corresponding relation from the \emph{Head}. Then another relation can be disclosed via the found ciphertext and guides the searcher to seek out the next matching ciphertext. By carrying on in this way, all matching ciphertexts can be found. Clearly, the search time depends on the actual number of the ciphertexts containing the queried keyword, rather than on the total number of all ciphertexts.

To guarantee appropriate security, the hidden star-like structure should
preserve the semantic security of keywords, which indicates that partial relations are disclosed only when the corresponding keyword search trapdoor is known. Each sender should be able to generate the keyword-searchable ciphertexts with the hidden star-like structure by the receiver's public-key; the server having a keyword search trapdoor should be able to disclose partial relations, which is related to all matching ciphertexts. Semantic security is preserved 1) if no keyword search trapdoor is
known, all ciphertexts are indistinguishable, and no information is leaked about the structure, and 2) given a keyword search trapdoor, only the corresponding relations can be disclosed, and the matching ciphertexts leak no information about the rest of ciphertexts, except the fact that the rest do not contain the queried keyword.

\subsection{Our Work}

We start by formally defining the concept of Searchable Public-key Ciphertexts with Hidden Structures (SPCHS) and its semantic security. In this new concept, keyword-searchable ciphertexts with their hidden structures can be generated in the public key setting; with a keyword search trapdoor, partial relations can be disclosed to guide the discovery of all matching ciphertexts. Semantic security is defined for both the keywords and the hidden structures. It is worth noting
that this new concept and its semantic security are suitable for keyword-searchable ciphertexts with any kind of hidden structures. In contrast, the concept of traditional PEKS does not contain any hidden structure among the PEKS ciphertexts; correspondingly, its semantic security is only defined for the keywords.

Following the SPCHS definition, we construct a simple SPCHS from scratch in the random oracle (RO) model. The scheme generates keyword-searchable ciphertexts with a hidden star-like structure. The search performance mainly depends on the actual number of the ciphertexts containing the queried keyword. For security, the scheme is proven semantically secure based on the Decisional Bilinear Diffie-Hellman (DBDH) assumption \cite{BB04} in the RO model.

We are also interested in providing a generic SPCHS construction to generate keyword-searchable ciphertexts with a hidden star-like structure. Our generic SPCHS is inspired by several interesting observations on Identity-Based Key Encapsulation Mechanism (IBKEM). In IBKEM, a sender encapsulates a key $K$ to an intended receiver $ID$. Of course, receiver $ID$ can decapsulate and obtain $K$, and the sender knows that receiver $ID$ will obtain $K$. However, a non-intended receiver $ID^\prime$ may also try to decapsulate and obtain $K^\prime$. We observe that, (1) it is usually the case that $K$ and $K^\prime$ are independent of each other from the view of the receivers, and (2) in some IBKEM the sender may also know $K^\prime$ obtained by receiver $ID^\prime$. We refer to the former property as \emph{collision freeness} and to the latter as \emph{full-identity malleability}. An IBKEM scheme is said to be \emph{collision-free full-identity malleable} if it possesses both properties.

We build a generic SPCHS construction with Identity-Based Encryption (IBE) and collision-free full-identity malleable IBKEM. The resulting SPCHS can generate keyword-searchable ciphertexts with a hidden star-like structure. Moreover, if both the underlying IBKEM and IBE have semantic security and anonymity (\emph{i.e.} the privacy of receivers' identities), the resulting SPCHS is semantically secure. As there are known IBE schemes \cite{BW06,G06,AG09,D10} in both the RO model and the standard model, an SPCHS construction is reduced to collision-free full-identity malleable IBKEM with anonymity. In 2013, Abdalla \emph{et al.} proposed several IBKEM schemes to construct Verifiable Random Functions\footnote{VRF behaves like a pseudo-random function but one can verify that the output was
pseudo-random.} (VRF) \cite{ACF13}. We show that one of these IBKEM schemes is anonymous and collision-free full-identity malleable in the RO model. In \cite{FHPS13}, Freire \emph{et al.}  utilized the ``approximation'' of multilinear maps \cite{GGH13} to construct a standard-model version of Boneh-and-Franklin (BF) IBE scheme \cite{BF01}. We transform this IBE scheme into a collision-free full-identity malleable IBKEM scheme with semantic security and anonymity in the standard model. Hence, this new IBKEM scheme allows us to build SPCHS schemes secure in the standard model with the same search performance as the previous SPCHS construction
from scratch
in the RO model.

\subsection{Other Applications of Collision-Free Full-Identity Malleable IBKEM}

We note that collision-free full-identity malleable IBKEM is of independent interest. In addition to being a building block for the generic SPCHS construction, it may also find other applications, as outlined in the sequel.

\textbf{Batch identity-based key distribution.} A direct application of collision-free full-identity malleable IBKEM is to achieve batch identity-based key distribution. In such an application, a sender would like to distribute different secret session keys to multiple receivers so that each receiver can only know the session key to himself/herself. With collision-free full-identity malleable IBKEM, a sender just needs to broadcast an IBKEM encapsulation in the identity-based cryptography setting, e.g., encapsulating a session key $K$ to a single user $ID$. According to the collision-freeness of IBKEM, each receiver $ID'$ can decapsulate and obtain a different key $K'$ with his/her secret key in the identity based crypto-system. Due to the full-identity malleability, the sender knows the decapsulated keys of all the receivers. In this way, the sender efficiently shares different session keys with different receivers, at the cost of only a single encapsulation and one pass of communication.

\textbf{Anonymous identity-based broadcast encryption.}  A slightly more complicated application is anonymous identity-based broadcast encryption with efficient decryption. An analogous application was proposed respectively by Barth \emph{et al.} \cite{BBW06} and Libert \emph{et al.} \cite{LPQ12} in the traditional public-key setting. With collision-free full-identity malleable IBKEM, a sender generates an identity-based broadcast ciphertext $\langle C_1$, $C_2$, $(K_1^1||SE(K_2^1,F_1))$, $...$, $(K_1^N||SE(K_2^N,F_N))\rangle$,  where $C_1$ and $C_2$ are two IBKEM encapsulations, $K_1^i$ is the encapsulated key in $C_1$ for receiver $ID_i$, $K_2^i$ is the encapsulated key in $C_2$ for receiver $ID_i$, and $SE(K_2^i,F_i)$ is the symmetric-key encryption of file $F_i$ using the encapsulated key $K_2^i$. In this ciphertext, the encapsulated key $K_1^i$ is not used to encrypt anything. Indeed, it is an index to secretly inform receiver $ID_i$ on which part of this ciphertext belongs to him. To decrypt the encrypted file $F_i$, receiver $ID_i$ decapsulates and obtains $K_1^i$ from $C_1$, finds out $K_1^i||SE(K_2^i,F_i)$ by matching $K_1^i$, and finally extracts $F_i$ with the decapsulated key $K_2^i$ from $C_2$. It can be seen that the application will work if the IBKEM is collision-free full-identity malleable. It preserves the anonymity of receivers if the IBKEM is anonymous. Note that trivial anonymous broadcast encryption suffers decryption cost linear with the number of the receivers. In contrast, our anonymous identity-based broadcast encryption enjoys constant decryption cost, plus logarithmic complexity to search the matching index in a set $(K_1^1,...,K_1^N)$ organized by a certain partial order, e.g., a dictionary order according to their binary representations.

\subsection{Related Work}

Search on encrypted data has been extensively investigated in recent years. From a cryptographic perspective, the
existing works fall into two categories, {\em i.e.}, symmetric searchable encryption \cite{CGK06} and public-key
searchable encryption.

Symmetric searchable encryption is occasionally referred to as symmetric-key encryption with keyword search (SEKS).
This primitive was introduced by Song \emph{et al.} in \cite{SWP00}. Their instantiated scheme takes search time linear with the size of the database. A number of efforts \cite{G03,BC04,AKSX04,CM05,BCLN09} follow this research line and
refine Song \emph{et al.}'s original work. The SEKS scheme due to Curtmola \emph{et al}. \cite{CGK06} has been proven to be semantically secure against an
adaptive adversary. It allows the search to be processed in logarithmic time, although the keyword search trapdoor has
length linear with the size of the database. In addition to the above efforts devoted to either provable security or
better search performance, attention has recently been paid to achieving versatile SEKS schemes as follows. The works
in \cite{CGK06,BDDY08} extend SEKS to a multi-sender scenario. The work in \cite{LWWCRL10} realizes fuzzy keyword
search in the SEKS setting. The work in \cite{WBDS04} shows practical applications of SEKS and employs it to realize
secure and searchable audit logs. Chase \emph{et al.} \cite{CK10} proposed to encrypt structured data and a secure method to search these data. To support the dynamic update of the encrypted data, Kamara \emph{et al.}  proposed the dynamic searchable symmetric encryption in \cite{KPR12} and further enhanced its security in \cite{KP13} at the cost of large index. The very recent work \cite{CJJJKRS14} due to Cash \emph{et al.} simultaneously achieves strong security and high efficiency.

Following the seminal work on PEKS, Abdalla\emph{ et al}. \cite{ABC05} fills some gaps w.r.t. consistency for PEKS
and deals with the transformations among primitives related to PEKS. Some efforts have also
been devoted to make PEKS versatile. The work of this kind includes conjunctive search
\cite{PKL04,GSW04,BKM05,HL07,RT07,BSS08}, range search \cite{BCP06,SBC07,BW07}, subset search \cite{BW07}, time-scope search \cite{ABC05,DMR04}, similarity search \cite{CMWYZ10}, authorized search \cite{TC11,INH11}, equality test between heterogeneous ciphertexts \cite{YTHW10}, and fuzzy keyword search \cite{XHW13}. In addition, Arriaga et al. \cite{ATR14} proposed a PEKS scheme to keep the privacy of keyword search trapdoors.

In the above PEKS schemes, the search complexity takes time linear with the number of all ciphertexts. In [24],  an oblivious generation of keyword search trapdoor is to  maintain the privacy of the keyword against a curious trapdoor generation. A chain-like structure is described to speed up the search on encrypted keywords. One may note that the chain in \cite{CKRS09} cannot be fully hidden to the server and leaks the frequency of the keywords (see Supplemental Materials A for details). To realize an efficient keyword search, Bellare \emph{et al.} \cite{BBN07} introduced
deterministic public-key encryption (PKE) and formalized a security notion ``as strong as possible'' (stronger than
onewayness but weaker than semantic security). A deterministic searchable encryption scheme allows efficient keyword search as if the keywords were not
encrypted. Bellare \emph{et al.} \cite{BBN07} also presented a deterministic PKE scheme (\emph{i.e.}, RSA-DOAEP) and a
generic transformation from a randomized PKE to a deterministic PKE in the random oracle model. Subsequently,
deterministic PKE schemes secure in the standard model were independently proposed by Bellare \emph{et al.}
\cite{BFNR08} and Boldyreva \emph{et al.} \cite{BFN08}. The former uses general complexity assumptions and the
construction is generic, while the latter exploits concrete complexity assumptions and has better efficiency. Brakerski \emph{et al.} \cite{BS11} proposed the deterministic PKE schemes with better security, although these schemes are still not semantically secure. So far, deterministic PEKS schemes can guarantee semantic security only if the keyword space has a high
min-entropy. Otherwise, an adversary can extract the encrypted keyword by a simple encrypt-and-test attack. Hence, deterministic PEKS schemes are applicable to applications where the keyword space is of a high min-entropy.

\subsection{Organization of this article}
The remaining sections are as follows. Section \ref{S.SPCHS.Concept} defines SPCHS and its semantic security. A simple SPCHS scheme is constructed in Section \ref{S.SPCHS.Instance}. A general construction of SPCHS is given in Section \ref{S.SPCHS.Generic}. Two collision-free full-identity malleable IBKEM schemes, respectively in the RO and standard models, are introduced in Section \ref{S.IBKEM.Instances}. Section \ref{S.Conclusion} concludes this paper.

\section{Modeling SPCHS}\label{S.SPCHS.Concept}

We first explain intuitions behind SPCHS. We describe a hidden structure formed by ciphertexts as $(\mathbb{C},\mathbf{Pri},\mathbf{Pub})$, where $\mathbb{C}$ denotes the set of all ciphertexts, $\mathbf{Pri}$ denotes the hidden relations among $\mathbb{C}$, and $\mathbf{Pub}$ denotes the public parts. In case there is more than one hidden structure formed by ciphertexts, the description of multiple hidden structures formed by ciphertexts can be $(\mathbb{C},(\mathbf{Pri}_1,\mathbf{Pub}_1),...,(\mathbf{Pri}_N,\mathbf{Pub}_N))$, where $N\in\mathbb{N}$. Moreover, given $(\mathbb{C},\mathbf{Pub}_1,...,\mathbf{Pub}_N)$ and $(\mathbf{Pri}_1,...,\mathbf{Pri}_N)$ except $(\mathbf{Pri}_i,\mathbf{Pri}_j)$ (where $i\neq j$), one can neither learn anything about $(\mathbf{Pri}_i,\mathbf{Pri}_j)$ nor decide whether a ciphertext is associated with $\mathbf{Pub}_i$ or $\mathbf{Pub}_j$.

In SPCHS, the encryption algorithm has two functionalities. One is to encrypt a keyword, and the other is to generate a hidden relation, which can associate the generated ciphertext to the hidden structure. Let $(\mathbf{Pri},\mathbf{Pub})$ be the hidden structure. The encryption algorithm must take $\mathbf{Pri}$ as input, otherwise the hidden relation cannot be generated since $\mathbf{Pub}$ does not contain anything about the hidden relations. At the end of the encryption procedure, the $\mathbf{Pri}$ should be updated since a hidden relation is newly generated (but the specific method to update $\mathbf{Pri}$ relies on the specific instance of SPCHS). In addition, SPCHS needs an algorithm to initialize $(\mathbf{Pri},\mathbf{Pub})$ by taking the master public key as input, and this algorithm will be run before the first time to generate a ciphertext. With a keyword search trapdoor, the search algorithm of SPCHS can disclose partial relations
to guide the discovery of the ciphertexts containing the queried keyword with the hidden structure.

\begin{definition}[SPCHS]\label{D.SPCHS.Concept}
SPCHS consists of five algorithms:
\begin{itemize}
\item $\mathbf{SystemSetup}(1^k,\mathcal{W})$: Take as input a security parameter $1^k$ and a keyword space $\mathcal{W}$, and probabilistically output a pair of master public-and-secret keys $(\mathbf{PK},\mathbf{SK})$, where $\mathbf{PK}$ includes the keyword space $\mathcal{W}$ and the ciphertext space $\mathcal{C}$.

\item $\mathbf{StructureInitialization}(\mathbf{PK})$: Take as input $\mathbf{PK}$, and probabilistically initialize a hidden structure by outputting its private and public parts $(\mathbf{Pri},\mathbf{Pub})$.

\item $\mathbf{StructuredEncryption}(\mathbf{PK},W,\mathbf{Pri})$: Take as inputs $\mathbf{PK}$, a keyword $W\in\mathcal{W}$ and a hidden structure's private part $\mathbf{Pri}$, and probabilistically output a keyword-searchable ciphertext $C$ of keyword $W$ with the hidden structure, and update $\mathbf{Pri}$.

\item $\mathbf{Trapdoor}(\mathbf{SK},W)$: Take as inputs $\mathbf{SK}$ and a keyword $W\in\mathcal{W}$, and output a keyword search trapdoor $T_W$ of $W$.

\item $\mathbf{StructuredSearch}(\mathbf{PK},\mathbf{Pub},\mathbb{C},T_W)$: Take as inputs $\mathbf{PK}$, a hidden structure's public part $\mathbf{Pub}$, all keyword-searchable ciphertexts $\mathbb{C}$ and a keyword search trapdoor $T_W$ of keyword $W$, disclose partial relations to guide finding out the ciphertexts containing keyword $W$ with the hidden structure.
\end{itemize}
An SPCHS scheme must be consistent in the sense that given any keyword search trapdoor $T_W$ and any hidden structure's public part $\mathbf{Pub}$, algorithm $\mathbf{StructuredSearch}(\mathbf{PK},\mathbf{Pub},\mathbb{C},T_W)$ finds out all ciphertexts of keyword $W$ with the hidden structure $\mathbf{Pub}$.
\end{definition}

In the application of SPCHS, a receiver runs algorithm $\mathbf{SystemSetup}$ to set up SPCHS. Each sender uploads the public part of his hidden structure and keyword-searchable ciphertexts to a server, respectively by algorithms $\mathbf{StructureInitialization}$ and $\mathbf{StructuredEncryption}$. Algorithm $\mathbf{Trapdoor}$ allows the receiver to delegate a keyword search trapdoor to the server. Then the server runs algorithm $\mathbf{StructuredSearch}$ for all senders' structures to find out the ciphertexts of the queried keyword.

The above SPCHS definition requires each sender to maintain the private part of his hidden structure for algorithm $\mathbf{StructuredEncryption}$. A similar requirement appears in symmetric-key encryption with keyword search (SEKS) in which each sender is required to maintain a secret key shared with the receiver. This implies interactions via authenticated confidential channels before a sender encrypts the keywords to the receiver in SEKS. In contrast,  each sender in SPCHS just generates and maintains his/her private values locally, i.e., without requirement of extra secure interactions before encrypting keywords.

In the general case of SPCHS, each sender keeps his/her private values $\mathbf{Pri}$. We could let each sender be stateless by storing his/her $\mathbf{Pri}$ in encrypted form at a server and having each sender download and re-encrypt his/her $\mathbf{Pri}$ for each update of $\mathbf{Pri}$. A similar method also has been suggested by \cite{CJJJKRS14}.

The semantic security of SPCHS is to resist adaptively chosen keyword and structure attacks (SS-CKSA). In this security notion, a probabilistic polynomial-time (PPT) adversary is allowed to know all structures' public parts, query the trapdoors for adaptively chosen keywords, query the private parts of adaptively chosen structures, and query the ciphertexts of adaptively chosen keywords and structures (including the keywords and structures which the adversary would like to be challenged). The adversary will choose two challenge keyword-structure pairs. The SS-CKSA security means that for a ciphertext of one of two challenge keyword-structure pairs, the adversary cannot determine which challenge keyword or which challenge structure the challenge ciphertext corresponds to, provided that the adversary does not know the two challenge keywords' search trapdoors and the two challenge structures' private parts.

\begin{definition}[SS-CKSA Security]\label{D.SPCHS.Security}
Suppose there are at most $N\in\mathbb{N}$ hidden structures. An SPCHS scheme is SS-CKSA secure,
if any PPT adversary $\mathcal{A}$ has only a negligible advantage $Adv^{\text{SS-CKSA}}_{SPCHS,\mathcal{A}}$  to win in the following SS-CKSA game:

\begin{itemize}
\item \textbf{Setup Phase}: A challenger sets up the SPCHS scheme by running algorithm $\mathbf{SystemSetup}$ to generate a pair of master public-and-secret keys $(\mathbf{PK},\mathbf{SK})$, and initializes $N$ hidden structures by running algorithm $\mathbf{StructureInitialization}$ $N$ times (let $\mathbf{PSet}$ be the set of all public parts of these $N$ hidden structures.); finally the
challenger sends $\mathbf{PK}$ and $\mathbf{PSet}$ to $\mathcal{A}$.
\item \textbf{Query Phase 1}: $\mathcal{A}$ adaptively issues the following queries multiple times.
	\begin{itemize}
	 \item Trapdoor Query $\mathcal{Q}_{Trap}(W)$: Taking as input a keyword $W\in\mathcal{W}$, the challenger outputs the keyword search trapdoor of keyword $W$;
	\item Privacy Query $\mathcal{Q}_{Pri}(\mathbf{Pub})$: Taking as input a hidden structure's public part $\mathbf{Pub}\in\mathbf{PSet}$, the challenger outputs the corresponding private part of this structure;
	\item Encryption Query $\mathcal{Q}_{Enc}(W,\mathbf{Pub})$: Taking as inputs a keyword $W\in\mathcal{W}$ and a hidden structure's public part $\mathbf{Pub}$, the challenger outputs an SPCHS ciphertext of keyword $W$ with the hidden structure $\mathbf{Pub}$.
     \end{itemize}
\item \textbf{Challenge Phase}: $\mathcal{A}$ sends two challenge keyword-and-structure pairs $(W^*_0,\mathbf{Pub}^*_0)\in\mathcal{W}\times\mathbf{PSet}$ and $(W^*_1,\mathbf{Pub}^*_1)\in\mathcal{W}\times\mathbf{PSet}$ to the challenger; The challenger randomly chooses $d\in\{0,1\}$, and sends a challenge ciphertext $C^*_d$ of keyword $W_d^*$ with the hidden structure $\mathbf{Pub}_d^*$ to $\mathcal{A}$.
\item \textbf{Query Phase 2}: This phase is the same as \textbf{Query Phase 1}. Note that in \textbf{Query Phase 1} and \textbf{Query Phase 2}, $\mathcal{A}$ cannot query the corresponding private parts both of $\mathbf{Pub}^*_0$ and $\mathbf{Pub}^*_1$ and the keyword search trapdoors both of $W^*_0$ and $W^*_1$.
\item \textbf{Guess Phase}: $\mathcal{A}$ sends a guess $d^\prime$ to the challenger. We say that $\mathcal{A}$ wins if $d=d^\prime$. And let $Adv^{\text{SS-CKSA}}_{SPCHS,\mathcal{A}}=Pr[d=d^\prime]-\frac{1}{2}$ be the advantage of $\mathcal{A}$ to win in the above game.
\end{itemize}
\end{definition}

A weaker security definition of SPCHS is the selective-keyword security. We refer to this weaker security notion as SS-sK-CKSA security, and the corresponding attack game as SS-sK-CKSA game. In this attack game, the adversary $\mathcal{A}$ chooses two challenge keywords before the SPCHS scheme is set up, but the adversary still adaptively chooses two challenge hidden structures at $\textbf{Challenge Phase}$. Let $Adv^{\text{SS-sK-CKSA}}_{SPCHS,\mathcal{A}}$ denote the advantage of adversary $\mathcal{A}$ to win in this game.

\section{A Simple SPCHS Scheme from Scratch}\label{S.SPCHS.Instance}

Let $\gamma\overset{\$}\leftarrow \Re$ denote an element $\gamma$ randomly sampled from $\Re$. Let $\mathbb{G}$ and $\mathbb{G}_1$ denote two multiplicative groups of
prime order $q$. Let $g$ be a generator of $\mathbb{G}$. A bilinear map $\hat{e}:\mathbb{G}\times\mathbb{G} \rightarrow
\mathbb{G}_1$ \cite{MOV93,FMR99} is an efficiently computable and non-degenerate function, with the bilinearity
property $\hat{e}(g^a,g^b)=\hat{e}(g,g)^{ab}$, where $(a,b)\overset{\$} {\leftarrow} \mathbb{Z}_q^*$ and $\hat{e}(g,g)$
is a generator of $\mathbb{G}_1$. Let $\mathbf{BGen}(1^k)$ be an efficient bilinear map generator that takes as input a security
parameter $1^k$ and probabilistically outputs $(q,\mathbb{G},\mathbb{G}_1,g,\hat{e})$. Let keyword space $\mathcal{W}=\{0,1\}^*$.

A simple SPCHS scheme secure in the random oracle model is constructed as follows.

\begin{itemize}
\item $\mathbf{SystemSetup}(1^k,\mathcal{W})$: Take as input $1^k$ and the keyword space $\mathcal{W}$, compute $(q,\mathbb{G}, \mathbb{G}_1, g,\hat{e})=\mathbf{BGen}(1^k)$, pick $s\overset{\$}\leftarrow \mathbb{Z}_q^*$, set $P=g^s$, choose a cryptographic hash function $H: \mathcal{W}\rightarrow \mathbb{G}$, set the ciphertext space $\mathcal{C}\subseteq\mathbb{G}_1\times\mathbb{G}\times\mathbb{G}_1$, and finally output the master public key $\mathbf{PK}=(q,\mathbb{G},\mathbb{G}_1,g,\hat{e},P,H,\mathcal{W},\mathcal{C})$, and the master secret key $\mathbf{SK}=s$.

\item $\mathbf{StructureInitialization}(\mathbf{PK})$: Take as input $\mathbf{PK}$, pick $u\overset{\$}{\leftarrow}\mathbb{Z}_q^*$, and initialize a hidden structure by outputting a pair of private-and-public parts $(\mathbf{Pri}=(u),\mathbf{Pub}=g^u)$. Note that $\mathbf{Pri}$ here is a variable list formed as $(u,\{(W,Pt[u,W])|W\in\mathcal{W}\})$, which is initialized as $(u)$.

\item $\mathbf{StructuredEncryption}(\mathbf{PK},W,\mathbf{Pri})$: Take as inputs $\mathbf{PK}$, a keyword $W\in\mathcal{W}$, a hidden structure's private part $\mathbf{Pri}$, pick $r\overset{\$}{\leftarrow}\mathbb{Z}_q^*$ and do the following steps:
\begin{enumerate}
\item Search $(W,Pt[u,W])$ for $W$ in $\mathbf{Pri}$;
\item If it is not found, insert $(W,Pt[u,W]\overset{\$}\leftarrow
\mathbb{G}_1)$ to $\mathbf{Pri}$, and output the keyword-searchable ciphertext $C=(\hat{e}(P,H(W))^u,g^r,\hat{e}(P,H(W))^r\cdot Pt[u,W])$;
\item Otherwise, pick $R\overset{\$}{\leftarrow}\mathbb{G}_1$,
set $C=(Pt[u,W],g^r,\hat{e}(P,H(W))^r\cdot R)$, update $Pt[u,W]=R$, and output the keyword-searchable ciphertext $C$;
\end{enumerate}

\item $\mathbf{Trapdoor}(\mathbf{SK},W)$: Take as inputs $\mathbf{SK}$ and a keyword $W\in\mathcal{W}$, and output a keyword search trapdoor $T_W=H(W)^s$ of keyword $W$.

\item $\mathbf{StructuredSearch}(\mathbf{PK},\mathbf{Pub},\mathbb{C},T_W)$: Take as inputs $\mathbf{PK}$, a hidden structure's public part $\mathbf{Pub}$, all keyword-searchable ciphertexts $\mathbb{C}$ (let $\mathbb{C}[i]$ denote one ciphertext of $\mathbb{C}$, and this ciphertext can be parsed as $(\mathbb{C}[i,1],\mathbb{C}[i,2],\mathbb{C}[i,3])\in\mathbb{G}_1\times\mathbb{G}\times\mathbb{G}_1$) and a keyword trapdoor $T_W$ of keyword $W$, set $\mathbb{C}^\prime=\phi$, and do the following steps:
\begin{enumerate}
\item Compute $Pt^\prime=\hat{e}(\mathbf{Pub},T_W)$;
\item Seek a ciphertext $\mathbb{C}[i]$ having $\mathbb{C}[i,1]=Pt^\prime$;
if it exists, add $\mathbb{C}[i]$ into $\mathbb{C}^\prime$;
\item If no matching ciphertext is found, output $\mathbb{C}^\prime$;
\item Compute $Pt^\prime=\hat{e}(\mathbb{C}[i,2],T_W)^{-1}\cdot\mathbb{C}[i,3]$, and go to Step 2.
\end{enumerate}
\end{itemize}

Figure \ref{F.SPCHS.Instance} shows a hidden star-like structure, which is generated by the SPCHS instance. When running algorithm $\mathbf{StructuredSearch}(\mathbf{PK},\mathbf{Pub},\mathbb{C},T_{W_i})$, it discloses the value $\hat{e}(P,H(W_i))^u$ by computing $\hat{e}(\mathbf{Pub},T_{W_i})$,  and matches $\hat{e}(P,H(W_i))^u$ with all ciphertexts to find out the ciphertext $(\hat{e}(P,H(W_i))^u,g^r,\hat{e}(P,H(W_i))^r\cdot Pt[u,W_i])$. Then the algorithm discloses $Pt[u,W_i]$ by computing $\hat{e}(g^r,T_{W_i})^{-1}\cdot\hat{e}(P,H(W_i))^r\cdot Pt[u,W_i]$, and matches $Pt[u,W_i]$ with all ciphertexts to find out the ciphertext $(Pt[u,W_i],g^r,\hat{e}(P,H(W_i))^r\cdot R)$.
By carrying on in this way,
the algorithm will find out all ciphertexts of keyword $W_i$ with the hidden star-like structure, and stop the search if no matching ciphertext is found.

\begin{figure*}[!htp]
\centering\begin{boxedminipage}{0.9\textwidth}
\includegraphics[scale=0.7]{InstanceofSPCHS}
\begin{quote}
Note that, in each ciphertext, the value $R$ and the value $r$ are randomly chosen. For $i\in[1,L]$, $Pt[u,W_i]$ is initialized with a random value when generating the first ciphertext of keyword $W_i$, and it will be updated into $R$ after generating each subsequent ciphertext of keyword $W_i$.
\end{quote}
\end{boxedminipage}
\caption{Hidden star-like structure generated by the above SPCHS instance}\label{F.SPCHS.Instance}
\end{figure*}

\textbf{Consistency.} Roughly speaking, algorithm $\mathbf{StructuredSearch}$ repetitively discloses the value of $Pt^\prime$ and matches the value with all ciphertexts' first parts to find out the matching ciphertexts. Since all disclosed values of $Pt^\prime$ are either collision-free (due to the hash function $H$) and random (according to algorithm $\mathbf{StructuredEncryption}$), no more than one ciphertext matches in each matching process. The found ciphertexts should contain the queried keyword, since given a keyword search trapdoor, algorithm $\mathbf{StructuredSearch}$ only can disclose the values of $Pt^\prime$, which are corresponding to the queried keyword. Formally, we have Theorem \ref{T.SPCHS.Instance.Consistency} on consistency whose proof can be found in Supplemental Materials B.

\begin{theorem}\label{T.SPCHS.Instance.Consistency}
Suppose the hash function $H$ is collision-free, except with a negligible probability in the security parameter $k$. The above SPCHS instance is consistent, also except with a negligible probability in the security parameter $k$.
\end{theorem}

\textbf{Semantic Security.} The SS-CKSA security of the above SPCHS scheme relies on the DBDH assumption in $\mathbf{BGen}(1^k)$. The definition of DBDH assumption \cite{BB04} is as follows.

\begin{definition}[The DBDH Assumption]\label{D.DBDH} The DBDH problem in $\mathbf{BGen}(1^k)=(q,\mathbb{G},\mathbb{G}_1,g,\hat{e})$ is defined as the advantage of any PPT algorithm $\mathcal{B}$ to distinguish the tuples $(g^a,g^b,g^c,\hat{e}(g,g)^{abc})$ and $(g^a,g^b,g^c,\hat{e}(g,g)^y)$, where $(a,b,c,y)\overset{\$}\leftarrow \mathbb{Z}_q^{*4}$. Let  $Adv_\mathcal {B}^{DBDH}(1^k)=\text{Pr}[\mathcal{B}(g^a,g^b,g^c,\hat{e}(g,g)^{abc})=1]-\text{Pr}[\mathcal{B}(g^a,g^b,g^c,\hat{e}(g,g)^y)=1]$ be the advantage of algorithm $\mathcal{B}$ to solve the DBDH problem. We say that the DBDH assumption holds in $\mathbf{BGen}(1^k)$, if the advantage $Adv_\mathcal {B}^{DBDH}(1^k)$ is negligible in the parameter $k$.
\end{definition}

In the security proof, we prove that if there is an adversary who can break the SS-CKSA security of the above SPCHS instance in the RO model, then there is an algorithm which can solve the DBDH problem in $\mathbf{BGen}(1^k)$. Formally we have Theorem \ref{T.SPCHS.Instance.Security} whose proof can be found in Supplemental Materials C.

\begin{theorem}\label{T.SPCHS.Instance.Security}
Let the hash function $H$ be modeled as the random oracle $\mathcal{Q}_{H}(\cdot)$. Suppose there are at most $N\in\mathbb{N}$ hidden structures, and a PPT adversary $\mathcal{A}$ wins in the SS-CKSA game of the above SPCHS instance with advantage $Adv^{\text{SS-CKSA}}_{SPCHS,\mathcal{A}}$, in which
$\mathcal{A}$ makes at most $q_t$ queries to oracle $\mathcal{Q}_{Trap}(\cdot)$ and at most $q_p$ queries to oracle $\mathcal{Q}_{Pri}(\cdot)$. Then there is a PPT algorithm $\mathcal{B}$ that solves the
DBDH problem in $\mathbf{BGen}(1^k)$ with advantage
$$Adv_\mathcal {B}^{DBDH}(1^k)\approx\frac{27}{(e\cdot q_t\cdot q_p)^3}\cdot Adv^{\text{SS-CKSA}}_{SPCHS,\mathcal{A}},$$ where $e$ is the base of natural logarithms.
\end{theorem}

\textbf{Forward and Backward Security.} Even in the case that a sender
gets his local privacy $\mathbf{Pri}$ compromised, SPCHS still offers forward security. This means that the existing hidden structure of ciphertexts stays confidential, since the local privacy only contains the relationship of the new generated ciphertexts. To offer backward security with SPCHS, the sender can initialize a new structure by algorithm $\mathbf{StructureInitialization}$ for the new generated ciphertexts. Because the new structure is independent of the old one, the compromised local privacy will not leak the new generated structure.

\textbf{Search Complexity.} All keyword-searchable ciphertexts can be indexed by their first parts' binary bits. Assume that there are in total $n$ ciphertexts from $n_{\mbox{\tiny \emph S}}$ hidden structures, and the $i$-th hidden structure contains $n_{{\mbox{\tiny \emph W}},i}$ ciphertexts of keyword $W\in\mathcal{W}$. With the $i$-th hidden structure, the search complexity is $O(n_{{\mbox{\tiny \emph W}},i}\log n)$. For all hidden structures, the sum search complexity is $O((n_{\mbox{\tiny \emph S}}+n_{{\mbox{\tiny \emph W}}})\log n)$, where $n_{\mbox{\tiny \emph W}}=\sum_{i=1}^{n_{\mbox{\tiny \emph S}}} n_{{\mbox{\tiny \emph W}},i}$. Since $n=\sum_{W\in\mathcal{W}} n_{\mbox{\tiny \emph W}}$ and $n_{\mbox{\tiny \emph W}}=\sum_{i=1}^{n_{\mbox{\tiny \emph S}}} n_{{\mbox{\tiny \emph W}},i}$, we have that $n_{\mbox{\tiny \emph S}}\ll n_{\mbox{\tiny \emph W}}\ll n$. Thus the above SPCHS instance allows a much more efficient search than existing PEKS schemes, which have $O(n)$ search complexity.

One may note that SPCHS loses its significant advantage in search performance compared with PEKS if $n_{\mbox{\tiny \emph S}}=n$ holds. However, this special case seldom happens. In practice, a sender will extract several keywords from
each of his files. So we usually have  $n_{\mbox{\tiny \emph S}}\ll n$ even if each sender only has one file. In addition, most related works on SEKS and PEKS assume that each file has several keywords.

\textbf{Experiment.} We coded our SPCHS scheme, and tested the time cost of algorithm $\mathbf{StructuredSearch}$ to execute its cryptographic operations for different numbers of matching ciphertexts. We also coded the PEKS scheme \cite{BCO04}. Table \ref{T.Parameters} shows the system parameters including hardware, software and the chosen elliptic curve. Assume there are in total $10^4$ searchable ciphertexts. PEKS takes about 53.8 seconds search time per keyword, since it must test all ciphertexts for each search.
Figure \ref{F.Result} shows the experimental results of SPCHS. It is clear that the time cost of SPCHS is linear with the number of matching ciphertexts, whereas for PEKS it is linear with
the number of total ciphertexts. Hence, SPCHS is much more efficient than PEKS.

\begin{table}
\centering
\caption{System parameters}\label{T.Parameters}
\begin{tabular}{|c|c|c|}
\hline
Hardware & \multicolumn{2}{c|}{Intel CPU
	E5300 @ 2.60GHz}
\\ \hline OS and compiler & \multicolumn{2}{c|}{Win XP and
Microsoft VC++ 6.0}
\\ \hline Program library & \multicolumn{2}{c|}{MIRACL version 5.4.1}
\\ \hline \multicolumn{3}{|c|}{Parameters of bilinear map}
\\ \hline Elliptic curve & \multicolumn{2}{c|}{$y^2=x^3+A\cdot x+B\cdot x$}
\\ \hline Pentanomial basis & \multicolumn{2}{c|}{$t^m+t^a+t^b+t^c+1$}
\\ \hline Base field: $2^m$ & \multicolumn{2}{c|}{$m=379$}
\\ \hline A & \multicolumn{2}{c|}{1}
\\ \hline B & \multicolumn{2}{c|}{1}
\\ \hline Group order: $q$ & \multicolumn{2}{c|}{$2^m+2^{(m+1)/2}+1$}
\\ \hline a & \multicolumn{2}{c|}{315}
\\ \hline b & \multicolumn{2}{c|}{301}
\\ \hline c & \multicolumn{2}{c|}{287}
\\ \hline \multicolumn{3}{|l|}{The default unit is decimal.}
\\ \hline
\end{tabular}
\end{table}

\begin{figure}
\centering
\includegraphics[width=0.5\textwidth,height=0.195\textheight]{Decrypt.eps}
\caption{Time cost of SPCHS}\label{F.Result}
\end{figure}

\section{A Generic Construction of SPCHS \\ from IBKEM and IBE}\label{S.SPCHS.Generic}

In this section, we formalize collision-free full-identity malleable IBKEM and a generic SPCHS construction from IBKEM and IBE.

\subsection{Reviewing IBE}
Before the generic SPCHS construction, let us review the concept of IBE and its Anonymity and Semantic Security both under adaptive-ID and Chosen Plaintext Attacks (Anon-SS-ID-CPA).

\begin{definition}[IBE \cite{BF01}]\label{D.IBE}
IBE consists of four algorithms:
\begin{itemize}
\item $\mathbf{Setup}_{\mbox{\tiny IBE}}(1^k,\mathcal{ID}_{\mbox{\tiny IBE}})$: Take as inputs a security parameter $1^k$ and an identity space $\mathcal{ID}_{\mbox{\tiny IBE}}$, and probabilistically output the master public-and-secret-key pair $(\mathbf{PK}_{\mbox{\tiny IBE}},\mathbf{SK}_{\mbox{\tiny IBE}})$, where $\mathbf{PK}_{\mbox{\tiny IBE}}$ includes the message space $\mathcal{M}_{\mbox{\tiny IBE}}$, the ciphertext space $\mathcal{C}_{\mbox{\tiny IBE}}$ and the identity space $\mathcal{ID}_{\mbox{\tiny IBE}}$.

\item $\mathbf{Extract}_{\mbox{\tiny IBE}}(\mathbf{SK}_{\mbox{\tiny IBE}},ID)$: Take as inputs $\mathbf{SK}_{\mbox{\tiny IBE}}$ and an identity $ID\in\mathcal{ID}_{\mbox{\tiny IBE}}$, and output a decryption key $\tilde{S}_{ID}$ of $ID$.

\item $\mathbf{Enc}_{\mbox{\tiny IBE}}(\mathbf{PK}_{\mbox{\tiny IBE}},ID,M)$: Take as inputs $\mathbf{PK}_{\mbox{\tiny IBE}}$, an identity $ID\in\mathcal{ID}_{\mbox{\tiny IBE}}$ and a message $M$, and probabilistically output a ciphertext $\tilde{C}$.

\item $\mathbf{Dec}_{\mbox{\tiny IBE}}(\tilde{S}_{ID^\prime},\tilde{C})$: Take as inputs the decryption key $\tilde{S}_{ID^\prime}$ of identity $ID^\prime$ and a ciphertext $\tilde{C}$, and output a message or $\bot$, if the ciphertext is invalid.
\end{itemize}

An IBE scheme must be consistent in the sense that for any $\tilde{C}=\mathbf{Enc}_{\mbox{\tiny
IBE}}(\mathbf{PK}_{\mbox{\tiny IBE}},ID,M)$ and $\tilde{S}_{ID^\prime}=\mathbf{Extract}_{\mbox{\tiny IBE}}(\mathbf{SK}_{\mbox{\tiny
IBE}},ID^\prime)$, $\mathbf{Dec}_{\mbox{\tiny IBE}}(\tilde{S}_{ID^\prime},\tilde{C})=M$ holds if $ID^\prime=ID$, except with a negligible probability in the security parameter $k$.
\end{definition}

In the Anon-SS-ID-CPA security notion of IBE, a PPT adversary is allowed to query the decryption keys for adaptively chosen identities, and adaptively choose two challenge identity-and-message pairs. The Anon-SS-ID-CPA security of IBE means that for a challenge ciphertext, the adversary cannot determine which challenge identity and which challenge message it corresponds to, provided that the adversary does not know the two challenge identities' decryption keys. The Anon-SS-ID-CPA security of an IBE scheme is as follows.

\begin{definition}[Anon-SS-ID-CPA security of IBE \cite{ABN10}]
An IBE scheme is Anon-SS-ID-CPA secure if any PPT adversary $\mathcal{B}$ has only a negligible advantage $Adv^{\text{Anon-SS-ID-CPA}}_{IBE,\mathcal{B}}$ to win in the following Anon-SS-ID-CPA game:

\begin{itemize}
\item \textbf{Setup Phase}: A challenger sets up the IBE scheme by running algorithm $\mathbf{Setup}_{\mbox{\tiny IBE}}$ to generate the master public-and-secret-keys pair $(\mathbf{PK}_{\mbox{\tiny IBE}},\mathbf{SK}_{\mbox{\tiny IBE}})$, and sends $\mathbf{PK}_{\mbox{\tiny IBE}}$ to $\mathcal{B}$.

\item \textbf{Query Phase 1}: Adversary $\mathcal{B}$ adaptively issues the following query multiple times.
\begin{itemize}
\item Decryption Key Query $\mathcal{Q}_{DK}^{IBE}(ID)$: Taking as input an identity $ID\in\mathcal{ID}_{\mbox{\tiny IBE}}$, the challenger outputs the decryption key of identity $ID$.
\end{itemize}

\item \textbf{Challenge Phase}: Adversary $\mathcal{B}$ sends two challenge identity-and-message pairs $(ID_0^*,M_0^*)$ and $(ID_1^*,M_1^*)$ to the challenger; the challenger picks $\tilde{d}\overset{\$}\leftarrow\{0,1\}$, and sends the challenge IBE ciphertext $\tilde{C}^*_{\tilde{d}}=\mathbf{Enc}_{\mbox{\tiny IBE}}(\mathbf{PK}_{\mbox{\tiny IBE}},ID^*_{\tilde{d}},M^*_{\tilde{d}})$ to $\mathcal{B}$.

\item \textbf{Query Phase 2}: This phase is the same as \textbf{Query Phase 1}. Note that in \textbf{Query Phase 1} and \textbf{Query Phase 2}, $\mathcal{B}$ cannot query the decryption key corresponding to the challenge identity $ID_0^*$ or $ID_1^*$.

\item \textbf{Guess Phase}: Adversary $\mathcal{B}$ sends a guess $\tilde{d}^\prime$ to the challenger. We say that $\mathcal{B}$ wins if $\tilde{d}^\prime=\tilde{d}$. Let $Adv^{\text{Anon-SS-ID-CPA}}_{IBE,\mathcal{B}}=Pr[\tilde{d}^\prime=\tilde{d}]-\frac{1}{2}$ be the advantage of $\mathcal{B}$ to win in the above game.
\end{itemize}
\end{definition}

\subsection{The Collision-Free Full-Identity Malleable IBKEM}

Our generic construction also relies on a notion of collision-free full-identity malleable IBKEM. The following IBKEM definition is derived from \cite{IP08}. A difference only appears in algorithm $\mathbf{Encaps}_{\mbox{\tiny IBKEM}}$. In order to highlight that the generator of an IBKEM encapsulation knows the chosen random value used in algorithm $\mathbf{Encaps}_{\mbox{\tiny IBKEM}}$, we take the random value as an input of the algorithm.

\begin{definition}[IBKEM]\label{D.IBKEM}
IBKEM consists of four algorithms:

\begin{itemize}
\item $\mathbf{Setup}_{\mbox{\tiny IBKEM}}(1^k,\mathcal{ID}_{\mbox{\tiny IBKEM}})$: Take as inputs a security parameter $1^k$ and an identity space $\mathcal{ID}_{\mbox{\tiny IBKEM}}$, and probabilistically output the master public-and-secret-keys pair $(\mathbf{PK}_{\mbox{\tiny IBKEM}},\mathbf{SK}_{\mbox{\tiny IBKEM}})$, where $\mathbf{PK}_{\mbox{\tiny IBKEM}}$ includes the identity space $\mathcal{ID}_{\mbox{\tiny IBKEM}}$, the encapsulated key space $\mathcal{K}_{\mbox{\tiny IBKEM}}$ and the encapsulation space $\mathcal{C}_{\mbox{\tiny IBKEM}}$.

\item $\mathbf{Extract}_{\mbox{\tiny IBKEM}}(\mathbf{SK}_{\mbox{\tiny IBKEM}},ID)$: Take as inputs $\mathbf{SK}_{\mbox{\tiny IBKEM}}$ and an identity $ID\in\mathcal{ID}_{\mbox{\tiny IBKEM}}$, and output a decryption key $\hat{S}_{ID}$ of $ID$.

\item $\mathbf{Encaps}_{\mbox{\tiny IBKEM}}(\mathbf{PK}_{\mbox{\tiny IBKEM}},ID,r)$: Take as inputs $\mathbf{PK}_{\mbox{\tiny IBKEM}}$, an identity $ID\in\mathcal{ID}_{\mbox{\tiny IBKEM}}$ and a random value $r$, and deterministically output a key-and-encapsulation pair $(\hat{K},\hat{C})$ of $ID$.

\item $\mathbf{Decaps}_{\mbox{\tiny IBKEM}}(\hat{S}_{ID^\prime},\hat{C})$: Take as inputs the decryption key $\hat{S}_{ID^\prime}$ of identity $ID^\prime$ and an encapsulation $\hat{C}$, and output an encapsulated key or $\bot$, if the encapsulation is invalid.
\end{itemize}

An IBKEM scheme must be consistent in the sense that for any $(\hat{K},\hat{C})=\mathbf{Encaps}_{\mbox{\tiny
IBKEM}}($ $\mathbf{PK}_{\mbox{\tiny IBKEM}},ID,r)$, $\mathbf{Decaps}_{\mbox{\tiny IBKEM}}(\hat{S}_{ID^\prime},\hat{C})=\hat{K}$ holds if $ID^\prime=ID$, except with a negligible probability in the security parameter $k$.
\end{definition}

The collision-free full-identity malleable IBKEM implies the following characteristics: all
identities' decryption keys can decapsulate the same encapsulation; all decapsulated keys are collision-free; the generator of the encapsulation can also compute these decapsulated keys; the decapsulated keys of different encapsulations are also collision-free.

\begin{definition}[Collision-Free Full-Identity Malleable IBKEM]\label{D.FIM}
IBKEM is collision-free full-identity malleable, if there is an efficient
function $\mathbf{FIM}$ that for any $(\hat{K},\hat{C})=\mathbf{Encaps}_{\mbox{\tiny IBKEM}}($ $\mathbf{PK}_{\mbox{\tiny IBKEM}},ID,r)$, the function $\mathbf{FIM}$ satisfies the following features:

\begin{itemize}
\item (Full-Identity Malleability) For any identity $ID^\prime\in\mathcal{ID}_{\mbox{\tiny IBKEM}}$, the equation $\mathbf{FIM}(ID^\prime,r)=\mathbf{Decaps}_{\mbox{\tiny IBKEM}}(\hat{S}_{ID^\prime},\hat{C})$ always holds, where
$\hat{S}_{ID^\prime}=\mathbf{Extract}_{\mbox{\tiny IBKEM}}(\mathbf{SK}_{\mbox{\tiny IBKEM}},ID^\prime)$;
\item (Collision-Freeness) For any identity $ID^\prime\in\mathcal{ID}_{\mbox{\tiny IBKEM}}$ and any random value $r^\prime$, if $ID\neq ID^\prime\bigvee r\neq r^\prime$, then $\mathbf{FIM}(ID,r)\neq \mathbf{FIM}(ID^\prime,r^\prime)$ holds,  except with a negligible probability in the security parameter $k$.
\end{itemize}
\end{definition}

A collision-free full-identity malleable IBKEM scheme may preserve semantic security and anonymity. We incorporate the semantic security and anonymity into Anon-SS-ID-CPA secure IBKEM. But this security is different from the traditional version  \cite{IP08} of the Anon-SS-ID-CPA security due to the full-identity malleability of IBKEM. The difference will be introduced after defining that security. In that security, a PPT adversary is allowed to query the decryption keys for adaptively chosen identities, and adaptively choose two challenge identities.  The Anon-SS-ID-CPA security of IBKEM means that for a challenge key-and-encapsulation pair, the adversary cannot determine the correctness of this pair and the challenge identity of this pair, given that the adversary does not know the two challenging identities' decryption keys. The Anon-SS-ID-CPA security of a collision-free full-identity malleable IBKEM scheme is as follows.

\begin{definition}[Anon-SS-ID-CPA security of IBKEM]\label{D.IBKEM.Security}
An IBKEM scheme is Anon-SS-ID-CPA secure if any PPT adversary $\mathcal{B}$ has only a negligible advantage $Adv^{\text{Anon-SS-ID-CPA}}_{IBKEM,\mathcal{B}}$ to win in the following Anon-SS-ID-CPA game:

\begin{itemize}
\item \textbf{Setup Phase}: A challenger sets up the IBKEM scheme by running algorithm $\mathbf{Setup}_{\mbox{\tiny IBKEM}}$ to generate the master public-and-secret-keys pair $(\mathbf{PK}_{\mbox{\tiny IBKEM}},\mathbf{SK}_{\mbox{\tiny IBKEM}})$, and sends $\mathbf{PK}_{\mbox{\tiny IBKEM}}$ to $\mathcal{B}$.

\item \textbf{Query Phase 1}: $\mathcal{B}$ adaptively issues the following query multiple times.
\begin{itemize}
\item Decryption Key Query $\mathcal{Q}_{DK}^{IBKEM}(ID)$: Taking as input an identity $ID\in\mathcal{ID}_{\mbox{\tiny IBKEM}}$, the challenger outputs the decryption key of identity $ID$.
\end{itemize}

\item \textbf{Challenge Phase}: $\mathcal{B}$ sends two challenge identities $ID^*_0$ and $ID_1^*$ to the challenger; the challenger picks $\hat{d}\overset{\$}\leftarrow\{0,1\}$, computes $(\hat{K}^*_0,\hat{C}^*_0)=\mathbf{Encaps}_{\mbox{\tiny IBKEM}}(PK_{\mbox{\tiny IBKEM}},ID^*_0,r_0)$
and $(\hat{K}^*_1,\hat{C}^*_1)=\mathbf{Encaps}_{\mbox{\tiny IBKEM}}(PK_{\mbox{\tiny IBKEM}},ID^*_1,r_1)$, and sends the challenge key-and-encapsulation pair $(\hat{K}_{\hat{d}}^*,\hat{C}_0^*)$ to $\mathcal{B}$, where $r_0$ and $r_1$ are randomly chosen.

\item \textbf{Query Phase 2}: This phase is the same as \textbf{Query Phase 1}. Note that in \textbf{Query Phase 1} and \textbf{Query Phase 2}, $\mathcal{B}$ cannot query the decryption keys both of the challenge identities $ID_0^*$ and $ID_1^*$.

\item \textbf{Guess Phase}: $\mathcal{B}$ sends a guess $\hat{d}^\prime$ to the challenger. We say that $\mathcal{B}$ wins if $\hat{d}^\prime=\hat{d}$. Let $Adv^{\text{Anon-SS-ID-CPA}}_{IBKEM,\mathcal{B}}=Pr[\hat{d}^\prime=\hat{d}]-\frac{1}{2}$ be the advantage of $\mathcal{B}$ to win in the above game.
\end{itemize}
\end{definition}

In the above definition, the anonymity of the encapsulated keys is defined by the indistinguishability of $\hat{K}_0^*$ and $\hat{K}_1^*$. But we do not define the anonymity of the IBKEM encapsulations (\emph{i.e.} the challenge key-and-encapsulation pair consists of $\hat{C}_0^*$ instead of $\hat{C}_{\hat{d}}^*$), since the full-identity malleability of IBKEM implies that any IBKEM encapsulation is valid for all identities.

A weaker security definition of IBKEM is the selective-identity security, referred to as the Anon-SS-sID-CPA security. The corresponding attack game is called the Anon-SS-sID-CPA game in which the adversary must commit to the two challenge identities before the system is set up.

\subsection{The Proposed Generic SPCHS Construction}

Let keyword space $\mathcal{W}\subset\mathcal{ID}_{\mbox{\tiny IBKEM}}=\mathcal{ID}_{\mbox{\tiny IBE}}$. Our generic SPCHS construction from the collision-free full-identity malleable IBKEM and IBE is as follows.

\begin{itemize}
\item $\mathbf{SystemSetup}(1^k,\mathcal{W})$: Take as inputs a security parameter $1^k$ and the keyword space $\mathcal{W}$, run $(\mathbf{PK}_{\mbox{\tiny IBKEM}},\mathbf{SK}_{\mbox{\tiny IBKEM}})=\mathbf{Setup}_{\mbox{\tiny IBKEM}}(1^k,\mathcal{ID}_{\mbox{\tiny IBKEM}})$ and $(\mathbf{PK}_{\mbox{\tiny IBE}},\mathbf{SK}_{\mbox{\tiny IBE}})=\mathbf{Setup}_{\mbox{\tiny IBE}}(1^k,$ $\mathcal{ID}_{\mbox{\tiny IBE}})$, and output a pair of master public-and-secret keys $(\mathbf{PK}=(\mathbf{PK}_{\mbox{\tiny IBKEM}},\mathbf{PK}_{\mbox{\tiny IBE}}),\mathbf{SK}=(\mathbf{SK}_{\mbox{\tiny IBKEM}},\mathbf{SK}_{\mbox{\tiny IBE}}))$. Let the SPCHS ciphertext space $\mathcal{C}=\mathcal{K}_{\mbox{\tiny IBKEM}}\times\mathcal{C}_{\mbox{\tiny IBE}}$, and $\mathcal{K}_{\mbox{\tiny IBKEM}}=\mathcal{M}_{\mbox{\tiny IBE}}$.

\item $\mathbf{StructureInitialization}(\mathbf{PK})$: Take as input $\mathbf{PK}$, arbitrarily pick a keyword $W\in\mathcal{W}$ and a random value $u$, generate an IBKEM encapsulated key and its encapsulation $(\hat{K},\hat{C})=\mathbf{Encaps}_{\mbox{\tiny IBKEM}}(\mathbf{PK}_{\mbox{\tiny IBKEM}},W,u)$, and initialize a hidden structure by outputting a pair of private-and-public parts $(\mathbf{Pri}=(u),\mathbf{Pub}=\hat{C})$. Note that $\mathbf{Pri}$ here is a variable list formed as $(u,\{(W,Pt[u,W])|W\in\mathcal{W}\})$, which is initialized as $(u)$.

(In the above, an IBKEM encapsulation and its related random value are respectively taken as the public-and-private parts of a hidden structure. To generate these two parts , an arbitrary keyword have to be chosen to run algorithm $\mathbf{Encaps}_{\mbox{\tiny IBKEM}}$.)

\item $\mathbf{StructuredEncryption}(\mathbf{PK},W,\mathbf{Pri})$: Take as inputs $\mathbf{PK}$, a keyword $W\in\mathcal{W}$, a hidden structure's private part $\mathbf{Pri}$, and do the following steps: \begin{enumerate}
\item Search $(W,Pt[u,W])$ for $W$ in $\mathbf{Pri}$;
\item If it is not found, insert $(W,Pt[u,W]\overset{\$}\leftarrow
\mathcal{M}_{\mbox{\tiny IBE}})$ to $\mathbf{Pri}$, and output the keyword-searchable ciphertext $C=(\mathbf{FIM}(W,u),\mathbf{Enc}_{\mbox{\tiny IBE}}(\mathbf{PK}_{\mbox{\tiny IBE}},W,Pt[u,W])$;
\item Otherwise, pick $R\overset{\$}{\leftarrow}\mathcal{M}_{\mbox{\tiny IBE}}$, set $C=(Pt[u,W],\mathbf{Enc}_{\mbox{\tiny IBE}}(\mathbf{PK}_{\mbox{\tiny IBE}},W,R))$, update $Pt[u,W]=R$, and output the keyword-searchable ciphertext $C$;
\end{enumerate}

\item $\mathbf{Trapdoor}(\mathbf{SK},W)$: Take as inputs $\mathbf{SK}$ and a keyword $W\in\mathcal{W}$, run $\hat{S}_W=\mathbf{Extract}_{\mbox{\tiny IBKEM}}($ $\mathbf{SK}_{\mbox{\tiny IBKEM}},W)$ and $\tilde{S}_W= \mathbf{Extract}_{\mbox{\tiny IBE}}(\mathbf{SK}_{\mbox{\tiny IBE}},W)$, and output a keyword search trapdoor $T_W=(\hat{S}_W,\tilde{S}_W)$ of keyword $W$.

\item $\mathbf{StructuredSearch}(\mathbf{PK},\mathbf{Pub},\mathbb{C},T_W)$: Take as inputs $\mathbf{PK}$, a hidden structure's public part $\mathbf{Pub}$, all keyword-searchable ciphertexts $\mathbb{C}$ (let $\mathbb{C}[i]$ denote one ciphertext of $\mathbb{C}$, and this ciphertext can be parsed as $(\mathbb{C}[i,1],\mathbb{C}[i,2])\in\mathcal{C}=\mathcal{K}_{\mbox{\tiny IBKEM}}\times\mathcal{C}_{\mbox{\tiny IBE}}$) and a keyword trapdoor $T_W=(\hat{S}_W,\tilde{S}_W)$ of keyword $W$, set $\mathbb{C}^\prime=\phi$, and do the following steps:
\begin{enumerate}
\item Compute $Pt^\prime=\mathbf{Decaps}_{\mbox{\tiny IBKEM}}(\hat{S}_W,\mathbf{Pub})$;
\item Seek a ciphertext $\mathbb{C}[i]$ having $\mathbb{C}[i,1]=Pt^\prime$; if
it exists,  add $\mathbb{C}[i]$ into $\mathbb{C}^\prime$;
\item If no matching ciphertext is found, output $\mathbb{C}^\prime$;
\item Compute $Pt^\prime=\mathbf{Dec}_{\mbox{\tiny IBE}}(\tilde{S}_{ID^\prime},\mathbb{C}[i,2])$, go to step 2;
\end{enumerate}
\end{itemize}

Figure \ref{F.SPCHS.Generic} shows a hidden star-like structure generated by the generic SPCHS construction. When running algorithm $\mathbf{StructuredSearch}(\mathbf{PK},\mathbf{Pub},\mathbb{C},T_{W_i})$, the full-identity malleability of IBKEM allows the algorithm to disclose the value $\mathbf{FIM}(W_i,u)$ by computing $\mathbf{FIM}(W_i,u)=\mathbf{Decaps}_{\mbox{\tiny IBKEM}}(\hat{S}_{W_i},\mathbf{Pub})$ and find out the ciphertext $(\mathbf{FIM}(W_i,u),\mathbf{Enc}_{\mbox{\tiny IBE}}(\mathbf{PK}_{\mbox{\tiny IBE}},$ $W_i,Pt[u,W_i]))$. Then the consistency of IBE allows the algorithm to disclose $Pt[u,W_i]$ by decrypting $\mathbf{Enc}_{\mbox{\tiny IBE}}(\mathbf{PK}_{\mbox{\tiny IBE}},$ $W_i,Pt[u,W_i])$ and find out the ciphertext $(Pt[u,W_i],\mathbf{Enc}_{\mbox{\tiny IBE}}($ $\mathbf{PK}_{\mbox{\tiny IBE}},$ $W_i,R))$. By carrying on in this way,
the consistency of IBE allows the algorithm to find out the rest of ciphertexts of keyword $W_i$ with the hidden star-like structure, and stop the search if no more ciphertexts are found.

\begin{figure*}[!htp]
\centering
\begin{boxedminipage}{0.9\textwidth}
\includegraphics[scale=0.7]{GenericSPCHS}
\begin{quote}
Note that in each ciphertext, the value $R$ is randomly chosen. For $i\in[1,L]$, $Pt[u,W_i]$ is initialized with a random value when generating the first ciphertext of keyword $W_i$, and it will be updated into $R$ after generating each subsequent ciphertext of keyword $W_i$.
\end{quote}
\end{boxedminipage}
\caption{Hidden star-like structure generated by the generic SPCHS construction}\label{F.SPCHS.Generic}
\end{figure*}

\textbf{Consistency.} When running the above algorithm $\mathbf{StructuredSearch}(\mathbf{PK},\mathbf{Pub},\mathbb{C},T_W)$, the consistency and full-identity malleability of IBKEM assures that $\mathbf{FIM}(W,u)=\mathbf{Decaps}_{\mbox{\tiny IBKEM}}(\hat{S}_W,\mathbf{Pub})$ holds. The collision-freeness of IBKEM assures that only one ciphertext containing keyword $W$ has the value $\mathbf{FIM}(W,u)$ as its first part. Therefore the algorithm can find out the first ciphertext of keyword $W$ with the hidden structure $\mathbf{Pub}$. Then the consistency of IBE allows the algorithm $\mathbf{StructuredSearch}$ to find out the rest of ciphertexts containing keyword $W$ with the hidden structure $\mathbf{Pub}$. Formally we have Theorem \ref{T.SPCHS.Generic.Consistency}. The proof can be found in Supplemental Materials D.

\begin{theorem}\label{T.SPCHS.Generic.Consistency}
The above generic SPCHS scheme is consistent if its underlying collision-free full-identity malleable IBKEM and IBE schemes are both consistent.
\end{theorem}

\textbf{Semantic Security.} The SS-sK-CKSA security of the above generic SPCHS construction relies on the Anon-SS-sID-CPA security of the underlying IBKEM and the Anon-SS-ID-CPA security of the underlying IBE. In the security proof, we prove that if there is an adversary who can break the SS-sK-CKSA security of the above generic SPCHS construction, then there is another adversary who can break the Anon-SS-sID-CPA security of the underlying IBKEM or the Anon-SS-ID-CPA security of the underlying IBE. Theorem \ref{T.SPCHS.Generic.Security} formally states the semantic security of our generic SPCHS construction. The proof can be found in Supplemental Materials E.

\begin{theorem}\label{T.SPCHS.Generic.Security}
Suppose there are at most $N\in\mathbb{N}$ hidden structures, and a PPT adversary $\mathcal{A}$ wins in the SS-sK-CKSA game with advantage $Adv^{\text{SS-sK-CKSA}}_{SPCHS,\mathcal{A}}$. Then there is a PPT adversary $\mathcal{B}$, who utilizes the capability of $\mathcal{A}$ to win in the Anon-SS-sID-CPA game of the underlying IBKEM or the Anon-SS-ID-CPA game of the underlying IBE with advantage $\frac{1}{4N}\cdot Adv^{\text{SS-sK-CKSA}}_{SPCHS,\mathcal{A}}$.
\end{theorem}

\section{Two Collision-Free Full-Identity Malleable IBKEM Instances}\label{S.IBKEM.Instances}

\textbf{The Instance in the RO Model.} Abdalla \emph{et al.} proposed several VRF-suitable IBKEM instances in \cite{ACF13}. An IBKEM instance is VRF-suitable if it provides \emph{unique decapsulation}. This means that given any encapsulation, all the decryption keys corresponding to the same identity decapsulate out the same encapsulated key, and the key is pseudo-random. Here, the decryption key extraction is probabilistic and for the same identity, different decryption key may be extracted in different runs of the key extraction algorithm. It is clear that our proposed collision-free full-identity malleability not only implies \emph{unique decapsulation}, but also implies that the generator of an encapsulation knows what keys will be decapsulated by the decryption keys of all identities. In Supplemental Materials  F, we prove that the VRF-suitable IBKEM instance proposed in Appendix A.2 of \cite{ACF13} is collision-free full-identity malleable. Even though this IBKEM scheme has the traditional Anon-SS-ID-CPA security, we further prove that this IBKEM scheme is Anon-SS-ID-CPA secure based on the DBDH assumption in the RO model according to Definition \ref{D.IBKEM.Security}.

\textbf{The Instance in the Standard Model.}  In \cite{FHPS13}, Freire \emph{et al.} utilized the ``approximation'' of multilinear maps \cite{GGH13} to construct a programmable hash function in the multilinear setting (MPHF). Then Freire \emph{et al.} utilized this hash function to replace the traditional hash functions of the BF IBE scheme in \cite{BF01} and reconstructed this IBE scheme in the multilinear setting. They finally constructed a new IBE scheme with semantic security in the standard model. We find that this new IBE scheme can be easily transformed into a collision-free full-identity malleable IBKEM scheme with Anon-SS-ID-CPA security in the standard model. To simplify the description of this IBKEM scheme, we do not consider the ``approximation'' of multilinear maps. This means that we will leave out the functions that are the encoding of a group element,  the re-randomization of an encoding and the extraction of an encoding.  Some related definitions are reviewed as follows.

\begin{definition}[Multilinear Maps \cite{FHPS13}]\label{D.Multilinear}
An $\ell$-group system in the multilinear setting consists of $\ell$ cyclic groups $\mathbb{G}_1,\cdots ,\mathbb{G}_{\ell}$ of prime order $p$, along with bilinear maps $\hat{e}_{i,j} : \mathbb{G}_i \times \mathbb{G}_j \rightarrow \mathbb{G}_{i+j}$ for all $i,j \geq 1$ with $i+j \leq \ell$. Let $g_i$ be a generator of $\mathbb{G}_i$. The map $\hat{e}_{i,j}$ satisfies $\hat{e}_{i,j}(g^a_i,g^b_j) = g^{ab}_{i+j}$ (for all $a,b \in \mathbb{Z}_p$). When $i,j$ are clear, we will simply write $\hat{e}$ instead of $\hat{e}_{i,j}$. It will also be convenient to abbreviate $\hat{e}(h_1, \cdots, h_j) =\hat{e}(h_1,\hat{e}(h_2, \cdots, \hat{e}(h_{j-1},h_j)\cdots))$ for $h_j \in \mathbb{G}_{i_j}$ and $i = (i_1 + i_2 + \cdots + i_j) \leq \ell$. By induction, it is easy to see that this map is $j$-linear. Additionally, We define $\hat{e}(g)= g$. Finally, it can also be useful to define the group $\mathbb{G}_0 = \mathbb{Z}^+_{\left| \mathbb{G}_1 \right|}$ of exponents to which this pairing family naturally extends. In the following, we will assume an $\ell$-group system  $\mathbf{MPG}_{\ell} = \{\{\mathbb{G}_i\}_{i \in [1,\ell]},p, \{\hat{e}_{i,j}\}_{i,j\geq1,i+j\leq\ell}\}$ generated by a \emph{multilinear maps parameter generator} $\mathbf{MG}_{\ell}$ on input a security parameter $1^k$.
\end{definition}

\begin{definition}[The $\ell$-MDDH Assumption \cite{FHPS13}]\label{D.MDDH}
Given $(g,g^{x_1},\cdots,$ $g^{x_{\ell+1}})$ (for $g\overset{\$}{\leftarrow} \mathbb{G}_1$ and uniform exponents $x_i$), the $\ell$-MDDH assumption is that the element $\hat{e}(g^{x_1},\cdots ,g^{x_\ell})^{x_{\ell+1}} \in \mathbb{G}_\ell$ is computationally indistinguishable from a uniform $\mathbb{G}_\ell$-element.
\end{definition}

\begin{definition}[Group hash function \cite{FHPS13}]\label{D.GroupHash}
A group hash function $\mathbf{H}$ into $\mathbb{G}$ consists of two polynomial-time algorithms: the probabilistic algorithm $\mathbf{HGen}(1^k)$ outputs a key $hk$, and $\mathbf{HEval}($ $hk,X)$ (for a key $hk$ and $X \in {\{0,1\}}^k$) deterministically outputs an image $\mathbf{H}_{hk}(X)\in\mathbb{G}$.
\end{definition}

\begin{definition}[MPHF \cite{FHPS13}]\label{D.MPHF}
Assume an $\ell^\prime$-group system $\mathbf{MPG}_{\ell^\prime}$ as generated by $\mathbf{MG}_{\ell^\prime}(1^k)$. Let $\mathbf{H}$ be a group hash function into $\mathbb{G}_{\ell}(\ell \leq \ell^\prime)$, and let $m,n \in \mathbb{N}$. We say that $\mathbf{H}$ is an (m,n)-programmable hash function in the multilinear setting ((m,n)-MPHF) if there are PPT algorithms $\mathbf{TGen}$ and $\mathbf{TEval}$ as follows.

\begin{itemize}
\item $\mathbf{TGen}(1^k,c_1,\cdots,c_l,h)$ (for $c_i,h \in \mathbb{G}_1$ and $h\neq 1$) outputs a key $hk$ and a trapdoor $td$. We require that for all $c_i,h$, that distribution of $hk$ is statistically close to the output of $\mathbf{HGen}$.

\item $\mathbf{TEval}(td,X)$ (for a trapdoor $td$ and $X \in {\{0,1\}}^k$) deterministically outputs $a_X \in \mathbb{Z}_p^*$ and $B_X \in \mathbb{G}_{\ell-1}$ with $\mathbf{H}_{hk}(X)= \hat{e}(c_1,\cdots,c_\ell)^{a_X} \cdot \hat{e}(B_X,h)$. We require that there is a polynomial $p(k)$ such that for all $hk$ and $X_1, \cdots, X_m$, $Z_1, \cdots, Z_n \in {\{0,1\}}^k$ with ${\{X_i\}}_i \bigcap {\{Z_j\}}_j = \emptyset$,
$P_{hk,\{X_i\},\{Z_j\}} =Pr[(a_{X_1} = \cdots = a_{X_m} = 0) \land (a_{Z_1},\cdots,a_{X_n}\neq0)]\geq 1/p(k)$,
where the probability is over possible trapdoors $td$ output by $\mathbf{TGen}$ along with the given $hk$. Furthermore, we require that
    $P_{hk,\{X_i\},\{Z_j\}}$ is close to statistically independent of $hk$. (Formally, $|P_{hk,\{X_i\},\{Z_j\}}-P_{hk^\prime,\{X_i\},\{Z_j\}}|\leq v(k)$ for all $hk$ and $hk^\prime$ in the range of $\mathbf{TGen}$,
    all $\{X_i\},\{Z_j\}$, and negligible $v(k)$.)
\end{itemize}
We say that $\mathbf{H}$ is a $(\mathsf{poly},n)$-MPHF if it is a $(q(k),n)$-MPHF for every polynomial $q(k)$. Note that $\mathbf{TEval}$ algorithm of an MPHF into $\mathbb{G}_1$ yields $B_X \in \mathbb{G}_0$, i.e., exponents $B_X$.
\end{definition}

Let identity space $\mathcal{ID}_{\mbox{\tiny IBKEM}}=\{0,1\}^k$. The IBKEM instance in the standard model is as follows.

\begin{itemize}
\item $\mathbf{Setup}_{\mbox{\tiny IBKEM}}(1^k,\mathcal{ID}_{\mbox{\tiny IBKEM}})$: Take as input a security parameter $1^k$ and the identity space $\mathcal{ID}_{\mbox{\tiny IBKEM}}$, generate an $(\ell+1)$-group system $\mathbf{MPG}_{\ell+1}= \{\{\mathbb{G}_i\}_{i \in [1,\ell+1]}, p, \{\hat{e}_{i,j}\}_{i,j\geq1,i+j\leq\ell+1}\}\leftarrow\mathbf{MG}_{\ell+1}(1^k)$, generate a $(\mathsf{poly},2)$-MPHF $\mathbf{H}$ into $\mathbb{G}_\ell$ and $hk\leftarrow \mathbf{HGen}(1^k)$, choose $h\overset{\$}{\leftarrow} \mathbb{G}_1$ and  $x\overset{\$}{\leftarrow}\mathbb{Z}_p$, set the encapsulated key space $\mathcal{K}_{\mbox{\tiny IBKEM}}=\mathbb{G}_{\ell+1}$, set the encapsulation space $\mathcal{C}_{\mbox{\tiny IBKEM}}=\mathbb{G}_1$, and output the master public key $\mathbf{PK}_{\mbox{\tiny IBKEM}}=(\mathbf{MPG}_{\ell+1},hk,\mathbf{H},h,h^x,\mathcal{ID}_{\mbox{\tiny IBKEM}},\mathcal{K}_{\mbox{\tiny IBKEM}},$ $\mathcal{C}_{\mbox{\tiny IBKEM}})$ and the master secret key $\mathbf{SK}_{\mbox{\tiny IBKEM}}=(hk,x)$.

\item $\mathbf{Extract}_{\mbox{\tiny IBKEM}}(\mathbf{SK}_{\mbox{\tiny IBKEM}},ID)$: Take as inputs $\mathbf{SK}_{\mbox{\tiny IBKEM}}$ and an identity $ID\in\mathcal{ID}_{\mbox{\tiny IBKEM}}$, and output a decryption key $\hat{S}_{ID}=\mathbf{H}_{hk}(ID)^x$ of $ID$.

\item $\mathbf{Encaps}_{\mbox{\tiny IBKEM}}(\mathbf{PK}_{\mbox{\tiny IBKEM}},ID,r)$: Take as inputs $\mathbf{PK}_{\mbox{\tiny IBKEM}}$, an identity $ID\in\mathcal{ID}_{\mbox{\tiny IBKEM}}$ and a random value $r\in\mathbb{Z}_p^*$, and output a key-and-encapsulation pair $(\hat{K},\hat{C})$, where $\hat{K}=\hat{e}(\mathbf{H}_{hk}(ID),h^x)^r\in\mathbb{G}_{\ell+1}$ and $\hat{C}=h^r$.

\item $\mathbf{Decaps}_{\mbox{\tiny IBKEM}}(\hat{S}_{ID^\prime},\hat{C})$: Take as inputs the decryption key $\hat{S}_{ID^\prime}$ of identity $ID^\prime$ and an encapsulation $\hat{C}$, and output the encapsulated key $\hat{K}=\hat{e}(\hat{C},\hat{S}_{ID^\prime})\in\mathbb{G}_{\ell+1}$ if $\hat{C}\in\mathbb{G}_1$ or output $\bot$ otherwise.
\end{itemize}

\textbf{Consistency.} According to Definitions \ref{D.Multilinear} and \ref{D.GroupHash}, it is very easy to verify the consistency of the above IBKEM scheme.

\textbf{Collision-Free Full-Identity Malleability.} Let the function $\mathbf{FIM}(ID,r)=\hat{e}(h^x,\mathbf{H}_{hk}(ID))^r\in\mathbb{G}_{\ell+1}$ for any identity $ID\in\mathcal{ID}_{\mbox{\tiny IBKEM}}$ and any random value $r\in\mathbb{Z}_p^*$. Given any $(\hat{K},\hat{C})\leftarrow\mathbf{Encaps}_{\mbox{\tiny IBKEM}}(\mathbf{PK}_{\mbox{\tiny IBKEM}},ID,r)$, we clearly have that: (1) for any identity $ID^\prime$, equation $\mathbf{FIM}(ID^\prime,$ $r)=\mathbf{Decaps}_{\mbox{\tiny IBKEM}}(\hat{S}_{ID^\prime},\hat{C})$ holds; (2) for any identity $ID^\prime$ and any random value $r^\prime$, if $ID^\prime\neq ID\bigvee r^\prime\neq r$ holds, equation $\mathbf{FIM}(ID,r)\neq \mathbf{FIM}(ID^\prime,r^\prime)$ holds except with a negligible probability. So the above IBKEM scheme is collision-free full-identity malleable.

\textbf{Anon-SS-ID-CPA Security.} In \cite{FHPS13}, Freire \emph{et al.} utilized a $(\mathsf{poly},1)$-MPHF to construct a standard-model version of the BF IBE scheme with the SS-ID-CPA security. On the contrary, we use a $(\mathsf{poly},2)$-MPHF in constructing the above IBKEM scheme, since this kind of MPHF is more useful in proving the Anon-SS-ID-CPA security. Theorem \ref{T.IBKEM.Instance.Security} formally states the Anon-SS-ID-CPA security of the above IBKEM scheme. The proof can be found in Supplemental Materials  G.

\begin{theorem}\label{T.IBKEM.Instance.Security}
Assume the above IBKEM scheme is implemented in an $(\ell+1)$-group system, and with a $(\mathsf{poly},2)$-MPHF $\mathbf{H}$ into $\mathbb{G}_\ell$. Then, under the $(\ell+1)$-MDDH assumption, this IBKEM scheme is Anon-SS-ID-CPA secure.
\end{theorem}

According to Theorem \ref{T.SPCHS.Generic.Security} and \ref{T.IBKEM.Instance.Security}, the generic SPCHS construction implies a SPCHS instance with SS-sK-CKSA security in the standard model. Indeed, this SPCHS instance can be provably SS-CKSA secure.

\section{Conclusion and Future Work}\label{S.Conclusion}

This paper investigated as-fast-as-possible search in PEKS with semantic security. We proposed the concept of SPCHS as a variant of PEKS. The new concept allows keyword-searchable ciphertexts to be generated with a hidden structure. Given a keyword search trapdoor, the search algorithm of SPCHS can disclose part of this hidden structure for guidance on finding out the ciphertexts of the queried keyword. Semantic security of SPCHS captures the privacy of the keywords and the invisibility of the hidden structures. We proposed an SPCHS scheme from scratch with semantic security in the RO model. The scheme generates keyword-searchable ciphertexts with a hidden star-like structure. It has search complexity mainly linear with the exact number of the ciphertexts containing the queried keyword. It outperforms existing PEKS schemes with semantic security, whose search complexity is linear with the number of all ciphertexts. We identified several interesting properties, i.e., collision-freeness and full-identity malleability in some IBKEM instances, and formalized these properties to build a generic SPCHS construction. We illustrated two collision-free full-identity malleable IBKEM instances, which are respectively secure in the RO and standard models.

SPCHS seems a promising tool to solve some challenging problems in public-key searchable encryption. One application may be to achieve retrieval completeness verification which, to the best of our knowledge, has not been achieved in existing PEKS schemes. Specifically, by forming a hidden ring-like structure, i.e., letting the last hidden pointer always point to the head, one can obtain PEKS allowing to check the completeness of the retrieved ciphertexts by checking whether the pointers of the returned ciphertexts form a ring.

Another application may be to realize public key encryption with content search, a similar functionality realized by symmetric searchable encryption. Such kind  of content-searchable encryption is useful in practice, e.g., to filter the encrypted spams. Specially, by forming a hidden tree-like structure between the sequentially encrypted words in one file, one can obtain public-key searchable encryption allowing content search (e.g., to find whether there are specific contents in an encrypted file). The search complexity is linear with the size of the queried content.

\section*{Acknowledgments}
The authors would like to thank the reviewers for their valuable suggestions that helped to improve the paper greatly. The first author is partly supported by the National Natural Science Foundation of China under grant no. 61472156 and the National Program on Key Basic Research Project (973 Program) under grant no. 2014CB340600. The second author is supported by by the Chinese National Key Basic Research Program (973 program) through project 2012CB315905, the Natural Science Foundation of China through projects 61370190, 61173154, 61472429, 61402029, 61272501, 61202465, 61321064 and 61003214, the Beijing Natural Science Foundation through project 4132056, the Fundamental Research Funds for the Central Universities, and the Research Funds (No. 14XNLF02) of Renmin University of China and the Open Research Fund of Beijing Key Laboratory of Trusted Computing. The fifth author is partly support by the European Commission (H2020 project ``CLARUS''), the Government of Catalonia (grant 2014 SGR 537 and ICREA Acad\`emia Award 2013) and the Spanish Government (TIN2011-27076-C03-01 ``CO-PRIVACY''). The views in this paper do not necessarily reflect the views
of UNESCO.

redpajama_set_name: RedPajamaArXiv


If poetry would have a physical form what would it be?
UTOPIA blu* is a cooperative architectural design firm located in Amsterdam, NL and London, UK. They work with a variety of partners and have collaborated with Dutch fashion designer Anouk Wipprecht to create the amazing spiderbots.
The creative duo of Philip H Wilck and Tiia Vahula focuses on design for 3D printing and creative fabrication. By using various digital tools numerous projects are investigating cutting edge digital fabrication methods and limits of physical forms. They shape the future by pushing boundaries of art and science and merging complex geometry with technology.


Evidence gathered from NERVA I and the work done on PBR indicated fuel elements survival at high temperature and pressure are among the critical issues. Driven also by the need to extend the life of fuel elements in the reactors powering the nuclear airplane planned in the 1950s and 1960s, USAF developed the CERMET reactor concept, and tested a single fuel element to check improvements in its working life [Lawrence, 2008].
In a CERMET NTR the fuel is stored as 235U-rich UO2 encapsulated by, or dispersed in, tungsten, molybdenum or tungsten-rhenium. No moderator (e.g., graphite) is interposed between fuel and jackets, so that the energy spectrum of fission fragments is broader, up to O(1) MeV. The main task of the refractory metal is to contain fission fragments better than more conventional ceramic or metal matrices, i.e., with less damaging structural effects. CERMET fuel in this form has been tested at temperatures of order 1,900 K (in the US and Russia) with excellent results. The maximum operating T of CERMET fuel elements is 2,500 K; lifetime up to 19,000 hours at 1,900 K has been demonstrated, even after fuel elements were cycled through many restarts and shutdowns. For this reason, this type of NTR technology is considered best suited to OTV propulsion, where engines must be turned on and off very reliably for many years. The spatial density of fuel is not as high as in PBR: in fact, the estimated thrust/weight ratio is only 5-6. Pressure losses of order 30%, very high, contribute to the low absolute performance. In fact, the Isp predicted in future rocket engines embodying this technology is only about 900 s. The major advantage of this concept is therefore its very attractive and robust fuel elements technology, resulting in the ability of multiple restarts and (presumably) long maintenance-free engine life.


Person is on instagram saying he can turn your $100 into $1000 and wants you to send him the money through moneygram and he will reroute it back to you and all you have to do is send him his 30% back. This is a scam! When I sent the money he never answers my text or calls anymore.


Thank you for considering The Fraiche Kitchen for your next special occasion! We are committed to freshly inspired, seasonal menus created for your event. All of our dishes are made 100% from scratch using locally sourced organic ingredients.
Sharing nutritional information and cooking for our clients is a pleasure. We have numerous clients with special diet requirements and at TFK we strive to create pleasurable as well as delectable dining experiences. Please contact us to inquire about Private Chef Services.
TFK is excited to bring small, hands-on cooking classes to you! Together with guest chefs and instructors, TFK will share their knowledge and passion for foods. TFK Cooking Classes are available for your private parties and corporate team building. Perfect for kids' birthday parties too!
TFK is always excited to work with our clients to create custom gift packages.
With extensive experience styling on TV shows, videos & commercials, and working with many chefs and recipes, we are available to assist on your next project!


text:
Pulling Weeds before Planting Seeds
Andy Napier Footsteps
In 1 Corinthians 3:5-6 (NKJV), the apostle Paul writes, "Who then is Paul, and who is Apollos, but ministers through whom you believed, as the Lord gave to each one? I planted, Apollos watered, but God gave the increase." For some skeptics, we need to add another, earlier step to this process of coming to know Christ--"Dave Fisher pulled weeds." For most of his 58 years with TWR, the late Dave served as the editor for TWR's program, Truth In The Test Tube. On today's Footsteps, Dave referred to "those who have never thought seriously about God." He was referencing the parable of the sower in Matthew 13:7 (ESV)--"Other seeds fell among thorns, and the thorns grew up and choked them." So Dave's approach was to "pull weeds before planting seeds." What exactly are some of these "weeds?" You definitely need to listen to this program!
Click here to listen to Truth In The Test Tube
Click here to listen to Footsteps' Latest Program
Click here to visit Footsteps
(Photo of Dave Fisher)
Andy Napier
Andy Napier is the host and producer of TWR's 2-minute daily feature called "Footsteps." Previously, Andy served for 24 years with WMBW (Moody Radio Chattanooga, Tennessee) in several capacities including Program Director and Host of the Morning Program. Andy and his wife, Kathy, along with their two boys, Sam (13) and John Edward (10), made the move to North Carolina in October of 2013 to serve as missionaries with TWR.
More Posts by Andy Napier :
A Big Part
Hidden in a Sleeping Bag
A Man in Montenegro

redpajama_set_name: RedPajamaCommonCrawl


Description: Simple Electric Circuit Drawing Drawing Artsy Simple Circuit Drawing Simple Electric Circuit Diagram For Kids #2248 from the above 1438x1024 resolutions which is part of the "DIY Needed" directory. Download this image for free in HD resolution the choice "Save full resolution" below. If you do not find the exact resolution you are looking for, then go for a native or higher resolution.
One among probably the most popular electrical wiring thoughts is on how to wire a swap. While making use of switches in the home is kind of simple, wiring just one may not be that effortless for everybody. An ON-OFF switch is definitely quite simple to wire. There are actually various kinds of switches, but for this instance, let us say that you are setting up a single-pole toggle switch, a really popular switch (and the most straightforward).
There are three shades of wires in a very typical single-pole toggle switch: black, white, and inexperienced. Splice the black wire in two and join them to the terminal screws - 1 on major and the other over the base screw on the swap. The white wire serves being a supply of uninterrupted energy which is commonly linked to your light-weight coloured terminal screw (e.g., silver). Connect the environmentally friendly wire for the ground screw of your swap.
These steps would normally be ample to produce an average change function without a challenge. Nevertheless, when you will not be self-confident you can carry out the process adequately and properly you improved permit the pros get it done alternatively. Soon after all, there is a reason why this task is amongst the commonest electrical wiring questions questioned by most people.
For a few rationale, the best way to wire a ceiling fan is usually considered one of probably the most widespread electrical wiring questions. To simplify this process, you should use one change for any single ceiling fan. To wire the lover, it can be just a matter of connecting the black wire in the ceiling fan into the black wire on the switch. When there is a lightweight, the blue wire must be connected for the black wire with the switch in addition.
You will discover good reasons why they're quite possibly the most frequently asked electrical wiring questions. Just one, a lot of assume it is basic to do, and two, these are definitely the popular electrical jobs at your home. But then you definately must not place your security at risk as part of your purpose to save cash. The stakes could even be a great deal bigger should you attempt to save money and do an electrical wiring work without ample awareness or knowledge.


text:
FirstSun Capital Bancorp to Acquire Pioneer Bancshares, Inc.
FirstSun Capital Bancorp: Jeanne Lipson, [email protected], 915.881.6785
Pioneer Bancshares, Inc.: Joni Phariss, [email protected], 281.632.1431
Colorado-based FirstSun Capital Bancorp ("FirstSun," or the "Company"), the holding company of Sunflower Bank, N.A. ("Sunflower Bank") and Texas-based Pioneer Bancshares, Inc. ("Pioneer"), the holding company of Pioneer Bank, SSB ("Pioneer Bank") jointly announced today that they have entered into a definitive agreement pursuant to which Pioneer and Pioneer Bank will merge with and into FirstSun and Sunflower Bank, respectively, in an all-stock transaction.
On a pro forma basis as of March 31, 2021, the combined company would have over $7 billion in total assets with over $5 billion in both loans and deposits, and over 60 branch locations. Sunflower Bank's expanded pro forma footprint will include some of the largest growth markets in the United States. This combination will bring Sunflower Bank an expanded presence in Texas, along with its footprint in Arizona, Colorado, Kansas and New Mexico and home mortgage origination capabilities in 43 states.
The transaction is intended to qualify as a tax-free reorganization for U.S. federal income tax purposes. The financial terms of the transaction were not disclosed. The transaction is expected to close early in October 2021, subject to satisfaction of customary closing conditions, including receipt of regulatory approvals and Pioneer shareholder approval. Upon closing, the Board of Directors of both FirstSun a nd Sunflower Bank will be expanded to include former directors of Pioneer and Pioneer Bank.
"We are thrilled to welcome Pioneer Bank's customers and associates to the Sunflower family," said Mollie Carter, Chairman of FirstSun and Sunflower. "We believe the additions brought by Pioneer will complement our growing presence in Texas and will be a perfect fit with our existing customer base and relationship-driven philosophy."
"The opportunity for Pioneer Bank to join forces with Sunflower is a uniquely exciting one. The combined institution brings together two strong, growth-oriented banks that will provide a more competitive platform to our communities in Austin, Houston, Dallas, San Antonio and our markets in between," added Ron Coben, President and CEO of Pioneer.
Stephens Inc. served as financial advisor to FirstSun and Nelson Mullins Riley & Scarborough LLP served as legal counsel. Piper Sandler & Co. served as financial advisor to Pioneer and Bracewell LLP served as legal counsel.
About FirstSun Capital Bancorp
FirstSun Capital Bancorp, headquartered in Denver, Colorado, is the financial holding company for Sunflower Bank, N.A., which operates as Sunflower Bank, First National 1870 and Guardian Mortgage. Sunflower Bank provides a full range of relationship-focused services to meet personal, business and wealth management financial objectives, with a branch network in five states and mortgage capabilities in 43 states. FirstSun had total consolidated assets of $5.3 billion as of March 31, 2021.
First National 1870 and Guardian Mortgage are divisions of Sunflower Bank. To learn more, visit SunflowerBank.com, FirstNational1870.com or GuardianMortgageOnline.com.
About Pioneer Bancshares, Inc.
Pioneer Bancshares, Inc. is the bank holding company for Pioneer Bank, SSB, an Austin-based community bank that lives and breathes Texas by serving markets, large and small, across the state, including Austin, Houston, Dallas, San Antonio, and Waco. At March 31, 2021, Pioneer reported consolidated total assets of $1.8 billion and total deposits of $1.3 billion. Visit Pioneer.Bank to learn more.
Statements included in this press release which are not historical in nature are intended to be, and hereby are identified as, forward-looking statements within the meaning of the Private Securities Litigation Reform Act of 1995. Examples of forward-looking statements include, but are not limited to, statements regarding the outlook and expectations of FirstSun and Pioneer with respect to their planned merger and the expected timing of the closing of the transaction. Words such as "may," "will," "believe," "anticipate," "expect," "intend," "opportunity," "continue," "should," and "could" and variations of such words and similar expressions are intended to identify such forward-looking statements. Forward-looking statements are subject to risks, uncertainties and assumptions that are difficult to predict with regard to timing, extent, likelihood and degree of occurrence, which could cause actual results to differ materially from anticipated results. Such risks, uncertainties and assumptions, include, among others, the following:
the failure to obtain necessary regulatory approvals when expected or at all (and the risk that such approvals may result in the imposition of conditions that could adversely affect the combined company or the expected benefits of the transaction);
the failure of Pioneer to obtain shareholder approval, or the failure of either party to satisfy any of the other closing conditions to the transaction on a timely basis or at all;
the occurrence of any event, change or other circumstances that could give rise to the right of one or both of the parties to terminate the merger agreement;
the possibility that the anticipated benefits of the transaction, including as a result of the impact of, or problems arising from, the integration of the two companies or as a result of the strength of the economy, competitive factors in the areas where FirstSun and Pioneer do business, or as a result of other unexpected factors or events;
diversion of management's attention from ongoing business operations and opportunities;
potential adverse reactions or changes to business or employee relationships, including those resulting from the announcement or completion of the transaction;
the outcome of any legal proceedings that may be instituted against FirstSun or Pioneer; and
other factors that may affect future results of FirstSun or Pioneer including changes in asset quality and credit risk; the inability to sustain revenue and earnings growth; changes in interest rates and capital markets; inflation; customer borrowing, repayment, investment and deposit practices; the impact, extent and timing of technological changes; capital management activities; and other actions of the Federal Reserve Board and legislative and regulatory actions and reforms.
FirstSun and Pioneer disclaim any obligation to update or revise any forward-looking statements contained in this press release, which speak only as of the date hereof, whether as a result of new information, future events or otherwise, except as required by law.
Additional Information About the Merger and Where to Find It
This communication is being made in respect of the proposed merger transaction between FirstSun and Pioneer. In connection with the proposed merger, FirstSun will file a registration statement on Form S-4 with the SEC to register FirstSun's shares that will be issued to Pioneer's shareholders in connection with the merger. The registration statement will include a proxy statement of Pioneer and a prospectus of FirstSun, as well as other relevant documents concerning the proposed transaction. INVESTORS ARE URGED TO READ THE REGISTRATION STATEMENT AND THE PROXY STATEMENT/PROSPECTUS REGARDING THE MERGER WHEN IT BECOMES AVAILABLE AND ANY OTHER RELEVANT DOCUMENTS FILED WITH THE SEC, AS WELL AS ANY AMENDMENTS OR SUPPLEMENTS TO THOSE DOCUMENTS, BECAUSE THEY WILL CONTAIN IMPORTANT INFORMATION.
This communication does not constitute an offer to sell or the solicitation of an offer to buy any securities or a solicitation of any vote or approval, nor shall there be any sale of securities in any jurisdiction in which such offer, solicitation or sale would be unlawful prior to registration or qualification under the securities laws of such jurisdiction.
A free copy of the proxy statement/prospectus, when it becomes available, as well as other documents filed with the SEC by FirstSun may be obtained at the SEC's Internet site at http://www.sec.gov. The definitive proxy statement/prospectus will also be mailed to shareholders of Pioneer.


While the world celebrates change today, one friend of the fashion community, designer Isabel Toledo, is dancing in her studio for another (very good) reason. It is her "lemongrass" ensemble that Michelle Obama decided to wear to the inauguration. "We feel so blessed and honored to be woven up in this great time of transition," said her artist-husband Ruben following the historic occasion.
newly minted First Lady insulated. "Izz and the ladies in our studio were really concerned about keeping Michelle warm!," beamed Ruben.


text:
14,000 persons which  wouldhavc brought the 1975 population to 222,000
without adjusting for in and out migration.    In addition, we know from the
1975 Population Study that there are 48,000 persons in the Boston SMSA who
came into the area since 1965.    By natural change and m-migration    the
population by 1975 would be at 270,000.    The difference of 75,000 between
the potential 270,000 and the actual 1975 population of 195,000 is due to an
ou t-rnigration  from the SMSA  which occurred during the  10 years.     The
figures for in-migration,   48,000,  and out-migration,   75,000,   for a total
turnover of 123,000 people,  are under-estimates of these movements since
the Population Study includes only those persons who were residing in the
area in 1975 and therefore does not include those who came and left between
the two surveys.
The magnitude of i.iis turnover can be seen by the following:
(1) 25 percent of the population (48, 000   here in 1975 came
here within the last 10 year period.
(2) The number of persons who moved away from the area
(75,000) is equal to 36 percent of the population here in 1965.
(3) The total number of people who have moved into or out of the
This data is based on the U.S.   Census Statistical Abstract for 1971 which gives the
birth rate as 18 per 1,000 and the mortality rate as 7. per 1,000 for the year.    The
rates for that year were used to arrive at the estimate for the 10 year period as it
an approximate mid-point.
Transcript -2- 14,000 persons which wouldhavc brought the 1975 population to 222,000 without adjusting for in and out migration. In addition, we know from the 1975 Population Study that there are 48,000 persons in the Boston SMSA who came into the area since 1965. By natural change and m-migration the population by 1975 would be at 270,000. The difference of 75,000 between the potential 270,000 and the actual 1975 population of 195,000 is due to an ou t-rnigration from the SMSA which occurred during the 10 years. The figures for in-migration, 48,000, and out-migration, 75,000, for a total turnover of 123,000 people, are under-estimates of these movements since the Population Study includes only those persons who were residing in the area in 1975 and therefore does not include those who came and left between the two surveys. The magnitude of i.iis turnover can be seen by the following: (1) 25 percent of the population (48, 000 here in 1975 came here within the last 10 year period. (2) The number of persons who moved away from the area (75,000) is equal to 36 percent of the population here in 1965. (3) The total number of people who have moved into or out of the This data is based on the U.S. Census Statistical Abstract for 1971 which gives the birth rate as 18 per 1,000 and the mortality rate as 7. per 1,000 for the year. The rates for that year were used to arrive at the estimate for the 10 year period as it an approximate mid-point.


Recovery after stroke: not so proportional after all?
The proportional recovery rule asserts that most stroke survivors recover a fixed proportion of lost function. To the extent that this is true, recovery from stroke can be predicted accurately from baseline measures of acute post-stroke impairment alone. Reports that baseline scores explain more than 80%, and sometimes more than 90%, of the variance in the patients' recoveries, are rapidly accumulating. Here, we show that these headline effect sizes are likely inflated. The key effects in this literature are typically expressed as, or reducible to, correlation coefficients between baseline scores and recovery (outcome scores minus baseline scores). Using formal analyses and simulations, we show that these correlations will be extreme when outcomes are significantly less variable than baselines, which they often will be in practice regardless of the real relationship between outcomes and baselines. We show that these effect sizes are likely to be over-optimistic in every empirical study that we found that reported enough information for us to make the judgement, and argue that the same is likely to be true in other studies as well. The implication is that recovery after stroke may not be as proportional as recent studies suggest.
The finding: Several recent studies suggesting that long-term outcome (of a variety of deficits) in stroke is robustly quantitatively predicted by initial symptom severity, may be significantly flawed.
Extensive statistical argumentation (ambitious readers can follow links to two appendices that explain the propositional, theorem, and simulation-based backing of the authors' methods) seems to reveal that in situations where there is much greater variability in baseline (post-stroke) than outcome conditions, correlations will be inflated and extreme. Under these conditions, the idea that baseline impairment accounts for up to 90% of the variance and determines proportionate recovery does not hold.
Strength and weaknesses: While pointing out that "Stroke researchers [and clinicians] are used to thinking of recovery as a complex, multi-factorial process," the authors first provide a succinct yet well-referenced review of the nature and backing of the "proportional recovery rule." The idea that initial deficit severity is related to long-term outcome is not new, but the finding that most patients (and even rats) can be predicted to recover 70% of lost function, with around 90% of the variance explained by initial deficit severity, is relatively new (or at least newly, and seemingly robustly, supported). The statistical analysis employed here is dense, but the main text does not go beyond correlations and standard deviations. Still, they are related to each other in ways that make these 7 pages pretty slow going. Rigor and readability were not correlated with one another in a statistically or comprehensibility significant way by the authors. There is just enough discussion of the nature of stroke victims as patients and subjects to show that the authors understand what they are studying as more than a mere abstraction. The discussion section summarizes things nicely and reveals the paper to be an attempt at being constructive, rather than a mere takedown.
Relevance: The review and critique of the proportional recovery rule are quite important to those of us working in neurological settings. The proportional recovery rule has been applied to paresis, aphasia, and "may even apply generally across cognitive domains." The evidence supporting this idea has been published in several prestigious clinical journals in the past three years particularly. Familiarity with this concept and with its possible shortcomings will inform case contemplation as well as conversations with neurologist consultees (who may be unfamiliar with, wedded to, or skeptical of it), patients, and families.