Paillier là một mật mã bảo mật CPA, do đó, bất cứ điều gì chúng ta có thể suy ra từ các bản mã đều yêu cầu khóa riêng. Vì vậy, "Tôi muốn tìmâ¦" yêu cầu "Tôi" có khóa riêng và sau đó "Tôi có một mảng được mã hóa" ngụ ý rằng "Tôi" có thể giải mã từng bản mã, điều này khiến câu hỏi như đã nêu trở thành tranh luận.
Do đó, chúng tôi sẽ thay đổi tuyên bố vấn đề thành: chúng tôi có nhiều nhất $k$ số nguyên nhỏ $m_i\in[0,\ell)$ (trong vấn đề hiện tại, chúng tôi muốn $k\ge6$, và $\ell>20$); và chúng tôi muốn một phương thức công khai để thể hiện những $m_i$ được mã hóa dưới dạng $c_i$ sử dụng Hệ thống mật mã Paillier và kết hợp $c_i$ thành một $c$ như chúng tôi làm ở Paillier. Đó là làm sản phẩm theo modulo $n$ sau đó $c_i$, và tùy ý nhân modulo $n$ bằng một bản mã cho $0$ để tiếp tục che giấu kết quả. Chúng tôi muốn mọi thứ để một người nắm giữ khóa riêng tư có thể xác định từ $c$ nếu $0$ đã có mặt trong tập dữ liệu ban đầu của $m_i$. Điều đó thay đổi hai điều quan trọng trong tuyên bố vấn đề ban đầu:
- Có khái niệm về việc kết hợp các bản mã $c_i$ vào trong $c$, với $c_i$ không có sẵn cho người giữ khóa riêng.
- Chúng tôi không "có một mảng được mã hóa". Chúng tôi muốn có một cái, nhưng có thể tự do xác định cách nó được tạo ra, miễn là nó có mã hóa sử dụng Paillier. Không có sự tự do như vậy, sẽ không có giải pháp nào, bởi vì việc giải mã Paillier sẽ chỉ cho phép một người có được $m=(\sum m_i)\bmod n$ và không có cách nào để nói từ đó nếu một $m_i$ là $0$.
Đây là một cái gì đó mà chúng ta sẽ không chỉ biết nếu $0$ đã có mặt trong $m_i$, chúng ta cũng sẽ biết mỗi số nguyên trong $[0,\ell)$ đã có mặt trong mảng ban đầu.
Hướng tới điều này, chúng tôi mã hóa $m_i$ vào trong $m'_i=(k+1)^{m_i}$ trước khi áp dụng mã hóa Paillier. Paillier sẽ cho phép chúng tôi kết hợp các bản mã $c_i$ sau đó giải mã sự kết hợp $c$ vào trong $m'=(\sum m'_i)\bmod n$. Từ $m'$ chúng ta có thể suy ra bao nhiêu lần mỗi số nguyên trong $[0,\ell)$ đã có mặt trong $m_i$, miễn là $k(k+1)^{\ell-1}<n$, bằng cách thể hiện $m'$ ở cơ sở $k+1$ và nhìn vào các chữ số / tay chân. Tôi sẽ bỏ qua phần đại số để biết cách làm và sử dụng một ví dụ ở dạng thập phân (do đó $k=9$). $m_0=2$, $m_1=4$, $m_2=5$, $m_3=10$, $m_4=0$, $m_5=20$ mã hóa thành $m'_0=100$, $m'_1=10000$, $m'_2=100000$, $m'_3=10000000000$, $m'_4=1$, $m'_5=0$, $m'_6=100000000000000000000$ ở dạng thập phân. chúng tôi sẽ nhận được $m'=1000000000010000110101$, từ đó chúng ta có thể biết có chính xác một trong mỗi $0$, $2$, $4$, $5$, $10$, $20$ trong mảng ban đầu của $m_i$, bằng cách nhìn vào vị trí của các chữ số khác không và thấy chúng là $1$. Nếu $20$ đã được đổi thành $0$, kết quả sẽ là $m'=10000110102$ và chúng tôi biết có hai $m_i=0$, vì chữ số ngoài cùng bên phải là $2$.
Câu hỏi không nói lên điều chúng ta đừng muốn người nắm giữ khóa riêng có thể xác định từ $c$. Có lẽ chúng tôi muốn hạn chế điều đó để xác định xem có một $0$, với ít rò rỉ về bao nhiêu $0$ càng tốt.
Hướng tới điều này, chúng ta có thể mã hóa từng $m_i\ne0$ đến $m'_i=0$, và mỗi $m_i=0$ đến một số nguyên $m'_i$ Trong $[1,\lsàn n/k\rsàn)$ được chọn ngẫu nhiên với phân phối thiên về các giá trị thấp. Khi giải mã kết hợp bằng 0, người ta biết rằng không có số 0 trong $m_i$, và không có gì khác. Mặt khác, người ta biết rằng có một số 0 và ít thông tin về số lượng bị rò rỉ. Việc phân phối có thể được tối ưu hóa để giảm thiểu sự rò rỉ đó, đây là một bài tập cho người đọc.
Có thể tinh chỉnh mọi thứ sao cho một thứ có khóa riêng và $c_i$ có thể tìm $m_i$, nhưng (như trên) một với khóa riêng và $c$ có thể nhận được ít thông tin về $m_i$, ngoài cái đó là $0$. Tôi sẽ không nêu chi tiết vì điều đó không có trong báo cáo vấn đề.
Giống như nhiều thứ mã hóa đồng hình, đây là những hệ thống lý thuyết hay với ít vấn đề thực tế phù hợp.
