Các cổ phiếu chia sẻ bí mật Shamir có phải là các số ngẫu nhiên được phân phối đồng đều không?

Để cho $t$ là một ngưỡng trong sơ đồ chia sẻ bí mật Shamir (SSS).

Giả sử chúng ta biết $t'<t$ cổ phiếu. Giả sử chúng ta được cung cấp một số giá trị ngẫu nhiên được chọn thống nhất từ ​​cùng một trường với giá trị được sử dụng trong SSS.

Câu hỏi: chúng ta có thể phân biệt các giá trị ngẫu nhiên với các cổ phiếu có xác suất không đáng kể không?

Mỗi giá trị của độ $t-1$ đa thức SSS đầy đủ $P$ đánh giá ở bất kỳ $x$ trong trường hữu hạn $F$ nó được xác định trên được phân phối đồng đều trong $F$. Nhìn thấy câu trả lời này Ví dụ.

Bây giờ giả sử $tâ<t$ cổ phiếu được tiết lộ, nói rằng họ là $Sâ=\{(x_1,P(x_1)),\ldots,(x_{tâ},P(x_{tâ}))\}.$

Nếu tập hợp cổ phiếu ban đầu là $S$ tập hợp không rỗng $T=S\setminus Sâ$ bây giờ xác định duy nhất theo cách thông thường một đa thức nội suy Lagrange hợp lệ của bậc $t-tâ-1$ đưa ra bất kỳ $t-tâ$ điểm $x$ Trong $K \setminus \{x_1,\ldots,x_{tâ}\}$.

Thuật toán phân biệt: Để cho $k>t-tâ$ và để cho cổ phần tuyên bố $$C=\{(x_j,y_j):1\leq j \leq k\}$$ được cho. Nếu đây là cổ phiếu thật $t-tâ$ của chúng sẽ cho đa thức nội suy Lagrange giống như bất kỳ tập con nào khác có cùng kích thước. Nếu $y_j$ là ngẫu nhiên, hai nội suy Lagrange riêng biệt cho biết hai được hỗ trợ trên $$A=\{x_1,\ldots,x_{t-tâ}\}$$ và hơn thế nữa $$Aâ=\{x_2,\ldots,x_{t-tâ},x_{t-tâ+1}\}$$ sẽ cho khác biệt Đa thức nội suy Lagrange với xác suất $$1-\frac{1}{q}$$ ở đâu $q$ là kích thước của trường chúng tôi đang sử dụng.

Trong thực tế, ngay cả khi chỉ có một cổ phần trong $A \bigcup Aâ$ là ngẫu nhiên, thuộc tính này sẽ đúng vì ít nhất một trong các phép nội suy sẽ mang lại một đa thức ngẫu nhiên.

Giả sử chúng ta biết $t'<t$ cổ phiếu. Giả sử chúng ta được cung cấp một số giá trị ngẫu nhiên được chọn thống nhất từ ​​cùng một trường với giá trị được sử dụng trong SSS.

Câu hỏi: chúng ta có thể phân biệt các giá trị ngẫu nhiên với các cổ phiếu có xác suất không đáng kể không?

Nó phụ thuộc.

Bây giờ, có hai cách có thể để diễn giải câu hỏi của bạn (và mặc dù câu trả lời giống nhau cho cả hai cách, logic hơi khác một chút). Đây là những cách tôi thấy:

• Này $r$ 'giá trị ngẫu nhiên' sẽ được coi ngay lập tức là cổ phần tiềm năng; nghĩa là, đối thủ đã được đưa ra tổng cộng $t' + r$ cổ phiếu, $t'$ trong số đó là cổ phiếu thực sự, và $r$ trong số đó có thể là các giá trị ngẫu nhiên hoặc (đối với đối thủ) cũng có thể là các cổ phiếu thực. Nếu đúng như vậy, hãy làm theo logic dưới đây.

• Này $r$ 'giá trị ngẫu nhiên' là tất cả các khả năng của phần bị thiếu. Đó là, $r-1$ trong số chúng là các giá trị ngẫu nhiên (và đối thủ biết điều đó), giá trị cuối cùng đó cũng có thể là giá trị ngẫu nhiên hoặc có thể là giá trị thực - đối thủ không biết giá trị nào và anh ta cũng không biết giá trị nào có thể là giá trị đích thực. Nếu đúng như vậy, hãy làm theo logic bên dưới, nhưng với $r=1$và lặp lại qua các khả năng khác nhau để chia sẻ trung thực.

Tôi cũng sẽ cho rằng kẻ tấn công có một số kiến ​​thức về bí mật được chia sẻ có thể là gì; anh ta có thể không biết giá trị chính xác, nhưng anh ta có thể biết giá trị đó là một trong một tập hợp nhỏ các khả năng (hoặc ít nhất, biết rằng có một tập hợp lớn các giá trị mà nó không thể).

Trong trường hợp đó, nếu $t' + r < t$, thì đối thủ không thể xác định bất cứ điều gì; tất cả những chia sẻ này trông ngẫu nhiên. Nghĩa là, đối với bất kỳ giá trị nào của chia sẻ đã biết và bất kỳ giá trị nào của bí mật được chia sẻ, có các hệ số khả dĩ đối với đa thức chưa biết sẽ dẫn đến các giá trị được quan sát (và hóa ra là có một số khả năng bằng nhau không phụ thuộc vào các giá trị được quan sát, do đó đối thủ thậm chí không thể nhận được bất kỳ thông tin xác suất nào).

Mặt khác, nếu $t' + r \ge t$, thì đối thủ có cách tiếp cận; anh ta có thể lấy những cổ phiếu mà anh ta có (cả những cổ phiếu tốt đã biết và những cổ phiếu có khả năng dự phòng đáng ngờ), và tái cấu trúc bí mật chung mà chúng ám chỉ; sau đó anh ấy sẽ kiểm tra xem liệu bí mật được chia sẻ đó có khả thi hay không. Nếu đó không phải là một trong những giá trị có thể, thì anh ấy biết rằng một số chia sẻ mà anh ấy sử dụng là không chính xác.

Không, chúng tôi không thể.Chúng tôi biết rằng SSS là hoàn hảo có nghĩa là kiến ​​​​thức về (t-1) hoặc ít cổ phiếu hơn không cung cấp thông tin về s -do đó về các cổ phiếu khác-