Làm cách nào để tìm trình trích xuất trong Giả định kiến ​​thức về số mũ?

của Mihir Bellare giấy

Để cho $q$ là số nguyên tố sao cho $2q +1$ cũng là số nguyên tố, và để $g$ là một người tạo ra thứ tự $q$ phân nhóm của ${Z^â}_{2q+1}$. Giả sử chúng ta được cung cấp đầu vào $q$, $g$, $g^a$ và muốn xuất một cặp $(C, Y)$ như vậy mà $Y = C^a$. Một cách để làm điều này là chọn một số $c \in Z_q$, để cho $C = g^c$, và để $Y = (g^a)^c$. Theo trực giác, có thể xem KEA1 nói rằng đây là cách "duy nhất" để sản xuất một cặp như vậy. Giả định nắm bắt điều này bằng cách nói rằng bất kỳ đối thủ nào xuất ra một cặp như vậy đều phải "biết" một số mũ. $c$ như vậy mà $g^c = C$. Việc chính thức hóa yêu cầu rằng có một "trình trích xuất" có thể trả về $c$.

Tôi hiểu làm thế nào để tìm thấy một cặp $(C, Y)$ như vậy mà $Y = C^a$ bằng cách chọn bất kỳ $c \in Z_q$

Tuy nhiên, tôi bối rối về ý nghĩa của "trình trích xuất" ở đây. Liệu nó có nghĩa là đưa ra các cặp $(C, Y)$ người ta phải tìm $c$ được sử dụng để tính toán $C$? Nếu có, làm thế nào để chúng tôi tìm thấy $c$ đưa ra chỉ $(C, Y)$?

Hay nó có ý nghĩa gì khác?

Nếu chúng ta nhìn vào các tài liệu tham khảo giấy 11, tất cả sẽ rõ ràng hơn và đây là cách chúng ta đọc các bài báo; bằng cách xem tài liệu tham khảo.

Các từ viết tắt

• DHA : giả định Diffie-Hellman
• SDHA-1: Giả định Diffie-Hellman mạnh mẽ -1

Giả định 8 là về những gì KEA1 nói về; (SDHA-1). Với đề xuất 9 cho thấy rằng theo SDHA-1, DHA nắm giữ ( SDHA-1 $\ngụ ý$ DHA). KEA-1 là sự trình bày lại đề xuất này;

KEA1: Đối với bất kỳ đối thủ $A$ có đầu vào $q, g, g^a$ và trả về $(C, Y )$ với $Y = C^a$ tồn tại một trình trích xuấtâ $\bar{A}$ , được cung cấp các đầu vào giống như $A$ lợi nhuận $c$ như vậy mà $g^c = C$. I E. như là $\bar{A}$ được gọi là máy chiết xuất.

I.e từ, nếu đối thủ $A$ giải quyết SDHA-1 sau đó $\bar{A}$ (gọi là vắt) có thể giải DHA.