Этот вопрос возник в контексте криптографии, но ниже я представлю его с точки зрения теории сложности, поскольку здесь люди больше знакомы с последним. Этот вопрос связан с проблемами в NP, но не в Average-P / poly и неоднородности биения по Oracle Access . Неформальное утверждение: когда...
Большинство современных методов криптографии зависят от сложности факторизации чисел, являющихся произведением двух больших простых чисел. Насколько я понимаю, это сложно только до тех пор, пока метод, использованный для генерации больших простых чисел, не может быть использован в качестве ярлыка...
В работе Ади Шамира [1] за 1979 г. он показывает, что факторинг можно выполнить за полиномиальное число арифметических шагов . Этот факт был вновь подтвержден и поэтому привлек мое внимание в недавней работе Borwein and Hobart [2] в контексте программ прямой линии связи (SLP). Поскольку я был...
Википедия - SHA-2 говорит SHA-224 идентичен SHA-256, за исключением того, что: начальные значения переменных от h0 до h7 различны, и выход строится путем пропуска h7. RFC3874 - 224-битная односторонняя хэш-функция: SHA-224 говорит Использование другого начального значения гарантирует, что усеченное...
Вкратце: если предположить, что существуют односторонние перестановки , можем ли мы создать такую, которая не имеет люка? Больше информации: Односторонняя перестановка - это перестановка ππ\piкоторый легко вычислить, но трудно инвертировать (см. вики-тег с односторонним действием для более...
Я думал о следующем вопросе в разное время с тех пор, как увидел этот вопрос по криптографии . Вопрос Позволять рRRбыть отношением TFNP . Может ли случайный оракул помочь П / поли сломаться?рRRс ничтожной вероятностью? Более формально, \newcommand{\Pr}{\operatorname{Pr}}...
Как вы можете заставить партию быть честной (подчиняться правилам протокола)? Я видел некоторые механизмы, такие как обязательства, доказательства и т. Д., Но они просто не решают всей проблемы. Мне кажется, что структура дизайна протокола и такие механизмы должны выполнять свою работу. У...
Background––––––––––––––Background_\underline{\bf Background} В 2005 году Регев [1] представил проблему «Обучение с ошибками» (LWE) - обобщение проблемы «Обучение с ошибками». Предположение о сложности этой задачи для определенных вариантов параметров теперь лежит в основе доказательств...