Với câu hỏi này, tôi đang đề cập đến phép nhân BGW của Gennaro et al (PDF đây).
Phép nhân được mô tả ở trang thứ 4.
(Một nguồn khác cho tôi là "Giới thiệu thực tế về tính toán đa bên an toàn" P. 43-44)
Tóm tắt quy trình nhân BGW:
Để thực hiện phép nhân 2 giá trị bí mật $\alpha$ và $\beta$ của mọi người chơi $P_i$ phải có phần $f_{\alpha}(i)$ và $f_{\beta}(i)$ ở đâu $f_{\alpha}$ và $f_{\beta}$ là các đa thức bậc t ngẫu nhiên từ chia sẻ bí mật Shamir.
Bây giờ mọi người chơi $P_i$ tính toán $f_{\alpha}(i) \cdot f_{\beta}$ và gửi cổ phiếu có giá trị này $h_i(j)$ được tạo với đa thức bậc t ngẫu nhiên $h_i$ (để có thể $h_i(0) = (f_{\alpha} \cdot f_{\beta})(i)$) cho người chơi $P_j$ vì $1 \le j \le n$.
Tiếp theo, bài viết ở trên mô tả cách người chơi có thể nhận được mức độ ngẫu nhiên t cổ phần của giá trị $\alpha \cdot \beta$ (để sau đó họ có thể xây dựng lại kết quả của phép nhân với những chia sẻ này):
mọi người chơi $P_i$ tính giá trị $H(i)$ từ đa thức bậc t $H$ được định nghĩa là:
$$H(x) = \sum_{i=1}^{n} \lambda_i h_i(x)$$
($the \lambda_i$s là các hệ số Lagrange thích hợp).
$H$ là một đa thức ngẫu nhiên với
$$H(0) = \sum_{i=1}^{n} \lambda_i h_i(0) = \sum_{i=1}^{n} \lambda_i (f_{\alpha} \cdot f_{\beta })(i) = (f_{\alpha} \cdot f_{\beta})(0) = \alpha \cdot \beta$$
Câu hỏi của tôi: H(x) có thực sự cấp t không? Nó không thể lớn hơn bởi vì $n$ điểm từ khác biệt đa thức bậc t $h_i$ vì $1 \le i \le n$ được sử dụng để nội suy? Thông thường người ta lập luận rằng các hoạt động tuyến tính trên $(t,n)$ chia sẻ chia sẻ dẫn đến mới $(t,n)$ chia sẻ và bởi vì $h_i$ chức năng có mức độ $t$ tổ hợp tuyến tính của các giá trị $h_i{j}$ vì $1 \le i \le i$ nên dẫn đến $(t,n)$ cổ phiếu là tốt. Điều này cũng đúng trong trường hợp này, vì chúng tôi luôn kết hợp các giá trị từ các mức độ khác nhau $t$ đa thức đồng dạng $x$ giá trị?
Câu hỏi khác: Người ta cũng lưu ý rằng $t$ phải như vậy mà $2t+1 \le n$. Điều này có thực sự cần thiết? sẽ không $t+1 \le n$ đủ vì $H(x)$ là bằng cấp $t$ dù sao đi nữa hoặc là thông tin từ các cổ phiếu 2t+1 cần thiết để xây dựng chính xác $H(x)$? (Giả thuyết của tôi là, nếu không có $2t+1$ hệ số lagrange $\lambda_i$, $H(0)$ sẽ không được $\alpha \cdot \beta$)
Phần "Giới thiệu thực dụng" tr. 44 nói rằng chỉ với $2t+1 \le n$ người chơi có đủ thông tin để xác định giá trị $(f_{\alpha} \cdot f_{\beta})(0)$. Tại sao điều này là trường hợp?