Tính ngẫu nhiên ngắn trong ElGamal và Paillier

Bảo mật ngữ nghĩa trong cài đặt đó giảm xuống thành bảo mật ngữ nghĩa cho sơ đồ tiêu chuẩn khi và chỉ khi một phân phối entropy thấp nhất định trong nhóm con "không có bản mã" là không thể phân biệt bằng tính toán với ngẫu nhiên.

• Trong trường hợp của ElGamal, giả định là $(g^r, h^r)$ nhỏ ngẫu nhiên $r$ không thể phân biệt được về mặt tính toán với một cặp DH tiêu chuẩn, cụ thể là $(g^r, h^r)$ cho đồng phục $r$. Điều này đã được nghiên cứu bởi Kurosawa và Koshiba trong một giấy PKC 2004và họ đã chỉ ra rằng giả định đúng nếu bài toán log rời rạc lũy thừa tính toán khó. Đối với các nhóm liên quan đến mật mã, cách tấn công tốt nhất vào nhật ký rời rạc theo cấp số nhân ngắn thường là lambda của Pollard hoặc giống như đối với các nhật ký rời rạc không ngắn, vì vậy nếu $r$ đủ lớn (ít nhất gấp đôi thông số bảo mật), điều này được coi là ổn. Tuy nhiên, điều này ràng buộc trên $r$ dù sao cũng giống như giới hạn trên số mũ kích thước đầy đủ nếu bạn đặt tham số chính xác, do đó, việc này là vô ích trong hầu hết các cài đặt.

• Trong trường hợp của Paillier, giả định là $r^n$ cho nhỏ $r$ không thể phân biệt về mặt tính toán với ngẫu nhiên trong nhóm con của thứ tự $\varphi(n)$ của $\mathbb{Z}/n^2\mathbb{Z}$. Tôi không biết về bất kỳ cuộc tấn công nào vào vấn đề cụ thể này và có vẻ hợp lý nếu $r$ không quá nhỏ, mặc dù tôi không biết nó có thể liên quan đến giả định tiêu chuẩn nào hơn. Tuy nhiên, bất kể, tốc độ tăng từ việc sử dụng một nhỏ hơn $r$ trong tính toán của $r^n \bmod n^2$ nên không đáng kể (trên thực tế, sẽ không có sự tăng tốc nào cả nếu bạn sử dụng số học nhanh), vì vậy tôi cũng không chắc chắn để hiểu điểm của biến thể này.