(â¦) là $\alpha\oplus\beta$ không thể phân biệt với một số ngẫu nhiên?
Lưu ý rằng chúng ta cần phải chuyển đổi $\alpha$ và $\beta$ đến bitstrings để áp dụng XOR theo bit. Vì vậy, thực sự chúng tôi tính toán $\underline\alpha\oplus\underline\beta$ ở đâu $\underline\gamma$ is là ký hiệu cho một đại diện được xác định duy nhất của một phần tử nhóm tùy ý $\gamma$ dưới dạng một chuỗi bit có kích thước cố định và được hỏi liệu $\underline\alpha\oplus\underline\beta$ là một chuỗi bit ngẫu nhiên. Câu trả lời sẽ phụ thuộc vào đại diện được sử dụng.
Thật dễ dàng tìm thấy một phản ví dụ rõ ràng với một nhóm mật mã và biểu diễn quen thuộc, chẳng hạn như một nhóm con của dư lượng bậc hai sau đó nhóm nhân modulo $(2p+1)$, khi nào $p$ là một ngẫu nhiên lớn Sophie Germain thủ tướng nói 1999 bit¹ và các bit hàng đầu 1010và biểu diễn các phần tử nhóm dưới dạng chuỗi bit 2000 bit trên mỗi người lớn quy ước. $\underline\alpha$ và $\underline\beta$ là các chuỗi bit 2000 bit có độ lệch rõ rệt đối với 0 trong hai bit đầu tiên và có độ lệch tương tự (mặc dù thấp hơn) trong hai bit đầu tiên của $\underline\alpha\oplus\underline\beta$.
Mặt khác, nếu ở trên chúng ta thay thế 1010 với 111â¦111 hơn 200 bit², sau đó $\underline\alpha$ sẽ không thể phân biệt được với ngẫu nhiên ngoại trừ việc đại diện cho một $\alpha$ đó là dư lượng bậc hai³. Mặc dù vậy, và $\alpha$ và $\beta$ không hoàn toàn độc lậpâ´, tôi phỏng đoán cả hai hiệu ứng đều đủ yếu để $\underline\alpha\oplus\underline\beta$ là tính toán không thể phân biệt từ ngẫu nhiên.
Đối với bất kỳ biểu diễn nào của các phần tử nhóm dưới dạng chuỗi bit, chúng ta có thể tạo ra một biểu diễn khác có cùng kích thước bằng cách áp dụng Hoán vị ngẫu nhiên giả có thể tính toán hiệu quả và có thể đảo ngược công khai cho biểu diễn. Các thuộc tính của nhóm vẫn còn, mã hóa ElGamal vẫn hoạt động và an toàn như nhau. Và bây giờ, đối với bất kỳ $p$ đủ lớn để DLP cứng, $\underline\alpha\oplus\underline\beta$ có thể được chứng minh là không thể phân biệt về mặt tính toán với các thuộc tính sử dụng ngẫu nhiên của PRP.
¹ Như vậy mã hóa ElGamal là an toàn, điều này ẩn chứa trong câu hỏi.
² Chúng tôi có thể muốn tăng kích thước bit của $p$ một chút để bù đắp cho Bài toán logarit rời rạc được giảm bớt một chút bởi $p$ gần với sức mạnh của hai.
³ Một đặc tính có thể kiểm tra hiệu quả bằng cách kiểm tra xem biểu tượng Legendre $\left(\frac\alpha{2p+1}\right)\,\underset{\text{def}}=\,\alpha^p\bmod(2p+1)$ Là $+1$
´ Lưu ý rằng $\alpha^{-1}\beta\bmod(2p+1)$ là một phần tử hơi thiên vị của nhóm.
