înregistrare Logare
Puncte:3
avatar Crypto

Ce este o funcție hash criptografică eficientă în calculul λ?

drapel ca
MaiaVictor

Majoritatea funcțiilor hash sunt concepute pentru a fi rapide în procesoarele convenționale, dar există contexte în care numerele întregi ale mașinii fie nu există, fie nu sunt cea mai eficientă opțiune. De exemplu, circuitele zk-snark nu au acestea, iar brainfuck are doar increment și decrement. Dacă aveai nevoie de funcții hash rapide în aceste medii, este puțin probabil ca sha2/keccak/blake să funcționeze mai bine decât ceva conceput pentru ele.

Caut în special o funcție hash care este proiectată să fie eficientă pe calculul λ pur netipizat. Nu doar limbaje funcționale pure, care au de obicei numere întregi de mașină, ci și calculul λ pur, care are doar lambda și aplicații. Fără numere întregi native, cel mai bun pariu al nostru este să λ-codăm datele, astfel, cea mai puternică primitivă pe care o avem este potrivirea modelelor.Performanța unei funcții hash ar putea fi astfel măsurată, sau aproximată, prin cantitatea de potriviri de tipare pe care le efectuează. Întrebarea este: care sunt funcțiile hash simple care funcționează bine într-un astfel de context?

186
0 + 4
fgrieu avatar
drapel ng
fgrieu
Corectează-mă dacă greșesc, dar cred că nu știm dacă există o funcție criptografică în timp polinomial (securizat) în calculul λ obișnuit, cu atât mai puțin o astfel de funcție eficientă pentru orice definiție mai clară a eficientului. Ar urma că nu putem demonstra că există o astfel de funcție în orice restricție a calculului λ. Astfel, dacă putem răspunde la această întrebare cu certitudine, asta trebuie să fie negativ. Pentru puținul pe care îl înțeleg despre restricție, este atât de severă încât, intuitiv, nu există într-adevăr nimic de interes criptografic care este permis.
0
Răspunde
drapel ca
MaiaVictor
@fgrieu există totuși funcții criptografice în timp polinomial în λ-calcul. Ca exemplu practic, limbajul meu de programare [Kind](https://github.com/uwu-tech/kind) are o implementare a lui Keccak și se compilează în calculul λ. Desigur, atunci când țintiți calculul λ pur, performanța lui Keccak este groaznică, dar funcționează indiferent. Poate că ceea ce întreb ar fi mai familiar dacă l-aș reformula astfel: *"cât de eficient, cel mult, am putea implementa funcții hash, dacă am putea folosi doar tipurile de date Haskell și case-of (adică, fără inters native)?" * (Aceasta este o întrebare echivalentă.)
0
Răspunde
fgrieu avatar
drapel ng
fgrieu
Mă refer la: în afară de a presupune Pâ NP, nu avem nicio dovadă a existenței unei funcții hash criptografice securizate implementabile pe o mașină Turing (adică o familie hash care nu se poate distinge asimptotic de o familie de funcții aleatoare cu probabilitate de nedispășire de către oricare algoritm PPT). În cazul lui Keccak, nu cunosc o dovadă chiar dacă presupun Pâ NP.
0
Răspunde
drapel ca
MaiaVictor
@fgrieu oh, dar mă refeream la unul sigur echivalent cu Keccak, Sha2 și similar. Nu înțeleg totuși. Știu că nu există nicio dovadă că aceste funcții sunt de fapt sigure, dar care sunt criteriile folosite? Este doar: „amestecă destule bucăți și speră la ce e mai bun”? Funcțiile hash moderne sunt, în esență, doar algoritmi suficient de ascunși pentru ca nimeni să nu știe cum să le revină... încă?
0
Răspunde
Mark avatar
drapel ng
Mark
@MaiaVictor de obicei evaluează performanța construcției la atacuri cunoscute. Există și alte lucruri pe care le puteți face (să spunem să construiți un hash dintr-o funcție de compresie și să demonstrați că dacă funcția de compresie este bună, atunci hash-ul este bun).
0
Răspunde
Mark avatar
drapel ng
Mark
@MaiaVictor poți rezuma câteva operațiuni „standard” care sunt eficiente în calculul lambda pur netipizat? De exemplu, anumite operațiuni mai cunoscute care au „complexitate de potrivire a modelelor” scăzută
0
Răspunde
drapel romania
SEF 777
întrebarea această in alte limbi:

Postează un răspuns

Majoritatea oamenilor nu înțeleg că a pune multe întrebări deblochează învățarea și îmbunătățește legătura interpersonală. În studiile lui Alison, de exemplu, deși oamenii își puteau aminti cu exactitate câte întrebări au fost puse în conversațiile lor, ei nu au intuit legătura dintre întrebări și apreciere. În patru studii, în care participanții au fost implicați în conversații ei înșiși sau au citit transcrieri ale conversațiilor altora, oamenii au avut tendința să nu realizeze că întrebarea ar influența – sau ar fi influențat – nivelul de prietenie dintre conversatori.