![](https://csdnimg.cn/release/download_crawler_static/36495541/bg4.jpg)
D. System and Security Model
We give an overview of our desired security properties.
We consider three stakeholders: encryptor(s), cloud, and
decryptor. We assume all stakeholders behave semi-honestly
and the cloud does not collude with the decryptor. Let x be
a private input of the encryptor and y be a private input
of the cloud and f be a known function. If the cloud do
not provide any private input then we simply set y = ⊥.
We consider the following model. The encryptor(s) sends
the ciphertext Enc(x) to the cloud for the computation of
a particular function f. The cloud operates specified homo-
morphic operations on Enc(x) and y and sends the resulting
ciphertext Enc(f(x, y)) to the decryptor who decrypts to
learn f(x, y) but nothing else. Under this model, the security
against a semi-honest cloud follows from the fact that the
view of the cloud consists of ciphertexts only. Also, even
if the decryptor knows x, e.g., the encryptor and decryptor
are the same entity, it learns nothing about the input of the
cloud except the result f(x, y).
Recently, Li et al. [41] point out that the approximated de-
cryption results of CKKS can leak additional information of
the decryption keys. They successfully constructed passive
attacks that could recover the decryption keys if given access
to the decryption results. We warn that the decryptor in
PEGASUS should not reveal the decrypted values of CKKS
ciphertexts to the encryptor and anyone else without doing
any counter-measurement such as [13].
In the following descriptions, we describe the computation
on the cloud side and omit the decryption phase of the
decryptor and the encryption phase of the encryptor since
these operations are either simple or application dependent.
III. BUILDING BLOCKS OF PEGASUS
In this section, we propose PEGASUS, a novel framework
that stays in the RLWE form for efficient SIMD computation
(e.g., addition, multiplication, and rotation) and transforms
to LWE for evaluating a wide range of other complex func-
tions via a fine-grained look-up table approximation (e.g.,
sigmoid, ReLU, max/min). The PEGASUS transformation
consists of four core functions including key-switching (F
KS
of Fig. 1a), look-up-table evaluation (F
LUT
of Fig. 1b),
linear transform (F
LT
of Fig. 1c), and approximated modulo
(F
mod
of Fig. 1d), which are detailed in this section. It is
noteworthy that the LUT function in PEGASUS is not exact
and would introduce some (bounded) approximation errors.
A. Overview
PEGASUS works on a set of (R)LWE-based schemes pa-
rameterized by different (R)LWE dimensions and arguments.
Particularly, we use the notations n, n, and n to denote
different (R)LWE dimensions and we write the secret keys in
these dimensions as s, s, and s, respectively. Moreover, the
“bar” mark is used to indicate the magnitude of them, i.e.,
Function F
KS
Input: ct
in
∈ LWE
n,q
s
(m).
Output: ct
out
∈ LWE
n,q
s
(m) such that n ≤ n.
(a) Key-switching Function F
KS
.
Function F
LUT
Input: ct
in
∈ LWE
n,q
s
(d∆mc) of m ∈ R. A look-up
table function T (x) : R 7→ R.
Output: ct
out
∈ LWE
n,q
s
(d∆T (m)c + e) with a small
approximation error e.
(b) Look-up table Function F
LUT
.
Function F
LT
Input: ct
in
∈ RLWE
n,q
s
(Ecd (z, ∆)) of z ∈ R
n
.
A matrix M ∈ R
`×n
and a vector t ∈ R
`
such
that `, n ≤ n/2.
Output: ct
out
∈ RLWE
n,q
0
s
(Ecd (Mz + t, ∆)).
(c) Linear transform Function F
LT
.
Function F
mod
Input: ct
in
∈ RLWE
n,q
0
s
(ˆz + qˆe) for a polynomial ˆz ∈
R
n,q
and some small norm polynomial ˆe ∈ R
n
.
Output: ct
out
∈ RLWE
n,q
00
s
(ˆz + ˆe
0
) with an approxima-
tion error ˆe of a small norm.
(d) Mod q Function F
mod
.
Figure 1: Core functions used in PEGASUS.
n < n < n. In this section, we use q to denote the modulus
of the (R)LWE ciphertexts in a general way, i.e., q might
be a large value with thousands of bits or just a machine
word-sized integer. We give the specific value of q in the
full description of PEGASUS in § IV.
PEGASUS can start with an RLWE ciphertext, e.g., ct ∈
RLWE
n,q
s
(Ecd (v, ∆)) for v ∈ R
`
. On a high level, it can
be summarized in a three-step transformation.
1) Extract the elements of the encoded vector and obtains
a set of LWE ciphertexts.
ct → ct
i
∈ LWE
n,q
s
(∆v[i]) for i ∈ h`i.
2) Evaluate a look-up table T (x) on each LWE ciphertext.
ct
i
→ ct
0
i
∈ LWE
n,q
s
(∆T (v[i])) for i ∈ h`i.
3) Repack the set of LWE ciphertexts to a single RLWE
ciphertext that encrypts the encoded vector T (v).
{ct
0
i
}
i∈h`i
→ ct
00
∈ RLWE
n,q
00
s
(Ecd (T (v), ∆)).
In practice, we usually switch down the LWE ciphertext
of dimension n to a smaller dimension n < n of the
1060