# 鎶楅噺瀛愬鏂瑰畨鍏ㄨ绠楁柟妗�

## 闇€姹傝儗鏅�
鏈ā鍧椾负闀垮畨閾炬彁渚涗竴绉嶆姉閲忓瓙鐨勫鏂归棬闄愯В瀵嗚兘鍔涳紝鍔犲瘑鏂逛娇鐢ㄥ叕閽ュ鏁版嵁杩涜鍔犲瘑锛屽涓閽ユ寔鏈夋柟鑱斿悎瀵规暟鎹繘琛岃В瀵嗐€�

鍦ㄥ尯鍧楅摼搴旂敤鍦烘櫙涓紝甯稿父闇€瑕佹湁澶ч噺闅愮鏁版嵁瀛樺偍锛屼负浜嗕繚鎶ゆ暟鎹殑闅愮锛屾暟鎹線寰€浠ュ姞瀵嗙殑褰㈠紡杩涜瀛樺偍銆備絾瑙ｅ瘑鐢ㄧ殑绉侀挜濡傛灉鍦ㄥ崟涓妭鐐逛笂杩涜绠＄悊锛屼細閫犳垚鑺傜偣鏉冮檺杩囧ぇ鍜岀閽ユ硠闇查闄┿€�

鎶楅噺瀛愬鏂归棬闄愯В瀵嗗彲浠ヤ娇寰楃閽ョ敱澶氫釜鑺傜偣杩涜绠＄悊锛岄渶瑕佸鍔犲瘑鏁版嵁杩涜瑙ｅ瘑鐨勬椂鍊欙紝瀵瑰涓閽ョ鐞嗚妭鐐瑰彂璧疯В瀵嗚姹傦紝绉侀挜绠＄悊鑺傜偣浣跨敤鑷繁鐨勭閽ヤ唤棰濆鏁版嵁鎵ц瑙ｅ瘑锛屽緱鍒拌В瀵嗗垎鐗囷紝灏嗚В瀵嗗垎鐗囧彂閫佺粰瑙ｅ瘑璇锋眰鏂癸紝瑙ｅ瘑璇锋眰鏂规敹闆嗗埌涓€瀹氭暟閲忕殑瑙ｅ瘑鍒嗙墖鍚庯紝鎭㈠鍑洪殣绉佹暟鎹€�

浼犵粺澶氭柟闂ㄩ檺瑙ｅ瘑鐨勬瀯閫犻兘渚濊禆浜庡ぇ鏁存暟鍒嗚В銆佺鏁ｅ鏁版眰瑙ｇ瓑鍥伴毦闂锛岀劧鑰屽湪閲忓瓙璁＄畻鏈虹殑鏀诲嚮涓嬶紝杩欎簺鍥伴毦闂灏嗕笉鍐嶅畨鍏ㄣ€傚熀浜庢牸鏋勯€犵殑瀵嗙爜绠楁硶閫氬父渚濊禆浜庢牸涓婄殑鍥伴毦闂锛屽鏍间笂鏈€鐭悜閲忛棶棰樸€佹渶杩戝悜閲忛棶棰橈紝杩欎簺鍥伴毦闂鍦ㄩ噺瀛愯绠楁満鏀诲嚮涓嬩粛鐒舵槸瀹夊叏鐨勩€傚湪浼楀鍩轰簬鏍兼瀯閫犵殑瀵嗙爜绠楁硶涓紝鍩轰簬NTRU鏍兼瀯閫犵殑绠楁硶鍏锋湁杈撳嚭鍚戦噺鐭紝杩愮畻楂樻晥鐨勭壒鎬э紝鏈ā鍧楃爺绌跺熀浜嶯TRU鏍肩殑澶氭柟闂ㄩ檺瑙ｅ瘑绠楁硶锛屽埄鐢ㄧ嚎鎬х瀵嗗垎浜柟妗堝绉侀挜杩涜瀹夊叏鍒囧壊銆�

