Bảo mật của hàm băm

Với Hàm băm H, các thuộc tính như khả năng chống va chạm, khả năng chống va chạm mục tiêu, tính một chiều và tính không uốn được chứng minh như thế nào? Tôi đã đọc về hàm băm và nói rằng nó có khả năng chống va chạm nhưng chúng được chứng minh chính thức như thế nào? Nếu một hàm băm thỏa mãn tất cả các thuộc tính thì nó có hoạt động như một mô hình tiên tri ngẫu nhiên không?

Bạn không thể chứng minh những tính chất này từ các tiên đề ZF. Ví dụ, đối với tính một chiều, điều đó có nghĩa là $FNP\neq FP$ và như vậy $P\neq NP$, được biết đến như một vấn đề khó khăn.

Cách truyền thống để coi hàm băm là chống va chạm, một chiều, v.v. là đề xuất công khai nó và chờ xem liệu các nhà phân tích mật mã có tìm thấy một cuộc tấn công hay không (tất nhiên, bạn phải chắc chắn rằng mọi người sẽ quan tâm đến cái này - vì có phần thưởng lớn chẳng hạn).

Bạn cũng có thể xây dựng hàm băm dựa trên hàm băm đã được nghiên cứu kỹ lưỡng (như SHA-3) và chứng minh rằng các thuộc tính bảo mật của hàm băm đã được nghiên cứu kỹ lưỡng bao hàm các thuộc tính bảo mật của hàm băm mới; chúng tôi gọi những loại lập luận này là bảo mật có thể chứng minh được.