多方同态加密：安全多方计算的新方案

版权申诉

71 浏览量更新于2024-07-08 收藏 488KB PDF 举报

"这篇论文探讨了一种基于环学习带误差（Ring-Learning-with-Errors,RLWE）的多方同态加密（Multiparty Homomorphic Encryption, MHE）方案，旨在实现安全多方计算（Secure Multiparty Computation, MPC）。作者提出了一个多人版本的Brakerski-Fan-Vercauteren同态加密系统，并将其实现为开源库，以支持这种解决方案。该方案在半诚实模型中具有抵御恶意多数的优势，其特点包括公开的交互记录、紧凑的离线阶段和非交互式的电路评估过程。这使得通信复杂度从平方级别降低到线性级别，极大地扩展了安全计算的参与方数量，涵盖了从传统的点对点环境到云外包和智能合约技术等多种计算范式。" 本文的核心知识点包括： 1. 同态加密：同态加密允许在密文上进行计算，而不会揭示任何关于原始明文的信息。这种特性使得数据在加密状态下仍能进行处理，从而提高了隐私保护能力。 2. 隐私计算：隐私计算是一类技术，它允许数据在被保护的状态下进行计算，确保敏感信息不被泄露，同时保持计算结果的准确性。在这个场景中，多方同态加密是实现隐私计算的一种有效手段。 3. 安全多方计算：安全多方计算允许多个参与者共同计算一个函数，而无需透露他们的输入数据。在此过程中，即使有部分参与者是恶意的，也能保证计算的正确性和数据的隐私。 4. 环学习带误差（RLWE）：RLWE是一种用于构建后量子密码学的数学问题，是同态加密中的基础工具。它的安全性基于解决环上的线性方程组的困难性。 5. Brakerski-Fan-Vercauteren同态加密系统：这是一个特定的同态加密方案，以其发明者的名字命名，它提供了一种有效的方式来进行部分同态加密操作。 6. 多方同态加密（MHE）：MHE是同态加密的扩展，适用于多个人之间的计算。论文中提出的MHE方案能够支持大量参与者，降低了通信复杂度，使得大规模的分布式安全计算成为可能。 7. 开源库实现：为了促进研究和应用，作者实现了MHE方案的一个开源库，这将方便其他研究者和开发者在实际项目中利用这一技术。 8. 通信复杂度降低：传统MPC方案的通信复杂度与参与方数量的平方成正比，而MHE方案通过优化，将复杂度降为线性，极大地提升了大规模协作计算的效率。 9. 应用场景：MHE方案不仅适用于传统的点对点环境，还可以应用于云服务外包和智能合约等新兴领域，展示了其在现实世界中的广泛应用潜力。这篇论文为隐私保护和安全计算提供了新的视角，通过多方同态加密技术，解决了大规模协作计算中的隐私和安全挑战，有望推动相关领域的进步。

Scheme 1. BFV(t, n, q, w, σ, B)

BFV.SecKeyGen(): Sample s ← R

. Output: sk = s

BFV.PubKeyGen(sk):

Let sk = s. Sample p

← R

, and e ← χ. Output:

pk = (p

, p

) = (−sp

+ e, p

)

BFV.RelinKeyGen(sk, w):

Let sk = s. Sample r

← R

, e ← χ

. Output:

rlk = (r

, r

) = (s

w − sr

+ e, r

)

BFV.Encrypt(pk, m):

Let pk = (p

, p

). Sample u ← R

and e

, e

← χ.

Output: ct = (∆m + up

+ e

, up

+ e

)

BFV.Decrypt(sk, ct):

Let sk = s, ct = (c

, c

). Output:

= [b

+ c

and truncated support over [−B, B] where σ and B are two

cryptosystem parameters.

The security of BFV is based on the hardness of the

decisional-RLWE problem [31] that is informally stated as

follows: Given a uniformly random a ← R

, a secret s ← R

and an error term e ← χ, it is computationally hard for an

adversary that does not know s and e to distinguish between

the distribution of (sa+e, a) and that of (b, a) where b ← R

Encrypted arithmetic operations must preserve the plaintext

arithmetic. We denote BFV.Add and BFV.Mul the homomor-

phic addition and multiplication, respectively, and we refer

the reader to [34] for their implementation. The BFV.Mul

operation outputs a ciphertext consisting of three R

elements

that can be seen as a degree two ciphertext. This higher degree

ciphertext can be further operated on and decrypted. Yet it is

often desirable to reduce this degree back to one, by using a

BFV.Relinearize operation [34]. This operation is public but

requires the generation of a speciﬁc public key, referred to as

the relinearization key (rlk).

The decryption of a ciphertext (c

, c

) can be seen as a two-

step process. The ﬁrst step requires the secret key to compute

a noisy plaintext in R

+ sc

]

