Điểm:2

Ai đó có thể giải thích bằng chứng của Rabin và Ben-or về tính toán đa bên an toàn không?

lá cờ ua

Ai có thể giải thích bằng chứng của Rabin và Ben-or của tính toán đa bên an toàn?

Ý tưởng là mọi người chơi $i$, của $N<+\infty$ người chơi, giữ một bí mật nói $s_i$. Tất cả họ đều muốn chia sẻ thông tin của mình theo cách mà một quy tắc hoạt động $f(s_1,s_2,\cdots,s_N)=(a_1,a_2,...a_N)$ được định hình và mọi người chơi ở cuối giao thức sẽ chỉ biết thành phần của riêng mình $a_i$ và không có thông tin nào khác.

  • Giao thức của Rabin và Ben-or được thực hiện từng bước như thế nào? Ai có thể giải thích các thủ tục?
  • Các tác giả có sử dụng hoán vị không? Nếu không, chúng tôi có thể cung cấp một bằng chứng khác về một giao thức như vậy với các hoán vị không? nói cách khác những chức năng này là gì $f$ giống như các thông điệp được mã hóa đầu vào của việc chia sẻ bí mật giữa những người chơi và có thể tính toán đầu ra $a$ đó có thể là một hồ sơ đề xuất hành động ngẫu nhiên, trong đó mọi người chơi $i$ học $a_i$?

Ok, hãy để tôi cung cấp thêm chi tiết từ giao thức với định nghĩa sau

$\textbf{Định nghĩa:}$ một nhóm $N$ người chơi nắm giữ một bí mật đã được xác minh (dữ liệu) $s$, được chia sẻ bằng cách sử dụng đa thức $f(x)$, để có thể $f(0)=s$, và đáp ứng các điều kiện của BHXHVN nếu:

  • đa thức $f(x)$ có bằng cấp $t$
  • Mỗi người chơi, $P_i$, nắm giữ một phần bí mật $b_i=f(a_i)$
  • Mỗi mảnh $b_i$ đã được chia sẻ bởi $P_i$, sử dụng WSS

Trong trường hợp có hòa giải viên, điều này rất dễ chỉ ra, nhưng khi không có hòa giải viên thì vấn đề trở nên phức tạp và thách thức. Theo quan điểm của tôi, tôi hiểu rằng điều đầu tiên tôi muốn làm là chứng minh rằng bí mật có thể kiểm chứng được. Nhưng điều gì xảy ra khi bí mật mà mọi người chơi nắm giữ là thông tin riêng tư mà người chơi biết trước khi họ bắt đầu trao đổi thông tin? Cụ thể, mỗi người chơi đều có một bí mật riêng $s_i$ và nếu tất cả họ chia sẻ bí mật của mình với một sơ đồ cụ thể, thì họ sẽ tạo ra một chức năng quy tắc sẽ lấy các tín hiệu riêng lẻ làm đầu vào và cung cấp cho họ thông tin "mới" đầu ra mà họ sẽ sử dụng để thực hiện một hành động trong trò chơi. có thể khác nhau đối với trường hợp không có giao tiếp nào tồn tại. Vì vậy, để tạo ra chức năng này $f$ Tôi cần phải chứng minh rằng những bí mật cá nhân $s_i$ đó là các thành phần của dữ liệu bí mật $s=(s_1,s_2,...,s_N)$ tuân theo một sơ đồ chia sẻ bí mật có thể kiểm chứng được và đồng thời, giao thức gốc được ưu đãi với việc bổ sung và nhân lên bí mật có thể kiểm chứng này. Dựa trên giao thức của Rabin và Ben-hoặc làm thế nào tôi có thể thực hiện việc này?

Ngoài ra, tôi có thể sử dụng giao thức của Dodis và cộng sự (2000) thay vì giao thức Rabin và Ben-or để hiển thị sơ đồ chia sẻ bí mật có thể kiểm chứng cho nhiều hơn hai người chơi?

Daniel avatar
lá cờ ru
Sẽ rất hữu ích nếu bạn cung cấp một chút chi tiết về các phần cụ thể của giao thức mà bạn không hiểu.
Hunger Learn avatar
lá cờ ua
@Daniel Tôi đề cập đến trường hợp tính toán đa bên nhưng tôi sẽ thêm một số phần vào văn bản chính
Điểm:2
lá cờ ru

