Có phải "trường hợp khó" có nghĩa là các vấn đề khó giải quyết như giả định DDH (Decisional Diffie Hellman) không?
Về cơ bản là có, nó có nghĩa là một cụ thể ví dụ của một vấn đề khó khăn - ví dụ, trong trường hợp DDH, nó có nghĩa là một thách thức cụ thể $(g^a, g^b, g^c)$.
Phép rút gọn hoạt động bằng cách chỉ ra rằng nếu bạn có một phương pháp/thuật toán để giải quyết một vấn đề (thường là phá vỡ một giao thức), thì bạn có thể sử dụng cùng một thuật toán để giải quyết vấn đề khó khăn như DDH. Điều này chứng tỏ rằng phá vỡ giao thức ít nhất cũng khó như phá vỡ DDH. Và ngược lại, nếu DDH cứng thì giao thức đó an toàn.
Việc rút gọn thường bắt đầu bằng việc lấy một ví dụ về bài toán khó, chẳng hạn như bài toán DDH. Sau đó, bạn sẽ nói điều gì đó như "giả sử $\mathcal{A}$ là một đối thủ/thuật toán có thể phá vỡ giao thức XXX với lợi thế $\epsilon$". Tiếp theo, bạn sẽ chỉ ra cách bạn có thể biến trường hợp của mình về vấn đề DDH $g^a, g^b, g^c$ thành các giá trị mà bạn có thể cung cấp cho $\mathcal{A}$, để bất cứ điều gì $\mathcal{A}$ trả về, bạn sẽ tìm hiểu câu trả lời cho phiên bản DDH (có thể với một số xác suất thấp hơn so với $\epsilon$, được gọi là "mất độ kín"). Đây là cách bằng cách nào đó biến phiên bản DDH thành thứ bạn có thể cung cấp cho $\mathcal{A}$ được gọi là "nhúng" một trường hợp của sự cố DDH vào giao thức của bạn.
Nhưng bạn sẽ tìm ra xác suất và nếu bạn có thể chỉ ra rằng lợi thế của mình trong việc giải bài toán DDH bằng cách sử dụng $\mathcal{A}$ là không đáng kể nếu $\epsilon$ nghĩa là bạn đã chứng minh thành công việc giảm thiểu tính bảo mật cho giao thức của mình khỏi DDH.