= ∆m + e

, (1)

where e

is the ciphertext overall error, or ciphertext noise. In

the second step, the message is decoded from the noisy term

in R

to a plaintext in R

, by rescaling and rounding

(∆m + e

)e]

= [bm + at + ve]

, (2)

where m ∈ R

, a has integer coefﬁcients, and v has coef-

ﬁcients in Q. Provided that kvk <

, Eq. (2) outputs m.

Hence, the correctness of the scheme is conditioned on the

noise magnitude ke

k that must be kept below

throughout

the homomorphic computation, notably by choosing a sufﬁ-

ciently large q. To preserve this condition when multiplying

with the rlk (as a part of BFV.Relinearize), ciphertexts are

temporarily decomposed in a basis w < q and the product

is performed on each element of the decomposition [34].

We write l = dlog

(q)e the number of coefﬁcients in this

decomposition, and w = (w

, w

, ..., w

l−1

)

the base-w

reconstruction vector.

D. Parameter Selection

Selecting the parameters for a given application consti-

tutes a signiﬁcantly more challenging task for homomorphic-

encryption schemes than for traditional encryption. Although

the standardization document [30] is a good basis for mapping

the subset of commonly used parameter values to bit-security

levels, mapping the correctness and efﬁciency requirements

to concrete parameters in a systematic way is still an open

question in FHE research: it goes beyond the scope of this

work. Nowadays, we see the rise of compilers for HE [38]

that will, as they evolve, automate this process.

We describe the common heuristic approach for select-

ing BFV parameters; the one we used for the evalua-

tion of our work (Section VI). The task consists in ﬁnd-

ing (t, n, q, w, σ, B) that satisfy the required security and

homomorphic-capacity parameters (λ, κ) for the set of con-

sidered homomorphic circuits. The standardization document

and most implementations ﬁx the noise standard deviation and

bound to σ ≈ 3.2 and B ≈ 20, respectively. Hence, only the

ring degree n, plaintext-space and ciphertext-space moduli t

and q, and the decomposition basis w remain to be determined.

The message-space characteristics of the application usually

sets t directly, by considering the bit-width of the input values.

The targeted set of homomorphic circuits constrain q and n:

Choosing larger q permits larger circuit depth (Equation (2))

but also reduces the hardness of the RLWE problem. Choosing

larger w reduces the noise incurred by Relinearize (hence en-

ables smaller q) and increases its computation cost and the rlk

size. Choosing larger n increases the security (hence enables

larger q for a ﬁxed security level) but has a signiﬁcant impact

on the cost incurred by polynomial multiplication. Hence, the

most common strategy is to set q and w experimentally, as

an acceptable trade-off for the application, then to choose the

smallest power-of-two n for the desired security level.

IV. THE MULTIPARTY BFV SCHEME

We introduce a novel multiparty version of the Brakerski-

Fan-Vercauteren (BFV) cryptosystem [34]. Although formu-

lated for the BFV scheme, the introduced protocols can be

straightforwardly adapted to other RLWE-based cryptosys-

tems, such as BGV [39] or the more recent CKKS [40],

which enables homomorphic approximate arithmetic. We im-

plemented both multiparty versions for the BFV and CKKS

schemes in the Lattigo open-source library [16]. Our approach

follows the blueprint of the LWE-based protocols by Asharov

et al. [14], and introduces several improvements to their

schemes. In particular, we propose a novel procedure for the

剩余17页未读，继续阅读

chenxin0215

粉丝: 26
资源: 16

多方同态加密：安全多方计算的新方案

全同态加密研究动态及其应用概述.pdf

完全同态加密

具有自适应选择密文安全性但没有随机预言的同态加密方案

基于同态加密的高效多方保密计算

国密SM2与SM9支持的高效加法同态加密方案

整数多项式环上的多对一全同态加密算法研究

云计算下的多方安全集合并集计算：基于同态加密的高效解决方案

具有短密文的多身份全同态加密构造框架

同态加密驱动的高效安全多方乘积协议

基于同态加密的高效多方保密计算新方法

最新资源