Thành thật mà nói, tôi không quen thuộc 100% với cách trình bày ban đầu trong RB89, nhưng họ đã giới thiệu một số kỹ thuật đã được sử dụng trong nhiều bài báo tiếp theo và ngày nay có một loại phiên bản đơn giản hóa (theo thuật ngữ hiện đại) của bí mật mạnh mẽ -chương trình chia sẻ ở đó. Ví dụ: bạn có thể tìm thấy mô tả cấp cao ở trang 3 đây.

Tóm lại mục đích là lấy bí $s\in\mathbb{F}$ và phân phối nó giữa $n$ tiệc tùng $P_1,\ldots,P_n$ để sau này, các bên có thể tái tạo lại bí mật này cho nhau, đồng thời đảm bảo rằng ngay cả khi một số $t$ đảng tham nhũng với $t<n/2$ gửi các giá trị không chính xác, các bên trung thực (tức là không bị hỏng) vẫn có thể lấy được bí mật cơ bản. Điều này đạt được như sau:

  • Người chia bài sử dụng chia sẻ bí mật Shamir truyền thống để lấy phần bí mật $(s_1,\ldots,s_n)$. Nếu $t<n/2$, thì những chia sẻ này cung cấp phát hiện lỗi, có nghĩa là một bên nhận được những cổ phiếu này, trong đó $t$ trong số chúng có thể bị sửa đổi do hành vi đối nghịch, có thể tìm ra bí mật có bị giả mạo hay không, nhưng trong trường hợp có sai sót, bên được cho không thể "sửa chúng" để tạo lại bí mật chính xác. Điều này là không đủ để chia sẻ bí mật mạnh mẽ.

  • Các đại lý lấy mẫu các cặp ngẫu nhiên thống nhất $(\alpha_{ij},\beta_{ij})\in\mathbb{F}^2$ và tính toán $\tau_{ji} = \alpha_{ij}\cdot s_j + \beta_{ij}$ cho mỗi cặp $i,j\in[n]$ (đây $[n] = \{1,\ldots,n\}$). Như chúng ta sẽ thấy, mục tiêu của dữ liệu bổ sung này là để đảm bảo rằng bên nhận không chỉ có thể phát hiện xem các chia sẻ có bị giả mạo hay không mà còn thực sự nhận dạng những cái không chính xác, do đó lọc ra những cái đúng, dẫn đến bí mật đúng được xây dựng lại.

  • Đại lý gửi $\sigma_i = (s_i, \{(\alpha_{ij},\beta_{ij})\}_{j\in[n]}, \{\tau_{ij}\}_{j\in[n ]})$ cho mỗi bên $P_i$. Nói cách khác: mỗi $P_i$ nhận được một phần $s_i$ cộng với một cặp chìa khóa $(\alpha_{ij},\beta_{ij})$ cho nhau. Thêm vao Đoa, $P_i$ nhận được một "phiên bản xác thực của $s_i$" bằng cách sử dụng các khóa của bên kia.

Hãy nói rằng một bữa tiệc $P_j$ được cho là để tìm hiểu bí mật. Để đạt được điều này, các bên $P_i$$i\in[n]\setminus\{j\}$ gửi $P_j$ giá trị của họ $(s_i',\tau_{ij}')$ (nếu $P_i$ là trung thực, sau đó $s_i' = s_i$$\tau_{ij}' = \tau_{ij}$, nhưng một bên tham nhũng có thể gửi các giá trị không chính xác), và $P_j$ kiểm tra, sử dụng chìa khóa riêng của mình $(\alpha_{ji},\beta_{ji})$, điều đó $\tau_{ij}' = \alpha_{ji}\cdot s_i' + \beta_{ji}$.

Như một bài tập, người ta có thể kiểm tra xem nếu $s_i'\neq s_i$, thì xác suất mà phương trình này đúng là nhiều nhất $1/|\mathbb{F}|$ (điều này tận dụng thực tế là $P_i$ không biết chìa khóa $(\alpha_{ji}, \beta_{ji})$, là ngẫu nhiên), vì vậy, miễn là trường đủ lớn, $P_j$ sẽ có thể lọc ra những chia sẻ sai và do đó xây dựng lại bí mật từ những chia sẻ đúng còn lại.


Điều này bằng cách nào đó giúp bạn với những câu hỏi cụ thể mà bạn có? Vui lòng gửi bất kỳ nhận xét nào nếu bạn cần làm rõ theo hướng nhất định.

