PEGASUS：融合多项式与非多项式评估的同态加密框架

需积分: 10 108 浏览量更新于2024-07-09 收藏 2.95MB PDF 举报

"PEGASUS:Bridging Polynomial and Non-polynomial Evaluations in Homomorphic Encryption" 在密码学领域，同态加密（Homomorphic Encryption, HE）是一种革命性的技术，它允许对加密数据进行计算，而无需先解密。这为隐私保护应用提供了强大的基础。然而，现有的同态加密方案在处理混合了多项式和非多项式函数的计算时效率低下，这限制了其在现实世界中的广泛应用。为了解决这个问题，"PEGASUS"框架应运而生。 PEGASUS（Probabilistic Encryption for Galois Fields and Switching Unbounded Series of Structures）是一种实用的同态加密框架，旨在有效地在打包的CKKS（Ciphertext-Packing for Approximate Arithmetic）密文和FHEW（Full Homomorphic Encryption over the Integers with Fast Evaluation using the Wiedemann algorithm）密文之间切换，而无需解密。CKKS是用于近似算术运算的同态加密方案，适合处理多项式函数；FHEW则适用于执行查找表操作，更适合处理非多项式函数。在PEGASUS中，一个关键创新是FHEW到CKKS的转换算法。与现有的转换方法相比，这个算法更具有实用性。它将计算复杂度从线性降低到亚线性级别，显著提高了效率。此外，转换密钥的大小也大幅减小，例如，从80GB减少到12MB，这在存储和传输方面都带来了巨大的改进。为了验证PEGASUS的有效性，作者进行了详尽的基准测试。这些测试结果展示了PEGASUS在处理混合型计算任务时的高效性能，进一步证明了该框架在实际应用中的潜力。通过这种框架，可以预见同态加密在大数据分析、云计算以及机器学习等领域的隐私保护应用将得到显著提升，特别是在那些需要同时处理多项式和非多项式运算的场景中。 PEGASUS为同态加密技术提供了一个新的视角，它解决了混合计算的难题，提升了效率，并降低了资源需求，有望推动同态加密技术在实际场景中的广泛应用。

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 speciﬁed 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 efﬁcient SIMD computation

(e.g., addition, multiplication, and rotation) and transforms

to LWE for evaluating a wide range of other complex func-

tions via a ﬁne-grained look-up table approximation (e.g.,

sigmoid, ReLU, max/min). The PEGASUS transformation

consists of four core functions including key-switching (F

of Fig. 1a), look-up-table evaluation (F

LUT

of Fig. 1b),

linear transform (F

of Fig. 1c), and approximated modulo

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

Input: ct

∈ LWE

n,q

(m).

Output: ct

out

∈ LWE

n,q

(m) such that n ≤ n.

(a) Key-switching Function F

Function F

LUT

Input: ct

∈ LWE

n,q

(d∆mc) of m ∈ R. A look-up

table function T (x) : R 7→ R.

Output: ct

out

∈ LWE

n,q

(d∆T (m)c + e) with a small

approximation error e.

(b) Look-up table Function F

LUT

Function F

Input: ct

∈ RLWE

n,q

(Ecd (z, ∆)) of z ∈ R

A matrix M ∈ R

`×n

and a vector t ∈ R

such

that `, n ≤ n/2.

Output: ct

out

∈ RLWE

n,q

(Ecd (Mz + t, ∆)).

Function F

mod

Input: ct

∈ RLWE

n,q

(ˆz + qˆe) for a polynomial ˆz ∈

n,q

and some small norm polynomial ˆe ∈ R

Output: ct

out

∈ RLWE

n,q

(ˆz + ˆe

) 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 speciﬁc value of q in the

full description of PEGASUS in § IV.

PEGASUS can start with an RLWE ciphertext, e.g., ct ∈

RLWE

n,q

(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

∈ LWE

n,q

(∆v[i]) for i ∈ h`i.

2) Evaluate a look-up table T (x) on each LWE ciphertext.

→ ct

∈ LWE

n,q

(∆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

}

i∈h`i

→ ct

∈ RLWE

n,q

(Ecd (T (v), ∆)).

In practice, we usually switch down the LWE ciphertext

of dimension n to a smaller dimension n < n of the

1060

剩余16页未读，继续阅读

Champhoenix

粉丝: 183
资源: 57

PEGASUS：融合多项式与非多项式评估的同态加密框架

Lua实现视频流技术库：video-streaming.lua

Pegasus天马座开发板与超声波传感器的测距实践

"Apple Watch安全研究与漏洞利用技术

ArubaInstant_Pegasus_6.4.2.6-4.1.3.7_71499

ArubaInstant_Pegasus_6.4.4.8-4.2.4.6_58505

ArubaInstant_Pegasus_6.4.4.8-4.2.4.17_75903

ArubaInstant_Pegasus_6.5.4.19_79367

ArubaInstant_Pegasus_6.5.4.3_61959

Aruba AP103 ArubaInstant_Pegasus_6.5.4.22_83089

SCA_WS-BPEL客户端及实现模型_V100_Pegasus.pdf

最新资源