浜嗚В浣跨敤鏂规硶锛岃鍙傝€僛鎶楅噺瀛愬鏂瑰畨鍏ㄨ绠椾娇鐢ㄦ枃妗(../dev/鎶楅噺瀛愬鏂瑰畨鍏ㄨ绠椾娇鐢ㄦ枃妗�.md)
## 鍦烘櫙浠嬬粛

-	鍦ㄤ笟鍔″満鏅腑锛屾煇浠芥晱鎰熸暟鎹姞瀵嗙粰钁ｄ簨浼氾紝鐢ㄤ簬姹囨姤锛岀敱浜庢暟鎹晱鎰熸€э紝闇€瑕佸涓懀浜嬩細鎴愬憳鍦ㄥ満锛屾暟鎹墠鑳借瑙ｅ瘑銆�
-	鍖荤枟鏁版嵁搴撲腑锛岀梾浜虹殑鏁忔劅鏁版嵁閫氬父鍔犲瘑瀛樺偍锛屼娇鐢ㄥ崟绉侀挜瑙ｅ瘑浼氫娇寰楃閽ユ帉绠℃柟鏉冮檺杩囧ぇ锛屽垏涓€鏃︾閽ユ硠闇诧紝鍒欎細閫犳垚闅愮鏁版嵁娉勯湶銆傞€氳繃澶氭柟闂ㄩ檺瑙ｅ瘑锛屽彲浠ュ皢绉侀挜鐨勮В瀵嗚兘鍔涘垎鏁ｇ粰鍚勪釜鏁版嵁搴撶洃鐫ｇ鐞嗚妭鐐癸紝鍙湁澶氫釜鑺傜偣鑱斿悎瑙ｅ瘑锛岃姹傛暟鎹柟鎵嶈兘鑾峰緱鏁忔劅鏁版嵁銆�


## 瀹炴柦鏂规
1. 闀垮畨閾剧郴缁熷垵濮嬪寲鍚庯紝灏哊TRU绠楁硶鐨勭閽ユ寜锛坱-n锛夐棬闄愬垏鍓插悗鍒嗗彂缁欐暟鎹鐞嗚妭鐐硅繘琛屾帉绠°€傚皢鍏挜鍦ㄧ郴缁熷唴杩涜鍏紑
2.	涓氬姟鏁版嵁鏂逛娇鐢ㄥ叕閽ュ闅愮鏁版嵁杩涜鍔犲瘑瀛樺偍
3.	鏁版嵁鐢ㄦ埛杩涜瑙ｅ瘑鐢宠
- 鏁版嵁鐢ㄦ埛閫氳繃鏅鸿兘鍚堢害鍚戝瘑閽ユ帉绠¤妭鐐圭敵璇疯В瀵嗗瘑鏂囨暟鎹�
- 瀵嗛挜鎺岀鑺傜偣鎵ц閮ㄥ垎瑙ｅ瘑寰楀埌瑙ｅ瘑鍒嗙墖
- 瀵嗛挜鎺岀鑺傜偣灏嗚В瀵嗗垎鐗囧彂閫佺粰鏁版嵁鐢ㄦ埛
- 鏁版嵁鐢ㄦ埛鏀堕泦鍒颁竴瀹氭暟閲忕殑瑙ｅ瘑鍒嗙墖鍚庯紝鎵ц鏈€缁堣В瀵嗐€�

鏁翠綋鏋舵瀯濡傚浘鎵€绀�
![](../images/post-quantum-cryptography.png)

## 闀垮畨閾剧殑鎶楅噺瀛愬鏂瑰畨鍏ㄩ棬闄愮畻娉曚粙缁�

### 绾挎€х瀵嗗垎浜柟妗�

