闀垮畨閾惧悓鎬佸姞瀵嗘柟妗堣璁℃枃妗�
==========================

鑳屾櫙
----

闇€姹�
~~~~

闇€姹傛杩�
^^^^^^^^

鍦ㄤ簰鑱旂綉鎶€鏈笉鏂垚鐔熷畬鍠勭殑浠婂ぉ锛屼负浜嗕繚鎶ょ敤鎴烽殣绉侊紝鏁版嵁寰€寰€浠ュ瘑鏂囩殑褰㈠紡鍦ㄨ绠楁満鍐呰繘琛屽瓨鍌ㄣ€備絾鏄紝瀵嗘枃褰㈠紡鐨勬暟鎹毦浠ヨ绠椼€佸鐞嗙殑鐗规€т粠鏌愮绋嬪害涓婃潵璇撮檺鍒朵簡璇稿浜戣绠椼€佸尶鍚嶆姇绁ㄧ瓑璁稿搴旂敤銆傚悓鎬佸姞瀵嗕綔涓鸿В鍐宠闂鐨勬湁鏁堟墜娈靛緱鍒颁簡杩呴€熺殑鍙戝睍銆傚悓鎬佸姞瀵嗛櫎浜嗚兘瀹炵幇浼犵粺鐨勬暟鎹姞瀵嗕箣澶栵紝杩樺彲浠ヤ繚璇佸瘑鏂囨搷浣滀笌鏄庢枃鎿嶄綔瀵瑰簲锛屼粠鏍规湰涓婅В鍐充簡鍔犲瘑鏁版嵁涓嶅彲鎿嶄綔鎬х殑闂銆侾aillier
绠楁硶灏辨槸涓€绉嶅叿鏈夎壇濂藉悓鎬佺壒鎬х殑鍔犲瘑绠楁硶锛屽湪闇€瑕佸瘑鏂囧姞娉曡绠椼€佸瘑鏂囨槑鏂囦箻娉曡绠楃殑鍦哄悎鏋佸叿绔炰簤鍔涖€傛€昏€岃█涔嬶紝鍚屾€佸姞瀵嗘彁渚涗簡涓€绉嶅鍔犲瘑鏁版嵁杩涜澶勭悊鐨勫姛鑳斤紝浠讳綍浜洪兘鍙互瀵瑰姞瀵嗘暟鎹繘琛岃繍绠楋紝杩愮畻杩囩▼涓嶄腑涓嶄細娉勯湶浠讳綍鍘熷鍐呭銆傚悓鏃讹紝鎷ユ湁瀵嗛挜鐨勭敤鎴峰澶勭悊杩囩殑鏁版嵁杩涜瑙ｅ瘑鍚庯紝寰楀埌鐨勬濂芥槸杩愮畻鍚庣殑缁撴灉銆�

鍏蜂綋鍦烘櫙
^^^^^^^^

-  缁撳悎鍖哄潡閾句腑鐨勬櫤鑳藉悎绾﹀拰鍚屾€佸姞瀵嗘妧鏈紝鍦ㄤ釜浜哄緛淇￠殣绉佷繚鎶や腑锛屽埄鐢ㄥ悓鎬佸姞瀵嗭紝璁剧疆璁块棶鏉冮檺锛屽湪涓嶆毚闇蹭釜浜烘槑鏂囦俊鎭殑鍚屾椂锛屽垱寤轰笌涔嬬浉鍖归厤鐨勫悎绾︼紝浣嗗緛淇＄郴缁熸棤娉曞緱鐭ヨ闂敤鎴风殑闇€姹傘€�

-  寮鸿皟闅愮鐨勪笟鍔★紝渚嬪鏈烘瀯涔嬮棿杞处锛岄殣钘忚处鎴蜂綑棰濓紝灏嗙敤鎴疯处鎴蜂綑棰濊繘琛屽姞瀵嗗悗锛岄€氳繃瀵嗘枃涔嬮棿鐨勫姞鍑忚绠楋紝杩涜闅愮鐨勮浆璐︺€�

Paillier鍔犲瘑绠楁硶
~~~~~~~~~~~~~~~~

Paillier绠楁硶姒傝堪
^^^^^^^^^^^^^^^^

