11institutetext: certSIGN – Research and Innovation, Bucharest, Romania
22institutetext: Institute of Mathematics “Simion Stoilow” of the Romanian
Academy 33institutetext: Babeş-Bolyai University, Cluj-Napoca, Romania
33email<EMAIL_ADDRESS>
# Composing Bridges

Mugurel Barcau 1122 Vicenţiu Paşol 1122 George C. Ţurcaş 1133

###### Abstract

The present work builds on previous investigations of the authors (and their
collaborators) regarding bridges, a certain type of morphisms between
encryption schemes, making a step forward in developing a (category theory)
language for studying relations between encryption schemes. Here we analyse
the conditions under which bridges can be performed sequentially, formalizing
the notion of composability. One of our results gives a sufficient condition
for a pair of bridges to be composable. We illustrate that composing two
bridges, each independently satisfying a previously established IND-CPA
security definition, can actually lead to an insecure bridge. Our main result
gives a sufficient condition that a pair of secure composable bridges should
satisfy in order for their composition to be a secure bridge. We also
introduce the concept of a complete bridge and show that it is connected to
the notion of Fully composable Homomorphic Encryption (FcHE), recently
considered by Micciancio. Moreover, we show that a result of Micciancio which
gives a construction of FcHE schemes can be phrased in the language of
complete bridges, where his insights can be formalised in a greater
generality.

###### Keywords:

Bridge Composability Fully Composable Homomorphic Encryption IND-CPA security

##  1 Introduction

1.1 When designing a complex cryptographic solution, one has to combine
multiple cryptographic protocols and the interaction between these protocols
is playing an important role in the security of the global solution. For
example, in such a solution one might have ciphertexts encrypted under
different secret keys, or even encrypted using different encryption schemes.
This gives rise to the necessity of switching ciphertexts encrypted using one
secret key to ciphertexts encrypted under a different key. A solution can be
found in the literature under the name of Proxy Re-Encryption (see [6] and the
references within). A similar idea emerges in Hybrid Homomorphic Encryption
(see for example [11] and [12]). Such a protocol is used mainly to reduce
bandwidth costs resulting from ciphertext expansion for the homomorphic
encryption schemes. When Hybrid Homomorphic Encryption is deployed, a server
is able to convert ciphertexts encrypted using a symmetric cipher to
ciphertexts encrypted using a homomorphic encryption scheme. In our previous
work [2], we defined and gave examples of bridges, formalizing the conditions
under which an algorithm that publicly transforms encrypted data from one
scheme to another should perform. In the same work, we defined the IND-CPA
security of a bridge by relating it to the security of a specific encryption
scheme associated to the bridge.

1.2 Here we take a step forward and study the context of interactions between
bridges and deal with their security from a global point of view in relation
with their individual security considerations. For a fair general treatment of
this situation, we point out to the work of Canetti and his collaborators
([8],[9],[10]).

In this work we are concerned with the sequential evaluation, i.e.
composition, of multiple bridges. Ideally, after composing two bridges, the
resulting ciphertext should preserve the underlying plaintext after
decryption. The notion of composability we use and define here for bridges is
finer than the mere instantiation to our case of the universal composition
(UC) notion of Canetti. The universality UC theorem does not apply in our
setting, and neither do the modularity results that can be deduced from the
aforementioned theorem. In our Example 4, both components (protocols) are
secure, while their composition fails this requirement. Moreover, the
correctness property (which is seen in the ideal-process framework as a
security feature) also fails for the generic composition of bridges. However,
we remark that our main theorems which give sufficient conditions for the
composition of bridges to be correct and secure resemble the ideal-process
structural shape in the work of Canetti [8], namely, the indistinguishability
from a process that can be (publicly) described.

1.3 Let us recall some practical and theoretical applications of bridges.
Proxy Re-Encryption can be used in protocols for secure distribution of files
[1], e-mail forwarding and secure payments. As pointed out in [7, page 2], a
procedure called “key rotation”, based on Proxy Re-Encryption is required by
Payment Card Industry Data Security Standard (PCI DSS) and by the Open Web
Application Security Project (OWASP).

In practice, by construction, all Proxy Re-Encryption (PRE) protocols can
convert ciphertexts between the same scheme. Recently, the theoretical concept
of Universal Proxy Re-Encryption (UPRE) [13] was proposed in order to extend
the concept of PRE by accommodating scenarios in which a delegate can convert
ciphertexts from a PKE scheme into ciphertexts of a potentially different PKE
scheme. Unfortunately, UPREs are very difficult to realize in practice.

The overwhelming majority of the examples discussed here involve Fully
Homomorphic Encryption (FHE) schemes. Within this setting, bootstrapping
procedures (such as the recent bootstrapping in FHEW-like cryptosystems [20,
18]) are of great importance. As we pointed out in [2], these give rise to
bridges. The theoretical language of bridges developed in the present work
offers a conceptual framework for explaining the following previously known
fact about certain homomorphic encryption schemes: if one performs a circuit
on encrypted data (which is a bridge) and then a bootstrapping procedure
(which is also a bridge), then the correctness of decryption is preserved
(hence one obtains a third bridge).

In the previous situation, the IND-CPA security analysis of the third bridge
reduces to the circular security of the homomorphic encryption scheme.

1.4 The present article is a natural continuation of the work in [2], where
the underlying motivation was to create a category whose objects are
encryption schemes, aiming to understand relations among them. Considering
bridges as viable candidates for the arrows in such a category, one is
naturally lead to the notion of composing bridges. As we mention in Remark 4
bellow, one can perform composition of bridges when restricting to bridges
that are complete. Unfortunately, composition is not compatible with yet
another feature of encryption schemes, namely their semantic security. Thus,
we are forced, for the moment, to further restrict the morphisms in our
envisaged category to _Gentry-type_ bridges as Theorem 6.2 asserts. Sadly,
this constraint on morphisms forces a restriction on the objects (i.e.
encryption schemes), namely in this setting one must restrict to the study of
relations between FHE schemes. Moreover, if we want to allow “self-morphisms”
(there is a nuance that differentiates them from endomorphisms), i.e. bridges
between the same scheme which have the _same_ secret key, then we need to
limit our attention to those FHE schemes which are circular secure (see
Theorem 7.1).

1.5 As we shall see throughout this paper, multiple technical difficulties
arise when one sequentially performs bridges.

Firstly, as we point out shortly after Definition 7, due to the possible loss
of correctness of decryption, the composition of two bridges is not
necessarily a bridge. We overcome this by introducing the notion of complete
bridges (see Definition 8), a type of bridge which satisfies an enhanced
correctness property with respect to the decryption algorithms. We then show
(in Proposition 1) that complete bridges can be composed.

Secondly, in Section 5 we observe that, even if one is able to compose two
secure bridges, the resulting bridge might not be secure (see Example 4).
Theorem 5.2 gives a sufficient condition on a pair of composable secure
bridges for their composition to be secure.

1.6 We apply our theoretical results to certain types of bridges that arise in
the context of homomorphic encryption schemes. In such schemes, some boolean
circuits can be evaluated on encrypted data and such an evaluation is called
homomorphic. We show that the homomorphic evaluation of a circuit gives rise
to a bridge between a _fiber power_ of the encryption scheme to the scheme
itself (see Section 7).

In a recent talk, Micciancio [19] points out that the definition of fully
homomorphic encryption does not guarantee that one can sequentially
homomorphically evaluate two circuits while preserving correct decryption. In
this paper, we formulate the previous aspect in the language of bridges. The
mere definition of a correct bridge does not guarantee that one can further
apply another bridge to the resulting ciphertext of the first bridge without
the risk of loosing correctness. Motivated by the definitional issue raised
above, Micciancio introduces the notion of fully composable homomorphic
encryption (FcHE) and inspired by the bootstrapping procedure (used to
construct FHE schemes) he sketches [19] the proof of a theorem asserting
sufficient conditions for the existence of a FcHE scheme. The security of the
FcHE scheme constructed by Micciancio follows from the circular security of a
FHE. To address an analogous issue, building up on previous work in [2], we
introduce the definition of a complete bridge. Finally, we show that the
aforementioned result of Micciancio [19] can be phrased in the language of
bridges, where its proof becomes more conceptual. In our proof, we constructed
a special type of bridge inspired from the Gentry type bridges defined in [2].
The difference between the former and later bridges is subtle and resides in
their KeyGen algorithms. The KeyGen algorithm for the bridge needed in this
proof satisfies an additional condition which accounts for the fact that the
security of this bridge is equivalent to the circular security of a
homomorphic encryption scheme.

1.7 The paper is organized as follows. In the next section we give some
preliminaries used throughout the paper. In Section 3 we recall the main
concepts needed in this article. We define complete and composable bridges in
Section 4 and prove that complete bridges are composable. In Section 5 we
investigate the security of composition of bridges and prove our main result.
The next section is dedicated to Gentry-type bridges and compositions of
general bridges with such bridges, proving the correctness and security of
these protocols. In the last section, we explicitly construct bridges from
circuits and show how one can translate the original discussion of Micciancio
about composition of homomorphic evaluation of circuits into our language of
bridge composition.

1.8 In his talk, Micciancio explained that one of the motivations of his
analysis was the connection between circular security and fully composable
homomorphic encryption. The biggest hope is to place circular security into a
larger setting, which will then allow to possibly prove that circular security
reduces to standard assumptions. We are informally asking if the language of
bridges and bridge composition adds valuable insights into this problem. In
addition, the theory of composable bridges can be related to the way the third
generation of FHE schemes realise the bootstrapping procedure. Indeed, the
accumulator proposed in [14] can be viewed as a composition of bridges, one of
which is a Gentry type bridge. It would be interesting to further investigate
the connections between this theory and the theory of fully homomorphic
encryption schemes constructed on the LWE assumption.

### Acknowledgements

The authors are indebted to George Gugulea, Cristian Lupaşcu and Mihai Togan
for helpful discussions and comments during the preparation of this work.

##  2 Preliminaries

In all our definitions, we denote the security parameter by $\lambda$. We say
that a function $\mathrm{negl}:\mathbb{N}\rightarrow[0,+\infty)$ is a
negligible function if for any positive integer $c$ there exists a positive
integer $N_{c}$, such that $\mathrm{negl}(n)<\dfrac{1}{n^{c}}$ for all $n\geq
N_{c}$.

Throughout this article, we will use the language of finite distributions (see
section 2.1 of [2]). In particular, an encryption scheme comes with the
following finite distributions: secret keys, public keys and the encryptions
of every fixed message. To be precise, all of the distributions mentioned here
are defined for each fixed value of the security parameter $\lambda$. For
example, the secret key distributions
$\\{\mathcal{SK}_{\lambda}:\lambda\in\mathbb{N}\\}$ form an ensemble of finite
distributions. Such ensembles form a category, in which one can define finite
products and study relations between its objects. To fix ideas, we choose to
recall the following illustrative example of a relation between two finite
distributions. Given $\lambda$, the key generation algorithm of an encryption
scheme gives rise to the distribution of secret keys $\mathcal{SK}_{\lambda}$
and, for each sample $sk\leftarrow\mathcal{SK}_{\lambda}$, the second part of
the algorithm outputs a sample $pk$ from a distribution of public keys. We say
that the resulted distribution of public keys $\mathcal{PK}_{\lambda}$ is an
$\mathcal{SK}_{\lambda}$-distribution. More details about the language of
finite distributions and the relations between the distributions associated to
an encryption scheme are explained in [2].

