chữ

So sánh riêng tư đề cập đến việc có được mối quan hệ tầm cỡ giữa hai bên mà không tiết lộ các giá trị cụ thể của hai bên. Vấn đề triệu phú đầu tiên bắt nguồn từ Yao Zhizhi: Có hai triệu phú muốn so sánh xem ai giàu hơn, nhưng họ không muốn tiết lộ số tiền mình có, làm sao họ có thể so sánh nếu không có bên thứ ba đáng tin cậy? Câu hỏi này đã được Yao Qizhi, người đầu tiên và duy nhất đoạt giải thưởng Turing ở Trung Quốc đưa ra vào những năm 1980. Ông là người đầu tiên trong lĩnh vực giáo dục và khoa học máy tính ở Trung Quốc, đồng thời mở ra một cánh cửa mới cho mật mã hiện đại.

Trong bài viết trước "Tìm việc thanh lịch—Ví dụ về thuật toán so sánh quyền riêng tư", các kịch bản ứng dụng so sánh quyền riêng tư và cách thực hiện nó đã được giới thiệu thông qua các trường hợp tìm việc. Bài viết này chủ yếu giới thiệu một giao thức so sánh quyền riêng tư với hiệu quả tương đối cao hiện nay.

Giao thức này là một giao thức con được đề xuất trong [1] CrypTFlow2: Thực tế 2-Party SecureInference, và dựa trên giao thức này, chức năng kích hoạt DRelu được áp dụng cho mạng thần kinh.

--Công nghệ liên quan--

Giao thức được xây dựng chủ yếu bằng hai công nghệ chia sẻ bí mật Boolean và truyền không rõ ràng:

▲ vô ý truyền

Truyền không rõ ràng (OT, Truyền không rõ ràng) có nghĩa là người gửi dữ liệu có n dữ liệu, người nhận dữ liệu nhận được một trong các dữ liệu và người nhận dữ liệu không thể lấy dữ liệu khác và người gửi dữ liệu không biết chi tiết về dữ liệu mà người nhận chọn nhận. Đó là cái nào. Sơ đồ triển khai đã được giới thiệu trong bài viết trước "Công nghệ tính toán bảo mật dựa trên tính toán đa bên an toàn (MPC) (1)" nên bài viết này sẽ không nhắc lại.

▲ Chia sẻ bí mật Boolean

Trong điện toán đa bên an toàn, chia sẻ bí mật sẽ được sử dụng để phân tách dữ liệu và chia sẻ nó. Mỗi bên nhận được phân đoạn tương ứng của mỗi dữ liệu và logic tính toán cho dữ liệu gốc sẽ được chuyển đổi thành phép tính của các phân đoạn. Sau toàn bộ logic tính toán được hoàn thành, Sau đó tổng hợp và khôi phục kết quả tính toán của các đoạn để thu được kết quả tính toán của dữ liệu gốc.

Chia sẻ bí mật Boolean đề cập đến việc chia một giá trị Boolean b thành hai đoạn b0 và b1 và đưa hai đoạn này lại với nhau để khôi phục dữ liệu gốc b.

Tạo đoạn: Tạo ngẫu nhiên giá trị Boolean b0 và thực hiện XOR với b để tính b1=b0⊕b

 b=b0⊕b1

Khôi phục phân đoạn: Thực hiện thao tác XOR trên hai phân đoạn

      a=a0⊕a1，b=b0⊕b1

      a⊕b=(a0⊕b0)⊕(a1⊕b1)

Hoạt động XOR: Chia sẻ bí mật Boolean thỏa mãn thuộc tính đồng hình trong hoạt động XOR và thực hiện hoạt động XOR trên các đoạn cục bộ và sau đó khôi phục nó tương đương với hoạt động XOR trên dữ liệu gốc

Hoạt động AND: Chia sẻ bí mật Boolean không đáp ứng thuộc tính đồng hình cho các hoạt động AND và sử dụng công nghệ chuyển giao không rõ ràng để đạt được các hoạt động AND an toàn:

Alice giữ các đoạn a0 và b0, Bob giữ các đoạn a1 và b1, thông qua phép toán AND, Alice lấy c0, Bob lấy c1, c0⊕c1=(a0⊕a1)∧(b0⊕b1) và độ an toàn của cả hai đoạn là đảm bảo ;