Paillier绠楁硶鏄叕閽ュ姞瀵嗕綋绯荤殑涓€涓唬琛ㄧ畻娉曘€備絾鏄紝涓嶅悓浜庝紶缁熺殑鍏挜鍔犲瘑绠楁硶锛孭aillier
绠楁硶闄や簡瀹炵幇瀵规暟鎹殑鍏挜鍔犲瘑锛岃繕鑳戒繚璇佸湪瀵嗘枃涓婄洿鎺ヨ繘琛屽姞娉曟搷浣滐紝鍏剁粨鏋滆В瀵嗗悗涓庡湪鏄庢枃涓婅繘琛屾搷浣滅殑缁撴灉涓€鏍凤紝鍥犳Paillier绠楁硶瀹屽叏鐨勬弧瓒冲瘑鏂囩殑鍔犳硶鍚屾€佹€с€傞櫎姝や箣澶栵紝Paillier绠楁硶杩樻敮鎸佹槑鏂囧拰瀵嗘枃鐨勪箻娉曟搷浣滐紝鍏锋湁鑹ソ鐨勫悓鎬佹€э紝鐩告瘮浜庡綋鍓嶇殑鍏朵粬鍚屾€佸姞瀵嗘洿鍔犲疄鐢ㄣ€�

绠楁硶娴佺▼
''''''''

Paillier鍔犲瘑绠楁硶瀹氫箟涓庝竴鑸叕閽ュ姞瀵嗙浉鍚岋紝涓昏鐢变互涓嬩笁涓儴鍒嗙粍鎴愶細

-  :math:`\mathsf{KeyGen}(\lambda) \rightarrow (pk, sk)`\ 锛氬瘑閽ョ敓鎴愮畻娉曪紝鐢盞GA杩愯锛岃緭鍏ヤ负瀹夊叏鍙傛暟\ :math:`\lambda`\ 锛岃緭鍑轰负涓€瀵瑰叕閽ョ閽ュ\ :math:`(pk,sk)`\ 銆�
-  :math:`\mathsf{Encrypt}(m,pk) \rightarrow CT`\ 锛氬姞瀵嗙畻娉曪紝鐢卞姞瀵嗘柟杩愯锛岃緭鍏ヤ负鐢ㄦ埛鍏挜\ :math:`pk`\ 锛屾槑鏂囩┖闂寸殑浠讳竴娑堟伅\ :math:`m`\ 锛岃緭鍑哄搴斿瘑鏂�
   :math:`CT`\ 銆�
-  :math:`\mathsf{Decrypt}(sk,CT) \rightarrow m`\ 锛氳В瀵嗙畻娉曪紝鐢辫В瀵嗘柟杩愯锛岃緭鍏ヤ负瑙ｅ瘑绉侀挜\ :math:`sk`\ 锛屽瘑鏂嘰 :math:`CT`\ 锛岃緭鍑哄搴旀槑鏂嘰 :math:`m`\ 銆�

鍚屾€佹€ц川
''''''''

鈥�
鍚屾€佸姞瀵嗘槸鎸囪繖鏍蜂竴绉嶅姞瀵嗗嚱鏁帮紝瀵规槑鏂囪繘琛岀幆涓婄殑鍔犳硶鍜屼箻娉曡繍绠楀啀鍔犲瘑锛屼笌鍔犲瘑鍚庡瀵嗘枃杩涜鐩稿簲鐨勮繍绠楋紝缁撴灉鏄瓑浠风殑銆傜敱浜庤繖涓壇濂界殑鎬ц川锛屼汉浠彲浠ュ鎵樼涓夋柟瀵规暟鎹繘琛屽鐞嗚€屼笉娉勯湶淇℃伅銆傚叿鏈夊悓鎬佹€ц川鐨勫姞瀵嗗嚱鏁版槸鎸囦袱涓槑鏂嘰 :math:`a銆乥`\ 婊¤冻\ :math:`Dec(En(a)鈯橢n(b))=a鈯昩`\ 鐨勫姞瀵嗗嚱鏁般€傚叾涓璡 :math:`En`\ 鏄姞瀵嗚繍绠楋紝\ :math:`Dec`\ 鏄В瀵嗚繍绠楋紝\ :math:`鈯欍€佲姇`\ 鍒嗗埆瀵瑰簲鏄庢枃鍜屽瘑鏂囧煙涓婄殑杩愮畻銆傚綋\ :math:`鈯昤\ 浠ｈ〃鍔犳硶鏃讹紝绉拌鍔犲瘑涓哄姞鍚屾€佸姞瀵嗭細褰揬 :math:`鈯昤\ 浠ｈ〃涔樻硶鏃讹紝绉拌鍔犲瘑涓轰箻鍚屾€佸姞瀵嗐€�

