Đầu tiên, phép loại suy tung đồng xu của bạn đồng thời
- đúng, và
- không liên quan về mật mã.
Tôi sẽ giải thích ngắn gọn lý do bằng cách đưa ra một tuyên bố chính thức về kết quả tung đồng xu.
Sau đó, tôi sẽ cố gắng trả lời câu trả lời chia sẻ bí mật, câu trả lời tương tự có câu trả lời tương đối đơn giản (tiêu cực).
Để cho $p\in[0,1]$ được tùy tiện. Sau đó, tồn tại một thủ tục để lấy mẫu từ một $\mathsf{Bern}(p)$ Sử dụng $\leq H(p)+2$ coinflips nhị phân Trong kỳ vọng, ở đâu $H(x)$ là hàm entropy nhị phân.
Đây là từ việc hấp dẫn "Lấy mẫu Knuth-Yao" (ít nhất là để có được một giới hạn $H(p) + 2$).
Tương đối khó để theo dõi bài báo ban đầu về điều này, nhưng iirc nằm trong một số tác phẩm được sưu tầm của Knuth.
Phần quan trọng nhất của định lý nói trên là Trong kỳ vọng bản tường trình.
Trong khi người ta hoàn toàn có thể lấy mẫu một $\mathsf{Bern}(p)$, một không thể mẫu hoàn hảo từ phân phối này nếu có một số trường hợp xấu nhất giới hạn trên của số lần lật đồng xu được sử dụng.
Người ta có thể lấy mẫu từ một xấp xỉ cực kỳ tốt (hợp lý) để $\mathsf{Bern}(p)$, nhưng bạn đã đề cập rằng đây không phải là điều bạn muốn.
Điều này có quan trọng không?
Câu trả lời là có --- nếu số lượng coinflips mà một người sử dụng có thể thay đổi, thì (về nguyên tắc) nó có thể mở ra một kênh phụ.
Cụ thể, ai đó có thể quan sát xem có bao nhiêu lần lật đồng xu đã được sử dụng để lấy mẫu $\mathsf{Bern}(p)$ có thể khám phá thông tin không tầm thường về kết quả sau đó $\mathsf{Bern}(p)$, có thể phá vỡ bảo mật.
Điều này thật tệ và tại sao mọi người thường lấy mẫu từ một (chất lượng cao) xấp xỉ của một số phân phối mong muốn, thay vì lấy mẫu chính xác từ một số phân phối.
Còn về chia sẻ bí mật, câu trả lời là không.
Lý do đơn giản nhất là vì lý do "nhàm chán", mặc dù tôi sẽ suy đoán một chút về những lý do thú vị hơn tại sao câu trả lời có thể là "không".
Sơ đồ chia sẻ bí mật được tham số hóa chính thức bằng hai số
- $t$, ngưỡng tái cấu trúc chia sẻ và
- $n$, tổng số cổ phần.
Đôi khi có tham số thứ ba (đối với một khái niệm nhất định về chia sẻ bí mật "gần đúng"), nhưng tôi sẽ không trình bày vấn đề này ở đây.
Dù sao, một $(t,n)$lược đồ chia sẻ bí mật được tham số hóa bởi hai số tự nhiên thông số $(t, n)$.
Sau đó, phần cần thiết để tái thiết nếu $\frac{t}{n}$, đó là (tầm thường) một ngưỡng hợp lý.
Như $t, n$ luôn được cho dưới dạng các số tự nhiên thì việc thực hiện ý tưởng của bạn gặp trở ngại đáng kể.
Tuy nhiên, điều này hơi nhàm chán vì nó chỉ nói rằng định nghĩa hiện tại về chia sẻ bí mật ngăn cản ý tưởng của bạn hoạt động.
Đối với một lý do thú vị hơn, số thực làm không phải trộn đều với tính toán.
Để hiểu tại sao, tôi sẽ nói ngắn gọn về mã hóa.
Một mã hóa là một chức năng tiêm $\phi : A\đến B$.
Chúng tôi muốn mã hóa những thứ khác nhau để dẫn đến các mã hóa khác nhau, tức là $a\neq b\ngụ ý \phi(a)\neq\phi(b)$, đó là ý nghĩa của "tiêm".
Dù sao thì
Để cho $X$ là một tập hợp hữu hạn. Sau đó, cho bất kỳ bộ nào khác $A$, bất kỳ mã hóa nào $\phi : A\đến X$ có $|A|\geq |X|$.
Điều này thường được gọi là "nguyên tắc Pidgeonhole".
Dù sao đi nữa, kết quả này có thể được coi là nói rằng nếu chúng ta muốn mã hóa của mình thành một tập hợp hữu hạn nào đó $X$, chúng ta chỉ có thể có nhiều "thứ để mã hóa" hữu hạn $A$.
Điều này có nghĩa là nếu vì lý do nào đó, chúng ta sử dụng các số vô tỷ $\alpha$ trong mã hóa của chúng tôi, chúng tôi chỉ có thể xem xét hữu hạn nhiều cái riêng biệt.
Khi một người đưa ra hạn chế này, không rõ mọi thứ khác với tình huống tiêu chuẩn như thế nào (nhiều cặp số tự nhiên hữu hạn, tức là số hữu tỷ).
Tại sao chúng ta muốn $X$ là hữu hạn?
Vì lý do tương tự tại sao chúng tôi không thể lấy mẫu chính xác từ $\mathsf{Bern}(p)$.
Nếu $X$ là vô hạn, thì độ dài của mỗi thứ được mã hóa $\varphi(x)$ sẽ phải là
- "độ dài vô hạn" (nghĩa là không thể sử dụng trên máy tính thực tế) hoặc
- chiều dài thay đổi.
Nhưng nếu mã hóa có độ dài thay đổi, nó sẽ làm rò rỉ thông tin về những gì đã được mã hóa, điều này không phù hợp với mật mã.
