Shamir門限問題廣泛的應用于多方安全計算中，這里簡單的介紹一下Shamir門限的原理
Shamir門限是基于拉格朗日插值法的一種需要多個用戶共同參與才能獲取到秘密的一種方法
1. 門限簡介
假設需要保護的資料為a0，并且要求：
（1）任意t個（或者更多的）分塊可以很容易的重構出D；
（2）任意t-1個（或者更少的）分塊都不可能重構出D，
該項技術可以被稱為(t, n)門限，
2. 一個簡單的(t, n)門限
該門限基于這樣的事實：在一個二維坐標系中給定k個點(x1, y1), ..., (xk, yk)，則滿足q(xi)=yi的多項式有且僅有一個，且最高項系數為k-1，
不妨假設該多項式為q(x) = a[0] + a[1] * x + ... a[t-1] * x(t-1)，且a0為需要保護的秘密，顯然，只要給出任意t對(x, q(x))的值就可以計算出該多項式，從而得出D，
給定整數D，選擇一個大于D和n的素數p，從[0, p)中選擇ai，Di=Di mod p，
以下為該(k, n)門限一些有用的性質：
（1）任意分塊的大小不會超過原始資料的大小；
（2）當t保持不變時，分塊Di可以動態的加入或者洗掉，并且不會影響到其他分塊；
（3）可以改變分塊而不會影響到原始資料，
（4）可以根據重要性設定參與者掌握的分塊數目，
3.實作程序
現有秘密a0，分享者D，參與者（P1,P2,P3，....,Pn)，
分享者隨機選取t-1個亂數，記為a1,a2,,,at-1，構造多項式F(x)=a0+a1*x+a2*x^2+....+at-1* modL(L為素數且L大于a0)
分享者隨機選取N值，分別為x1,x2,....,xn（公開）,計算出f(x1),f(x2),...f(xn),分為n個參與者（只有參與者知道自己的影子秘密），
現在隨機選取t個參與者，將他們的秘密影子和對應的Xi取出，利用拉格朗日插值公式可以恢復F(x)，
因為秘密為a0，令X=0.即可求得秘密，
為什么少于t人就不可以恢復秘密a0？為什么t人就可以恢復秘密a0？
將恢復出來的F(x)用不同的代入（x的值為公開），將a0,a1,...,at-1看成未知數，可以得到一個t個未知數，t個方程的方程組，可以求解，如果有t個未知數，t-1個方程，則不可求解（可以參考線性代數的相關知識），
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/229088.html
標籤：其他
上一篇：到底什么是國土空間規劃？
下一篇：[JT]攻防世界web專項qwq