Sơ đồ mã hóa an toàn, hiện đại, đồng hình một phần là gì?

lúc đó tôi đang đọc sách tờ giấy này của Philippe Golle về việc sử dụng các thuộc tính đồng hình của mã hóa ElGamal để chơi một trò chơi bài xì phé tinh thần (tức là bài xì phé bảo mật bằng mật mã mà không cần người chia bài bên thứ ba đáng tin cậy). Tôi đã quyết định rằng sẽ là một dự án tốt nếu thử triển khai một số phiên bản cơ bản của nó nhưng tôi nhanh chóng gặp phải một số vấn đề.

Có vẻ như ElGamal (và RSA, đối với vấn đề đó) thường được coi là không an toàn và lời khuyên phổ biến dường như là tránh chúng. Do đó, hai lựa chọn lớn cho sự sụp đổ của thuyết đồng hình một phần là điều không thể bàn cãi đối với các trò chơi có tiền cược đủ cao. Hơn nữa, tôi thực sự không thể tìm thấy bất kỳ hệ thống mật mã được tiêu chuẩn hóa nào khác có thuộc tính này và hoạt động trên các giá trị rời rạc chứ không phải xấp xỉ (cần thiết để triển khai thuật toán được nêu trong bài báo). Tôi có thiếu một cái gì đó rõ ràng?

Tôi đoán câu hỏi của tôi là: nếu Golle viết bài báo này vào năm 2022, thì anh ấy sẽ đề xuất gì thay vì ElGamal cho các trò chơi poker có tiền cược đủ cao?

ElGamal và RSA «được coi là không an toàn» NẾU một giả định Máy tính lượng tử liên quan đến mật mã. Nhưng những điều này vẫn còn mang tính giả thuyết cao. Thế giới (internet, ngân hàng, di động..) hiện đang chạy trên các hệ thống mật mã, khi không đối xứng, về mặt lý thuyết dễ bị tổn thương trước các CRQC giả định sau: RSA, ECDSA, EdDSA, ECIESâ¦

Hệ thống mật mã Paillier đáng được xem xét khi người ta bỏ qua giả thuyết CRQC. Nó đơn giản¹, cung cấp mã hóa đồng hình bổ sung cho các số nguyên (có thể được ký) với một hạn chế nhỏ và rõ ràng², có hiệu quả trong một yếu tố không đổi nhỏ của giải mã RSA (do đó có thể chịu được trong nhiều ứng dụng), không có bằng sáng chế, có thể chứng minh là có thể rút gọn thành một bài toán được cho là siêu đa thức cho các máy tính cổ điển và được coi là an toàn như RSA với cùng kích thước nguyên tố.

Tôi tin rằng lý do chính mà hệ thống mật mã của Paillier không được sử dụng nhiều trong thực tế là do mã hóa đồng hình nói chung không có nhu cầu cao.

Ngoài ra: Mã hóa Paillier không dễ bị tấn công bởi lời tiên tri đệm hoặc lựa chọn đệm kém, vì (trái ngược với RSA) nó không cần đệm. Nó dễ bị tấn công khi triển khai giống như RSA, bao gồm khai thác các trình tạo số ngẫu nhiên kém khi tạo hoặc sử dụng khóa, các kênh bên và các cuộc tấn công lỗi. Sự tương đồng với RSA là một tin tốt, vì các biện pháp đối phó hiệu quả chống lại các cuộc tấn công đã được biết đến với RSA và phần lớn có thể được điều chỉnh cho phù hợp với Paillier.

¹ Đặc biệt với hạn chế chung của $n$ tích của hai số nguyên tố có kích thước bằng nhau, và $g=n+1$.

² Bản rõ vượt quá $n$ được giảm modulo $n$, với $n$ một tham số công khai đủ lớn không phải là vấn đề đối với bất kỳ thứ gì có thể đếm được, bao gồm bất kỳ phần tiền tệ có ý nghĩa nào, thậm chí cả nguyên tử. Tương phản với biến thể đồng cấu bổ sung của ElGamal, biến thể này có những hạn chế nghiêm trọng về các số nguyên mà nó có thể thêm vào.

Có hai điều rõ ràng cần đề cập. Đầu tiên, với lời cảnh báo rằng tôi chỉ đọc lướt qua bài báo mà bạn đã liên kết, tôi thấy phần 3 nói rằng sơ đồ mã hóa được sử dụng cần 3 thuộc tính, cụ thể là

1. đồng hình phụ gia,

2. "so sánh bản rõ mô-đun", ví dụ: kiểm tra nếu $Enc(c)$ là một mã hóa của 0,

3. một giao thức tạo khóa phân tán.

sẽ dễ dàng hơn để trả lời câu hỏi này nếu bạn có thể chính thức hóa chính xác những hoạt động/thuộc tính nào bạn cần.

lưới dựa trên

Như đã nói, cho đến nay, loại sơ đồ mã hóa đồng hình một phần phổ biến nhất hiện nay là các biến thể mã hóa R(LWE). Tuy nhiên, điều này thỏa mãn một biến thể "ồn ào" của đồng cấu phụ gia, nghĩa là người ta chỉ có thể đánh giá một số giới hạn tiên nghiệm số đồng cấu cộng. Nếu bạn cần bổ sung tùy ý, điều này cũng có thể được thực hiện, ví dụ như lược đồ FHEW/TFHE có lẽ rất phù hợp cho việc này (lưu ý rằng đây là hoàn toàn đồng hình lược đồ mã hóa, mặc dù chúng là những lược đồ đặc biệt hiệu quả). Điều này hợp lý/có khả năng điều này là tốt trong trường hợp của bạn.

Đối với hai điểm còn lại, tôi cần đọc/biết rõ hơn các yêu cầu chính xác của chương trình. Mặc dù vậy, có vẻ hợp lý với tôi rằng các lược đồ mã hóa dựa trên RLWE có thể phù hợp với tình huống của bạn, nhưng tôi không bận tâm đến việc điền chi tiết vì...

El-Gamal dựa trên:

Trong khi bạn nói đúng rằng El-Gamal "cổ điển" (giả sử dựa trên trường hữu hạn Diffie Hellman) hơi lỗi thời, thì bạn có thể sử dụng El-Gamal dựa trên các nhóm đường cong elliptic. Điều này là "hiện đại" (mặc dù vẫn còn yếu so với máy tính lượng tử, nếu đây là mối quan tâm của bạn) và có thể dễ dàng hơn cho mục đích của bạn hơn là tìm ra chi tiết về cách sử dụng sơ đồ dựa trên mạng tinh thể. Lưu ý rằng đối với mã hóa chung có rất ít lý do để sử dụng các biến thể đường cong elip của El Gamal (xem ở đây để biết chi tiết), nhưng vì bạn đặc biệt muốn sử dụng đồng cấu phụ gia, nên sử dụng El Gamal sẽ hợp lý.

Nếu bạn phản đối việc sử dụng Đường cong Elliptic El Gamal vì một số lý do, thì các tùy chọn chính còn lại của bạn là các lược đồ dựa trên mạng tinh thể. Điều này sẽ đòi hỏi nhiều công việc hơn để tìm hiểu chi tiết, điều này sẽ dễ dàng hơn cho những người trên trang web này giúp bạn nếu bạn có thể nói chính xác những yêu cầu của bạn đối với sơ đồ mã hóa cơ bản.