Tham gia Đăng nhập
Điểm:3
avatar Crypto

Hàm băm mật mã hiệu quả trong phép tính λ là gì?

lá cờ ca
MaiaVictor

Hầu hết các hàm băm được thiết kế để hoạt động nhanh trong các bộ xử lý thông thường, nhưng có những trường hợp mà số nguyên máy không tồn tại hoặc không phải là tùy chọn hiệu quả nhất. Ví dụ, các mạch zk-snark không có những thứ này và brainfuck chỉ có tăng và giảm. Nếu bạn cần các hàm băm nhanh trên các môi trường này, thì không chắc rằng sha2/keccak/blake sẽ hoạt động tốt hơn một thứ được thiết kế cho chúng.

Tôi đặc biệt đang tìm kiếm một hàm băm được thiết kế để hoạt động hiệu quả trên λ-tính toán thuần túy chưa được nhập. Không chỉ các ngôn ngữ chức năng thuần túy, thường có số nguyên máy, mà còn là phép tính λ thuần túy thực tế, chỉ có lambdas và ứng dụng. Nếu không có số nguyên gốc, cách tốt nhất của chúng tôi là λ-mã hóa dữ liệu, do đó, nguyên hàm mạnh nhất mà chúng tôi có là so khớp mẫu.Do đó, hiệu suất của hàm băm có thể được đo lường hoặc tính gần đúng bằng số lượng khớp mẫu mà nó thực hiện. Câu hỏi đặt ra là: các hàm băm đơn giản hoạt động tốt trong bối cảnh như vậy là gì?

186
0 + 4
fgrieu avatar
lá cờ ng
fgrieu
Sửa lỗi cho tôi nếu tôi mắc lỗi, nhưng tôi nghĩ chúng ta không biết liệu có tồn tại một hàm mã hóa thời gian đa thức (an toàn) trong phép tính λ thông thường hay không, một hàm hiệu quả như vậy kém hơn nhiều đối với bất kỳ định nghĩa rõ ràng hơn nào về hiệu quả. Theo đó, chúng ta không thể chứng minh có một hàm như vậy trong bất kỳ giới hạn nào của λ-giải tích. Vì vậy, nếu chúng ta có thể trả lời câu hỏi này một cách chắc chắn, thì đó phải là câu phủ định. Đối với một chút ít hiểu biết của tôi về hạn chế, nó nghiêm trọng đến mức theo trực giác, thực sự không có bất kỳ điều gì đáng quan tâm về mật mã học được cho phép.
0
Hồi đáp
lá cờ ca
MaiaVictor
Tuy nhiên, @fgrieu có các hàm mã hóa thời gian đa thức trong λ-calculus. Ví dụ thực tế, ngôn ngữ lập trình của tôi [Kind](https://github.com/uwu-tech/kind) có triển khai Keccak và ngôn ngữ này biên dịch thành λ-calculus. Tất nhiên, khi nhắm mục tiêu vào phép tính λ thuần túy, hiệu suất của Keccak rất tệ, nhưng nó vẫn hoạt động bất kể. Có lẽ những gì tôi đang hỏi sẽ quen thuộc hơn nếu tôi diễn đạt lại thành: *"chúng ta có thể triển khai các hàm băm hiệu quả đến mức nào nếu chúng ta chỉ có thể sử dụng các kiểu dữ liệu Haskell và trường hợp (nghĩa là không có số nguyên gốc)?" * (Đó là một câu hỏi tương đương.)
0
Hồi đáp
fgrieu avatar
lá cờ ng
fgrieu
Tôi đang đề cập đến: ngoài việc giả sử Pâ NP, chúng tôi không có bằng chứng về sự tồn tại của hàm băm mật mã an toàn có thể thực hiện được trên máy Turing (đó là họ hàm băm không thể phân biệt một cách tiệm cận với họ hàm ngẫu nhiên với xác suất không biến mất bởi bất kỳ thuật toán PPT). Trong trường hợp của Keccak, tôi không biết chứng minh ngay cả khi giả sử Pâ NP.
0
Hồi đáp
lá cờ ca
MaiaVictor
@fgrieu ồ, nhưng ý tôi là một thứ an toàn tương đương với Keccak, Sha2 và tương tự. Tôi không nhận được nó mặc dù. Tôi biết không có bằng chứng nào cho thấy các chức năng này thực sự an toàn, nhưng tiêu chí được sử dụng là gì? Có phải chỉ là: "trộn đủ bit và hy vọng điều tốt nhất"? Có phải các hàm băm hiện đại về cơ bản chỉ là các thuật toán bị che khuất đủ để không ai biết cách hoàn nguyên chúng ... chưa?
0
Hồi đáp
Mark avatar
lá cờ ng
Mark
@MaiaVictor thường đánh giá hiệu suất của công trình đối với các cuộc tấn công đã biết. Ngoài ra còn có những việc khác mà người ta có thể làm (giả sử xây dựng hàm băm từ hàm nén và chứng minh rằng nếu hàm nén tốt thì hàm băm cũng tốt).
0
Hồi đáp
Mark avatar
lá cờ ng
Mark
@MaiaVictor, bạn có thể tóm tắt một số thao tác "tiêu chuẩn" hiệu quả trong phép tính lambda chưa được gõ thuần túy không? Ví dụ: một số hoạt động được biết đến nhiều hơn có "độ phức tạp khớp mẫu" thấp
0
Hồi đáp
lá cờ VietNam
Phan Văn Trường
Câu hỏi này là trong các ngôn ngữ khác:

Đă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.