突破性进展：更快的全同态加密技术

需积分: 50 79 浏览量更新于2024-07-19 收藏 416KB PDF 举报

全同态加密（Fully Homomorphic Encryption, FHE）是密码学领域的一项革命性突破，由IBM公司的克雷格·金特里在2009年提出。传统的加密系统只允许数据在加密状态下进行有限的操作，如读取或比较，但全同态加密则打破了这个限制，允许对加密数据进行任意的计算，包括加法、乘法等，且结果在解密后与未加密数据的运算结果一致。这就像在加密的状态下解决一个问题，然后在解开谜底时得到与明文计算一样的答案。金特里的工作基于理想格理论，这是一种数学构造，使得加密数据能够在保持其加密状态的同时执行各种计算。他的方案依赖于两个关键部分：一是对相关于稀疏子集和问题的复杂性假设进行了更为激进的分析；二是引入了一个概率性的解密算法，这个算法可以在低度乘法电路中实现，这意味着在加密处理过程中所需的计算资源更少。 Faster Fully Homomorphic Encryption（FFHE）论文进一步优化了金特里的全同态加密技术，主要体现在两个方面。首先，通过深入研究与稀疏子集和问题相关的假设，研究人员提供了更为严格的理论基础，这有助于提升加密系统的安全性，并可能减少对难以破解的硬问题的依赖。其次，论文提出了一种新的解密算法，它显著降低了加密操作的复杂性。通过设计具有低度乘法度的代数电路，FFHE的每个基本二元加/乘运算的复杂度被降低到了O(λ^3.5)位，其中λ是安全参数，通常代表了加密强度。这一改进对于Smart和Vercauteren在PKC'2010年提出的全同态加密方案以及van Dijk等人在Eurocrypt'2010年的相关工作同样适用，意味着这些系统在实际应用中的效率得到了提升。 FFHE的出现标志着全同态加密技术迈入了一个新的发展阶段，它不仅提升了加密处理的速度，还降低了实施难度，这对于涉及大量数据处理和隐私保护的场景，如云计算、大数据分析和机器学习等领域具有重大意义。随着研究的深入，全同态加密有望在保障数据安全的同时，实现更加高效的计算能力。

Let us discuss the conjecture. One often considers the lattice gap

> γ

, then

-SVP is equivalent to

-SVP for any

: a

-SVP

solver is guaranteed to output a multiple of a shortest vector, from which

solving SVP is easy. Similarly, if

= O(1)

but

> γ

, then lattice

reduction will return a basis whose rst two vectors span a sublattice

containing vectors reaching

and

: SVP can then be solved by

dimensional reduction. This explains why we consider

rather than the

more standard

. Note that for most common lattices, there is no a

priori reason to expect

to be signicantly larger than

. Finally, when

≤ γ

, the complexity of

-SVP does not seem to depend on

. The

experimental results in [7] seem to be consistent with this conjecture.

Algorithmic improvements have been proposed (e.g., [6, 16]), but they

have only led to better constants, without changing the overall frame-

work. The conjecture seems to hold even if one considers quantum com-

puters [18]. We will consider it for two families of lattices: no algorithm is

known to perform non-negligibly better for them than for general lattices.

For a lattice

, we dene

det L

|det B|

for any basis

. Minkowski's

theorem provides a link between the minimum and the determinant.

Theorem 2.1 ([4, III.2.2]).

Let

be an

-dimensional lattice and

be a compact convex set that is symmetric about the origin. Let

m ≥ 1

an integer. If

vol(V ) ≥ m2

det(L)

, then

contains at least

non-zero

pairs of points

±b

2.2 Ideal lattices

Let

f ∈ Z[x]

a monic degree

irreducible polynomial. Let

denote the

polynomial ring

Z[x]/f

. Let

be an (integral) ideal of

, i.e., a subset of

that is closed under addition, and multiplication by arbitrary elements

. By mapping polynomials to the vectors of their coecients, we see

that the ideal

corresponds to a sublattice of

: we can thus view

both a lattice and an ideal. An

ideal lattice

for

is a sublattice of

that corresponds to an ideal

I ⊆ Z[x]/f

. In the following, an ideal lattice

will implicitly refer to an

-ideal lattice. For

v ∈ R

we denote by

kvk

its Euclidean norm (as a vector). We dene a multiplicative expansion

factor

(R)

for the ring

(R) = max

u,v∈R

ku×vk

kuk·kvk

. A typical choice

f = x

+ 1

with

a power of

, for which

(R) =

√

(see [9, Th. 9]).

Two ideals

and

are said coprime if

I + J = R

, where

I + J =

{i+j : i ∈ I, j ∈ J}

. An ideal

is said prime of degree

det(I)

is prime.

For an ideal

, we dene

−1

= {v ∈ Q[x]/f : ∀u ∈ J, u × v ∈ R}

剩余24页未读，继续阅读

飞梅尔

粉丝: 0
资源: 1

突破性进展：更快的全同态加密技术

基于同态公钥加密系统的图像可逆信息隐藏算法

完全同态加密

全同态加密技术.rar

云计算时代下的全同态加密进展与挑战

全同态加密：Gentry框架与整数方案解析

全同态加密：基于PACDP的高效整数方案

压缩解密算法在全同态加密中的应用

"全同态加密和可信执行环境的完整性保护

基于硬件全同态加密和可信执行环境的安全保障：一个软件库的介绍和评估

基于同态加密的安全数据分析方案

最新资源