两个“实用的”全同态加密方案一、方案说明1、 该方案为对称方案。

2、 该方案仅仅需要线性代数知识。

3、 不需要噪音消除工作。

4、 明文为有限域上的实数。

5、 密文为向量，但同态操作不膨胀。

6、 安全性基于近似最大公约数问题(AGCD)。

二、方案简单描述1、 参数选择(Setup)：设2l n ≤-为已知，例如5n =，3l =。

2、 密钥生成(KeyGen)：有如下几个工作。

- 随机选择向量()101,n n q k k k +=∈ ,,k Z ，()011l l q θθθ-=∈ ,,,Z Θ。

- 对明文q m ∈Z ，令()101Enc(,),,,n n q c m c c c +==∈ k Z ，满足m ⋅=k c ，称为低级加密。

其具体方式为：其中，121212,,,,,h mh r r r r s r sr s r v r v r v - 和rr都是q Z 上的随机数。

1()m ij j j S i s rs ==⋅∑。

ij s 是什么不知道。

- 令011[Enc(,),Enc(,),Enc(,),Enc(,1)]l θθθ-Φ= k k k k 。

- 输出密钥：PK {,}=k Θ，评估公钥PEK {p Enc(,k k ),0,}ij i j i j n ==≤≤k 。

3、 加密(Encryption)：对q m ∈Z ，选择01,,l q r r r ∈ Z ，使???01l m r r r =+++ ，计算：()()()()()()()()()001111Enc ,Enc ,Enc ,Enc ,1m l l l c r r r r θθθ--=⋅⊕⋅⊕⊕⋅⊕⋅ k k k k4、 解密(Decryption)：对密文m c ，计算得到m m ⋅=k c 。

证明：首先根据()Enc ,i θk 的定义，有0,0,1,2,1ni i ij i k i l θθ===⋅=-∑ ，011ni i i k ==⋅=∑。

故：11100110001,1,,1,l l l m i i l i i l i in l n i i i r r r r r r θθθ---===⎛⎫⋅=⋅⋅+⋅⋅+⋅⋅+⋅ ⎪⎝⎭∑∑∑ k c k0001n n nj i ij j l i j i j k r k r θ====⋅⋅+⋅⋅∑∑∑001110(1)01nn n nj j j j j l l j l i j j j j k r k r k r k r θθθ--=====⋅⋅+⋅⋅++⋅⋅+⋅⋅∑∑∑∑1l j j l j r r θ-==⋅+∑???m =。