*Alice, với tư cách là người gửi truyền dữ liệu ẩn, tạo ngẫu nhiên một giá trị Boolean r là c0 và tạo đầu vào của dữ liệu truyền dữ liệu ẩn như dưới đây:

*Bob, với tư cách là người nhận truyền vô tình, nối các đoạn a1 và b1 của anh ta thành a1||b1 như một tùy chọn cho việc truyền vô tình để lấy dữ liệu r⊕((a0⊕a1)∧(b0⊕b1)) thành c1;

Có thể kiểm chứng rằng c0⊕c1= r⊕r⊕((a0⊕a1)∧(b0⊕b1))=(a0⊕a1)∧(b0⊕b1);

Bản chất là liệt kê tất cả các khả năng của thao tác AND và sau khi thêm các mục ngẫu nhiên, bên kia sẽ chọn kết quả tính toán nhầm lẫn theo dữ liệu của chính mình.

--Ý tưởng thực hiện--

▲ So sánh bản rõ

Trước hết, bất kể tính riêng tư của các hoạt động so sánh, làm thế nào để so sánh hai số trong các trường hợp bình thường:

a=123，b=5879，a=>[0,1,2,3]，b=>[5,8,7,9]

*Căn hai số thành một dãy số có độ dài bằng nhau, nếu không đủ độ dài thì thêm số 0 vào trước

*So sánh tuần tự các số trong hai mảng, nếu các số ở các chữ số tương ứng bằng nhau thì tiếp tục so sánh các chữ số tiếp theo cho đến khi còn một chữ số không bằng nhau. Kết quả so sánh của chữ số không bằng nhau sớm nhất chính là kết quả so sánh của hai dữ liệu. Nếu Nếu tất cả các chữ số bằng nhau thì hai số đó bằng nhau. Toàn bộ quá trình có thể được tóm tắt như công thức sau:

