Tái thiết chia sẻ bí mật shamir với sự có mặt của các bên độc hại

Giả sử chúng ta có sơ đồ chia sẻ bí mật (t, n) Shamir. Một giá trị của một số tính toán được chia sẻ với n bên trong đó nhiều nhất $t-1$ các bên là độc hại. Chiến lược tốt nhất để tái cấu trúc cổ phần là gì? Tôi tin rằng chúng ta có thể sử dụng công cụ sửa lỗi Reed-Solomon để truy xuất giá trị cho tối đa t<n/3. Đối với t<n/2, chúng ta có thể tái tạo ngẫu nhiên $k$ lần sử dụng $t$ chia sẻ và kiểm tra giá trị xuất hiện nhiều lần nhất. Có điều gì tốt hơn thế này không?

Một cách tiếp cận mạnh mẽ hơn là sử dụng Thuật toán giải mã danh sách Guruswami-Sudan. Nếu bạn có $m$ chia sẻ thì thuật toán tái cấu trúc đa thức của họ sẽ trả về nhiều nhất là tất cả các đa thức bậc $t$ sao cho ít nhất $k$ của các cổ phiếu thỏa mãn đa thức, với điều kiện là $k>\sqrt{km}$. Như $m-t+1$ phát triển so với $t$, số lần xác thực sai lẻ tẻ sẽ giảm (lưu ý rằng nếu số bên trung thực gần bằng số bên không trung thực, thì có khả năng đáng kể là chúng ta không thể khôi phục đa thức một cách duy nhất nhưng có thể chứa nó vào một danh sách tương đối ngắn các khả năng ).