Đây là một ý tưởng có thể đáp ứng tất cả các yêu cầu đã nêu của bạn. Bây giờ, nó không đáp ứng các yêu cầu mật mã hợp lý khác; tuy nhiên bạn không bao giờ yêu cầu họ.
Đây là ý tưởng: chúng tôi làm việc trong một nhóm Đường cong Elliptic có kích thước phù hợp (giả sử P224) với quy mô nhóm $q$ (là số nguyên tố) và chọn ba máy phát điện $F, G, H$ (với các mối quan hệ không xác định; có lẽ được tạo bằng phương pháp Hash2Curve); và:
$$f(X) = F + X$$
$$g(X) = G + X$$
$$h(X) = H + X$$
Những hoạt động này rõ ràng là đi lại, và chúng tôi có $f^i(g^j(h^k(X))) = iF + jG + kH + X$.
Đi qua các yêu cầu của bạn:
Nếu bây giờ $f,g,h$, được áp dụng $i,j,k$-lần cho một đầu vào $x$ tìm kiếm/tính toán $x$ cho đã cho $c = f^i(g^j(h^k(x)))$ nên càng khó càng tốt và với điều này mất nhiều hơn $O(|i|+|j|+|k|)$ các bước.
Tôi cho rằng, trong yêu cầu này, kẻ tấn công không biết các giá trị của $i, j, k$ (anh ấy biết phạm vi tương đối). Trong trường hợp đó, tìm kiếm tốt nhất tôi có thể tìm thấy để xác minh giá trị $c$ nhận $O( \sqrt{i \cdot j \cdot k } )$ thời gian (giả sử $i \cdot j \cdot k < q$, chắc chắn); cái này lớn hơn $O(i + j + k)$. Việc tìm kiếm này được thực hiện bằng cách lấy $0F, 1F, ..., iF$, $0G, 1G, ..., jG$, $0H, 1H, ..., kG$, chia chúng thành hai danh sách trong đó tổng của ba mục bất kỳ trong ba danh sách có thể được biểu thị bằng tổng của hai nếu các mục trong danh sách, sau đó áp dụng thuật toán kiểu 'bước lớn/bước nhỏ'.
Hơn nữa các phương pháp $f,g,h$ đang bảo toàn định dạng: $X \rightarrow X$, vì vậy mọi đầu ra có thể đóng vai trò là đầu vào mới.
Miễn là bạn mát mẻ với $X$ là tập hợp các điểm của đường cong elliptic, chúng ta ổn ở đây.
Kích thước tối đa phải là: $|X|<2^{256}$
Với P-224, điều này là đúng.
Tin học $f,g,h$ và nghịch đảo của chúng cần có thời gian tương tự cho mỗi đầu vào (không phụ thuộc vào $i,j,k$).
chúng tôi ổn ở đây
Hơn nữa $f,g,h$ phải tạo ra một chu kỳ như $f(f(....f(x)...))=x$ với kích thước $F,G,H$ với $F \approx G \approx H \gg 1$
Thật; $f, g, h$ tất cả đều có thứ tự $q$, lớn hơn nhiều so với 1
Bạn có thể dễ dàng chọn phạm vi cho $i, j, k$ để đảm bảo an ninh mục tiêu được đáp ứng.
Bây giờ, một điều mà ý tưởng này không cung cấp là, cho trước $c, x$ với $c = f^i(g^j(h^k(x)))$, nó là tầm thường để tính toán $c' = f^i(g^j(h^k(x'))))$. Tuy nhiên, bạn chưa bao giờ yêu cầu điều đó khó...
