CẬP NHẬT 20220330: Câu trả lời mới sau khi làm rõ câu hỏi; câu trả lời cũ được giữ lại để hiểu ý nghĩa của các bình luận.
Tôi nghĩ rằng những gì bạn đang hỏi là liệu các bit của $y$ hoạt động như một hàm lõi cứng trên nghịch đảo của hàm một chiều (trong trường hợp này là hàm logarit rời rạc modulo $n$).Để biết thông tin cơ bản về các chức năng cốt lõi, hãy xem ví dụ phần 2.4 để biết Cơ sở của Mật mã học). Tuy nhiên, nếu nghịch đảo của hàm một chiều dễ tính toán (điều này đúng trong trường hợp của bạn vì hàm lũy thừa có thể được tính toán trong thời gian đa thức), thì không có hàm lõi cứng nào.
Các nhà mật mã học không diễn đạt điều này theo thuật ngữ phân phối đồng đều, mà theo thuật ngữ phân biệt đối xử có thể được tính toán trong thời gian đa thức và mang lại lợi thế không tầm thường (xem định nghĩa 2.4 của ghi chú). Họ nói rằng một vị ngữ $b(y)$ là cốt lõi cho $f$ nếu đối với tất cả các bộ phân biệt thời gian đa thức, chúng ta có
$$\mathbb P(A(f(U_n)),1^n)=b(U_n)<1/2+1/p(n).$$
Trong trường hợp của bạn $f$ là chức năng $y=g^x\mod n\mapsto x$ và chức năng của bạn $b$ là $i$chút của $y=g^x\mod n$. Tuy nhiên, tôi có bộ phân biệt phản ví dụ $A(z,1^n)$ đó là để tính toán $g^z\mod n$ (trong thời gian đa thức) và nhìn vào $i$một chút. Điều này phân biệt câu trả lời với xác suất 1 vì với đối số đầu tiên $f(y)=x$ nó trở lại $b(y)$.
Nói cách khác, có sự thiếu đồng nhất có thể kiểm chứng bằng máy tính vì tôi có thể nhanh chóng kiểm tra $x$ các giá trị để xem liệu chúng có tạo ra đầu ra nằm trong $Y'$.
Câu trả lời cũ.
Đúng. Để cho $|Y'|=M$ và để cho $z$ là bất kỳ yếu tố của $Y'$ thì định lý Bayes cho chúng ta biết rằng
$$\mathbb P(g^x\mod n=z|g^x\mod n\in Y')=\frac{\mathbb P(g^x\mod n=z)\mathbb P(g^x \mod n\in Y'|g^c\mod n=z)}{\mathbb P(g^x\mod n\in Y')}.$$
Bây giờ chúng tôi lưu ý rằng $\mathbb P(g^x\mod n=z)=1/\phi(n)$ (bởi tính đồng nhất được ghi trong câu hỏi), $\mathbb P(g^x\mod n\in Y'|g^c\mod n=z)=1$ và đó $\mathbb P(g^x\mod n\in Y')=M/\phi(n)$ (một lần nữa bởi tính đồng nhất trong câu hỏi). Như vậy
$$\mathbb P(g^x\mod n=z|g^x\mod n\in Y')=1/M$$
cho tất cả $z\in Y'$ trong đó mô tả một phân phối thống nhất.
