Вопросы с тегом «cr.crypto-security»

18
Можно ли проверить, является ли вычислимое число рациональным или целым?

Можно ли алгоритмически проверить, является ли вычисляемое число рациональным или целым? Другими словами, возможно ли для библиотеки, которая реализует вычислимые числа, предоставлять функции isIntegerили isRational? Я предполагаю, что это невозможно, и что это как-то связано с тем, что невозможно...

17
Можно ли зашифровать CNF?

Можно ли преобразовать CNF в другой CNF такой, чтобыCC\mathcal CΨ(C)Ψ(C)\Psi(\mathcal C) Функция может быть вычислена за полиномиальное время из некоторого секретного случайного параметра .ΨΨ\Psirrr Ψ(C)Ψ(C)\Psi(\mathcal C) имеет решение тогда и только тогда, когда имеет решение.CC\mathcal C Любое...

17
Используются ли теоретически обоснованные псевдослучайные генераторы на практике?

Насколько мне известно, большинство реализаций генерации псевдослучайных чисел на практике используют такие методы, как регистры обратной связи с линейным сдвигом (LSFR) или эти алгоритмы "Mersenne Twister". Хотя они проходят множество (эвристических) статистических тестов, нет никаких...

16
О состоянии обучаемости внутри

Я пытаюсь понять сложность функций, которые можно выразить через пороговые элементы, и это привело меня к . В частности, мне интересно, что в настоящее время известно об обучении в , так как я не эксперт в этой области.TC0TC0\mathsf{TC}^0TC0TC0\mathsf{TC}^0 На данный момент я обнаружил, что: Все из...

16
Классы сложности для доказательства знаний

В ответ на вопрос, заданный мне Грегом Купербергом, мне интересно, есть ли какие-нибудь статьи, которые определяют и изучают классы сложности языков, допускающие различные виды доказательств знания . Такие классы, как SZK и NISZK, являются чрезвычайно естественными с точки зрения сложности, даже...

16
Хеширование паролей с использованием проблем с NP

Обычно используемые алгоритмы хэширования паролей работают сегодня так: солить пароль и подавать его в KDF. Например, используя PBKDF2-HMAC-SHA1, процесс хеширования пароля DK = PBKDF2(HMAC, Password, Salt, ...). Поскольку HMAC представляет собой двухэтапное хеширование с дополненными клавишами, а...

16
Есть ли у «односторонних функций» какие-либо приложения вне криптографии?

Функция f:{0,1}∗→{0,1}∗f:{0,1}∗→{0,1}∗f \colon \{0, 1\}^* \to \{0, 1\}^* является односторонней, если fff может быть вычислена с помощью алгоритма полиномиального времени, но для каждого рандомизированного алгоритма полиномиального времени AAA,...

16
Какова мотивация определения псевдослучайного в Nisan / Wigderson?

Я читаю классическую «Твердость против случайности» Нисана и Вигдерсона. Пусть и исправим функцию . Они определяют семейство функций как псевдослучайное в случае, если для каждой схемы размера мы имеемl : N → N G = { G n : B l ( n ) → B n }B={0,1}B={0,1}B=\{0,1\}l:N→Nl:N→Nl\colon \mathbb{N} \to...

16
Приводит ли битовое обязательство к переносной передаче в теоретико-информационной модели безопасности?

Предположим, у вас есть два произвольно влиятельных участника, которые не доверяют друг другу. У них есть доступ к обязательству по битам (например, запечатанные конверты, содержащие данные, которые один игрок может передать другому, но которые нельзя открыть, пока первый игрок не даст второму...

16
Где недостаток в методе Блюма-Фельдмана-Микали

Блум, Микали и Фельдман (BFM) выдвинули новую (криптографическую) модель, в которой все стороны (честные или состязательные) имеют доступ к некоторой строке. Предполагается, что строка выбирается в соответствии с некоторым распределением (обычно равномерным) доверенной стороной. Это называется...

14
Гарантии твердости для AES

Многие криптосистемы с открытым ключом имеют доказуемую безопасность. Например, криптосистема Рабина доказуемо так же сложна, как и факторинг. Интересно, существует ли такая доказуемая безопасность для криптосистем с секретным ключом, таких как AES. Если нет, то каковы доказательства того, что...

14
Генерация графов с тривиальными автоморфизмами

Я пересматриваю некоторую криптографическую модель. Чтобы показать его неадекватность, я разработал искусственный протокол, основанный на изоморфизме графа. Это «обычное дело» (еще спорный!) Предположить существование BPP алгоритмов способны генерировать «жесткие экземпляры проблемы Изоморфизма...

14
Лучший метод исправления ошибок в квантовом распределении ключей

Насколько я могу судить, почти во всех реализациях QKD для исправления ошибок используется алгоритм CASCADE Brassard и Salvail . Действительно ли это самый известный метод исправления ошибок в общей последовательности случайных кубитов, или есть лучшее предложение, которое вместо этого следует...

14
Ассоциативное смешивание хешей

Рассмотрим простой односвязный список в чисто функциональной обстановке. Его похвалы пели с горных вершин и будут продолжать петь. Здесь я расскажу об одной из его сильных сторон и о том, как ее можно распространить на более широкий класс чисто функциональных последовательностей, основанных на...

13
Исчерпывающий симулятор протоколов нулевого знания в модели случайного Oracle

В статье под названием «Об отрицании в общей эталонной строке и случайной модели Oracle» Рафаэль Пасс пишет: Мы отмечаем, что при проверке безопасности в соответствии со стандартным определением нулевого знания в модели RO [Random Oracle], симулятор имеет два преимущества по сравнению с симулятором...

13
Какие языки были успешно криптографически захвачены?

Наблюдение, связанное с асимметричной криптографией, заключается в том, что некоторые функции (как полагают) легко выполнять в одном направлении, но трудно инвертировать. Кроме того, если существует некоторая информация о «ловушке», которая позволяет быстро вычислять обратную операцию, тогда...

12
Почему Фейге-Фиат-Шамир не является Нулевым Знанием без знаковых битов?

В главе 10 HAC (10.4.2) мы видим хорошо известный протокол идентификации Фейге-Фиат-Шамира, основанный на доказательстве с нулевым знанием, использующем (предполагаемую) сложность извлечения квадратных корней по модулю композита, который трудно проанализировать. Я дам схему своими словами (и,...

12
Что особенного в

В алгоритме Tiny Encryption : Различные кратные магической константы используются для предотвращения простых атак, основанных на симметрии раундов. Магическая постоянная, 2654435769 или 9E3779B9 16 , выбрана равной 232/ ϕ232/ϕ2^{32}/ \phi , где ϕ - золотое сечение. Какими свойствами обладает 232/...

12
Какие примеры секретных схем совместного использования фактически используются в реальных приложениях?

Концепция секретной схемы обмена часто приписывается Шамиру (A. Shamir, Как поделиться секретом , Comm. ACM, 22 (1979), pp. 612-613.) И Blakey (GR Blakey, Защита криптографических ключей , в Proc. NCC, vol. 48, 1979, pp. 313-317.). Общая идея заключается в том, что какой-то секрет S скрыт от...