Cả X và Y đều là dữ liệu có độ dài n, 1{X

X=x0||x1||x2||...||x(n-1), Y=y0||y1||y2||...||y(n-1), xi, yi nghĩa là Dữ liệu thứ i sau khi tách

1{X

1{X1

     ...

1{X(n-1)

Xi=xi||...||x(n-1), Yi=yi||...||y(n-1), dùng để biểu diễn dữ liệu sau khi loại bỏ i-1 bit đầu tiên

▲ So sánh quyền riêng tư không an toàn

Nếu bạn muốn chuyển lược đồ so sánh trên thành so sánh riêng tư, cách dễ nhất bạn có thể nghĩ đến là đặt riêng việc so sánh hai đơn vị so sánh nhỏ nhất, đã được giới thiệu trong bài viết trước "Thuật toán tìm việc tao nhã—Thuật toán so sánh riêng tư Ví dụ": Việc so sánh hai đơn vị so sánh nhỏ nhất có thể được thực hiện thông qua giao thức truyền không rõ ràng. Điều này thực sự đảm bảo tính bảo mật của một đơn vị so sánh tối thiểu duy nhất, nhưng trong một số trường hợp, một số tình huống dữ liệu sẽ bị lộ:

a=1230 b=1231, đối với phép so sánh hai số này, nếu b là bên nhận ot, tức là bên nhận kết quả so sánh dữ liệu của đơn vị so sánh nhỏ nhất và việc so sánh được thực hiện theo sơ đồ trên, hai thông tin bổ sung sẽ bị rò rỉ:

1) Khi ba chữ số đầu giống nhau: b biết ba chữ số đầu của a là 123;

2) Dữ liệu của hai đơn vị nhỏ nhất là dữ liệu ở hai đầu của dãy đơn vị nhỏ nhất: b sẽ biết rằng chữ số tận cùng của a là 0;

▲ Loại bỏ sự bất an

chữ

Trong giao thức so sánh quyền riêng tư trong bài báo này, toàn bộ ý tưởng so sánh phù hợp với so sánh quyền riêng tư không an toàn ở trên, nhưng giao thức này giới thiệu công nghệ chia sẻ bí mật và người gửi nhầm lẫn dữ liệu trước đó cho từng dữ liệu khi kết quả so sánh thu được thông qua chuyển giao vô tình giao thức. Các mục ngẫu nhiên, để không bên nào có được kết quả so sánh của dữ liệu đơn vị so sánh tối thiểu, nhưng các đoạn của kết quả so sánh và sử dụng các đoạn để so sánh đệ quy theo quy trình so sánh bản rõ. Sau khi tất cả các đơn vị so sánh tối thiểu được so sánh, sự so sánh Các đoạn kết quả được khôi phục để thu được kết quả so sánh cho toàn bộ dữ liệu.

Do kết quả so sánh của đơn vị nhỏ nhất đều là các mảnh nên kết quả tính toán đệ quy sẽ không được khôi phục cho đến khi hoàn thành so sánh, do đó tránh rò rỉ thông tin do lấy kết quả so sánh của đơn vị so sánh nhỏ nhất.

--Quy trình ký kết--

Alice có dữ liệu x, Bob có dữ liệu y, độ dài nhị phân của dữ liệu là l, độ dài nhị phân của đơn vị so sánh tối thiểu là m, số lượng đơn vị so sánh tối thiểu được chia là q=l/m và giá trị tối đa thập phân của đơn vị so sánh nhỏ nhất là M= 2^m-1

1) Hai bên chia dữ liệu riêng: x=x0||...||x(q-1), y=y0||...||y(q-1)

2) Với tất cả các đơn vị so sánh nhỏ nhất xi(0<=i_0，* Alice chuẩn bị dữ liệu với tư cách là người gửi chuyển khoản không biết: tạo boolean ngẫu nhiên

sij=_0 ⊕ 1{xi

      tij=_0 ⊕ 1{xi=j}

_0, vì các đoạn chia sẻ boolean về việc liệu xi có nhỏ hơn hoặc bằng yi hay không, tương ứng, đối với 0<=j<=M, đầu vào của hai trường hợp truyền vô ý được đặt tương ứng là:

*Bob sử dụng yi làm đầu vào để thực hiện tương ứng hai trường hợp chuyển giao vô tình và thu được các đoạn của hai kết quả so sánh:1

1 và_0，Ví dụ: khi m là 2, đơn vị so sánh tối thiểu đầu tiên của Alice x0=2, đơn vị so sánh tối thiểu đầu tiên của Bob y0=1, Alice tạo ngẫu nhiên

_0 và tạo hai đầu vào không biết như sau:

_1=0⊕_0，_1=0⊕_0

Bob sử dụng y0 như một tùy chọn cho cả hai lần chuyển tiền không biết gì, thu được:

3) Sau khi hoàn thành việc so sánh tất cả các đơn vị so sánh tối thiểu, cả hai bên đã thu được các đoạn chia sẻ Boolean về việc liệu các đơn vị so sánh tối thiểu tương ứng có nhỏ hơn hoặc bằng nhau hay không, sau đó có thể thực hiện theo quy trình so sánh văn bản gốc và sử dụng đệ quy đoạn để tính toán các mảnh của kết quả so sánh cuối cùng.

Đối với thao tác XOR của các đoạn, chỉ cần thực hiện XOR các đoạn cục bộ. Đối với hoạt động AND của các đoạn, cần phải vô tình chuyển các đoạn của kết quả tính toán theo sơ đồ được giới thiệu ở trên.

Trong quá trình đệ quy, chủ yếu có 2 chỗ cần thực hiện phép toán AND:

1{x0||x1 = y0||y1 } ∧ 1{x2 < y2 }

Khi tất cả các đơn vị so sánh trước bằng nhau và đơn vị so sánh tiếp theo:

1{x0||x1 = y0||y1} = 1{x0 = y0 } ∧ 1{x1 = y1 }

Khi tính xem tất cả các đơn vị so sánh trước đó có bằng nhau hay không:

--Tóm tắt--

Đối với việc so sánh một phần tử, phiên bản OT của thao tác không thể được tối ưu hóa thông qua mở rộng OT, vì tính toán đệ quy là bắt buộc và có các phụ thuộc trước và sau. Đối với việc so sánh các yếu tố lô, hiệu quả có thể được tối ưu hóa thông qua mở rộng OT theo hướng dọc cho các phiên bản OT có cùng vị trí và hoạt động.

Giới thiệu về tác giả

Giới thiệu về tác giả

chữ

người giới thiệu

người giới thiệu