Tại sao chúng ta giả sử rằng f là một hàm đa thức hoặc đa thức trong thời gian? Trực giác đằng sau điều này là gì?
Tôi tin rằng bạn đã quen thuộc với lý do tại sao chúng ta sử dụng thời gian đa thức làm cơ sở cho tất cả các mật mã (kiểm tra nhận xét của Kelalaka). Tóm lại, có vô số lý do khiến chúng tôi tin rằng đây là một mô hình hợp lý cho cái mà chúng tôi gọi bằng trực giác là "tính toán hiệu quả".Ở đây, trong bối cảnh của MPC, không có gì khác biệt: chúng tôi muốn có thể tập trung vào các tính toán hiệu quả để thực hiện.
điều này hạn chế các loại chức năng mà chúng ta có thể sao chép với sự trợ giúp của các giao thức phải không? Tại sao chúng ta cho rằng đây là họ chức năng duy nhất mà các giao thức có thể bắt chước? Họ các hàm này có giới hạn vấn đề đối với các hàm đa thức không? Liệu giả định này có thể
Tôi không quen với cách diễn đạt chính xác trong các bài báo này, nhưng thông thường, bất cứ khi nào bạn đề cập đến các hàm có đầu vào/đầu ra không giới hạn, thì bạn đang thực sự xem xét những hàm này vẫn có thể tính toán được trong thời gian đa thức đối với độ dài đầu vào. Một lần nữa, điều này là do chúng tôi mô hình hóa những người tham gia giao thức như những cỗ máy thời gian đa thức và chúng tôi muốn họ có thể hoàn thành việc tính toán.
thêm vao Đoa, có những khái niệm về bảo mật dựa trên giả định rằng đối thủ bị giới hạn về mặt tính toán. Ví dụ, có những giao thức mà tính bảo mật của nó phụ thuộc vào việc đối thủ không có khả năng phân tích số lượng lớn. Tất nhiên, điều này có thể thực hiện được khi có đủ thời gian tính toán để thử tất cả các thừa số nguyên tố có thể, nhưng đối thủ thời gian đa thức không thể làm được điều này.
Tuy nhiên, có những khái niệm khác trong bối cảnh tính toán đa bên an toàn, nơi chúng ta thực sự có thể chấp nhận những đối thủ chạy trong thời gian siêu đa thức. giao thức với hoàn hảo và thống kê bảo mật (nhận được điều khoản ô của an ninh lý thuyết thông tin) được thiết kế theo cách mà không đối thủ nào, bất kể số lượng tài nguyên tính toán hay thời gian chạy, có thể phá vỡ tính bảo mật của giao thức.
Với điều này, về nguyên tắc, chúng ta có thể cho phép tất cả các bên (không chỉ đối thủ) chạy trong thời gian siêu đa thức, nhưng sau đó câu hỏi trở thành những gì thực sự đạt được khi làm điều này. Về cơ bản, tôi không thể nghĩ ra các hàm phi đa thức có ý nghĩa mà chúng ta muốn tính toán.
