Вопросы с тегом «security»

39
Является ли проблема целочисленной факторизации сложнее, чем факторизация RSA: ?

Это кросс-пост от math.stackexchange. Обозначим через FACT целочисленную задачу факторинга: для найдите простые числа и целые числа такие чтоp i ∈ N , e i ∈ N , n = ∏ k i = 0 p e i i .n ∈ N ,n∈N,n \in \mathbb{N},пя∈ N ,pi∈N,p_i \in \mathbb{N},ея∈ N ,ei∈N,e_i \in \mathbb{N},n = ∏Кя =...

34
Последствия факторинга в П?

Факторинг не известен как NP-полный. Этот вопрос задавался о последствиях факторинга, являющегося NP-полным. Любопытно, что никто не спрашивал о последствиях факторинга в P (возможно, потому что такой вопрос тривиален). Итак, мои вопросы: Какими будут теоретические последствия факторинга в P? Как...

28
Быстрое сокращение от RSA до SAT

Сегодня в блоге Скотта Ааронсона приведен список интересных открытых задач / задач по сложности. Один из них привлек мое внимание: Создайте публичную библиотеку из 3SAT-экземпляров, используя как можно меньше переменных и предложений, что может привести к значительным последствиям в случае ее...

27
Лотерея, в которой можно убедиться, что это честно

(Извините, если это хорошо известно.) Я хотел бы передать какой-то предмет одному из агентов, чтобы агент получил предмет с вероятностью . Существует ли криптографический (или другой) инструмент, позволяющий каждому агенту (и даже каждому наблюдателю) быть уверенным в том, что случайное рисование...

25
Аргументы в пользу существования односторонних функций

Я читал в нескольких статьях, что существование односторонних функций широко распространено. Может кто-то пролить свет на то, почему это так? Какие у нас аргументы в пользу существования односторонних...

25
Криптография без допущений - ищет обзор

Предположим, что и быстрый линейный алгоритм времени для SAT появится завтра. Внезапно RSA становится небезопасным, большая часть нашей современной системы связи сломана, и мы должны пересмотреть, как хранить секреты друг от друга.п= Nппзнак равноNпP = NP Вопрос: Существует ли хороший единый...

24
В чем разница между вторым прообразом и столкновением?

Википедия определяет вторую атаку прообразом как: учитывая фиксированное сообщение m1, найдите другое сообщение m2, такое что hash (m2) = hash (m1). Википедия определяет атаку столкновением как: найдите два произвольных разных сообщения m1 и m2, таких что hash (m1) = hash (m2). Единственное...

23
Признание узла как доказательство работы

В настоящее время биткойн имеет систему проверки работоспособности (PoW) с использованием SHA256. Другие хеш-функции используют графы доказательства работы системы, частичное обращение хеш-функций. Можно ли использовать проблему принятия решений в теории узлов, такую ​​как распознавание узлов, и...

23
Оценка процентиля среди распределенных узлов без раскрытия значений

Этот вопрос был перенесен из Cross Validated, потому что на него можно ответить на теоретической бирже информатики. Мигрировал 8 лет назад . У меня есть довольно уникальная проблема, которую я хочу решить, и я надеюсь, что кто-то здесь может дать мне некоторое представление о том, как лучше всего...

23
Действительно ли реализация алгоритма Шора в 2016 году действительно масштабируема?

Этот вопрос перенесен из Биржи стеков информатики, потому что на него можно ответить в Теоретической бирже информатики. Мигрировал 3 года назад . В научной статье 2016 года « Реализация масштабируемого алгоритма Шора » [ 1 ] авторы учитывают 15 с только 5 кубитами, что меньше «требуемых» 8 кубитов...

22
Учебный план: логические / формальные методы в безопасности

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

22
Может ли полностью гомоморфное шифрование использоваться для выполнения забытого кода?

Прочитав этот ответ некоторое время назад, я заинтересовался полностью гомоморфным шифрованием. Прочитав введение в диссертацию Джентри, я начал задаваться вопросом, может ли его схема шифрования использоваться для выполнения забытого кода, как определено в третьем абзаце. В полностью гомоморфной...

21
Разница между теорией и практикой безопасности и криптографии?

Какие интересные различия существуют между теорией и практикой безопасности и криптографией? Самым интересным, конечно, будут примеры, которые предлагают новые возможности для теоретических исследований, основанных на практическом опыте :). Ответы могут включать (но не ограничиваются ими): Примеры,...

20
Может ли какая-либо вычислительная задача быть преобразована в доказательство работы?

Казалось бы, бессмысленность майнинга криптовалюты подняла вопрос о полезных альтернативах, см. Эти вопросы на Bitcoin , CST , MO . Интересно, существует ли алгоритм, который может преобразовать практически любую вычислительную задачу (решение которой может быть эффективно проверено) в другую такую...

20
Почему модульное возведение в степень Монтгомери не рассматривается для использования в квантовом факторинге?

Хорошо известно, что модульное возведение в степень (основная часть операции RSA) является вычислительно дорогим, и, насколько я понимаю, метод модульного возведения в степень Монтгомери является предпочтительным методом. Модульное возведение в степень также заметно присутствует в алгоритме...

20
PPAD и Quantum

Сегодня в Нью-Йорке и во всем мире отмечается день рождения Христоса Пападимитриу. Это хорошая возможность задать вопрос об отношениях между классом сложности Christos PPAD (и его смежными классами) и квантовыми компьютерами. В своей знаменитой работе 1994 года Пападимитриу представил и...

20
Проводятся ли в настоящее время исследования по внедрению экстракторов случайности?

Проводились ли исследования по внедрению конструкций экстракторов случайности? Кажется, что доказательства экстрактора используют Big-Oh, оставляя возможность для больших скрытых констант, делая программные реализации потенциально нереальными. Некоторый контекст: я заинтересован в использовании...

20
Параллельные генераторы псевдослучайных чисел

Этот вопрос в первую очередь связан с практической проблемой разработки программного обеспечения, но мне было бы любопытно услышать, могли бы теоретики дать более глубокое понимание этого. Проще говоря, у меня есть симуляция Монте-Карло, которая использует генератор псевдослучайных чисел, и я хотел...

19
Существует ли лучшая нижняя граница для факторинга и дискретного логарифмирования?

Существуют ли ссылки, которые предоставляют подробности о нижних границах схем для конкретных сложных задач, возникающих в криптографии, таких как целочисленный факторинг, задача простого / составного дискретного логарифма и ее вариант над группой точек эллиптических кривых (и их абелевых...

19
Есть ли у криптографии термодинамические затраты?

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