thuật toán băm mật mã phụ gia không thể đảo ngược

Tôi cần một hàm băm mật mã nhẹ có tính cộng nhưng không thể đảo ngược, tuy nhiên tôi không chắc có tồn tại hàm như vậy không! (sẽ tốt hơn nếu nó cũng hoạt động trong nhiều bộ)

Ý tôi là phụ gia: đưa ra chức năng như vậy f, chức năng khác g phải tồn tại, có tài sản g(f(X),f(Y))=f(X||Y), ở đâu || biểu thị nối các chuỗi X và Y.

Tôi đã tìm thấy một hàm băm đồng hình từ Facebook đó là phụ gia nhưng nó cũng có thể đảo ngược.

CHỈNH SỬA:

Bằng cách không thể đảo ngược, tôi không đề cập đến khả năng chống ảnh trước ngay cả khi tôi muốn có thuộc tính đó trong chức năng tổng thể.

tính không đảo ngược: Nếu chúng ta biết f(X||Y) và đó Y là một phần tử được sử dụng làm đầu vào, sẽ không thể tính được g^-1(f(X||Y),f(Y)) để có được f(X)

tái bútTôi đang cố gắng tìm một giải pháp đủ nhẹ và kháng lượng tử để hoạt động trong các thiết bị IoT

Bây giờ tôi đang vội, nhưng tôi muốn chia sẻ với bạn một số ý tưởng (nếu cần tôi sẽ trình bày chi tiết vào ngày hôm sau):

• nối có thể được xem như $x||y = xk+y$ ở đâu $k=2^{|y|}$
• Vì thế $f(x||y) = f(xk+y)$
• nếu chúng ta giả sử $f$ là phép nhân cho một máy phát điện EC $G$ (cài đặt khóa bí mật/pubkey phổ biến của EC) mà chúng tôi thu được:

$f(x) = Gx$

$f(y) = Gy$

$f(x||y) = G(xk+y) = G(xk) + Gy = G(x+x+...+x) + Gy = (Gx + Gx + ... + Gx) + Gy = kGx + Gy$

• đoạn văn cuối cùng mang lại cho bạn $g$ (một mối quan hệ tượng trưng bằng phép nối nhưng hiện đang hoạt động trên các điểm EC)

$f(x) = Gx$ tất nhiên không phải là một hàm băm, nhưng nó không thể đảo ngược (đó là vấn đề logarit rời rạc phổ biến) và với các định nghĩa đã nói ở trên, có vẻ như (nếu tôi không sai) phụ gia như bạn đã yêu cầu

CHỈNH SỬA: TỔNG HỢP

Như @poncho đã chỉ ra một cách cẩn thận, những ý tưởng trước đây chỉ hoạt động khi tất cả $y$ có kích thước cố định đã biết trước, vì điều này đảm bảo rằng $k$ là hằng số và có thể được sử dụng trong $g$ (không có "khả năng hiển thị trực tiếp" của $y$ để tính kích thước của nó). Cách giải quyết thông minh do @poncho đề xuất là để $f$ chuyển kích thước đầu vào của nó sang "giai đoạn tiếp theo". Vì vậy, các định nghĩa trước đây được khái quát hóa theo cách này:

• $x||y = xk+y$ ở đâu $k=2^{|y|}$ bất kể kích thước của $y$ Là
• $f(x) = (Gx, |x|) = (X, |x|)$
• $f(x||y) = f(xk+y) = (kX+Y,|x|+|y|) = (2^{|y|}X+Y,|x|+|y|) $
• $g((X,s_x),(Y,s_y)) = (2^{s_y}X+Y, s_x+s_y)$

Vẫn $f$ không phải là một hàm băm nhưng như đã nói trước đây, nó là chất phụ gia trong hương vị của bạn và không thể đảo ngược (kháng tiền ảnh đầu tiên trong thuật ngữ băm).