Điểm:0

Crypto

Công trình này có phải là OWF không?

zingiest

11:14, 11/05/2023

Với chức năng OWF $f: \{0,1\}^{2\lambda} \rightarrow \{0,1\}^{2\lambda}$ và PRG $G: \{0,1\}^{\lambda} \rightarrow \{0,1\}^{2\lambda}$, là hàm sau $f^*$ một OWF?

\begin{align} f^*: \{0,1\}^{\lambda} &\to \{0,1\}^{2\lambda}\ x &\to f^*(x) = f(G(x)\oplus(0^{\lambda}||x)) \end{align}

Ý tưởng của tôi là nó an toàn, chủ yếu là do chức năng $f$ là một OWF, nhưng tôi không thể chứng minh điều đó.Hơn nữa, tôi nghĩ rằng xác suất va chạm của đầu vào của nó có thể liên quan, nhưng nó không hơn gì trực giác.

124

0 + 0

đối xứng

chức năng một chiều

máy phát điện giả ngẫu nhiên

Maeher

12:41, 11/05/2023

Gợi ý: Đặt $G'$ là một PRG. Sau đó, $G$ được định nghĩa là $G(x_1\|x_2) = G(x_1)||x_2$ đủ lâu $x_1$ cũng là một PRG.

Hồi đáp

kelalaka

12:50, 11/05/2023

@Maeher đủ lâu =?

Hồi đáp

Maeher

15:18, 11/05/2023

@kelalaka Bất kỳ phân số không đổi nào cũng được. Giả sử 1/2 chiều dài đầu vào cho một công trình bê tông.

Hồi đáp

zingiest

16:03, 11/05/2023

@Maeher tôi có nên xây dựng một phản ví dụ với gợi ý của bạn không?

Hồi đáp

Maeher

18:31, 11/05/2023

Điều đó có thể làm việc.

Hồi đáp

zingiest

08:39, 12/05/2023

@Maeher tôi nghĩ rằng dựa trên gợi ý của bạn, chúng ta có thể xây dựng hàm $f^*(x_1||x_2) = f(G'(x_1)||x_2 \oplus (0^{\lambda}||x1||x2 ))$ và nếu chúng ta có $|G'(x_1)| = \lambda + |x1|$ chúng ta cũng có phần thứ hai của đầu vào của $f$ luôn bằng 0 (do xor). Do đó, xác suất tìm thấy hình ảnh trước của $f^*$ bị giới hạn so với lựa chọn $x_1$ trong trường hợp này. Nhưng chúng tôi cần $x_1$ đủ lớn để có PRG... Xem xét $|x_1|=\lambda/2$ như trong ví dụ của bạn, chúng tôi vẫn có xác suất tìm thấy hình ảnh trước $2^{-\lambda /2}$ vẫn không đáng kể.

Hồi đáp

kelalaka

11:03, 12/05/2023

Bạn có chắc chắn các thông số? thực hiện $f^*$ từ $2\lambda$ hoặc $\lambda$ từ $G$ từ $\lambda$. Ngoài ra @Maeher có ý viết $G(x_1\|x_2) = G'(x_1)||x_2$, đó là cấu trúc cho một ví dụ đáng thương $PRG$ thành ....

Hồi đáp

zingiest

11:59, 12/05/2023

@kelalaka $f*$ nhận đầu vào có độ dài $\lambda$, có thể là $x_1||x_2$. Nhưng tôi không hiểu ví dụ ngược có thể ở đâu, vì $G(x_1||x_2) = G'(x_1)||x_2 là an toàn cho $x_1$ đủ lớn.

Hồi đáp

Maeher

14:08, 12/05/2023

Gợi ý 2: Một OWF chỉ được đảm bảo là khó đảo ngược nếu đầu vào được lấy mẫu theo phân phối đồng đều. Một phân phối chỉ chứa các đầu vào kết thúc bằng nhiều số 0 là rất xa (và dễ dàng phân biệt với) thống nhất.

Hồi đáp

zingiest

23:34, 12/05/2023

Vì vậy, tôi đã nghĩ đến việc xây dựng một OWF $f'(x) $ "câm" trong trường hợp các bit $\lambda$ cuối cùng của đầu vào của nó là null thì đầu ra của chính đầu vào đó hoặc, nếu không, là đầu ra bình thường của $f$. Hàm vẫn phải là OWF vì xác suất có đầu vào ngẫu nhiên kết thúc bằng $0^{\lambda}$ là $2^{-\lambda}$ và do đó không đáng kể. Nhưng ngay cả khi kẻ tấn công nhìn thấy $G'(x)\oplus(0^{\lambda}||x)$, thì hắn có thể làm gì với nó? Làm thế nào anh ta có thể khấu trừ $x$? (Nhân tiện, cảm ơn rất nhiều vì sự giúp đỡ!)

Hồi đáp

Maeher

09:10, 13/05/2023

Có nhiều cách khác để OWF cư xử ngu ngốc. Hãy nhớ rằng, bạn không cần phải tìm $x$. Bạn chỉ cần tìm hình ảnh trước *a*, không phải hình ảnh trước *giống nhau*.

Hồi đáp

zingiest

09:55, 13/05/2023

Tôi nghĩ rằng tôi đã nhận nó! Tôi xây dựng một OWF $f'$ trả về $1^{2\lambda}$ nếu các bit ${\lambda/2}$ cuối cùng của đầu vào là $0$ và ngược lại, đầu ra của một OWF bình thường $f$. $f'$ là một OWF vì xác suất có một đầu vào ngẫu nhiên kết thúc bằng $0^{\lambda/2}$ là $2^{-\lambda/2}$ nhưng cấu trúc $f*$ có thể dễ dàng bị phá vỡ vì kẻ tấn công sẽ luôn nhận được $1^{2\lambda}$ và do đó, anh ta chỉ cần gửi tiền hình ảnh kết thúc bằng $0^{\lambda/2}$ bit để giành chiến thắng trong trò chơi. Nó có đúng không?

Hồi đáp

Maeher

11:06, 14/05/2023

Ví dụ của bạn sẽ hoạt động. Bạn nên thực sự viết ra các bằng chứng rằng $f$ và $G$ mà bạn xây dựng thực sự là một OWF và PRG an toàn tương ứng. Cuộc tấn công của bạn cũng hoạt động nhưng cụ thể hơn mức cần thiết. $f^*(x_1\|x_2) = f(G(x_1\|x_2)\oplus(0^\lambda\|x_1\|x_2) = f((G'(x_1)\|x_2)\oplus( 0^\lambda\|x_1\|x_2) = f((G'(x_1)\oplus 0^\lambda\|x_1) \|0^{\lambda/2}) = 1^{2\lambda}$ vì vậy $f^*$ là một hàm *hằng số* và giá trị *bất kỳ* $2\lambda$ là một tiền tố hợp lệ.

Hồi đáp

Phan Văn Trường

Câu hỏi này là trong các ngôn ngữ khác: