Điểm:4

Phép nhân BGW của Gennaro và cộng sự: Tại sao H(x) có chính xác bậc t và tại sao $2t + 1 \le n$ lại cần thiết?

lá cờ jp

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$$\beta$ của mọi người chơi $P_i$ phải có phần $f_{\alpha}(i)$$f_{\beta}(i)$ ở đâu $f_{\alpha}$$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$$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$$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}$$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?

Daniel S avatar
lá cờ ru
Chào mừng đến với cryptoSE! Tôi nghĩ ý của bạn là $2t+1\le n$ chứ không phải $2t+1
lá cờ jp
Cảm ơn bạn đã chỉ ra rằng. Đó chính xác là những gì tôi muốn nói.
Điểm:1
lá cờ ru

Đối với câu hỏi đầu tiên của bạn: $H(x)$ tối đa là bằng cấp $t$ miễn là người chơi tạo ra $h_i$ bằng cấp $t$. Các $\lambda_i$ là các hằng số và do đó nó là tổ hợp tuyến tính của các đa thức bậc $t$ và như vậy là của mức độ nhiều nhất $t$.

Đối với câu hỏi thứ hai của bạn: vâng, nó là cần thiết. Khi nhân cổ phiếu, nhóm xây dựng một cách giả định một mức độ $2t$ sản phẩm đa thức $q(x)=f_\alpha(x)\cdot f_\beta(x)$ với $2t+1$ hệ số. Người chơi $i$ biết giá trị của đa thức danh nghĩa này $q(i)$, và chúng tôi biết $q(0)$ có thể viết dưới dạng tổ hợp tuyến tính của $n$ trong số này bằng cách hủy bỏ sự đóng góp của các hệ số bậc cao hơn. Cụ thể, chúng tôi giải quyết hệ thống sau đây cho $\{\lambda_i:1\le i\le n\}$ $$\left(\begin{matrix} n^{2t} & (n-1)^{2t} & (n-2)^{2t} & \ldots & 2^{2t} & 1\ n^{2t-1} & (n-1)^{2t-1} & (n-2)^{2t-1} & \ldots & 2^{2t-1}& 1\ n^{2t-2} & (n-1)^{2t-2} & (n-2)^{2t-2} & \ldots & 2^{2t-2}& 1\ \vdots & \vdots & \vdots & \ddots & \vdots\ n & (n-1) & (n-2) & \ldots & 2 & 1\ 1 & 1 & 1 & \ldots & 1 & 1\ \end{ma trận}\right)\left(\begin{ma trận} \lambda_{n}\lambda_{n-1}\lambda_{n-2}\vdots\lambda_2\lambda_1\end{matrix}\right)= \left(\begin{matrix} 0\0\0\vdots\0\1\end{matrix}\right) $$ và suy ra rằng đối với $\lambda_i$ rằng chúng tôi phục hồi $\sum_i\lambda_iq(i)=q(0)$. Để có thể hòa tan, hệ thống này cần có ít nhất số cột bằng số hàng sao cho $n\ge 2t+1$. Lưu ý rằng chúng ta có thể chỉ định $n-(2t+1)$ sau đó $\lambda_i$ bằng 0 và vẫn có một hệ thống giải được. Bằng cách lôi kéo người chơi với $\lambda_i\neq 0$ hành động như các đại lý để chia sẻ $q(i)$ sử dụng bằng cấp $t$ đa thức $h_i(x)$, nhóm có thể xây dựng trên lý thuyết $H(x)=\sum\lambda_ih_i(x)$ đó là bằng cấp $t$ đa thức với $H(0)=q(0)=f_\alpha\cdot f_\beta(0)$.

lá cờ jp
Cảm ơn bạn rất nhiều vì câu trả lời hữu ích của bạn. Tôi có hiểu đúng không khi hằng số $\lambda_i$ bằng đa thức cơ sở Lagrange $\delta_i(0) = \prod_{j=1;j \ne i}^{n} \frac{0 - j }{i - j} = \prod_{j=1;j \ne i} \frac{-j}{i-j}$ hay nó được định nghĩa khác?
Daniel S avatar
lá cờ ru
Có, hai công thức là tương đương nhau. Điều này có thể được chứng minh bằng cách sử dụng định thức vandermonde.

Đăng câu trả lời

Hầu hết mọi người không hiểu rằng việc đặt nhiều câu hỏi sẽ mở ra cơ hội học hỏi và cải thiện mối quan hệ giữa các cá nhân. Ví dụ, trong các nghiên cứu của Alison, mặc dù mọi người có thể nhớ chính xác có bao nhiêu câu hỏi đã được đặt ra trong các cuộc trò chuyện của họ, nhưng họ không trực giác nhận ra mối liên hệ giữa câu hỏi và sự yêu thích. Qua bốn nghiên cứu, trong đó những người tham gia tự tham gia vào các cuộc trò chuyện hoặc đọc bản ghi lại các cuộc trò chuyện của người khác, mọi người có xu hướng không nhận ra rằng việc đặt câu hỏi sẽ ảnh hưởng—hoặc đã ảnh hưởng—mức độ thân thiện giữa những người đối thoại.