Có tồn tại PRNG nào có thể vượt qua bài kiểm tra bit tiếp theo không?

Có, PRNG như vậy tồn tại. Một ví dụ là Blum Blum Shub:

Có một bằng chứng làm giảm tính bảo mật của nó đối với độ khó tính toán của bao thanh toán. Khi các số nguyên tố được chọn một cách thích hợp và các bit có thứ tự thấp hơn O(log log M) của mỗi xn là đầu ra, thì trong giới hạn khi M tăng lớn, việc phân biệt các bit đầu ra với ngẫu nhiên ít nhất cũng khó như giải phần dư bậc hai bài toán modulo M.

Về mặt kỹ thuật, điều đó có nghĩa là Blum Blum Shub vượt qua bài kiểm tra bit tiếp theo với giả định là khó giải bài toán phần dư bậc hai. Chúng tôi không thể chứng minh cụ thể rằng đó là trường hợp, nhưng chúng tôi tin là như vậy.

Tôi nghi ngờ rằng bạn cũng có thể thực hiện giảm bảo mật bằng PRNG dựa trên HMAC ở chế độ truy cập, nhưng cá nhân tôi không biết về một điều trong tài liệu. Tuy nhiên, điều đó không có nghĩa là nó không tồn tại.