闀垮畨閾剧殑鎶楅噺瀛愬鏂瑰畨鍏ㄩ棬闄愮畻娉曚娇鐢ㄧ殑绾挎€х瀵嗗垎浜柟妗堝熀浜嶥an Boneh绛変汉浜�2018骞存彁鍑虹殑{0,1}-LSSS 鏂规锛屽叿浣撶殑缁嗚妭涓�

(1) 棣栧厛瀵逛簬涓€鑸殑t/u闂ㄩ檺鏂规锛屽叾瀵瑰簲鐨勫竷灏旇〃杈惧紡涓烘瀽鍙栬寖寮� $\bigvee{(\bigwedge{P_i)}}$锛屽叾涓�$P_i$涓虹$i$涓瘑閽ユ帉绠＄粨鐐癸紝杩欑鐗规畩褰㈠紡鐨勫竷灏旇〃杈惧紡涓彧鍖呭惈鈥滀笌鈥濆拰鈥滄垨鈥濓紝鍥犳鏄崟璋冪殑甯冨皵琛ㄨ揪寮忥紝鎴戜滑鍙互鏍规嵁璇ュ竷灏旇〃杈惧紡鏋勯€犱竴涓簩鍙夋爲缁撴瀯锛屽叾鍙跺瓙缁撶偣涓鸿〃杈惧紡涓殑鍏ㄩ儴$P_i$锛岄潪鍙跺瓙缁撶偣涓轰袱涓瓙鏍戝搴旇〃杈惧紡涔嬮棿鐨勨€滀笌鈥濇垨鑰呪€滄垨鈥濓紝鏈€鍚庝粠鏍戠殑鏍圭粨鐐瑰嚭鍙戝嵆鍙繕鍘熸暣涓竷灏旇〃杈惧紡銆�

(2) 瀵逛笂闈㈠緱鍒扮殑浜屽弶鏍戜娇鐢‵olklore绠楁硶锛岃缁嗚繃绋嬪涓�:  
		a. 涓烘牴缁撶偣璧嬪€�$m_1=(1)$锛屼护count=1锛�  
		b. 瀵硅〃杈惧紡褰㈡垚鐨勬爲涓婄殑姣忎釜缁撶偣n鎵ц濡備笅鎿嶄綔锛�  
			鑻ョ粨鐐筺瀵瑰簲鈥滄垨鈥濓紝鍒欏皢缁撶偣n鐨勫€糾璧嬬粰宸﹀彸瀛╁瓙锛�  
	        鑻ョ粨鐐筺瀵瑰簲鈥滀笌鈥濓紝鍒欏湪m鐨勬湯灏捐ˉ0锛屼娇寰梞鐨勯暱搴︾瓑浜巆ount锛岀劧鍚庡湪m鐨勫悗闈㈣ˉ涓€涓�1骞跺皢鍏惰祴鍊肩粰宸﹀瀛愶紝鏈€鍚庡皢闀夸负count+1鐨勫悜閲�$(0,0,\ldots,0,-1)$璧嬬粰鍙冲瀛愶紝骞朵护count=count+1锛�  
        c. 鍙栧嚭鎵€鏈夊彾瀛愮粨鐐圭殑鍊硷紝骞跺湪杩欎簺鍊煎悗闈㈣ˉ0浣垮緱浠栦滑鐨勯暱搴︾浉鍚屻€�

(3) 瀵瑰皢寰楀埌鐨勬墍鏈夊彾瀛愮粨鐐圭殑鍊兼寜鐓ч『搴忔帓鎴愪竴鍒楋紝鏋勬垚涓€涓�$t\cdot C_u^t\ \times\ \left(t-1\right)\cdot C_u^t+1$鐨勭煩闃碉紝璇ョ煩闃靛嵆涓虹瀵嗗垎浜煩闃礛銆�  
(4) 涓轰簡寰楀埌绉侀挜k瀵瑰簲鐨勬瘡涓瘑閽ユ帉绠＄粨鐐圭殑绉樺瘑浠介锛岄鍏堝湪$Z_p$涓婃寜鐓х鏁ｉ珮鏂垎甯冮噰鏍峰緱鍒伴殢鏈烘暟$r_2,r_3,\ldots,r_n$锛岀劧鍚庡畾涔夊悜閲�$w=M\cdot\left(k,r_2,r_3,\ldots,r_n\right)^T$锛屾鏃堕暱涓�$t\cdot C_u^t$鐨勫垪鍚戦噺w涓殑姣忎釜鏁板瓧鍗充负瀵瑰簲瀵嗛挜鎺岀缁撶偣$P_i$鍦ㄨ繘琛岀瀵嗗垎浜椂鐨勪竴涓瀵嗕唤棰濄€�

## 鎶楅噺瀛愬鏂归棬闄愬姞瀵嗘柟妗�
闀垮畨閾剧殑鎶楅噺瀛愬鏂归棬闄愬姞瀵嗘柟妗堝熀浜嶯TRU鍔犲瘑绠楁硶[2]鏋勯€狅紝鏂规鍖呭惈浠ヤ笅涓変釜鍏叡鍙傛暟锛氭鏁存暟$N$锛屽搴斿椤瑰紡鐨勬鏁帮紱澶фā鏁�$q$鍜屽皬妯℃暟$p$锛屾弧瓒�$\left(q,p\right)=1$锛屼笖$q\gg p$锛屽湪鏂规涓垜浠彇$p=3$銆傛澶栵紝鎴戜滑杩橀渶瑕佸畾涔夊椤瑰紡鐜�$\mathcal{R}=Z\left[x\right]/(X^N-1)$銆�

鎶楅噺瀛愬鏂归棬闄愬姞瀵嗘柟妗堢殑**瀵嗛挜鐢熸垚**杩囩▼濡備笅锛�
  1. 棣栧厛浠诲彇澶氶」寮�$F,G$锛屾弧瓒�$F,G$鐨勭郴鏁板潎灞炰簬${-1,0,1}$锛�
  2. 浠�$f\ =\ 1+pF$, 濡傛灉$f$鍦ㄥ椤瑰紡鐜�$\mathcal{R}_q$涓婁笉鍙€嗭紝鍒欓噸鏂伴€夋嫨澶氶」寮�
  3. 浠�$g=pG$锛屽畾涔�$h=f^{-1}g\ mod\ q$
  4. 瀵逛簬锛坱-n锛夐棬闄愶紝鎸夌嚎鎬х瀵嗗垎浜柟妗堟瀯閫犵瀵嗗垎浜煩闃祍hareMatrix锛屽垵濮嬩竴鏉￠暱搴︿负shareMatrix鍒楁暟鐨勫悜閲弅锛岃缃�$k\left[0\right]=f$锛屽叾浣欏垎閲忔寜姝ラ锛�1锛夈€侊紙2锛夛紝鐢熸垚$f_1,f_2,\ldots$锛屽苟璁剧疆$k\left[1\right]=f_1,k\left[2\right]=f_2,...$
  5. 浠�$keys\ =\ shareMatrix\ \cdot k$锛屽皢$keys$鍚勫垎閲忓垎缁欏悇鍙備笌鏂�
  6. 杈撳嚭鍏挜涓�$h$锛岀閽ヤ唤棰�$keys$

鎶楅噺瀛愬鏂归棬闄愬姞瀵嗘柟妗堢殑**鍔犲瘑**杩囩▼濡備笅锛�
  1. 浠诲彇闅忔満澶氶」寮�$r$锛�
  2. 瀵逛簬鏄庢枃娑堟伅$m$锛岃绠楀瘑鏂�$y=r\ast h+m\ (mod\ q)$銆�

**閮ㄥ垎瑙ｅ瘑**杩囩▼濡備笅锛�
  1. 闂ㄩ檺鍊紅涓弬涓庢柟杩涜瑙ｅ瘑
  2. 鍚勪釜鍙備笌鏂硅绠�$a_i=f_i\ast y\left(mod\ q\right)$

**鏈€缁堣В瀵�**杩囩▼濡備笅锛�
  1. 璁＄畻$a\ =\ \sum a_i\left(mod\ q\right)$
  2. 鏄庢枃$m=\ a(mod\ p)$



## 鍑芥暟璇存槑

### 鐩稿叧缁撴瀯浣�

#### PublicKey 

```
type PublicKey struct {
	H *poly.Polynomial
}
```

PublicKey缁撴瀯浣撳瓨鍌ㄥ叕閽ヤ俊鎭紝H涓哄叕閽ュ椤瑰紡

#### PrivateKey

```
type PrivateKey struct {
	PublicKey   
       F         *poly.Polynomial
}
```

PrivateKey 缁撴瀯浣撳瓨鍌ㄧ閽ヤ俊鎭紝鍖呮嫭鍖归厤鐨勫叕閽ャ€佺閽ュ搴斿椤瑰紡銆�

### 鐩稿叧鍑芥暟

#### Public

```
func (priv *PrivateKey) Public() *PublicKey
```

绉侀挜鑾峰彇瀵瑰簲鍏挜銆�

#### Encrypt

```
func (pub *PublicKey) Encrypt(rand io.Reader, plain *poly.Polynomial) (cipher *poly.Polynomial, err error)
```

鍏挜鍔犲瘑鍘熷椤瑰紡锛岀敓鎴愬姞瀵嗗椤瑰紡锛宺and 涓洪殢鏈烘簮锛宲lain 涓哄師澶氶」寮忥紝cipher 涓哄姞瀵嗗悗鐨勫椤瑰紡銆�


#### Decrypt

```
func (priv *PrivateKey) Decrypt(cipher*poly.Polynomial) (plain *poly.Polynomial)
```

浣跨敤绉侀挜瀵瑰姞瀵嗗椤瑰紡杩涜瑙ｅ瘑銆俢ipher 涓哄姞瀵嗗椤瑰紡锛宲lain 涓鸿В瀵嗗悗鐨勫椤瑰紡銆�

#### GenerateKey

```
func GenerateKey(rand io.Reader) (privateKey *PrivateKey, err error)
```

鏍规嵁闅忔満婧愮敓鎴愬叕绉侀挜瀵癸紝rand 涓洪殢鏈烘簮锛宲rivateKey 涓虹敓鎴愮殑绉侀挜锛屽唴鍖呭惈鍏挜

#### GenerateThresholdKey

```
GenerateThresholdKey(rand io.Reader, threshold, total int64) (privateKeys []*PrivateKey, err error)
```

鐢熸垚闂ㄩ檺绠楁硶绉樺瘑鍒嗕韩鐨勫涓叕绉侀挜瀵癸紝rand 涓洪殢鏈烘簮锛宼hreshold 涓洪棬闄愬€硷紝total 涓虹敓鎴愮殑鎬诲瘑閽ユ暟閲忥紝privateKeys 涓虹敓鎴愮殑澶氫釜瀵嗛挜


## 姝ｇ‘鎬ч獙璇�

鍦� ntru_test.go 鏂囦欢涓瀵嗛挜鐢熸垚銆佸姞瀵嗐€佽В瀵嗚繘琛屼簡姝ｇ‘鎬ч獙璇併€�



## 鍙傝€冩枃鐚�

[1] Boneh D, Gennaro R, Goldfeder S, et al. Threshold cryptosystems from threshold fully homomorphic encryption[C]//Annual International Cryptology Conference. Springer, Cham, 2018: 565-596.  
[2] Hoffstein J, Pipher J, Silverman J H. NTRU: A ring-based public key cryptosystem[C]//International algorithmic number theory symposium. Springer, Berlin, Heidelberg, 1998: 267-288.