Hunger Learn avatar
lá cờ ua
Vì vậy, nói cách khác, toàn bộ công việc được thực hiện bởi các đại lý. Anh ta là người cung cấp thông tin cho các tác nhân trong một sơ đồ được gọi là sơ đồ xác thực và họ cần trao đổi một số tin nhắn giữa họ để lấy tất cả các phần của tin nhắn riêng lẻ của họ và mã hóa nó bằng một số loại thủ tục... ?
Daniel avatar
lá cờ ru
Trong RB89, một kế hoạch Chia sẻ bí mật mạnh mẽ được đề xuất: Có một đại lý có $s$ bí mật, người này phân phối nó cho một nhóm các bên theo một cách nhất định.Sau đó, có một nhà tái cấu trúc muốn tìm hiểu bí mật này, vì vậy các bên đã gửi một số thông tin cho nhà tái tạo này. Đó là những gì được mô tả trong RB89.
Hunger Learn avatar
lá cờ ua
Ok, tôi hiểu điều này bây giờ. Nhưng, ý tưởng của tôi là như sau. Giả sử rằng mọi người chơi đều nắm giữ bí mật của riêng mình, đó là một loại thông tin riêng tư nào đó. Tất cả bọn họ, hãy nghĩ ra một cách nào đó để trao đổi những bí mật riêng tư của mình với những người còn lại trong bảng để sao chép chức năng quy tắc $f$. Vì vậy, theo quan điểm của tôi, mọi người chơi đều có thể là người chia bài và những người chơi khác có thể là người nhận thông báo theo một cách nhất định do RB89 đề xuất. Nhưng vai trò của người tái cấu trúc, bên này khác bên kia như thế nào?
Hunger Learn avatar
lá cờ ua
@Daniel đâu đó trong công thức mà bạn viết, đó là $\tau_{ji}=\alpha_{i,j}\cdot s_j+\beta_{i,j}$, nên có một thuật ngữ modulo $n$ (mod $n $) phải không?
Daniel avatar
lá cờ ru
@HungerLearn Không thực sự. Có một sự rút gọn mô-đun xảy ra bên trong, nhưng nó ẩn chứa một thực tế là các phần tử được chiếm lấy trường $\mathbb{F}$. Ví dụ, trường hữu hạn này có thể là các số nguyên modulo một số nguyên tố $p$ (nhưng chắc chắn không phải modulo $n$, vì $n$ đã được sử dụng để biểu thị số lượng cổ phần/các bên).
Hunger Learn avatar
lá cờ ua
@Daniel bạn nói đúng. Vậy p nguyên tố này biểu thị lực lượng của trường?
Daniel avatar
lá cờ ru
@HungerLearn Vâng, có các trường hữu hạn khác (trường mở rộng), nhưng trong trường hợp $\mathbb{F}$ biểu thị tập hợp các số nguyên modulo một số nguyên tố $p$, thì số lượng của trường kết quả sẽ là $p$.
Hunger Learn avatar
lá cờ ua
vì vậy bạn có thể viết $\tau_{ij}=\alpha_{ij}\cdot s_i+\beta_{ij} mod p$? Và câu hỏi cuối cùng.... các giao thức hoặc Rabin Ben-or và Ben-or et al là các giao thức mà bạn có thể xây dựng bất kỳ hàm quy tắc nào là phép cộng hoặc phép nhân của các bí mật. Nói cách khác, nếu bạn xác định một trường với các toán tử cộng và nhân, bạn có một cấu trúc đại số được xác định rõ ràng để xây dựng bất kỳ hàm nào bạn muốn. Chức năng này có thể là xác định hoặc xác suất phải không?
Hunger Learn avatar
lá cờ ua
@KingOdysseus xin lỗi vì mớ bình luận lộn xộn này trong câu hỏi của bạn... sẽ tốt hơn nếu làm một câu hỏi mới của tôi...
Daniel avatar
lá cờ ru
@HungerLearn Có, bạn có thể sử dụng ký hiệu mô-đun. Bạn có thể xác định bất kỳ hàm nào (xác định hoặc xác suất) sử dụng phép cộng và phép nhân trên một trường và sử dụng các giao thức MPC hiện có (chẳng hạn như BGW) để tính toán các hàm này một cách an toàn.
Hunger Learn avatar
lá cờ ua
Họ có mặc nhiên cho rằng họ làm việc với các nhóm abelian không?
Daniel avatar
lá cờ ru
Hãy để chúng tôi [tiếp tục cuộc thảo luận này trong cuộc trò chuyện](https://chat.stackexchange.com/rooms/132553/discussion-between-daniel-and-hunger-learn).

Đă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.