Vấn đề có một "giải pháp dễ dàng" bằng cách sử dụng các kỹ thuật chung.
Có những phần mở rộng của vấn đề Triệu phú của Yao về cách tính toán an toàn bất kỳ mạch nào $C(x, y)$. Đây là toàn bộ lĩnh vực nghiên cứu, thường có tên là "Tính toán an toàn" hoặc "Tính toán nhiều bên".
Tồn tại các mạch có thể sắp xếp các đầu vào theo tên của phân loại mạng. Trong khi có kỹ thuật $O(n \log n)$ (Mạng sắp xếp AKS + Sắp xếp Zigzag), chúng phức tạp về mặt kỹ thuật, với các hằng số không hợp lệ, do đó, trong thực tế hầu như luôn luôn tốt hơn khi sử dụng một $O(n (\log n)^2)$ mạng sắp xếp trong đó có nhiều mạng (giả sử Batcher Odd-Even Mergesort).
Điều này có nghĩa là vấn đề của bạn được giải quyết bằng cách tính toán một mạng sắp xếp (giả sử Hợp nhất số lẻ theo lô) bằng cách sử dụng các kỹ thuật tính toán chung của 2 bên.
Nhìn vào việc triển khai các giao thức MPC, có vẻ như cái này của Đại học Boston bao gồm một bản demo có liên quan. Đặc biệt, họ
- tính tổng hai mảng đầu vào, rồi
- sắp xếp kết quả, sử dụng Bubblesort.
Bạn có thể sử dụng lại một số đoạn mã này, nhưng sẽ cần phải cẩn thận một chút.
Đảm bảo an ninh của MPC là
Giao thức MPC chỉ tiết lộ $C(x,y)$, ví dụ.là tốt như cả hai người tham gia đưa ra đầu vào của họ $x, y$ cho một số bên thứ ba đáng tin cậy $T$, sau đó tính toán $C(x,y)$, và cho họ biết câu trả lời.
Về mặt lý thuyết, bạn có thể lấy mã mẫu ở trên, hoán đổi phần tính tổng các thứ thành một phép nối và tiếp tục. Điều này sẽ dẫn đến một kế hoạch thực tế không an toàn --- được đưa ra $x$ và $C(x,y)$, nó là chuyện nhỏ để phục hồi $y$.
thay vào đó tôi sẽ đề nghị có $C(x,y)$ tính toán (trong biểu diễn được sắp xếp của phép nối $x||y$) một vectơ bit cho biết vị trí các phần tử của mỗi bên sẽ kết thúc.
Điều này vẫn mã hóa tất cả thông tin đặt hàng có liên quan, nhưng ẩn đầu vào của mỗi bên với bên kia (ngoại trừ thông tin đặt hàng "phải bị rò rỉ").
Điều này có thể được thực hiện bởi
- Ánh xạ từng phần tử $t$ của $x$ đến $2t$,
- Ánh xạ từng phần tử $t$ của $y$ đến $2t+1$,
- nối các yếu tố biến đổi này,
- sắp xếp nối,
- lập bản đồ $t\mapsto t\bmod 2$ cuối cùng.
Mạch này tính toán chức năng tôi đã mô tả trước đây và "phá vỡ mối quan hệ" giữa $x$ và $y$ bằng cách đặt phần tử của $y$ sau trong vecto. Sự lựa chọn này là tùy ý.
Tất nhiên, đây là ý tưởng của tôi về một mạch hợp lý $C$ để tính toán mà có thể đạt được mục tiêu của bạn.
Bạn có thể nghĩ rằng nó rò rỉ quá nhiều thông tin và có một số mạch khác mà bạn muốn tính toán.
Bạn vẫn có thể sử dụng các kỹ thuật chung của MPC để thực hiện việc này --- miễn là bạn có thể chỉ định phép tính mà bạn muốn thực hiện.
Trong các nhận xét, bạn đã đề cập đến mong muốn có một phiên bản đa bên của điều này.
Điều này là ngay lập tức từ việc xây dựng ở trên, nhưng dù sao thì tôi cũng sẽ thảo luận về nó một cách rõ ràng.
Để cho $P_0,\dots, P_{k-1}$ là các bên có đầu vào $\vec x_0,\dots, \vec x_{k-1}$.
Xác định một mạch $C(x_0,\dots, x_{k-1})$ điều đó
- cho mỗi $i$, áp dụng chức năng $t\mapsto kt + i$ đến từng tọa độ của $x_i$,
- nối tất cả các kết quả lại với nhau
- sắp xếp kết quả, ví dụ với mạng phân loại,
- tính toán chức năng $t\mapsto t\bmod k$ trên mỗi phần tử của đầu ra.
Kết quả sẽ là một vectơ có các phần tử trong $\{0,\dots,k-1\}$.
Để đơn giản, nói rằng kết quả là $[0,3,2,2,1,0,1,3]$.
Điều này sẽ cho cả 4 bên biết rằng thứ tự tương đối của đầu vào của họ là
- phần tử nhỏ nhất của bên 0
- phần tử nhỏ nhất của bên 3
- phần tử nhỏ nhất của bên 2
- phần tử lớn nhất của bên 2
- phần tử nhỏ nhất của bên 1
- phần tử lớn nhất của bên 0
- phần tử lớn nhất của bên 1
- phần tử lớn nhất của bên 3.
Nếu một người sử dụng sơ đồ MPC thích hợp (các từ cần tra cứu là "Tính toán nhiều bên bảo mật ác ý"), thì đây có thể được chứng minh là tất cả những gì kẻ thù sẽ học được, điều chỉnh một số giả định kỹ thuật. Các giả định này phụ thuộc vào sơ đồ cụ thể mà bạn sử dụng, nhưng chúng thường giống như
- không có quá nhiều người tham gia giao thức “thông đồng phá giao thức”,
- các đối thủ có hiệu quả về mặt tính toán, và
- có lẽ có một số giai đoạn "thiết lập đáng tin cậy".
