SCRAPE Scalable Randomness Attested by Public Entities
Tính ngẫu nhiên có thể mở rộng được chứng thực bởi các thực thể công khai
Các Beacon ngẫu nhiên (một cơ chế được sử dụng để tạo ra các giá trị ngẫu nhiên có thể dự đoán và không thể được chi phối bởi bất kỳ bên nào) thống nhất có đầu ra có thể được chứng thực công khai là không thiên vị được yêu cầu trong một số giao thức mật mã. Một cách tiếp cận phổ biến để xây dựng các Beacon như vậy là yêu cầu một số bên chạy giao thức tung đồng xu (Coin Tossing) với phân phối đầu ra được đảm bảo (để kẻ tấn công không thể dễ dàng ngăn các bên trung thực nhận được tính ngẫu nhiên, do đó tạm dừng các giao thức dựa vào nó). Tuy nhiên, các công trình hiện tại phải đối mặt với các vấn đề nghiêm trọng về khả năng mở rộng do chi phí tính toán và truyền thông cao.
Bài nghiên cứu này trình bày một giao thức tung đồng xu cho đa số trung thực, cho phép bất kỳ thực thể nào xác minh rằng đầu ra được tạo một cách trung thực bằng cách quan sát thông tin có sẵn công khai (ngay cả sau khi quá trình thực thi hoàn tất), đồng thời đạt được cả phân phối đầu ra được đảm bảo và khả năng mở rộng. Khối xây dựng chính trong quá trình xây dựng của bài nghiên cứu là lược đồ Chia sẻ bí mật có thể kiểm chứng công khai đầu tiên cho các cấu trúc truy cập ngưỡng chỉ yêu cầu phép tính O(n). Các lược đồ trước đây yêu cầu các phép tính O(nt) (trong đó t là ngưỡng) từ mỗi bên liên quan, khiến chúng không phù hợp để tạo tính ngẫu nhiên phân tán có thể mở rộng, yêu cầu t = n/ 2 và do đó, có các phép tính O(n2).
Nguồn tài liệu tại đây
