Имеют ли отношение асимптотические нижние оценки к криптографии?

Обычно считается, что асимптотическая нижняя граница, такая как экспоненциальная жесткость, подразумевает, что проблема является «изначально сложной». Шифрование, которое «по своей сути трудно» взломать, считается безопасным.

Однако асимптотическая нижняя граница не исключает возможности того, что огромный, но конечный класс проблемных примеров прост (например, все экземпляры с размером менее ). $10^{1000}$

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

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

Я полагаю, что были предложены другие функции люка, которые считаются NP-сложными (см. Связанный вопрос ), а некоторые могут даже иметь доказанную нижнюю границу. Мой вопрос более фундаментален: имеет ли значение асимптотическая нижняя граница? Если нет, то связана ли практическая безопасность любого криптографического кода с какой-либо асимптотической сложностью?

complexity-theory cryptography asymptotics Мика Бек
источник

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

Рафаэль

Ответы:

Я постараюсь дать частичный ответ, так как я не полностью осознаю, как эта проблема рассматривается всем крипто-сообществом (может быть, репост на crypto.SE ?).

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

$2^{1024}$

$G$ $O(|G|)$ $\text{P}=\text{NP}$ $O(\log |G|)$ $G$

Ран Г.
источник

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

Мика Бек