Криптографическая логика

Nefertyty

В криптографии используются такие свойства некоторых преобразований, которые делают обратные преобразования невозможными на практике.
Например, односторонняя функция - это такая f, что для любого a существует x такой, что f(x)=a, но этот x нельзя вычислить (кроме случаев, если мы его заранее знали). То есть с точки зрения обычной математической логики x совершенно точно существует, с точки зрения конструктивной логики тоже всё нормально: существует алгоритм для нахождения х.
То есть, нужна какая-то формальная логика, которая бы умела работать с такими объектами, которые существуют, но не могут быть указаны. Например, для формального анализа криптопротоколов, в предположении о надёжности используемых шифров.
Видел идею, что "нельзя практически посчитать" - это значит алгоритм NP-сложен. Мне она не нравится по ряду причин:
1) вместо одной функции нужно рассматривать счётное семейство, а если его нет?
2) не доказано, что NP != P
3) алгоритм не обязан быть NP-сложным для того, чтобы вычисление было недопустимо долгим.
Может кто слышал про такую логику и назовёт ключевые слова, чтоб поискать статьи/книжки?

BSCurt

Хотя я тут и дилетант полный, но мне кажется тебе действительно странного и неразумного хочется.
То есть, нужна какая-то формальная логика, которая бы умела работать с такими объектами, которые существуют, но не могут быть указаны.
Тут же не теоремы чистого существования, объекты существуют и могут быть построены и указаны.
В общем ничего умнее вычислительной сложности, которую ты отмел, в уме не возникает.

Nefertyty

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

BSCurt

А ну теперь понятней, но разве от такого уровня абстрагирования не станут все криптографические системы практически идентичны.
нагуглилось что-то, хотя и не то, http://en.wikipedia.org/wiki/One-way_function

Nefertyty

> разве от такого уровня абстрагирования не станут все криптографические системы практически идентичны
ну как раз останутся существенные части
а конкретные алгоритмы часто подключаются плагинами - от них можно абстрагироваться

Jusun

Тебе нужно не это? http://en.wikipedia.org/wiki/Homomorphic_encryption
Подчасть Fully Homomorphic encryption.

stm7543347

Невычислимая булева функция? :spy:

c3po

В криптографии используются такие свойства некоторых преобразований, которые делают обратные преобразования невозможными на практике.
Неверно. Они осуществимы, но с такими ограничениями, что во многих случаях неактуальны.
Грубо говоря, есть 4 фактора
А — сколько стоят ресурсы для обратного преобразования;
Б — сколько времени оно займет;
В — сколько можно получить выгоды от узнавания зашифрованной информации;
Г — через какое время эта выгода превратится в пшик;
Эти факторы оцениваются в некоторых унифицированных попугаях, после чего смотрят на отношение (A*Б)/(В*Г). Односторонние функции, при правильном применении, позволяют обеспечить то, что, для подавляющего большинства практических ситуаций, это отношение будет больше 1. Ну, или, сделать A сильно дороже применения паяль^W социальной инженерии.
А так на практике многое возможно, растяжимое она понятие.

natunchik

То есть, нужна какая-то формальная логика, которая бы умела работать с такими объектами, которые существуют, но не могут быть указаны.
Может, есть смысл покопать в сторону теории вычислимости с оракулами? Типа, полиномиальный алгоритм с квантовым оракулом, постоянно используется например.

Nefertyty

Грубо говоря, есть 4 фактора
А — сколько стоят ресурсы для обратного преобразования;
Б — сколько времени оно займет;
В — сколько можно получить выгоды от узнавания зашифрованной информации;
Г — через какое время эта выгода превратится в пшик;
Эти факторы оцениваются в некоторых унифицированных попугаях, после чего смотрят на отношение (A*Б)/(В*Г). Односторонние функции, при правильном применении, позволяют обеспечить то, что, для подавляющего большинства практических ситуаций, это отношение будет больше 1. Ну, или, сделать A сильно дороже применения паяль^W социальной инженерии.
Ну в отличие от того, про что я спрашиваю, это рассуждение есть в каждой детской книжке, я их читал, да.

Nefertyty

А без асимптотических свойств нельзя? Потому что если с ними, то нужно счётное семейство функций вместо одной, а это вроде неудобно (ну и опять же P ?= NP). Хотя, возможно, логика и с этим может справиться - типа формальное правило преобразований, чтоб из высказывание про семейство сделать высказывание про конкретный протокол, и наоборот.

c3po

Ну, в первом-то посте как раз на уровне детского сада рассуждения, вот и не признала, простите.
Если хотелось строгости и взрослости, то Oded Goldreich, The Foundations of Cryptography должен полностью удовлетворить. Драфты бесплатно выложены, вполне читабельны.

Nefertyty

полистал драфты, благодарю
короче определения всяческих функций там через вычислительную сложность и полиномы, то есть функции действуют на словах произвольной длины
а те вопросы, которые я тут поднимаю, рассматриваются, как я понял, неформально - хотя я просмотрел по диагонали и может быть чего-то не заметил
посмотрю ещё список литературы, может там что есть

c3po

Не дочитал. Протоколы и схемы там определяются как раз через нетривиальные модификации машин Тьюринга с оракулами(второй том). И да, если глаз зацепился за неформальные объяснения, то стоит смотреть в середину/конец той же главы. Там итеративная подача материала — сначала в общих чертах, затем изложение по всей строгости.
Оставить комментарий
Имя или ник:
Комментарий: