Sử dụng ma trận khả nghịch ngẫu nhiên trên các trường hữu hạn để xác định hàm băm của danh sách

Đây là phần tiếp theo của câu hỏi trước Phép nhân ma trận của các thông báo băm có thừa nhận sự thao túng kết quả không?; công thức này không thành công vì nó thừa nhận các ma trận đơn lẻ và do đó suy biến thành ma trận không sau khi nhân đủ các phần tử. Người trả lời đã đề xuất sử dụng một trường như $GF(256)$ thay vì một vành và bác bỏ các ma trận đơn lẻ, đó là điều mà câu hỏi này khám phá.

Điều này được đăng chéo từ Toán học SE.

Xét một dãy các phần tử có thứ tự $a_n$, một chức năng $h$ tạo ra một ma trận khả đảo trên trường hữu hạn ââ â từ hàm băm mật mã của một phần tử và một hàm $H$ tìm tích của tất cả các ma trận như vậy từ một dãy:

$H(a) = \prod_{i = 1}^{n} h(a_i)$

Định nghĩa $H(a)$ là hàm băm của chuỗi $a_n$.

Lưu ý rằng do tính kết hợp, đưa ra hai trình tự $a_n$, $b_m$, sau đó $H(a)*H(b) = H(a ⧺ b)$ (ở đâu $⧺$ có nghĩa là nối các chuỗi).

Giả sử rằng chúng ta có thể tin tưởng hàm dẫn xuất ma trận khả nghịch có các thuộc tính của hàm băm mật mã, Có thuật toán nào tốt hơn brute force có thể tìm thấy hai chuỗi khác nhau có cùng hàm băm không?

Tôi đã mã hóa một ví dụ về định nghĩa này trong sổ ghi chép của Julia mà tôi xuất bản ở đây.