5、 同态加法：()'''112211'mod ,mod ,mod n n c c c c q c c q c c q ++⊕=++++ 。

可以证明：()()Dec(')Dec ,Dec ,'mod c c c c q ⊕=+k k 。

证明：()'''112211Dec(,')Dec ,(mod ,mod ,mod )n n c c c c q c c q c c q ++⊕=++++ k k'''112211(mod ,mod ,mod )n n c c q c c q c c q ++=⋅++++ k'''01112211(mod )(mod )(mod )n n n k c c q k c c q k c c q ++=⋅++⋅+++⋅+'''010*******()mod ()mod ()mod )n n n n k c k c q k c k c q k c k c q ++=⋅+⋅+⋅+⋅++⋅+⋅''011210112'1mod mod mod mod mod mod n n n n k c q k c q k c q k c q k c q k cq++=⋅+⋅++⋅+⋅+⋅++⋅')mod =(c c q ⋅+⋅k k()()Dec ,Dec ,'mod c c q =+k k另外，由同态加法可以引申出同态数乘运算：令q d ∈Z ，()121mod ,mod ,,mod n d c d c q d c q d c q +=⋅⋅⋅ ，可以证明：()Dec(,)Dec ,mod d c d c q =⋅ k k 。

6、 同态乘法：定义：()()()()()()'''1111121211(1)(1)'n n n n c c c c pek c c pek c c pek ++++⊗=⋅⊕⋅⊕⊕⋅ 。

可以证明：()()()Dec ,c c'Dec ,c Dec ,c'mod q ⊗=⋅k k k 。

证明：()Dec ,c c'c c'⊗=⋅⊗k k()1111Dec ,mod n n i j ij i j c c pek q ++===⋅⋅∑∑k()()111111111111mod mod mod Dec ,c Dec ,c'mod n n i j ij i j n n i i j j i j n n i i j j i j c c sek qk c k c qk c k c qq++==++==++===⋅⋅=⋅⋅⋅=⋅⋅⋅=⋅∑∑∑∑∑∑k k三、问题：由同态评估密钥可以得到密钥k 。

例如，假设01p [,,,]ij ij ij ijn p p p = ，则可从如下方程组求出k ：00000000n n k k p k p k =+00i j ij ijn n k k p k p k =+00n n nn nnn n k k p k p k =+四、可借鉴之处 1、 构造代数结构 ????与解密有关2、 同态运算的构造方式（同态操作密文不膨胀的原因）：采用⊕运算。

可否将类似方式用到基于LWE 的方案。

3、 能否构造为公钥方案。

王会勇 2015.7Huiyong,thanks for the message. For the first r_0 \xor r_1 \xor ...it should be interpreted as regular addition in the finite field.For the second \xor on the c_m (cipher text) in the encrytion phase, it should be interpreted as thehomomorphic addition of cipher text. YonggeMasahiro Yagisawa 方案一、八元数基础1、定义：八元代数是四个除法代数中最大的一个。

八元代数上的一个八元数的形式为[1]：7i i i a a e =∑，其中21i e =-，i q a ∈Z ，坐标形式为：8017(,,)q a a a a =∈ Z 。

a0 a1 a2 a3 a4 a5 a6 a7-a1 a0 a4 a7 -a2 a6 -a5 -a3 -a2 -a4 a0 a5 a1 -a3 a7 -a6 -a3 -a7 -a5 a0 a6 a2 -a4 a1 -a4 a2 -a1 -a6 a0 a7 a3 -a5-a5 -a6 a3 -a2 -a7 a0 a1 a4 -a6 a5 -a7 a4 -a3 -a1 a0 a2 -a a A =7 a3 a6 -a1 a5 -a4 -a2 a0⎛⎫⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪⎝⎭，称为8017(,,)q a a a a =∈ Z 的关联矩阵。

2、运算：令8017(,,)q a a a a =∈ Z ，8017(,,)q b b b b =∈ ZI. 8001177(,,)q a b a b a +b a +b +=+∈ Z 。

II. 017 a0 a1 a2 a3 a4 a5 a6 a7-a1 a0 a4 a7 -a2 a6 -a5 -a3 -a2 -a4 a0 a5 a1 -a3 a7 -a6 -a3 -a7 -a5 a0 a6 a2 -a4 a1 (,,)-a4 a2 -a1 -a6 a0 a7 a3 -a5-a5 -a6 a3 -a2 -a7 a0 a1 a4 -a6 a5 -a7 a4 -a ab bA b b b == (mod )a3 -a1 a0 a2 -a7 a3 a6 -a1 a5 -a4 -a2 a0q ⎛⎫⎪ ⎪ ⎪ ⎪⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪⎝⎭，III. a =。

有ab a b =。

IV.逆：若0(mod )a q ≠，记1071222((mod ),(mod ),,(mod ))a a a a q q q aaa---= 。

可知：1(1,0,0,0,0,0,0,0)aa -=，1mod a ab b q -=，1mod baa b q -=。

11()()mod a ba ab a q --=，12()()mod ba ab b q -=。

3、性质I. 显然加法满足结合律，交换律。

乘法不满足交换律，也不满足结合律。

II.ab a b A A A =（错误）。

III.设123,,n a a a a 为八元数，则有121123((())n n n a a a a a a a a A'A'A'-= 。

二、Yagisawa 方案，令(1,0,0,0)=1 ，x 为八元数。

1、Key setup ：随机取t 个可逆的八元数801,,t q sk k k k =∈ Z 。

2、Encryption ：对八元数明文8qm ∈Z ，记11100(())g ()t k k x x ---= ，0111((())()t k k k x g x -= ，计算：1101110()((((m((()))m t t C x k k k k k x ----=10(mg ())g x = 3、Decryption ：对密文()m C x ，计算：01(g ())m m g C =1 证明：010101(g ())((mg ())g ())m g C g g x =114、同态加法：定义0101()()()m m m m C x C x C x +=+，易知同态解密能成功。

5、同态乘法：定义0101()(())m m m m C x C C x =，可证明一次同态解密成功。

但多次不行。

因为八元数乘法是非结合的。

6、全同态构造：任取八元数8q ∈z Z 和q r ∈Z ，其中0=z ，且00≠z 。