Регистрация Войти
Рейтинг:3
avatar Crypto

Что такое эффективная криптографическая хэш-функция в λ-исчислении?

флаг ca
MaiaVictor

Большинство хеш-функций предназначены для работы в обычных процессорах, но есть ситуации, когда машинные целые числа либо не существуют, либо не являются наиболее эффективным вариантом. Например, в схемах zk-snark их нет, а в brainfuck есть только инкремент и декремент. Если вам нужны быстрые хеш-функции в этих средах, маловероятно, что sha2/keccak/blake будет работать лучше, чем то, что предназначено для них.

Я особенно ищу хеш-функцию, разработанную для эффективной работы с чистым нетипизированным λ-исчислением. Не просто чистые функциональные языки, в которых обычно используются машинные целые числа, а настоящее чистое λ-исчисление, в котором есть только лямбда-выражения и приложения. Без нативных целых чисел лучше всего использовать λ-кодирование данных, поэтому самый мощный примитив, который у нас есть, — это сопоставление с образцом.Таким образом, производительность хэш-функции может быть измерена или приблизительно определена количеством совпадений с образцом, которые она выполняет. Вопрос в том, какие простые хеш-функции хорошо работают в таком контексте?

186
0 + 4
fgrieu avatar
флаг ng
fgrieu
Поправьте меня, если я ошибаюсь, но я думаю, что мы не знаем, существует ли (безопасная) криптографическая функция с полиномиальным временем в обычном β-исчислении, а тем более эффективная такая функция для любого более точного определения эффективности. Отсюда следует, что мы не можем доказать, что существует одна такая функция в любом ограничении λ-исчисления. Таким образом, если мы можем с уверенностью ответить на этот вопрос, то это должно быть отрицательным. Что касается того немногого, что я понимаю об этом ограничении, то оно настолько серьезно, что интуитивно понятно, что действительно нет ничего, что представляло бы криптографический интерес.
0
Ответить
флаг ca
MaiaVictor
@fgrieu, однако, в λ-исчислении есть криптографические функции с полиномиальным временем. В качестве практического примера, мой язык программирования [Kind] (https://github.com/uwu-tech/kind) имеет реализацию Keccak и компилируется в λ-исчисление. Конечно, при работе с чистым λ-исчислением производительность Keccak ужасна, но тем не менее она работает. Возможно, то, о чем я спрашиваю, было бы более знакомым, если бы я перефразировал это так: * «насколько максимально эффективно мы могли бы реализовать хэш-функции, если бы мы могли использовать только типы данных Haskell и case-of (т. е. без родных целых чисел)?» * (Это эквивалентный вопрос.)
0
Ответить
fgrieu avatar
флаг ng
fgrieu
Я имею в виду: за исключением предположения P-NP, у нас нет доказательств существования безопасной криптографической хэш-функции, реализуемой на машине Тьюринга (то есть хеш-семейства, асимптотически неотличимого от семейства случайных функций с ненулевой вероятностью любым Алгоритм РРТ). В случае с Кеччаком я не знаю доказательства, даже если предположить, что P-NP.
0
Ответить
флаг ca
MaiaVictor
@fgrieu о, но я имел в виду тот, который эквивалентно безопасен для Keccak, Sha2 и подобных. Я не понимаю, хотя. Я знаю, что нет доказательств того, что эти функции действительно безопасны, но тогда какие критерии используются? Это просто: «смешайте достаточно кусочков и надейтесь на лучшее»? Являются ли современные хэш-функции по сути просто алгоритмами, достаточно скрытыми, чтобы никто не знал, как их вернуть... пока?
0
Ответить
Mark avatar
флаг ng
Mark
@MaiaVictor обычно оценивает производительность конструкции при известных атаках. Есть и другие вещи, которые можно сделать (скажем, построить хэш из функции сжатия и доказать, что если функция сжатия хороша, то и хэш хорош).
0
Ответить
Mark avatar
флаг ng
Mark
@MaiaVictor, не могли бы вы обобщить некоторые «стандартные» операции, которые эффективны в чистом нетипизированном лямбда-исчислении? Например, некоторые более известные операции с низкой «сложностью сопоставления с образцом».
0
Ответить
флаг Moldova
Admin
Этот вопрос на других языках:

Ответить или комментировать

Большинство людей не понимают, что склонность к познанию нового открывает путь к обучению и улучшает межличностные связи. В исследованиях Элисон, например, хотя люди могли точно вспомнить, сколько вопросов было задано в их разговорах, они не чувствовали интуитивно связи между вопросами и симпатиями. В четырех исследованиях, в которых участники сами участвовали в разговорах или читали стенограммы чужих разговоров, люди, как правило, не осознавали, что задаваемый вопрос повлияет — или повлиял — на уровень дружбы между собеседниками.