SZK: chứng minh không tiết lộ thông tin cho bài toán thống kê, thường là tương tác giữa máy khách yếu và máy chủ mạnh.

     • SRE: mã hóa ngẫu nhiên cho phép máy khách gửi một thông điệp duy nhất để máy chủ xác định tính hợp lệ mà không học thêm gì.

     • Câu hỏi mở: liệu SRE có tương đương với SZK?

   - Kết quả chính:

     • Trong mô hình phi tương tác và phi đồng đều, SRE với bảo mật một phía (1RE) tương đương với NISZK (chứng minh không tương tác).

     • Nếu SRE không thuộc BPP (tức là có bài toán khó), thì tồn tại hàm một chiều (one-way functions) mạnh hơn so với giả thuyết tương tự trong SZK.

     • Nếu tồn tại bài toán trung bình khó trong PRE (mã hóa ngẫu nhiên hoàn hảo), thì tồn tại hàm băm chống va chạm (CRH).

   - Hệ quả lý thuyết:

     • SRE ⊆ SZK, nhưng để chứng minh SRE = SZK cần chứng minh 1RE = SRE và NISZK = SZK.

     • Nếu SRE = SZK thì có thể xây dựng hàm một chiều mạnh từ giả thuyết độ phức tạp trong SZK.

     • PRE mạnh hơn SRE, và nếu PRE có bài toán khó trung bình thì có thể xây dựng CRH.

   - Kỹ thuật:

     • Sử dụng phân tích khoảng cách thống kê, entropy, hash ngẫu nhiên, và mô hình oracle để phân biệt lớp bài toán.

     • Chứng minh bằng cách chuyển đổi giữa các mô hình mã hóa và chứng minh, sử dụng các hàm giả lập và kỹ thuật làm phẳng phân phối.