Làm thế nào có thể chứng minh tính không thể phân biệt?

Tôi tò mò về cách chứng minh tính toán không thể phân biệt được.

Chẳng hạn, những điều sau đây có thể phân biệt được về mặt tính toán không? Nếu đúng thì chứng minh như thế nào?

Để cho $P_a$ là một cỗ máy xác suất biết một bí mật $a$ và tạo ra một chuỗi các $n$ bộ dữ liệu: $(x_1,{x_1}^a),...,(x_n,{x_n}^a)$ ở đâu $x_i$ đối với mỗi bộ dữ liệu được lấy mẫu ngẫu nhiên từ một nhóm tuần hoàn theo thứ tự nguyên tố. Tương tự, đặt một PPT $P_b$ được định nghĩa. Bây giờ hãy để một người thách thức chọn ngẫu nhiên hai chuỗi được tạo bởi $P_a$ và $P_b$ (họ có thể là cả hai từ $P_a$, hoặc một từ $P_a$ và một từ $P_b$). Một thuật toán hiệu quả có thể cho biết liệu hai chuỗi có được tạo bởi hai PPT khác nhau không?

Chúng tôi sẽ giả định rằng các giả định tiêu chuẩn về các nhóm được áp dụng, ví dụ: độ khó của logarit rời rạc hoặc quyết định Diffie-Hellman.