In an effort to keep the notation simple, we sometimes omit the subscript
$\lambda$ when referring to a certain ensemble of finite distributions. We
will use upper case calligraphic letters for the name of the distributions and
lower case italic letters for samples from various distributions.

Every PPT algorithm gives rise to a probability distribution. Throughout this
work, every written identity that involves the output of a PPT algorithm is
assumed to hold with overwhelming probability over the randomness introduced
by the PPT algorithm. This means that the probability of failure of that
identity is negligible. For brevity, we shall avoid the repeated use of the
phrase “with overwhelming probability” to indicate this situations.

##  3 Definitions

We first recall two technical definitions about ensembles of finite
distributions discussed in more detail in [2].

###### Definition 1

An ensemble $\\{\mathcal{X}_{\lambda}\\}_{\lambda}$ of finite distributions is
polynomial-time constructible if there exists a PPT algorithm $A$ such that
$A(1^{\lambda})=\mathcal{X}_{\lambda}$, for every $\lambda$. An
$\\{\mathcal{X}_{\lambda}\\}_{\lambda}$-ensemble of finite distributions
$\\{(\mathcal{Y}_{\lambda},\varphi_{\lambda}:\mathcal{Y}_{\lambda}\rightarrow\mathcal{X}_{\lambda})\\}_{\lambda}$
is polynomial-time constructible on fibers if there exist a PPT algorithm $A$,
such that for any $x_{\lambda}\leftarrow\mathcal{X}_{\lambda}$ we have
$A(1^{\lambda},x_{\lambda})=\mathcal{Y}_{\lambda}|_{\mathcal{X}_{\lambda}=x_{\lambda}}$,
where $\mathcal{Y}_{\lambda}|_{\mathcal{X}_{\lambda}=x_{\lambda}}$ is the
fiber distribution over $x_{\lambda}$.

We will also use the following notion of computational (or polynomial)
indistinguishability from [17] and [16].

###### Definition 2

Two ensembles of finite distributions $\\{\mathcal{X}_{\lambda}\\}_{\lambda}$
and $\\{\mathcal{Y}_{\lambda}\\}_{\lambda}$ are called computationally
indistinguishable if for any PPT distinguisher $D$, the quantity

$|\mathrm{Pr}\left\\{D(\mathcal{X}_{\lambda})=1\right\\}-\mathrm{Pr}\left\\{D(\mathcal{Y}_{\lambda})=1\right\\}|$

is negligible as a function of $\lambda$.

Next, we review some notions related to public key encryption schemes,
homomorphic encryption and bridges between encryption schemes.

######  Definition 3 ($PKE$)

A public key encryption scheme consists of three PPT algorithms

$\mathcal{E}=({\rm KeyGen},{\rm Enc},{\rm Dec})$

as follows:

  * $\bullet$

KeyGen: The algorithm $(sk,pk)\leftarrow{\rm KeyGen}(1^{\lambda})$ takes a
unary representation of the security parameter and outputs a secret key $sk$
and a public key $pk$.

  * $\bullet$

Enc: The algorithm $c\leftarrow{\rm Enc}(pk,m)$ takes the public key $pk$ and
a single message $m\in\mathcal{M}$ and outputs a ciphertext $c\in\mathcal{C}$.

  * $\bullet$

Dec: The algorithm $m^{*}\leftarrow{\rm Dec}(sk,c)$ takes the secret key $sk$
and a ciphertext $c$ and outputs a message $m^{*}$.

We shall always assume that a public key encryption scheme is correct, i.e. it
satisfies the following property:

Correct Decryption: The scheme $\mathcal{E}$ is correct if for all
$m\in\mathcal{M}$ and all pairs of keys $(sk,pk)$ outputted by
$\text{KeyGen}(1^{\lambda})$,

${\rm Dec}(sk,\mathrm{Enc}(pk,m))=m,$

with overwhelming probability over the finite distribution ${\rm Enc}(pk,m)$.

A (public key) homomorphic encryption scheme is a $PKE$ scheme such that its
${\rm KeyGen}$ algorithm outputs an additional evaluation key $evk$ (besides
$sk$ and $pk$), which is used by an additional PPT evaluation algorithm ${\rm
Eval}$. To be precise, there is a fourth PPT algorithm:

  * $\bullet$

$\mathrm{Eval}$: The algorithm takes the evaluation key $evk$, a
representation of a boolean circuit
$C:\mathcal{M}^{\ell}\rightarrow\mathcal{M}$ from a set of evaluable circuits
$\mathcal{L}$, and a set of $\ell$ ciphertexts $c_{1},...,c_{\ell}$, and
outputs a ciphertext $c^{*}\leftarrow{\rm Eval}(evk,C,c_{1},\ldots,c_{\ell})$.

Relative to the evaluation algorithm, a public-key homomorphic encryption
scheme is assumed to satisfy the following correctness property:

Correct Evaluation: The scheme $\mathcal{E}$ correctly evaluates all boolean
circuits in $\mathcal{L}$ if for all keys $(sk,pk,evk)$ outputted by
$\text{KeyGen}(1^{\lambda})$, for all circuits
$C:\mathcal{M}^{\ell}\rightarrow\mathcal{M}$, $C\in\mathcal{L}$ , and for all
$m_{i}\in\mathcal{M}$, $1\leq i\leq\ell$, it holds that

${\rm Dec}(sk,{\rm
Eval}(evk,C,\operatorname{\mathrm{Enc}}(pk,m_{1}),...,\operatorname{\mathrm{Enc}}(pk,m_{\ell}))=C(m_{1},...,m_{\ell}),$

with overwhelming probability over the randomness of ${\rm Enc}$ and ${\rm
Eval}$.

Remark. Nowadays, although omitted from most definitions, it is understood
that all homomorphic encryptions schemes should satisfy a certain compactness
property, namely that there exists a polynomial $s=s(\lambda)$ such that the
output length of ${\rm Eval}$ is at most $s$ bits long, regardless of
$C\in\mathcal{L}$ or the number of inputs.

We say that a public-key homomorphic encryption scheme is a fully homomorphic
encryption (FHE) scheme (over $\mathcal{M}$) if the scheme correctly evaluates
all possible boolean circuits $C:\mathcal{M}^{\ell}\rightarrow\mathcal{M}$,
for $\ell\in\mathbb{N}$.

The authors of [2] proposed a general definition for an algorithm that
publicly transforms encrypted data from one scheme to another. We recall here
their definition of a bridge between two encryption schemes.

###### Definition 4

Let $\mathcal{E}_{i}=({\rm KeyGen}_{i},{\rm Enc}_{i},{\rm Dec}_{i})$,
$i\in\\{1,2\\}$ be two PKE schemes. A bridge $\mathbf{B}_{\iota,f}$ from
$\mathcal{E}_{1}$ to $\mathcal{E}_{2}$ consists of:

  1. 1.

A function $\iota:\mathcal{M}_{1}\to\mathcal{M}_{2}$ that is computable by a
deterministic polynomial time algorithm, where $\mathcal{M}_{i}$ is the
plaintext space of the scheme $\mathcal{E}_{i}$.

  2. 2.

A PPT bridge key generation algorithm, which has the following three stages.
First, the algorithm gets the security parameter $\lambda$ and uses it to run
$\mathrm{KeyGen}_{1}$ in order to obtain a pair of keys $sk_{1},pk_{1}$. In
the second stage the algorithm uses $sk_{1}$ to find a secret key $sk_{2}$ of
level $\lambda$ for $\mathcal{E}_{2}$, and then uses the second part of
$\mathrm{KeyGen}_{2}$ to produce $pk_{2}$. In the final stage, the algorithm
takes as input the quadruple $(sk_{1},pk_{1},sk_{2},pk_{2})$ and outputs a
bridge key $bk$.

  3. 3.

A PPT algorithm $f$ which takes as input the bridge key $bk$ and a ciphertext
$c_{1}\in\mathscr{C}_{1}$ and outputs a ciphertext $c_{2}\in\mathscr{C}_{2}$,
such that

${\rm Dec}_{2}(sk_{2},f(bk,{\rm Enc}_{1}(pk_{1},m)))=\iota(m).$

Remark. To simplify the discussion, when
$\iota:\mathcal{M}_{1}\to\mathcal{M}_{2}$ is clear from the context, we will
abuse notation and write $f:\mathcal{E}_{1}\to\mathcal{E}_{2}$ instead of the
bridge $\mathbf{B}_{\iota,f}$.

We now give the definition/construction of the $k$-th fiber power encryption
scheme $\mathcal{E}^{(k)},$ associated to any encryption scheme $\mathcal{E}$
and any positive integer $k$.

###### Definition 5

Let $\mathcal{E}=({\rm KeyGen},{\rm Enc},{\rm Dec})$ be a PKE scheme, such
that $\mathcal{M}$ and $\mathcal{C}$ are its plaintext and ciphertext spaces.
For any positive integer $k$, the $k$-th fiber power of $\mathcal{E}$ is the
encryption scheme
$\mathcal{E}^{(k)}=(\mathrm{KeyGen},\mathrm{Enc}^{(k)},\mathrm{Dec}^{(k)})$,
whose plaintext and ciphertext are the $k$-th Cartesian products
$\mathcal{M}^{k}$ and $\mathcal{C}^{k}$ respectively. Moreover, the key
generation algorithm is identical to the one of $\mathcal{E}$, outputting a
pair $(sk,pk)$. The encryption and decryption algorithms of
$\mathcal{E}^{(k)}$ are

$\mathrm{Enc}^{(k)}(pk,(m_{1},\ldots,m_{k}))=\left(\mathrm{Enc}(pk,m_{1}),\ldots,\mathrm{Enc}(pk,m_{k})\right)$

and

$\mathrm{Dec}^{(k)}(sk,(c_{1},\ldots,c_{k}))=\left(\mathrm{Dec}(sk,c_{1}),\ldots,\mathrm{Dec}(sk,c_{k})\right),$

for any $(m_{1},\ldots,m_{k})\in\mathcal{M}^{k}$ and
$(c_{1},\ldots,c_{k})\in\mathcal{C}^{k}$.

###### Remark 1

In the category $\mathscr{F}in\mathscr{D}ist$ of finite distributions, the
encryptions of the defined scheme $\mathcal{E}^{(k)}$ are products of $k$
copies of the distributions of encryptions from $\mathcal{E}$ regarded as
$\mathcal{PK}$\- distributions, as defined in Section 2.1 of [2].

We end this section with a simple example of a bridge from $\mathcal{E}^{(2)}$
to $\mathcal{E}$, whose importance will become apparent in the next section.
Moreover, construction of certain bridges from $\mathcal{E}^{(k)}$ to
$\mathcal{E}$, for general $k$, will play a crucial role in our work presented
here.

###### Example 1

We recall briefly the definition of a basic homomorphic LWE encryption scheme
with plaintext space $\mathcal{M}={\mathbb{Z}}_{2}$. The scheme $\mathcal{E}$
is parameterized by a dimension $n$, a ciphertext modulus $q=n^{O(1)}$ and a
randomized rounding function $\chi:\mathbb{R}\to\mathbb{Z}$. In order to
achieve an additive homomorphic property, we impose that the rounding function
has error distribution satisfying $|\chi(x)-x|<q/8$. The secret key of the
encryption scheme is a vector $sk\in\mathbb{Z}_{q}^{n}$, which is chosen
uniformly at random. For simplicity, we will assume that this scheme is
symmetric, namely that the public key $pk=sk$. The encryption of a message
$m\in{\mathbb{Z}}_{2}$ under the key $sk\in{\mathbb{Z}}_{q}^{n}$ is given by

$\mathrm{Enc}(pk,m)=\left(a,\chi(a\cdot
sk+mq/2)\,\,\mathrm{mod}\,\,q\right)\in{\mathbb{Z}}_{q}^{n+1},$

where $a\leftarrow\mathbb{Z}_{q}^{n}$ is chosen uniformly at random. A
ciphertext $(a,b)$ is decrypted as follows

$\mathrm{Dec}(sk,(a,b))=\lfloor 2(b-a\cdot sk)/q\rceil\,\,\mathrm{mod}\,\,2.$

Note that correction of the decryption follows from the assumption on the
rounding error of $\chi$. Using the homomorphic addition that can be performed
on this scheme, we can easily construct a bridge from $\mathcal{E}^{(2)}$ to
$\mathcal{E}$, as we now explain.

The function $\iota:\mathcal{M}\times\mathcal{M}\to\mathcal{M}$ is defined as
$\iota(m_{1},m_{2})=m_{1}+m_{2}$, where the addition is performed in
${\mathbb{Z}}_{2}$.

The key generation algorithm of the bridge uses the key generation algorithm
of $\mathcal{E}^{(2)}$ to output a pair $(sk,pk)$ and then, in the second
stage, associates the same pair $(sk,pk)$ to $\mathcal{E}$. Finally, the
algorithm outputs an empty bridge key $bk$.

The ppt algorithm $f$ takes a pair of ciphertexts
$(a_{1},b_{1}),(a_{2},b_{2})\in{\mathbb{Z}}_{q}^{n+1}$ and computes

$f((a_{1},b_{1}),(a_{2},b_{2})):=(a_{1}+a_{2},b_{1}+b_{2}).$

The correctness property of the bridge follows immediately from the fact that
the rounding error of $\chi$ is less than $q/8$, in other words the corectness
is implied by the additive homomorphic property of the scheme $\mathcal{E}$.

###### Remark 2

Note that in the setting above, given a pair of elements in the ciphertext
space $(a_{1},b_{1}),(a_{2},b_{2})\in{\mathbb{Z}}_{q}^{n+1}$, it is not true
in general that

$\mathrm{Dec}(sk,f((a_{1},b_{1}),(a_{2},b_{2})))=\mathrm{Dec}(sk,(a_{1},b_{1}))+\mathrm{Dec}(sk,(a_{2},b_{2})).$

To see this, if $\mathrm{Dec}(sk,(a_{i},b_{i}))=m_{i}$, then the error
$b_{i}-a_{i}\cdot s_{k}-m_{i}q/2\,\,\textrm{mod}\,\,q$ might not lie in the
interval $(-q/8,q/8)$, for some $i\in\\{1,2\\}$. In this case,
$b_{1}+b_{2}-(a_{1}+a_{2})\cdot sk-(m_{1}+m_{2})q/2\,\,\textrm{mod}\,\,q$
might not belong to $(-q/4,q/4)$, so that

$\mathrm{Dec}(sk,f((a_{1},b_{1}),(a_{2},b_{2})))=\mathrm{Dec}(sk,(a_{1}+a_{2},b_{1}+b_{2}))$

is not guaranteed to be equal to $m_{1}+m_{2}$.

##  4 Complete and composable bridges

In general, as we noticed in the last remark of the previous section, the
square of the following diagram is not commutative:

${{\rm
Enc}_{1}(\mathcal{M}_{1})}$${\mathcal{C}_{1}}$${\mathcal{C}_{2}}$${\mathcal{M}_{1}}$${\mathcal{M}_{2}}$$\scriptstyle{f}$$\scriptstyle{\mathrm{Dec}_{1}}$$\scriptstyle{\mathrm{Dec}_{2}}$$\scriptstyle{\iota}$

where $f$ is a bridge between encryption schemes. Indeed, the definition of a
bridge is imposing commutativity only for the restriction of $f$ to
$\mathrm{Enc}_{1}(\mathcal{M}_{1})\subseteq\mathcal{C}_{1}$, i.e. to the
subset of the ciphertext space which consists of _fresh encryptions_. This
observation leads to the following definition.

###### Definition 6

Let $\mathcal{E}_{i}=(\mathcal{M}_{i},\mathcal{C}_{i},{\rm KeyGen}_{i},{\rm
Enc}_{i},{\rm Dec}_{i})$, $i\in\\{1,2\\}$ be two encryption schemes. A bridge
$\mathbf{B}_{\iota,f}$ from $\mathcal{E}_{1}$ to $\mathcal{E}_{2}$ is called
complete if the PPT algorithm $f$, which takes as input the bridge key $bk$
and _any_ ciphertext $c_{1}\in\mathcal{C}_{1}$ satisfies the equality

$\mathrm{Dec}_{2}(sk_{2},f(bk,c_{1}))=\iota(\mathrm{Dec}_{1}(sk_{1},c_{1})),$

for any the triple $(sk_{1},sk_{2},bk)$ outputted by the key generation
algorithm of the bridge.

Let us notice the following easy fact:

###### Remark 3

Suppose that $\mathcal{E}=(\mathrm{KeyGen},\mathrm{Enc},\mathrm{Dec})$ is an
encryption scheme. If for every pair
$(sk,pk)\leftarrow\mathrm{KeyGen}(1^{\lambda})$ and every $c\in\mathcal{C}$
there exists a $m\in\mathcal{M}$ such that $c\in\mathrm{Enc}(pk,m)$, then any
bridge from $\mathcal{E}$ to any other scheme, is complete.

As a consequence, the bridge from the Goldwaser-Micali (GM) encryption scheme
to the Sander-Young-Yung (SYY) encryption scheme described in [2] is complete.
Indeed, the GM encryption scheme does enjoy the property described in the
above remark: for any two distinct primes $p,q$, every element from the
ciphertext space $J_{1}(pq)$ can be obtained as an encryption
$\mathrm{Enc}_{GM}(pq,m)$ of some plaintext $m\in\mathbb{Z}_{2}$.

An example of a different flavor arises from the modulus switching procedure,
which is frequently used in homomorphic encryption schemes for different
purposes (such as reducing the noise of a ciphertext).

###### Example 2

Let $q,Q$ be two integers such that $q$ divides $Q$. For simplicity, assume
that $q,Q\equiv 2\pmod{4}$. We let ${\rm LWE}^{2/q}$ and ${\rm LWE}^{2/Q}$ be
the LWE encryption schemes with plaintext spaces $\mathcal{M}=\mathbb{Z}_{2}$
and ciphertext modulus $q$ and $Q$, respectively (see [14]).

Recall that a ciphertext encrypting the message $m$ in ${\rm LWE}^{2/q}$ is of
the form $(a,b)$, where $a\leftarrow\mathbb{Z}_{q}^{n}$ is sampled uniformly
and $b=\langle a,s\rangle+m\cdot\frac{q}{2}+e$, where $e$ is drawn from the
noise distribution.

The decryption can be regarded as a map from
$\mathbb{Z}_{q}^{n}\times\mathbb{Z}_{q}$ to $\mathbb{Z}_{2}$, given by

$\mathrm{Dec}_{q}\left(a,b\right)=\left\\{\begin{array}[]{l}0,\text{ if
}b-\langle a,s\rangle\in(-q/4,q/4)\\\ 1,\text{ otherwise.}\end{array}\right.$

We define a bridge $f$ from ${\rm LWE}^{2/q}$ to ${\rm LWE}^{2/Q}$, as
follows. In the second stage, the bridge key generation algorithm takes as
input $s\in\mathbb{Z}_{q}^{n}$, the secret key of ${\rm LWE}^{2/q}$, and
generates the same key for ${\rm LWE}^{2/Q}$, viewed in $\mathbb{Z}_{Q}^{n}$.
Finally, this algorithm outputs an empty bridge key.

The algorithm $f$ will take as input a ciphertext
$(a,b)\in\mathbb{Z}_{q}^{n}\times\mathbb{Z}_{q}$ and computes
$\left(\frac{Q}{q}\cdot a,\frac{Q}{q}\cdot
b\right)\in\mathbb{Z}_{Q}^{n}\times\mathbb{Z}_{Q}$. It is not hard to see that
this bridge is complete.

This resembles the modulus-switching procedures used initially to simplify the
decryption circuit in [5] and later to reduce the noise accumulated after
homomorphic multiplication in [4]. We note that in modulus-switching
procedures the ciphertexts are converted from a larger modulus $Q$, to a
smaller one $q$, whereas in the example described above the procedures go from
a smaller modulus to a larger one.

However, let us remark that, one can always modify the decryption algorithm in
${\rm LWE}^{2/q}$ to obtain a complete bridge to ${\rm LWE}^{2/Q}$ even when
the modulus $Q$ is smaller than $q$.

It will become apparent in the following that the completeness property of a
bridge plays an important role in being able to move an encryption through a
chain of bridges without performing any decryption. This triggers one of the
main notions presented in this paper, namely the composability of bridges
which shall be discussed in details in what follows.

Given two bridges $f:\mathcal{E}_{1}\to\mathcal{E}_{2}$,
$g:\mathcal{E}_{2}\to\mathcal{E}_{3}$, between encryption schemes
$\mathcal{E}_{1}$ and $\mathcal{E}_{2}$ respectively $\mathcal{E}_{2}$ and
$\mathcal{E}_{3}$, it is desirable to be able to use them, in order to convert
a ciphertext from $\mathcal{E}_{1}$ to $\mathcal{E}_{3}$ while preserving the
underlying plaintext. If possible, such a procedure should resemble the
composition of two functions. In particular, it is obvious that to achieve
such a conversion, the Key Generation algorithms of $f$ and $g$ should not run
independently, as we now explain in the following construction/definition:

######  Definition 7 (Composition of bridges)

Let $f:\mathcal{E}_{1}\to\mathcal{E}_{2}$ and
$g:\mathcal{E}_{2}\to\mathcal{E}_{3}$ be bridges between the encryption
schemes $\mathcal{E}_{1},\mathcal{E}_{2}$, and
$\mathcal{E}_{2},\mathcal{E}_{3}$, respectively. The composition of $g\circ f$
consists of the following procedures:

  1. 1.

The function $\iota_{g\circ
f}:=\iota_{g}\circ\iota_{f}:\mathcal{P}_{1}\to\mathcal{P}_{3}$, which is
computable by a deterministic polynomial time algorithm.

  2. 2.

A PPT bridge key generation algorithm, which runs as follows. First, it takes
the security parameter $\lambda$ and runs the Key Generation algorithm of $f$
to obtain $(sk_{1},pk_{1},sk_{2},pk_{2},bk_{f})$. After that, it only uses the
second and third stages of the Key Generation of $g$ to obtain
$(sk_{3},pk_{3},bk_{g})$. Finally, it outputs the bridge key $bk_{g\circ
f}=(bk_{f},pk_{2},bk_{g})$.

  3. 3.

A PPT algorithm $g\circ f$ which takes as input a ciphertext
$c_{1}\in\mathcal{C}_{1}$ and outputs $g(bk_{g},f(bk_{f},c_{1}))$.

A first observation is that, unfortunately, the composition of two bridges is
not necessarily a bridge. Indeed, due to the fact that for
$m\in\mathcal{P}_{1}$, the ciphertext $f(bk_{1},\mathrm{Enc}_{1}(pk_{1},m))$
is not necessarily a fresh encryption of $\iota_{f}(m)$, the correctness
properties of $f$ and $g$ do not imply that

$\mathrm{Dec}_{3}(sk_{3},(g\circ f)(bk_{g\circ
f},\mathrm{Enc}_{1}(pk_{1},m))=\iota_{g\circ f}(m).$

This feature will also be present in the case of bridges constructed from
circuits in section 7 and it was pointed out before in a presentation by
Micciancio [19].

On the other hand, if the second bridge of a pair of bridges is complete, then
the composition is also a bridge as the following proposition states.

###### Proposition 1

Let $f:\mathcal{E}_{1}\to\mathcal{E}_{2}$ and
$g:\mathcal{E}_{2}\to\mathcal{E}_{3}$ be bridges between the encryption
schemes $\mathcal{E}_{1},\mathcal{E}_{2}$ and $\mathcal{E}_{3}$, such that $g$
is complete. Then, the composition $g\circ
f:\mathcal{E}_{1}\to\mathcal{E}_{3}$ is a bridge.

###### Proof

Since $g$ is complete, the correctness property for $g$ holds for any
ciphertext. In particular, it holds for ciphertexts of the form
$f(bk_{1},\mathrm{Enc}_{1}(pk_{1},m))$, so that we have:

$\displaystyle\mathrm{Dec}_{3}(sk_{3},(g\circ f)(bk_{g\circ
f},\mathrm{Enc}_{1}(pk_{1},m)))$ $\displaystyle=$
$\displaystyle\iota_{g}(\mathrm{Dec}_{2}(sk_{2},f(bk_{f},\mathrm{Enc}_{1}(pk_{1},m))))$
$\displaystyle=$ $\displaystyle\iota_{g}(\iota_{f}(m))=\iota_{g\circ f}(m),$

where the first equality follows from the completeness of $g$ and the second
equality from the correctness property of $f$.

To end the discussion of this section we introduce the following definition:

###### Definition 8

A pair of bridges $(f,g)$ is called _composable_ if $g\circ f$ is defined and
is also a bridge.

We have the following consequence of the last proposition:

###### Corollary 1

If $f:\mathcal{E}_{1}\to\mathcal{E}_{2}$ and
$g:\mathcal{E}_{2}\to\mathcal{E}_{3}$ are two complete bridges then they are
composable and their composition is complete.

###### Proof

The proof follows immediately using the same argument as in the proof of the
last Proposition.

###### Remark 4

Since complete bridges behave well with respect to composition, they form the
class of morphisms of a category.

##  5 On the security of composition of bridges

The aim of this section is to investigate the security of the composition of
two bridges. We shall introduce first the security notions related to the
security of a bridge without giving all the details (for a full account see
[2]). Then we prove our main theorems stating that the composition of secure
bridges is secure under a certain technical condition. In the next section we
shall prove that this condition is satisfied by an important class of bridges.

Given a public-key encryption scheme
$\mathcal{E}=(\operatorname{\mathrm{KeyGen}},\operatorname{\mathrm{Enc}},\operatorname{\mathrm{Dec}})$
and an adversary $\mathcal{A}$ consider the following the IND-CPA experiment
$\mathrm{Expr}^{\mathrm{IND-CPA}}[\mathcal{A}]$:

1\. Run $\operatorname{\mathrm{KeyGen}}(1^{\lambda})$ to obtain the pair of
keys $(sk,pk)$.

2\. The key $pk$ is given to the adversary $\mathcal{A}$. It outputs a pair of
messages $m_{0}$, $m_{1}$ of its choice.

3\. The challenger chooses a uniform bit $b\in\\{0,1\\}$, and then a
ciphertext $c\leftarrow\operatorname{\mathrm{Enc}}(pk,m_{b})$ is computed and
given to $\mathcal{A}$.

4\. The adversary $\mathcal{A}$ outputs a bit $b^{\prime}$.

5\. The output of the experiment is defined to be 1 if $b^{\prime}=b$, and 0
otherwise.

######  Definition 9 (IND-CPA Security)

The advantage of adversary $\mathcal{A}$ against the IND-CPA security of the
scheme is $\mathcal{E}$ is defined by

$\mathrm{Adv}^{\mathrm{IND-
CPA}}[\mathcal{A}](\lambda):=|\mathrm{Pr}\\{\mathrm{Expr}^{\mathrm{IND-
CPA}}[\mathcal{A}]=1\\}-\mathrm{Pr}\\{\mathrm{Expr}^{\mathrm{IND-
CPA}}[\mathcal{A}]=0\\}|,$

where the probability is over the randomness of $\mathcal{A}$ and of the
experiment. A public key encryption scheme $\mathcal{E}$ has indistinguishable
encryptions under chosen-plaintext attack (or is IND-CPA-secure) if for any
probabilistic polynomial-time adversaries $\mathcal{A}$ there exists a
negligible function $\mathrm{negl}$ such that

$\mathrm{Adv}^{\mathrm{IND-
CPA}}[\mathcal{A}](\lambda)=\mathrm{negl}(\lambda).$

###### Remark 5

As it is well known (see for instance Proposition 5.9 in [3]), an encryption
scheme is IND-CPA-secure if and only if for any PPT-adversary $\mathcal{A}$
there exists a negligible function $\mathrm{negl}$ such that

$\mathrm{Pr}[\mathrm{Expr}^{\mathrm{IND-
CPA}}[\mathcal{A}]=1](\lambda)\leq\frac{1}{2}+\mathrm{negl}(\lambda).$

In [2], the authors associated to any bridge
$f:\mathcal{E}_{1}\to\mathcal{E}_{2}$ an encryption scheme $\mathcal{G}_{f}$
(called the graph of the bridge) and defined the security of the bridge as
being the security of the associated scheme $\mathcal{G}_{f}.$ On the other
hand, they proved that the security of $\mathcal{G}_{f}$ is equivalent to the
security of $\mathcal{E}_{1}[pk_{2},bk_{f}]$ which is the encryption scheme
$\mathcal{E}_{1}$ endowed with additional public information given by the
public key of $\mathcal{E}_{2}$ and the bridge key of $f$ (for further
details, see [2, Theorem 1]). Hereafter, we propose this equivalent notion as
the security of a bridge because in practice it is much easier to work with
it.

Since we will make use of the explicit construction of $\mathcal{G}_{f}$ in
our arguments, we shall briefly recall its structure (for more details see the
Section 3 of [2]):

  1. $\bullet$

The plaintext space of $\mathcal{G}_{f}$ is the same as the plaintext space of
$\mathcal{E}_{1}$, that is $\mathcal{M}_{1}$. The ciphertext space is
$\mathcal{C}_{1}\times\mathcal{C}_{2},$ where $\mathcal{C}_{i}$ is the
ciphertext space of $\mathcal{E}_{i}$, $\forall i\in\\{1,2\\}.$

  2. $\bullet$

The secret key of $\mathcal{G}_{f}$ is the pair:
$sk_{\mathcal{G}_{f}}:=(sk_{1},sk_{2}).$

  3. $\bullet$

The public key is the triple: $pk_{\mathcal{G}_{f}}:=(pk_{1},pk_{2},bk_{f}).$

  4. $\bullet$

The encryption algorithm is given by

$\operatorname{\mathrm{Enc}}_{\mathcal{G}_{f}}(pk_{\mathcal{G}_{f}},m):=(\operatorname{\mathrm{Enc}}_{1}(pk_{1},m),f(bk_{f},\operatorname{\mathrm{Enc}}_{1}(pk_{1},m)),$

for all $m\in\mathcal{M}_{1}.$

  5. $\bullet$

The decryption algorithm is
$\operatorname{\mathrm{Dec}}_{\mathcal{G}_{f}}(sk_{\mathcal{G}_{f}},(a,b)):=\operatorname{\mathrm{Dec}}_{1}(sk_{1},a).$

In what follows we are interested in finding conditions that ensure the
security of a bridge obtained as a composition of two composable bridges. The
following easy result, can be seen as a necessary condition for the security
of such a bridge.

###### Proposition 2

Suppose $f:\mathcal{E}_{1}\to\mathcal{E}_{2}$ and
$g:\mathcal{E}_{2}\to\mathcal{E}_{3}$ are composable bridges, such that
$g\circ f$ is a secure bridge. Then $f$ is a secure bridge.

###### Proof

Since the bridge key of $g\circ f$ is given by $bk_{g\circ
f}=(bk_{f},pk_{2},bk_{g})$, the security of $f$ follows from the above
considerations.

On the other hand, if the composition $g\circ f$ is a secure bridge, it does
not follow that $g$ is secure. Let us illustrate this with the following
example.

###### Example 3

Assume that $f:\mathcal{E}_{1}\to\mathcal{E}_{2}$ and
$g:\mathcal{E}_{2}\to\mathcal{E}_{3}$ are composable secure bridges such that
$g\circ f$ is secure. By [2, Proposition 1], the encryption schemes
$\mathcal{E}_{1}$ and $\mathcal{E}_{2}$ are IND-CPA secure. For simplicity,
assume that the common plaintext is $\mathcal{M}=\\{0,1\\}.$ We now construct
the encryption scheme $\mathcal{E}_{2}^{\prime}$, as follows: this scheme is
almost identical to $\mathcal{E}_{2}$, except that the encryption reveals the
message. More precisely,
$\mathrm{Enc}_{2}^{\prime}(pk_{2},m)=(\mathrm{Enc}_{2}(pk_{2},m),m)$ is a
concatenation of the encryption of $m$ in the scheme $\mathcal{E}_{2}$ with
the plaintext $m$ itself. This new encryption scheme
$\mathcal{E}_{2}^{\prime}$ is obviously not secure.

On the other hand, we modify $f$ and $g$ to new bridges $f^{\prime}$ and
$g^{\prime}$ in the following way. For any ciphertext $c\in\mathcal{C}_{1}$,
we let $f^{\prime}(c_{1})=(f(c_{1}),b)$, where $b\leftarrow\\{0,1\\}$ is
chosen uniformly at random. The bridge $g^{\prime}$ will perform as follows.
For any ciphertext $c_{2}^{\prime}=(c_{2},b)\in\mathcal{C}_{2}^{\prime}$, we
let $g^{\prime}(c_{2}^{\prime})=g(c_{2})\in\mathcal{C}_{3}$. It can be easily
verified that $g^{\prime}\circ f^{\prime}$ is a secure bridge from
$\mathcal{E}_{1}\to\mathcal{E}_{3}$. However, the bridge $g^{\prime}$ is not
secure because the modified encryption scheme $\mathcal{E}_{2}^{\prime}$ is
not secure.

Next, we give an example of two (complete) secure bridges $f$ and $g$, which
are composable, for which $g\circ f$ is an insecure bridge.

###### Example 4

Consider $\mathcal{E}$ an encryption scheme (not homomorphic or with any other
special property). We shall assume that knowing half of the secret key does
not harm the security. Denote by $\ell(\lambda)$ the bit length of its secret
key. We define $\mathcal{E}_{1}$ to be $\mathcal{E}$, while $\mathcal{E}_{2}$
is $\mathcal{E}$ with a modified cyphertext space, consisting of
concatenations of cyphertexts of $\mathcal{E}$ with strings of length
$\ell(\lambda)/2$. The encryption algorithm in $\mathcal{E}_{2}$ outputs a
concatenation of an encryption of $\mathcal{E}$ with a random sequence of
length $\ell(\lambda)/2$. The decryption algorithm is just the decryption
algorithm of $\mathcal{E}$ applied to the first part of the ciphertext, i.e.
the bit string corresponding to a ciphertext in the scheme $\mathcal{E}$.
Also, consider $\mathcal{E}_{3}$ to be the scheme obtained by applying on
$\mathcal{E}_{2}$ the same procedure used in the construction of
$\mathcal{E}_{2}$ from $\mathcal{E}$.

The bridge key of $f:\mathcal{E}_{1}\to\mathcal{E}_{2}$ consists of the first
half of the bit representation of the secret key of $\mathcal{E}$ and $f$ is
defined by the concatenation of the identity map with the bridge key. The
bridge $g:\mathcal{E}_{2}\to\mathcal{E}_{3}$ has a similar construction, only
that the bridge key of $g$ consists of the second half of the secret key of
$\mathcal{E}$. Now, by our assumptions, the schemes $\mathcal{E}[bk_{f}]$ and
$\mathcal{E}[bk_{g}]$ are secure. Hence, the bridges $f$ and $g$ are secure.
Moreover, $f$ and $g$ are clearly complete, thus composable.

However, their composition reveals the entire secret key because the bridge
key of the composition contains both halves of the secret key of
$\mathcal{E}$. Schemes $\mathcal{E}$ satisfying the above conditions are
plenty in the literature. For example any LWE scheme is such.

From these examples we learn that an additional condition on a pair of
composable bridges is required in order to get a secure composition.

This motivates our main result, that is Theorem 5.2. This result is heavily
influenced by the main result of [2], which we recall first together with a
more conceptual proof.

Suppose ${\bf B}_{\iota,f}$ is a bridge from $\mathcal{E}_{1}$ to
$\mathcal{E}_{2}$. Recall that the bridge key generation algorithm produces
the following ensembles of $\\{\mathcal{SK}_{1,\lambda}\\}_{\lambda}$
distributions: $\\{\mathcal{PK}_{1,\lambda}\\}_{\lambda}$,
$\\{\mathcal{PK}_{2,\lambda}\\}_{\lambda}$ and
$\\{\mathcal{BK}_{\lambda}\\}_{\lambda}$. Let $\mathcal{F}$ be the ensemble of
finite distributions of triples $(pk_{1},pk_{2},bk)$. Recall that
$\pi_{1}:\mathcal{F}\to\mathcal{PK}_{1}$ is a morphism of finite
distributions, so $\mathcal{F}$ is an ensemble of
$\mathcal{PK}_{1}$-distributions. In this theorem, we will make use for the
first time of the Definitions 1 and 2.

###### Theorem 5.1

Let ${\bf B}_{\iota,f}$ be a bridge between $\mathcal{E}_{1}$ and
$\mathcal{E}_{2}$ and assume that the scheme $\mathcal{E}_{1}$ is IND-CPA
secure. If there exists a polynomial time constructible on fibers ensemble of
${\mathcal{PK}}_{1}$-distributions $\widetilde{\mathcal{F}}$ which is
computational indistinguishable from $\mathcal{F}$, then the bridge ${\bf
B}_{\iota,f}$ is IND-CPA secure.

###### Proof

To show that the bridge ${\bf B}_{\iota,f}$ is IND-CPA secure it is enough to
show that for any attacker $\mathcal{A}$ on
$\mathcal{E}_{1}[\mathcal{PK}_{\mathcal{G}_{f}}]$ the probability of answering
correctly is bounded above by $\frac{1}{2}+\mathrm{negl}(\lambda)$ (see Remark
5). This probability is given by

$\mathrm{Pr}[\mathrm{Expr}[\mathcal{A}]=1]=\frac{1}{2}\mathrm{Pr}[\mathcal{A}(\mathcal{F},\mathrm{Enc}_{1}(pk_{1},0))=0]+\frac{1}{2}\mathrm{Pr}[\mathcal{A}(\mathcal{F},\mathrm{Enc}_{1}(pk_{1},1))=1].$

If $\mathcal{A}$ is any attacker on
$\mathcal{E}_{1}[\mathcal{PK}_{\mathcal{G}_{f}}]$, then we construct an
attacker $\mathcal{A}_{1}$ on $\mathcal{E}_{1}$ as follows: $\mathcal{A}_{1}$
receives the pair $(pk_{1},c\leftarrow\mathrm{Enc}_{1}(pk_{1},b))$ from the
challenger and uses the sampling algorithm of $\widetilde{\mathcal{F}}$ to
produce a triple $(pk_{1},\alpha,\beta)$. The attacker gives
$(pk_{1},\alpha,\beta,c)$ to $\mathcal{A}$ and then outputs the bit received
from it. Since $\mathcal{E}_{1}$ is IND-CPA secure we have

$\mathrm{Pr}[\mathrm{Expr}[\mathcal{A}_{1}]=1]\leq\frac{1}{2}+\mathrm{negl}_{1}(\lambda),$

for some negligible function $\mathrm{negl}_{1}(\lambda)$. We get that

$\displaystyle\begin{split}\mathrm{Pr}[\mathrm{Expr}[\mathcal{A}_{1}]=1]&=\frac{1}{2}\mathrm{Pr}[\mathcal{A}(\widetilde{\mathcal{F}},\mathrm{Enc}_{1}(pk_{1},0))=0]+\frac{1}{2}\mathrm{Pr}[\mathcal{A}(\widetilde{\mathcal{F}},\mathrm{Enc}_{1}(pk_{1},1))=1]\\\
&\leq\frac{1}{2}+\mathrm{negl}_{1}(\lambda).\end{split}$ (1)

We construct now an IND-CPA distinguisher $\mathcal{D}_{0}$ between
$\mathcal{F}$ and $\widetilde{\mathcal{F}}$ as follows. The distinguisher
receives a triple $(pk_{1},x,y)$ from the challenger and uses $pk_{1}$ to
compute $c\leftarrow\mathrm{Enc}_{1}(pk_{1},0)$, gives $(pk_{1},x,y,c)$ to
$\mathcal{A}$ and outputs the bit received from $\mathcal{A}$. We understand
that $\mathrm{Expr}[\mathcal{D}_{0}]$ identifies $\mathcal{F}$ if it outputs
$0$ and $\widetilde{\mathcal{F}}$, if it outputs $1$. Then we have:

$\displaystyle\begin{split}\mathrm{Pr}[\mathrm{Expr}[\mathcal{D}_{0}]=1]&=\frac{1}{2}\mathrm{Pr}[\mathcal{A}(\mathcal{F},\mathrm{Enc}_{1}(pk_{1},0))=0]+\frac{1}{2}\mathrm{Pr}[\mathcal{A}(\widetilde{\mathcal{F}},\mathrm{Enc}_{1}(pk_{1},0))=1]\\\
&\leq\frac{1}{2}+\mathrm{negl}_{2}(\lambda).\end{split}$ (2)

Similarly, one constructs $\mathcal{D}_{1}$, a distinguisher between
$\widetilde{\mathcal{F}}$ and $\mathcal{F}$, similarly as above, but now
$c\leftarrow\mathrm{Enc}_{1}(pk_{1},1)$. This time,
$\mathrm{Expr}[\mathcal{D}_{1}]$ outputs $0$ if the distinguisher identifies
$\widetilde{\mathcal{F}}$ and outputs $1$ if the distinguisher identifies
$\mathcal{F}$. Thus, we get:

$\displaystyle\begin{split}\mathrm{Pr}[\mathrm{Expr}[\mathcal{D}_{1}]=1]&=\frac{1}{2}\mathrm{Pr}[\mathcal{A}(\mathcal{F},\mathrm{Enc}_{1}(pk_{1},1))=1]+\frac{1}{2}\mathrm{Pr}[\mathcal{A}(\widetilde{\mathcal{F}},\mathrm{Enc}_{1}(pk_{1},1))=0]\\\
&\leq\frac{1}{2}+\mathrm{negl}_{3}(\lambda).\end{split}$ (3)

Adding the inequalities (1), (2), (3) and using the equalities:

$\mathrm{Pr}[\mathcal{A}(\widetilde{\mathcal{F}},\mathrm{Enc}_{1}(pk_{1},0))=0]+\mathrm{Pr}[\mathcal{A}(\widetilde{\mathcal{F}},\mathrm{Enc}_{1}(pk_{1},0))=1]=1$

$\mathrm{Pr}[\mathcal{A}(\widetilde{\mathcal{F}},\mathrm{Enc}_{1}(pk_{1},1))=0]+\mathrm{Pr}[\mathcal{A}(\widetilde{\mathcal{F}},\mathrm{Enc}_{1}(pk_{1},1))=1]=1$

we obtain

$\frac{1}{2}\mathrm{Pr}[\mathcal{A}(\mathcal{F},\mathrm{Enc}_{1}(pk_{1},0))=0]+\frac{1}{2}\mathrm{Pr}[\mathcal{A}(\mathcal{F},\mathrm{Enc}_{1}(pk_{1},1))=1]\leq\frac{1}{2}+\mathrm{negl}(\lambda),$

which is exactly what we wanted to prove.

Now, we are able to state and prove our main result.

###### Theorem 5.2

Suppose $f:\mathcal{E}_{1}\rightarrow\mathcal{E}_{2}$,
$g:\mathcal{E}_{2}\rightarrow\mathcal{E}_{3}$ are composable bridges such that
$f$ is IND-CPA secure and there exists a polynomial time constructible on
fibers ensemble of $\mathcal{PK}_{f}-$distributions which is computational
indistinguishable from $\mathcal{PK}_{g\circ f}$, then $g\circ f$ is IND-CPA
secure.

###### Proof

Notice that the composable pair of bridges $(f,g)$ gives rise to a bridge
$\widehat{g}:\mathcal{G}_{f}\rightarrow\mathcal{E}_{3}$, by the formula:

$\widehat{g}(bk_{\hat{g}},(a,b)):=g(bk_{g},b),$

where $bk_{\hat{g}}=bk_{g}$. Since $f$ is secure, it follows that the scheme
$\mathcal{G}_{f}$ is secure. By our assumptions, an immediate application of
Theorem 5.1 shows that $\widehat{g}$ is IND-CPA secure, which means that the
scheme $\mathcal{G}_{\widehat{g}}$ is IND-CPA secure. Notice that an
encryption of a message $m$ in $\mathcal{G}_{\widehat{g}}$ is in fact a triple
of the form $(a,f(bk_{f},b),g(bk_{g},f(bk_{f},c)))$, where $a,b,c$ are
encryptions of $m$ in $\mathcal{E}_{1}$, so that any adversary $\mathcal{A}$
on $\mathcal{G}_{g\circ f}$ gives rise to an adversary $\mathcal{A}^{\prime}$
on $\mathcal{G}_{\widehat{g}}$. Indeed, notice first that these encryption
schemes have the same public key. On the other hand if
$(a,f(bk_{f},b),g(bk_{g},f(bk_{f},c)))$ is the triple received by
$\mathcal{A}^{\prime}$ from the challenger (together with the public key),
then $\mathcal{A}^{\prime}$ gives the public key and the pair
$(a,g(bk_{g},f(bk_{f},c)))$ to $\mathcal{A}$ and outputs the bit received from
it. It is easy to see that, since

$\mathrm{Pr}[\mathrm{Expr}^{\mathrm{IND-
CPA}}[\mathcal{A}^{\prime}](\lambda)=1]=\mathrm{Pr}[\mathrm{Expr}^{\mathrm{IND-
CPA}}[\mathcal{A}](\lambda)=1],$

if the attacker $\mathcal{A}$ breaks the IND-CPA security of
$\mathcal{G}_{g\circ f}$, then $\mathcal{A}^{\prime}$ also breaks the security
of $\mathcal{G}_{\widehat{g}}$, and this is a contradiction.

##  6 Gentry type bridges

We recall the construction of Gentry type bridges from [2]. Briefly, the
Recrypt algorithm, used in the bootsrapping procedure that transforms a
somewhat homomorphic encryption scheme into a fully homomorphic encryption
scheme (see [15]), can be adapted to our situation in order to give a general
recipe for the construction of a bridge.

Let us consider an encryption scheme

$\mathcal{E}=(\operatorname{\mathrm{KeyGen}}_{\mathcal{E}},\operatorname{\mathrm{Enc}}_{\mathcal{E}},\operatorname{\mathrm{Dec}}_{\mathcal{E}})$

and a homomorphic encryption scheme

$\mathcal{H}=(\operatorname{\mathrm{KeyGen}}_{\mathcal{H}},\operatorname{\mathrm{Enc}}_{\mathcal{H}},\operatorname{\mathrm{Dec}}_{\mathcal{H}},\operatorname{\mathrm{Eval}}_{\mathcal{H}}).$

We shall also denote by $\mathcal{M}_{\mathcal{E}},\mathcal{C}_{\mathcal{E}}$
and $\mathcal{M}_{\mathcal{H}},\mathcal{C}_{\mathcal{H}}$, the plaintext and
ciphertext spaces of $\mathcal{E}$ and $\mathcal{H}$, respectively.

Fix once and for all, a function
$\iota:\mathcal{M}_{\mathcal{E}}\to\mathcal{M}_{\mathcal{H}}$ that is
computable by a deterministic polynomial time algorithm.

At a high level, the bridge key $bk_{f}$ of a Gentry-type bridge
$f:\mathcal{E}\to\mathcal{H}$ consists of the bit representation of the secret
key of $\mathcal{E}$ encrypted under the public key of $\mathcal{H}$.
Moreover, the bridge algorithm is the homomorphic evaluation of the circuit
$\iota\circ\operatorname{\mathrm{Dec}}_{\mathcal{E}}:\mathcal{C}_{\mathcal{E}}\to\mathcal{M}_{\mathcal{H}}$.

We now describe with details the algorithms of the bridge. Let us start with
the key generation algorithm.

$\bullet$ In the first stage, the key generation algorithm of the bridge runs
$\operatorname{\mathrm{KeyGen}}_{\mathcal{E}}(1^{\lambda})$ to obtain a pair
of keys $(sk_{\mathcal{E}},pk_{\mathcal{E}})$. The second stage of the
algorithm runs independently of the first one, and it just makes use of
$\operatorname{\mathrm{KeyGen}}_{\mathcal{H}}(1^{\lambda})$ to obtain
$(sk_{\mathcal{H}},pk_{\mathcal{H}})$.

The final stage of the algorithm takes as input
$(sk_{\mathcal{E}},pk_{\mathcal{E}},sk_{\mathcal{H}},pk_{\mathcal{H}})$
constructed as above, and creates $bk_{f}$ as the vector of encryptions of the
bit representation of $sk_{\mathcal{E}}$ under $pk_{\mathcal{H}}$ (the details
of this are below).

$\bullet$ The PPT algorithm $f$ mentioned in the third part of Definition 4 is
the homomorphic evaluation of the algorithm
$\iota\circ\operatorname{\mathrm{Dec}}_{\mathcal{E}}$. To rigorously perform
it, we need to realise $\iota\circ\operatorname{\mathrm{Dec}}_{\mathcal{E}}$
as a map
$\mathcal{M}_{\mathcal{H}}^{\ell}\rightarrow\mathcal{M}_{\mathcal{H}}$, and
for this we use the ring structure on $\mathcal{M}_{\mathcal{H}}$ (we shall
assume that such a ring structure exists; one can avoid this assumption with
little work, but since all the known FHE schemes have this property we chose
to work with it). Suppose that the ciphertext space
$\mathscr{C}_{\mathcal{E}}$ has a representation as a subset of
$\\{0,1\\}^{n}$ and that the set of secret keys is a subset of
$\\{0,1\\}^{e}$, so that
$\iota\circ\operatorname{\mathrm{Dec}}_{\mathcal{E}}:\\{0,1\\}^{e}\times\\{0,1\\}^{n}\rightarrow\mathcal{M}_{\mathcal{H}}$.
Now, we construct the map
$\widetilde{\iota\circ\operatorname{\mathrm{Dec}}}_{\mathcal{E}}:\mathcal{M}_{\mathcal{H}}^{e}\times\mathcal{M}_{\mathcal{H}}^{n}\rightarrow\mathcal{M}_{\mathcal{H}}$
as follows. Viewing $\mathcal{M}_{\mathcal{H}}$ as a subset of
$\\{0,1\\}^{m}$, we have that
$\iota\circ\operatorname{\mathrm{Dec}}_{\mathcal{E}}:\\{0,1\\}^{e}\times\\{0,1\\}^{n}\rightarrow\mathcal{M}_{\mathcal{H}}$
is a vector $(g_{1},...,g_{m})$ of boolean circuits expressed using ${\rm
XOR}$ and ${\rm AND}$ gates. Let
$\tilde{g_{i}}:\mathcal{M}_{\mathcal{H}}^{e}\times\mathcal{M}_{\mathcal{H}}^{n}\rightarrow\mathcal{M}_{\mathcal{H}}$
be the circuit obtained by replacing each ${\rm XOR}(x,y)$ gate by $x\oplus
y:=2(x+y)-(x+y)^{2}$ and each ${\rm AND}(x,y)$ gate by $x\otimes y:=x\cdot y$,
where $+$ and $\cdot$ are the addition and multiplication in
$\mathcal{M}_{\mathcal{H}}$. Notice that the subset of
$\mathcal{M}_{\mathcal{H}}$ consisting of its zero element $0_{\mathcal{H}}$
and its unit $1_{\mathcal{H}}$ together with $\oplus$ and $\otimes$ is a
realisation of the field with two elements inside $\mathcal{M}_{\mathcal{H}}$.
In other words, if $c=(c[1],...,c[n])\in\mathscr{C}_{\mathcal{E}}$ and
$sk_{\mathcal{E}}=(sk[1],...,sk[e])$ is the secret key, then
$\tilde{g_{i}}(sk[1]_{\mathcal{H}},...,sk[e]_{\mathcal{H}},c[1]_{\mathcal{H}},...,c[n]_{\mathcal{H}})=m_{\mathcal{H}}$
if $g_{i}(sk[1],...,sk[e],c[1],...,c[n])=m$ for all $i$, where
$m\in\\{0,1\\}$. For an element $x\in\mathcal{M}_{\mathcal{H}}$, we let
$[x=1_{\mathcal{H}}]$ be the equality test, which returns $1$ if
$x=1_{\mathcal{H}}$ and $0$ otherwise. Finally,
$\widetilde{\iota\circ\operatorname{\mathrm{Dec}}}_{\mathcal{E}}:\mathcal{M}_{\mathcal{H}}^{e}\times\mathcal{M}_{\mathcal{H}}^{n}\to\\{0,1\\}^{m}$
is defined by:

$\left(\left[\tilde{g_{i}}(y_{1},...,y_{e},x_{1},...,x_{n})={1_{\mathcal{H}}}\right]\right)_{i=\overline{1,m}}.$

One can verify immediately that

$\widetilde{\iota\circ\operatorname{\mathrm{Dec}}}_{\mathcal{E}}(sk[1]_{\mathcal{H}},...,sk[e]_{\mathcal{H}},c[1]_{\mathcal{H}},...,c[n]_{\mathcal{H}})=\iota\circ{\rm
Dec}_{\mathcal{E}}(sk_{\mathcal{E}},c).$

Now we are ready to define the bridge algorithm $f$. Given a ciphertext
$c\in\mathscr{C}_{\mathcal{E}}$, the algorithm $f$ first encrypts the bits of
$c$ (viewed as elements of $\mathcal{M}_{\mathcal{H}}$) under
$pk_{\mathcal{H}}$ and retains these encryptions in a vector $\tilde{c}$. The
bridge key $bk_{f}$ is obtained by encrypting the bits $sk[i]_{\mathcal{E}}$
under $pk_{\mathcal{H}}$, for $i\in\overline{1,e}$. Then, the algorithm $f$
outputs
$\mathrm{Eval}_{\mathcal{H}}(evk_{\mathcal{H}},\widetilde{\iota\circ\operatorname{\mathrm{Dec}}}_{\mathcal{E}},(bk_{f},\tilde{c})).$

###### Remark 6

Let us notice that in the above construction, one does not necessarily need to
encrypt the bit representation of the ciphertext $c$ under $pk_{\mathcal{H}}$.
The whole construction works if one homomorphically evaluates the circuits
$\widetilde{\iota\circ\operatorname{\mathrm{Dec}}}_{\mathcal{E}}(\cdot,c):\mathcal{M}_{\mathcal{H}}^{e}\to\mathcal{M}_{\mathcal{H}}$,
for each fixed ciphertext $c$. While this variant is often more efficient, one
needs to compute the circuit
$\widetilde{\iota\circ\operatorname{\mathrm{Dec}}}_{\mathcal{E}}(\cdot,c)$
every time the bridge is applied. Also, most of the time, there exist
”trivial” encryptions of $0_{\mathcal{H}}$ and $1_{\mathcal{H}}$, so that the
two bridges become identical.

###### Theorem 6.1

Any Gentry type bridge is complete.

###### Proof

With the above notations, if $c$ is _any_ ciphertext in
$\mathcal{C}_{\mathcal{E}}$, then $\tilde{c}$ consists of an $n$-dimensional
vector of ”fresh” encryptions of the scheme $\mathcal{H}$. Since $bk_{f}$ is
an $e$-dimensional vector consisting of fresh encryptions, we have:

$\displaystyle\operatorname{\mathrm{Dec}}_{\mathcal{H}}(sk_{\mathcal{H}},f(bk_{f},c))$
$\displaystyle=$
$\displaystyle\operatorname{\mathrm{Dec}}_{\mathcal{H}}\left(sk_{\mathcal{H}},\operatorname{\mathrm{Eval}}_{\mathcal{H}}(evk_{\mathcal{H}},\widetilde{\iota\circ\operatorname{\mathrm{Dec}}}_{\mathcal{E}},(bk_{f},\tilde{c}))\right)$
$\displaystyle=$
$\displaystyle(\iota\circ\operatorname{\mathrm{Dec}}_{\mathcal{E}})\left(\operatorname{\mathrm{Dec}}_{\mathcal{H}}(sk_{\mathcal{H}},bk_{f}),\operatorname{\mathrm{Dec}}_{\mathcal{H}}(sk_{\mathcal{H}},\tilde{c})\right)$
$\displaystyle=$ $\displaystyle\iota\left({\rm
Dec}_{\mathcal{E}}(sk_{\mathcal{E}},c)\right)$

which shows that third condition in the definition of a bridge is satisfied
for any ciphertext $c\in\mathscr{C}_{\mathcal{E}}$, i.e. $f$ is complete.

An immediate consequence of this theorem and Proposition 1 is the following:

###### Corollary 2

If $f:\mathcal{E}_{1}\rightarrow\mathcal{E}_{2}$ is a bridge and
$g:\mathcal{E}_{2}\rightarrow\mathcal{H}$ is a Gentry type bridge, then the
two bridges are composable.

Now, we can state and prove the main result of this section.

###### Theorem 6.2

If $f:\mathcal{E}_{1}\rightarrow\mathcal{E}_{2}$ is a secure bridge,
$g:\mathcal{E}_{2}\rightarrow\mathcal{H}$ is a Gentry type secure bridge, and
$\mathcal{H}$ is a secure FHE scheme, then $g\circ f$ is a secure bridge.

###### Proof

The security of the bridge will follow from Theorem 5.2, after showing that
the ensemble of distributions $\mathcal{PK}_{g\circ f}$ satisfies the required
indistinguishably condition with respect to a certain polynomial-time
constructible on fibers $\mathcal{PK}_{f}$-distribution. Let us recall that
$\mathcal{PK}_{f}$ consists of the tuple $(pk_{1},pk_{2},bk_{f})$ and that
$\mathcal{PK}_{g\circ f}$ consists of
$(pk_{1},pk_{2},bk_{f},pk_{\mathcal{H}},bk_{g})$. As $g$ is of Gentry-type,
$bk_{g}$ consists of a vector encrypting the bit representation of $sk_{2}$
under $pk_{\mathcal{H}}$. Let $\tilde{\mathcal{F}}$ be the ensemble of
distributions $(pk_{1},pk_{2},bk_{f},pk_{H},\tilde{bk})$, obtained in the
following way. Firstly, one samples $(pk_{1},pk_{2},bk_{f})$ from the
distribution $\mathcal{PK}_{f}$. Secondly, one uses
$\mathrm{KeyGen}_{\mathcal{H}}$ to sample $pk_{\mathcal{H}}$ and then we let
$\widetilde{bk}=(\widetilde{bk}[1],...,\widetilde{bk}[e])$ with
$\widetilde{bk}[i]\leftarrow{\rm Enc}(pk_{\mathscr{H}},0_{\mathscr{H}})$ for
all $i\in\overline{1,e}$, where $e$ is the bit-length of $sk_{2}$. Note that
$e$ can be considered public knowledge, as it only depends on the parameters
of encryption in the scheme $\mathcal{E}_{2}$. We also note that since $g$ is
a Gentry type bridge, the public key $pk_{\mathcal{H}}$ and any sample from
the distribution $\mathcal{PK}_{f}$ are chosen independently from each other.
Note that $\tilde{\mathcal{F}}$ is a polynomial-time constructible on fibers
$\mathcal{PK}_{f}$-distribution. If the scheme $\mathcal{H}$ is IND-CPA
secure, then one can prove by a hybrid argument, identical to the one in the
proof of Proposition 2 of [2], that the $\mathcal{PK}_{f}$-distributions
$\mathcal{PK}_{g\circ f}$ and $\tilde{\mathcal{F}}$ are computationally
indistinguishable.

###### Remark 7

Notice that the Gentry type bridge $g$ in the above theorem is already secure
if the schemes $\mathcal{E}_{2}$ and $\mathcal{H}$ are secure (cf. Theorem 3
in [2]).

##  7 Bridges from circuits and Micciancio’s Theorem

In this section we explain how a bridge can be canonically associated to a
pair consisting of an encryption scheme and a circuit that can be
homomorphically evaluated. As a consequence, one can translate every
discussion about homomorphic circuit evaluation and composition of circuits
into the language of bridges developed here and in [2]. Moreover, one can see
Theorem 6.1 as a generalisation of the following theorem:

######  Theorem 7.1 (Micciancio)

Every circular secure FHE encryption scheme
$\mathcal{H}=(\mathrm{KeyGen},\operatorname{\mathrm{Enc}},\operatorname{\mathrm{Dec}},\operatorname{\mathrm{Eval}})$,
can be transformed into a secure fully composable homomorphic encryption
scheme
$\mathcal{H}^{\prime}=(\mathrm{KeyGen}^{\prime},\operatorname{\mathrm{Enc}},\operatorname{\mathrm{Dec}},\operatorname{\mathrm{Eval}}^{\prime})$.

The terminology fully composable is clarified in Definition 10 below. A sketch
of the proof of this theorem can be found in the talk [19] 111This is a talk
given by D. Micciancio at the FHE.org conference 2022, that took place in
Trondheim, NO - an affiliated event to the Eurocrypt 2022 conference. The
proof starts at time 25:39.. The idea of the proof is to use a procedure
similar to the one in Gentry-type bridge construction. We saw in Theorem 6.1
that these give rise to complete bridges. The difference between the Gentry-
type bridge construction and Micciancio’s resides in the
$\operatorname{\mathrm{KeyGen}}$ algorithms. In the key generation process of
a Gentry type bridge, it is required that the keys of the second scheme are
generated independently from the keys of the first one. On the other hand, in
Micciancio’s construction the two schemes have identical secret and public
keys. This difference impacts only the security of the bridge and does not
affect its completeness property. This can give rise to security issues for
which one is forced to add an extra assumption, namely the circular security
assumption.

We start by showing how one can associate bridges to circuits and homomorphic
encryption schemes.

Let
$\mathcal{E}=(\operatorname{\mathrm{KeyGen}},\operatorname{\mathrm{Enc}},\operatorname{\mathrm{Dec}})$
be an encryption scheme and let $C:\mathcal{M}^{r}\to\mathcal{M}$ be a boolean
circuit defined over the plaintext $\mathcal{M}$ of $\mathcal{E}.$

Assume that the scheme $\mathcal{E}$ is $C-$homomorphic. Recall that a scheme
is homomorphic with respect to the circuit $C$, or is $C-$homomorphic, if
there exists an algorithm $\operatorname{\mathrm{Eval}}(evk,C,c_{1},\ldots
c_{r})$ which takes as input an evaluation key $evk$, the circuit $C$, and an
element of $\mathcal{C}^{r}$ such that the outputted ciphertext satisfies the
following correctness condition:

$\operatorname{\mathrm{Dec}}(sk,\operatorname{\mathrm{Eval}}(evk,C,\operatorname{\mathrm{Enc}}(m_{1}),\ldots,\operatorname{\mathrm{Enc}}(m_{r})))=C(m_{1},\ldots,m_{r}),$

for all $(m_{1},\ldots,m_{r})\in\mathcal{M}^{r}.$

In this context, we associated to the pair $(\mathcal{E},C)$, the bridge
$\mathbf{B}_{C}:\mathcal{E}^{(r)}\to\mathcal{E}$ where the function $\iota$ is
given by:

$\iota(m_{1},\ldots,m_{r}):=C(m_{1},\ldots,m_{r}),$

the bridge key $bk$ consists of the evaluation key $evk$ (possibly empty), and
the bridge algorithm is

$f_{C}(bk,c_{1},\ldots,c_{r}):=\operatorname{\mathrm{Eval}}(evk,C,c_{1},\ldots,c_{r}).$

One can easily see that the correctness property of
$\operatorname{\mathrm{Eval}}$ guarantees that the above construction is
indeed a bridge. Moreover, this bridge is secure as long as the
$C$-homomorphic scheme $\mathcal{E}$ is secure.

###### Remark 8

If $\mathcal{E}$ is an FHE scheme, the above procedure gives rise to a family
of bridges $\mathbf{B}_{C}$, one for each boolean circuit $C$. By
concatenating such bridges
$\mathbf{B}_{C_{1}},\ldots,\mathbf{B}_{C_{s}}:\mathcal{E}^{(r)}\to\mathcal{E}$,
one obtains a bridge
$\mathbf{B}_{C_{1},\ldots,C_{s}}:\mathcal{E}^{(r)}\to\mathcal{E}^{(s)}$.

In his talk [19], Micciancio points out one foundational problem in the
definition of a fully homomorphic encryption scheme. Namely, the definition of
an FHE scheme does not guarantee correct decryption if one sequentially
evaluates two (multivalued) circuits on encrypted data. This issue is an
instance of the more general problem of composing bridges.

More precisely, suppose bridges
$\mathbf{B}_{C_{1},\dots,C_{s}}:\mathcal{E}^{(r)}\to\mathcal{E}^{(s)}$ and
$\mathbf{B}_{D_{1},\ldots,D_{t}}:\mathcal{E}^{(s)}\to\mathcal{E}^{(t)}$ are
constructed as above, for some FHE scheme $\mathcal{E}$. The issue raised by
Micciancio is equivalent to the composability of the pair of bridges
$(\mathbf{B}_{C_{1},\dots,C_{s}},\mathbf{B}_{D_{1},\ldots,D_{t}})$ (see
Definition 8) for all such circuits.

We recall the following definition due to Micciancio.

###### Definition 10

An encryption scheme $\mathcal{E}$ is called _fully composable encryption
scheme_ 222This is the name coined by Micciancio, based on the consequence of
this property described bellow. We chose to use the name complete for its
generalisation to bridges. (FcHE) if for any circuit
$C:\mathcal{M}^{r}\to\mathcal{M}$, the following relation

$\operatorname{\mathrm{Dec}}(sk,\operatorname{\mathrm{Eval}}(evk,C,c_{1},\ldots,c_{r}))=C(\operatorname{\mathrm{Dec}}(sk,c_{1}),\ldots,\operatorname{\mathrm{Dec}}(sk,c_{r}))$

holds for all $c_{1},\ldots,c_{r}\in\mathcal{C}$.

###### Remark 9

It is an immediate consequence of the definition that a scheme is fully
composable if and only if every bridge $\mathbf{B}_{C}$ from the familly
defined above is a complete bridge (see Definition 6).

We point out the following immediate consequence, which is consistent with the
terminology chosen by Micciancio.

###### Proposition 3

Let $\mathcal{E}$ be an FcHE scheme and let $C_{1},C_{2}$ be two (multivalued)
circuits, $C_{1}:\mathcal{M}^{r}\to\mathcal{M}^{s}$ and
$C_{2}:\mathcal{M}^{s}\to\mathcal{M}^{t}$. Then

$\operatorname{\mathrm{Dec}}(sk,\operatorname{\mathrm{Eval}}(evk,C_{2},\operatorname{\mathrm{Eval}}(evk,C_{1},c_{1},\ldots,c_{r}))=C_{2}(C_{1}(m_{1},\ldots,m_{r}))$

for all $c_{1},\ldots,c_{r}\in\mathcal{C}$, where
$m_{i}=\operatorname{\mathrm{Dec}}(sk,c_{i})$ for all $i=\overline{1,r}$.

In particular, in FcHE schemes, one can homomorphically compose 333By
homomorphic composition we understand sequential evaluation of two
(multivalued) circuits on encrypted data. any circuits. However, the converse
is not true:

###### Example 5

Consider any FHE scheme $\mathcal{E}$ which is constructed using a
bootstrapping procedure and such that for every ciphertext $c$, we have
$\mathrm{Bootstrap}(c)\in\operatorname{\mathrm{Enc}}(pk,\operatorname{\mathrm{Dec}}(sk,c))$.
In such a scheme, one can homomorphically perform bootstrapping after every
operation. Then modify the evaluation algorithm of $\mathcal{E}$ such that for
every circuit $C$,

$\operatorname{\mathrm{Eval}}^{\prime}(evk,C,c_{1},\ldots,c_{r}):=\mathrm{Bootstrap}(\operatorname{\mathrm{Eval}}(evk,C,c_{1},\ldots,c_{r})).$

In such a scheme, one can homomorphically compose every two circuits, as the
output of every evaluation algorithm will be a fresh encryption. However, such
a scheme is not necessarily a FcHE scheme according to the Definition 10.

We obtain Micciancio’s result as a corollary to Theorem 6.1, as we now
explain. Indeed, recall from the construction of Gentry-type bridges that one
can realise the set of secret keys of $\mathcal{H}$ and its ciphertext space
as subsets of $\mathcal{M}^{e}$ and respectively $\mathcal{M}^{n}$, where
$\mathcal{M}$ is the plaintext of $\mathcal{E}$. In the same section, we
constructed the map
$\widetilde{\operatorname{\mathrm{Dec}}}:\mathcal{M}^{e}\times\mathcal{M}^{n}\to\mathcal{M}$.
For any ciphertext $c$ of $\mathcal{H}$, we can restrict the second argument
of $\widetilde{\operatorname{\mathrm{Dec}}}$ to obtain
$\widetilde{\operatorname{\mathrm{Dec}}}(\cdot,c):\mathcal{M}^{e}\to\mathcal{M}$.

The encryption scheme $\mathcal{H}^{\prime}$ proposed by Micciancio is
constructed as follows. The encryption and decryption procedures are the ones
from $\mathcal{H}$. The key generation algorithm uses $\mathrm{KeyGen}$ to
obtain a triple $(sk,pk,evk)$. The algorithm now encrypts each component of
$sk=(sk[1],...,sk[e])$, viewed as an element of $\mathcal{M}^{e}$, to obtain
$(\widetilde{sk[1]},...,\widetilde{sk[e]})\in\mathcal{C}^{e}$. Finally, it
outputs the triple $(sk,pk,evk^{\prime})$, where
$evk^{\prime}=(evk,\widetilde{sk[1]},...,\widetilde{sk[e]})$.

For any $C:\mathcal{M}^{l}\to\mathcal{M}$, the evaluation algorithm
$\mathrm{Eval}^{\prime}$ works as follows. Let
$c_{1},c_{2},\ldots,c_{l}\in\mathcal{C}\subseteq\mathcal{M}^{n}$ be any $l$
ciphertexts. Let $g_{(C,c_{1},...,c_{l})}:\mathcal{M}^{e}\to\mathcal{M}$ be
defined as

$g_{(C,c_{1},...,c_{l})}(sk)=C(\widetilde{\operatorname{\mathrm{Dec}}}(sk,c_{1}),\widetilde{\operatorname{\mathrm{Dec}}}(sk,c_{2}),\ldots,\widetilde{\operatorname{\mathrm{Dec}}}(sk,c_{l})).$

The evaluation algorithm of $\mathcal{H}^{\prime}$ is given by:

$\operatorname{\mathrm{Eval}}^{\prime}(evk^{\prime},C,c_{1},...,c_{l}):=\operatorname{\mathrm{Eval}}(evk,g_{(C,c_{1},...,c_{l})},\widetilde{sk[1]},...,\widetilde{sk[e]}).$

We now use the language of bridges to show that $\mathcal{H}^{\prime}$ is a
secure FcHE, under the circular security assumption for $\mathcal{H}$.

The circuit $C$ gives rise as above to a bridge

$\mathbf{B}_{C}:\mathcal{H}^{\prime}\,{}^{(l)}\to\mathcal{H}^{\prime}.$

Since $\mathcal{H}$ and $\mathcal{H}^{\prime}$ are identical once we forget
the evaluation algorithms, we can view this bridge as a bridge ${\bf
Br}_{C}:\mathcal{H}^{(l)}\to\mathcal{H}$. However, this bridge is _not_ the
bridge associated to the circuit $C$ as above. Actually, it is easy to see
that this bridge is the Gentry-type bridge constructed in Section 6 where
$\mathcal{E}=\mathcal{H}^{(l)}$, and $\iota:\mathcal{M}^{l}\to\mathcal{M}$ is
defined by $C$, with the difference that the $\operatorname{\mathrm{KeyGen}}$
outputs the same secret key for both $\mathcal{E}$ and $\mathcal{H}.$ However,
the proof of Theorem 6.1 transports identically, thus the bridge
$\mathbf{B}_{C}$ is complete. Using Remark 9, the scheme
$\mathcal{H}^{\prime}$ is an FcHE scheme.

As we mentioned in Remark 7, the authors proved in [2, Theorem 3] that any
Gentry-type bridge between two secure encryption schemes is also secure.
However, this result does not directly apply to $\mathbf{B}_{C}$ because this
bridge has a slightly different KeyGeneration algorithm. Namely, here the
secret keys of the encryption schemes involved in the bridge are identical,
whereas in Gentry-type bridges they are generated independently. In the
present situation, the security analysis of the scheme $\mathcal{H}^{\prime}$
is much simpler, because it is equivalent to the security analysis of
$\mathcal{H}[evk^{\prime}]$. On the other hand, the security of the latter
scheme reduces to the circular security assumption.

## References

  * [1] Ateniese, G., Fu, K., Green, M., Hohenberger, S.: Improved proxy re-encryption schemes with applications to secure distributed storage, In: ACM Trans. Inf. Syst. Secur., vol 9, no 1, 1–30 (2006)
  * [2] Barcau, M., Lupaşcu, C., Paşol, V., Ţurcaş G. C.: Bridges connecting Encryption Schemes, In Bella, G., Doinea, M., Janicke, H. (eds) Innovative Security Solutions for Information Technology and Communications. SecITC 2022. LNCS, vol 13809, pp. 37–64, Springer, Cham (2023).
  * [3] Bellare, M., Rogaway, P., Introduction to Modern Cryptography, University of California, Notes, https://web.cs.ucdavis.edu/~rogaway/classes/227/spring05/book/main.pdf.
  * [4] Brakerski, Z., Gentry, C., Vaikuntanathan, V.: (Leveled) fully homomorphic encryption without bootstrapping, ACM Transactions on Computation Theory 6(3), No. 13, pp. 1–36 (2014).
  * [5] Brakerski, Z., Vaikuntanathan, V.: Efficient fully homomorphic encryption from (standard) LWE, http://eprint.iacr.org/2011/34.
  * [6] Dodis, Y., Ivan, A.: Proxy cryptography revisited, In: Proceedings of the Tenth Network and Distributed System Security Symposium, February 2003.
  * [7] Phong, L. T., Wang, L., Aono, Y., Nguyen, M. H., Boyen, X.:Proxy Re-Encryption Schemes with Key Privacy from LWE, https://eprint.iacr.org/2016/327.pdf
  * [8] Canetti, R., Krawczyk, H.: Universally composable notions of key exchange and secure channels., In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 337–351. Springer, Heidelberg (2002).
  * [9] Canetti, R., Dodis, Y., Pass, R., Walfish, S.: Universally Composable Security with Global Setup, In: Vadhan, S.P. (eds) Theory of Cryptography. TCC 2007. Lecture Notes in Computer Science, vol 4392. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-70936-7-4
  * [10] Canetti, R.: Universally Composable Security, Journal of the ACM, 675, 2020, pag 1–94
  * [11] Dobraunig, C., Eichlseder, M., Grassi, L., Lallemand, V., Leander, G., List, E., Mendel, F., Rechberger, C.: Rasta: A Cipher with Low ANDdepth and Few ANDs per Bit, In: Advances in Cryptology, CRYPTO 2018, LNCS, vol. 10991, pp. 662 – 692. Springer, Cham (2018).
  * [12] Dobraunig, C., Grassi, L., Helminger, L., Rechberger, C., Schofnegger, M. and Walch, R.: Pasta: A Case for Hybrid Homomorphic Encryption. In Cryptology ePrint Archive (2021).
  * [13] Dottling, N., Nishimaki, R.: Universal Proxy Re-Encryption, Cryptology ePrint Archive, Report 2018/840, to appear in PKC ’21.
  * [14] Ducas, L., Micciancio, D.: FHEW: Bootstrapping Homomorphic Encryption in Less Than a Second, Advances in Cryptology - EUROCRYPT 2015, Lecture Notes in Computer Science vol. 9056, pp. 617 – 640.
  * [15] Gentry, C.: Computing arbitrary functions of encrypted data, Communications of the ACM, 53(3), pp. 97 – 105 (2010).
  * [16] Goldreich, O.: A note on computational indistinguishability, Information Processing Letters, 34(6), pp. 277 – 281.
  * [17] Goldwasser, S., Micali, S.: Probabilistic encryption and how to play mental poker keeping secret all partial information, In: STOC ’82: Proceedings of the fourteenth annual ACM symposium on Theory of computing, pp. 365 – 377. Association for Computing Machinery, New York, NY (1982).
  * [18] Lee, Y. et al. (2023): Efficient FHEW Bootstrapping with Small Evaluation Keys, and Applications to Threshold Homomorphic Encryption, In: Hazay, C., Stam, M. (eds) Advances in Cryptology, EUROCRYPT 2023. LNCS, vol. 14006, Springer, Cham (2023).
  * [19] Micciancio, D., [FHE_org], (9th of June, 2022), Fully Homomorphic Encryption: Definitional issues and open problems [Video], Youtube, https://www.youtube.com/watch?v=b24WJyS0dmg
  * [20] Micciancio, D., Polyakov, Y.: Bootstrapping in FHEW-like Cryptosystems, In: Proceedings of the 9th on Workshop on Encrypted Computing & Applied Homomorphic Cryptography (WAHC ’21). Association for Computing Machinery, New York, NY, USA, 17–-28.
  * [21] Sander, T., Young, A., Yung, M.: Non-Interactive CryptoComputing For $NC^{1}$. In: FOCS ’99: Proceedings of the 40th Annual Symposium on Foundations of Computer Science, pp. 554 – 566, IEEE Computer Society, NW Washington, DC, United States (1999).