Hàm trapdoor

Hàm trapdoor là một hàm số có thể tính theo một chiều dễ dàng, và được coi là rất khó để tính toán theo chiều ngược lại (tìm hàm đảo) nếu không có thông tin đặc biệt. Hàm trapdoor được sử dụng rộng rãi trong mật mã học. Một hàm trapdoor được định nghĩa bao gồm 3 giải thuật: TDF=(G,F,F−1), trong đó: G() là giải thuật sinh ngẫu nhiên một cặp khóa công khai (pk,sk). pk: khóa công khai, sk: khóa bí mật. F(pk,x)=y là hàm ánh xạ phần tử x thuộc tập X tới phần tử y thuộc tập Y sử dụng khóa công khai pk. F−1(sk,y)=x là hàm ngược của hàm F, ánh xạ phần tử y thuộc Y tới phần tử x thuộc X, sử dụng khóa bí mật sk. Điều kiện: ∀(pk,sk),∀x∈X: F−1(sk,F(pk,x)) = x Hàm secure trapdoor là một hàm trapdoor trong đó F là hàm một chiều, tức là có thể dễ dàng tính toán y=F(pk,x) ∀x∈X nhưng không thể tính được x từ y mà không có khóa bí mật sk hay xác suất tính được x từ y mà không có khóa bí mật sk là không đáng kể. Trapdoor One-Way Function trên Wolfram Mathworld