Điểm:0

Có mật mã không.các phương pháp $f,g,h$ đi lại và tìm $x$ cho $c=f^ig^jh^k(x)$ khó hơn $O(i+j+k)$ nhưng chỉ với $

lá cờ at

Có phương pháp mật mã nào không $f,g,h$ có thể được áp dụng theo bất kỳ thứ tự nào cho đầu vào $x$ trong khi vẫn dẫn đến kết quả tương tự $r$: $$f(g(h(x)))=h(g(f(x)))=ghf(x)=fhg(x)=hfg(x)=gfh(x) = r$$

Tương tự cho hàm nghịch đảo của chúng: $$f^{-1}(g^{-1}(h^{-1}(r)))=h^{-1}(g^{-1}(f^{-1}(r )))=g^{-1}(h^{-1}(f^{-1}(r))) =...= x$$

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$ $$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.
Hơn nữa các phương pháp $f,g,h$ đang bảo toàn định dạng: $X \mapsto X$, vì vậy mọi đầu ra có thể đóng vai trò là đầu vào mới.
Số lượng các giá trị khác nhau $|X|$ nên càng nhỏ càng tốt trong khi vẫn duy trì bảo mật đầy đủ.
Kích thước tối đa phải là: $$|X| < 2^{256}$$


Các nút khác:
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$).

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$

Và ngẫu nhiên $x$ có thể được tạo mà không cần biết về tham số bí mật từ $f,g,h$ (đối thủ có quyền truy cập vào mã đang chạy).


Mục tiêu: Đưa ra hai ngẫu nhiên $x_1,x_2$ với $x_2=f^ig^jh^k(x_1)$ tính toán/tìm kiếm $i,j,k$ nên càng khó càng tốt trong khi số lượng khác nhau $x$ nên càng nhỏ càng tốt.
Không thích hợp hơn nhưng một số kết hợp của $x_1,x_2$ có thể không có bất kỳ $i,j,k$, phương pháp $f,g,h: X_d \mapsto X_d$ với $d<\xấp xỉ 10$

Bảo mật mục tiêu $\khoảng 2^{100}$ bước (= số lần tính toán của $f,g$ hoặc $h$ (hoặc tương đương)) cần thiết.
với hoàn hảo $f,g,h$ (nếu chúng tồn tại) thì chỉ cần $|X| \khoảng 2^{150}$ (ví dụ: giao điểm của đường $f^l(x_1)$ với bề mặt $g^mh^n(x_2)$)
(Đối thủ không có máy tính lượng tử)


câu hỏi liên quan: Nếu chúng ta bỏ qua kích thước miền tối đa $|X|<2^{256}$ câu trả lời của tôi câu hỏi rất giống nhau dẫn đến một lớn $|X|$ để tránh thừa số hóa. Tôi đang tìm kiếm một cái nhỏ nhất có thể $|X|$.

kodlu avatar
lá cờ sa
một số dấu ngoặc bị thiếu trong bộ tác phẩm đầu tiên
J. Doe avatar
lá cờ at
@kodlu ý bạn là 'ghf(x)' phải không? Tôi để lại chúng để có cái nhìn tổng quan hơn. Nếu họ đi lại với nhau thì sẽ không có gì khác biệt. Hoặc?
Điểm:1
lá cờ my

Đâ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ó...

dave_thompson_085 avatar
lá cờ cn
ITYM f, g, h đi làm không cam kết.
J. Doe avatar
lá cờ at
Bạn nói đúng, đó không phải là điều tôi thực sự đang tìm kiếm nhưng đó là câu trả lời cho câu hỏi được viết ra và cũng đã là một kế hoạch dự phòng khả thi Nếu tôi không tìm thấy điều gì tốt hơn. Lẽ ra tôi nên thêm các chuỗi $f,g,h$ đang tạo chứa các giá trị khác nhau hoặc chúng có thể tạo ra nhiều giá trị khác nhau cùng nhau hơn là một mình hoặc tích của kích thước chuỗi riêng lẻ của chúng phải gần bằng $|X|$. Hoặc ít nhất là trong trường hợp tốt nhất họ làm như vậy. Khó có thể bao gồm tất cả mà không viết một bản roman không ai đọc. Vì vậy, cảm ơn bạn đã trả lời một lần nữa.
J. Doe avatar
lá cờ at
'Miễn là bạn hài lòng với $X$ là tập hợp các điểm đường cong elip, thì chúng tôi vẫn ổn ở đây' -> Tôi ổn với mọi thứ có thể được tạo ngẫu nhiên mà không cần biết về tham số bí mật. Cũng tốt nếu một số thành viên của $X$ không thể được tạo ngẫu nhiên. ### 'Bây giờ, một điều mà ý tưởng này không cung cấp là, với $c$,$x$ với [..] -> Đó không phải là vấn đề, $i,j,k$ sẽ khác (gần như) mỗi lần . $c$ và $x$ được chọn ngẫu nhiên và $i,j,k$ có liên quan nên không xác định/khó tính toán.
J. Doe avatar
lá cờ at
Bạn có thể đưa ra một ghi chú ngắn tại sao lại là $O(\sqrt{i\cdot j \cdot k})$ không. Tôi nghĩ đó là $O(\sqrt{q})$ (và nếu chúng ta giả sử $q\equiv |X|$ và $f,g,h$ *không* tạo ra các giá trị giống nhau (và không thể chuyển sang nhau, vì vậy trường hợp sử dụng tốt nhất (theo như tôi biết))) sẽ là $O(|X|^\frac{2}{3})$)

Đăng câu trả lời

Hầu hết mọi người không hiểu rằng việc đặt nhiều câu hỏi sẽ mở ra cơ hội học hỏi và cải thiện mối quan hệ giữa các cá nhân. Ví dụ, trong các nghiên cứu của Alison, mặc dù mọi người có thể nhớ chính xác có bao nhiêu câu hỏi đã được đặt ra trong các cuộc trò chuyện của họ, nhưng họ không trực giác nhận ra mối liên hệ giữa câu hỏi và sự yêu thích. Qua bốn nghiên cứu, trong đó những người tham gia tự tham gia vào các cuộc trò chuyện hoặc đọc bản ghi lại các cuộc trò chuyện của người khác, mọi người có xu hướng không nhận ra rằng việc đặt câu hỏi sẽ ảnh hưởng—hoặc đã ảnh hưởng—mức độ thân thiện giữa những người đối thoại.