.. figure:: ../images/Paillier-properties.png
   :alt: 

瀵逛簬Paillier绠楁硶鏄庢枃绌洪棿閲岀殑鏄庢枃\ :math:`m_1, m_2`\ 锛孭aillier鍔犲瘑绠楁硶鍏锋湁濡備笅鍚屾€佹€с€�

-  鍔犳硶鍚屾€佹€�

:math:`\mathsf{Encrypt}(m_1)*\mathsf{Encrypt}(m_2) = \mathsf{Encrypt}(m_1+m_2)`
;

鍗筹紝\ :math:`m_1 + m_2 = \mathsf{Decrypt}(\mathsf{Encrypt}(m_1)*\mathsf{Encrypt}(m_2))`
銆�

-  鏄庢枃鍜屽瘑鏂囦箻娉曞悓鎬佹€�

:math:`\mathsf{Encrypt}(m_1)^{m_2} = \mathsf{Encrypt}(m_1*m_2)`
;

鍗筹紝\ :math:`m_1 * m_2 = \mathsf{Decrypt}(\mathsf{Encrypt}(m_1)^{m_2})`
銆�

瀹夊叏鎬у垎鏋�
''''''''''

鍒嗘瀽Paillier绠楁硶鐨勫姞瀵嗚繃绋嬶紝涓嶉毦鍙戠幇銆侾aillier绠楁硶锛屾瘡娆″姞瀵嗛兘闅忔満閫夋嫨涓€涓殢鏈烘暟锛岃繖浼氬鑷村悓涓€鏄庢枃涓ゆ鍔犲瘑浼氫骇鐢熶笉鍚屽瘑鏂囷紝杩欑粰閫夋嫨鏄庢枃鏀诲嚮甯︽潵浜嗕笉灏忕殑闅惧害锛屾彁楂樹簡鍔犲瘑鏂规鐨勫畨鍏ㄦ€с€傚姞瀵嗙畻娉曞浜庝繚鎶ゆ暟鎹畨鍏ㄦ€у叿鏈夐潪甯搁噸瑕佺殑浠峰€硷紝浣嗚绠楀鏉傚害涔熶細闅忕潃绠楁硶瀹夊叏鎬х殑鎻愰珮鑰屽鍔犮€�

Pailier绠楁硶鐮旂┒鐜扮姸
^^^^^^^^^^^^^^^^^^^

鐮旂┒杩涘睍
''''''''

Paillier\ `1 <#refer1>`__\ 鍦�1999骞存彁鍑轰簡涓€绉嶆柊鐨勫悓鎬佸姞瀵嗙畻娉曪紝鍗砅aillier鍔犲瘑绠楁硶锛岀敱浜嶱aillier绠楁硶鍙互杩涜鏈夋晥鐨勫姞娉曞悓鎬侊紝鍙楀埌浜嗗箍娉涚殑鍏虫敞銆�2001 骞达紝Damgard 鍜� Jurik
`2 <#refer2>`__ 浣跨敤妯 :math:`n^i`\ 杩涗竴姝ュ Paillier鍔犲瘑浣撳埗杩涜浜嗘帹骞匡紝骞跺鍏跺簲鐢ㄨ繘涓€姝ユ帹骞裤€� Choi绛変汉\ `3 <#refer3>`__\ 閫氳繃閫夊彇鐗规畩鐨勫弬鏁癨 :math:`g`锛孿 :math:`(g^位 =1+ n\mod n^2锛屛� = lcm( p 鈭�1,q 鈭�1))`\ 鏀硅繘浜� Paillier鍔犲瘑浣撳埗銆� 浣嗘槸Choi 绛夋彁鍑虹殑鍙樹綋鏂规涓嶈兘鎶垫姉閫夋嫨瀵嗘枃鏀诲嚮銆傚湪2006
骞寸殑娆у瘑浼氫笂锛孲choenmakers鍜孴uyls `4 <#refer4>`__\ 灏哱 :math:`x鈭圸_n`\ 鐨凱aillier 鍔犲瘑鏂规锛屾墿灞曞埌浜嗗\ :math:`x`\ 杩涜閫愭瘮鐗瑰姞瀵嗙殑Pailier鍔犲瘑鏂规銆�2013
骞寸殑娆у瘑浼氫笂锛孞oye 鍜孡ibert `5 <#refer5>`__
鍒╃敤\ :math:`2^k`\ 闃跺墿浣欓棶棰樿繘涓€姝ュPaillier 鍔犲瘑鏂规杩涜浜嗘帹骞裤€傚湪2014骞寸殑浜氬瘑浼氫笂锛孋atalano `6 <#refer6>`__\ 绛夌瓑浜哄垯鏄彁鍑轰簡鏀寔Paillier鍔犲瘑瀹炰緥鐨勫鍖呭瘑鏂囩殑鍏紑鍙獙璇佹巿鏉冭绠楁柟妗堛€侰astagnos Laguilaumie
`7 <#refer7>`__\ 鍦�2015骞磋璁′簡涓€绉嶇嚎鎬у悓鎬佸姞瀵嗘柟妗堬紝鍏跺畨鍏ㄦ€т緷璧栦簬鍒ゅ畾Diffie-Hellman鍥伴毦闂銆�

鍚屾€佺畻娉曞姣�
''''''''''''

鍚屾€佸姞瀵嗘洿鍏峰叾鍚屾€佸畬澶囨€т笉鍚屽彲浠ュ垎涓哄叏鍚屾€佸拰閮ㄥ垎鍚屾€侊紝鎵€璋撳叏鍚屾€佸氨鏄寚鍔犲瘑鏂规鏀寔涔樻硶鍜屽姞娉曞悓鎬侊紝閮ㄥ垎鍚屾€佸垯鏄寚鍏跺彧婊¤冻鍔犳硶鎴栬€呬箻娉曞悓鎬併€侾aillier灏辨槸鍏峰鑹ソ鐨勫姞娉曞悓鎬佺殑閮ㄥ垎鍚屾€佸姞瀵嗙畻娉曪紝闄や簡Paillier涔嬪锛岃繕鏈夋敮鎸佷箻娉曞悓鎬佺殑RSA鍜孍IGamal绠楁硶锛屼互鍙婃敮鎸佹瘮鐗瑰紓鎴栧悓鎬佺殑Goldwasser
Micali绠楁硶銆備笅琛�1瀵圭洰鍓嶇粡鍏哥殑涓夌鍚屾€佸姞瀵嗘柟妗堜粠璁＄畻澶嶆潅搴︺€佸畨鍏ㄦ€с€佸悓鎬佹€т笁涓柟闈㈣繘琛屼簡瀵规瘮銆�

鈥� 琛�1 缁忓吀鍚屾€佺畻娉曞姣�

+----------------+--------------+------------------------+----------+--------------------------+
| 鍚屾€佸姞瀵嗙畻娉�   | 璁＄畻澶嶆潅搴�   | 鍘熺悊                   | 瀹夊叏鎬�   | 鍚屾€佹€�                   |
+================+==============+========================+==========+==========================+
| Paillier绠楁硶   | 杈冧綆         | 鍒ゆ柇澶嶅悎鍓╀綑绫诲洶闅炬€�   | 寮�       | 鍔犳硶鍚屾€併€佹槑鏂囦箻娉曞悓鎬�   |
+----------------+--------------+------------------------+----------+--------------------------+
| RSA 绠楁硶       | 杈冧綆         | 鍒嗚В澶х礌鏁�             | 杈冨急     | 涔樻硶鍚屾€�                 |
+----------------+--------------+------------------------+----------+--------------------------+
| Gentry 绠楁硶    | 楂�           | 绂绘暎瀛愰泦姹傚拰闂       | 寮�       | 鍔犳硶鍚屾€侊紝涔樻硶鍚屾€�       |
+----------------+--------------+------------------------+----------+--------------------------+

閲囩敤鐨刾aillier鍚屾€佸姞瀵嗙畻娉�
~~~~~~~~~~~~~~~~~~~~~~~~~~

鍩烘湰姒傚康
^^^^^^^^

鈥�
:math:`Paillier`\ 鍔犲瘑绯荤粺鏄竴绉嶅姞娉曞悓鎬佸叕閽ュ姞瀵嗙郴缁燂紝杩欑鍔犲瘑鎶€鏈凡骞挎硾搴旂敤浜庡姞瀵嗕俊鍙峰鐞嗘垨绗笁鏂规暟鎹鐞嗛鍩熴€傚叾鍚屾€佺壒鎬ц〃鐜颁负:鍦ㄥ姞瀵嗗悗鍙洿鎺ュ瀵嗘枃杩涜鐩稿簲鐨勭畻鏈繍绠楋紝鍏惰繍绠楃粨鏋滀笌鏄庢枃鍩熶腑瀵瑰簲鐨勮繍绠楃粨鏋滀竴鑷淬€傚叾姒傜巼鐗规€ц〃鐜颁负:瀵逛簬鐩稿悓鐨勬槑鏂囷紝鍙€氳繃涓嶅悓鐨勫姞瀵嗚繃绋嬪緱鍒颁笉鍚岀殑瀵嗘枃锛屼粠鑰屼繚璇佷簡瀵嗘枃鐨勮涔夊畨鍏ㄣ€�

鍓嶆彁鍋囪鈥嬶細
^^^^^^^^^^^

1. 闅忔満閫夋嫨涓や釜澶ц川鏁皃銆乹婊¤冻\ :math:`gcd(pq, (p-1)*(q-1))`\ 鈥嬨€�
2. :math:`璁＄畻n=p*q`
3. :math:`g = n+1`
4. :math:`位 = 蠁(n) = (p-1)*(q-1)`
5. 瀹氫箟\ :math:`L(x) = (x-1) / n`
6. :math:`渭 = 蠁(n)^{-1} (mod{n})`
7. 鍏挜涓篭 :math:`(n锛実)`
8. 绉侀挜涓篭 :math:`(位锛屛�)`

绠楁硶鏋勯€狅細
^^^^^^^^^^

Encryption
^^^^^^^^^^

1. 璁綷 :math:`m`\ 涓鸿鍔犲瘑鐨勬秷鎭紝鏄剧劧闇€瑕佹弧瓒筹紝\ :math:`0  \leq  m < n`
2. 閫夋嫨闅忔満 :math:`r`\ 锛屼繚璇乗 :math:`gcd(r, n) = 1`
3. 瀵嗘枃\ :math:`c`\ 锛歕 :math:`c = (g^m) *(r^n) mod n^2`

Decryption
^^^^^^^^^^

1. :math:`m = ( L( c^位 mod n^2 ) * 渭 ) mod n`

绠€鍖栫殑璇佹槑杩囩▼锛�

鐢� :math:`L(c^位 (mod{n^2}) * 渭)  (mod{n})`

鏈� :math:`L(g^{m位}*r^{n位} pmod{n^2}*渭) (mod{n})` 鈶�

鍏朵腑\ :math:`位 = (p-1)*(q-1)锛� 渭 = 蠁(n)^{-1} pmod{n}`

鈭礬 :math:`r^{n位} = r^{n(p-1)*(q-1)} = r^{蠁(n^2)}`

鐢辨鎷夊畾鐞嗭細\ :math:`r^{蠁(n^2)}\equiv1(mod{n^2})`

鈶犲紡 => :math:`L(g^{m位} pmod{n^2}*渭) pmod{n}` 鈶�

鈭礬 :math:`g = n+1`

鈭碶 :math:`g^{m位} = (1+n)^{m位} \equiv n位+1 (mod{n^2})`

鈶″紡=> :math:`L((nm位+1)*渭) mod{n}`

=> :math:`\frac{(nm位+1)-1}{n}*渭 (mod{n})`

=>\ :math:`(m位*渭) (mod{n})` 鈶�

鈭礬 :math:`位 = 蠁(n)锛屛� = 蠁(n)^{-1} (mod{n})`

鈭粹憿寮忥細 :math:`(m位*渭) \equiv m (mod{n})`

璇佹瘯

鍚屾€佸姞娉�
^^^^^^^^

涓や釜瀵嗘枃鐨勪箻绉В瀵嗕负鏄庢枃涔嬪拰

:math:`D\left(E\left(m_{1}, r_{1}\right) \cdot E\left(m_{2}, r_{2}\right) \bmod n^{2}\right)=m_{1}+m_{2} \bmod n`

璇佹槑

:math:`\begin{array}{l}D\left(E\left(m_{1}, r_{1}\right) \cdot E\left(m_{2}, r_{2}\right) \bmod n^{2}\right)=D\left(g^{m_{1}} \cdot r_{1}^{n} \cdot g^{m_{2}} \cdot r_{2}^{n}\right) \bmod n^{2}=D\left(g^{m_{1}+m_{2}} \cdot\left(r_{1} r_{2}\right)^{n}\right) \bmod n^{2}=m_{1}+m_{2}\end{array}`

鍚屾€佹暟涔�
^^^^^^^^

瀵嗘枃鐨勬槑鏂囨骞傝В瀵嗕负鏄庢枃鐨勬暟涔�

:math:`D\left(E\left(m_{1}, r_{1}\right)^{k} \bmod n^{2}\right)=k m_{1} \bmod n`

璇佹槑锛�

:math:`D\left(E\left(m_{1}, r_{1}\right)^{k} \bmod n^{2}\right)=D\left(\left(g^{m_{1}} \cdot r_{1}^{n}\right)^{k}\right) \bmod n^{2}=D\left(g^{k m_{1}} \cdot r_{1}^{k} n\right) \bmod n^{2}=k m_{1} \bmod n`

鏂规鎻忚堪
--------

鏁翠綋鏋舵瀯
~~~~~~~~

.. figure:: ../images/Paillier-structure.png
   :alt: 

鎵ц娴佺▼
~~~~~~~~

.. figure:: ../images/Paillier-flow.png
   :alt: 

鍙傝€�
----

.. raw:: html

   <div id="refer1">

.. raw:: html

   </div>

[1] Paillier P. Public-Key Cryptosystems Based on Composite Degree
Residuosity Classes[J]. Lecture Notes in Computer Science, 1999,
547(1):223-238.

.. raw:: html

   <div id="refer2">

.. raw:: html

   </div>

[2] Damg氓rd I, Jurik M. A Generalisation, a Simplication and Some
Applications of Paillier's Probabilistic Public-Key System[J]. Lecture
Notes in Computer Science, 2001, 7(45):119-136.

.. raw:: html

   <div id="refer3">

.. raw:: html

   </div>

[3] Choi D H, Choi S, Won D. Improvement of Probabilistic Public Key
Cryptosystems Using Discrete Logarithm[C]. International Conference
Seoul on Information Security and Cryptology. Springer-Verlag,
2001:72-80.

.. raw:: html

   <div id="refer4">

.. raw:: html

   </div>

[4] Schoenmakers B, Tuyls P. Efficient Binary Conversion for Paillier
Encrypted Values[C]. Advances in Cryptology - EUROCRYPT 2006:522-537.

.. raw:: html

   <div id="refer6">

.. raw:: html

   </div>

[5] Joye M, Libert B. Efficient Cryptosystems from 2k-th Power Residue
Symbols[M]. Advances in Cryptology 鈥� EUROCRYPT 2013. Springer Berlin
Heidelberg, 2013:651-4.

.. raw:: html

   <div id="refer6">

.. raw:: html

   </div>

[6] Catalano D, Marcedone A, Puglisi O. Authenticating Computation on
Groups: New Homomorphic Primitives and Applications [M]. Advances in
Cryptology 鈥� ASIACRYPT 2014. 193-212.

.. raw:: html

   <div id="refer7">

.. raw:: html

   </div>

[7] Castagnos G, Laguillaumie F. Linearly Homomorphic Encryption from
DDH [M]// Topics in Cryptology 鈥�- CT-RSA 2015. Springer International
Publishing, 2015:487-505.-