4) Вполне реалистично было бы предположить, что нарушитель имеет доступ лишь к ограниченным вычислительным ресурсам. Как и в криптографии достаточно потребовать, чтобы стегосистема выдерживала бы все полиномиальные тесты по ее обнаружению. Этот момент также не учитывают информационно-теоретические модели.
Рассмотрим модель стегосистемы, предложенную в работе [20]. Предположим, что имеется множество возможных контейнеров 
, элементы которого 
порождаются некоторым полиномиальным алгоритмом. Встраиваемое сообщение 
, выбирается из множества возможных сообщений 
. Стегосистема определяется тройкой 
полиномиальных алгоритмов.
Алгоритм 
. В соответствие с принципом Керхгофа стойкость зависит от ключа, а его длина является параметром секретности стегосистемы. Алгоритм 
, и 
. Алгоритм 
. Для определения наличия стегосистемы нарушитель должен решить следующую задачу:
на основе контейнера определить, существует ли ключ , порождаемый такие, что 
.
Интересно отметить, что если на структуру скрытого сообщения не накладывается никаких ограничений, то для многих стегосистем эта задача неразрешима. В самом деле, любая комбинация бит может быть вложением, и даже если нарушитель каким-то образом и заподозрит наличие скрытой связи, все равно ему невозможно будет доказать это третьей стороне. Поэтому, в работе [20] на структуру скрытого сообщения накладывается ограничение: оно должно иметь какой-то семантический смысл.
Далее, считается, что у нарушителя имеется стегосистема в виде «черного ящика», то есть он имеет возможность порождать стего из выбираемых им контейнеров и скрытых сообщений, не зная при этом ключа. Для этой цели у него имеется два оракула: один для генерации пустых контейнеров (стеганографический оракул), другой — для получения из них стего, то есть имитации алгоритма внедрения (оракул оценки). Так как оба оракула вероятностные, то в случае выбора первым оракулом несколько раз подряд одного и того же контейнера, стего будут получаться различными. Это помогает нарушителю выяснять структуру алгоритма внедрения, выбрав в качестве контейнера, например, однотоновое изображение.
Атака (игра) заключается в следующем. Нарушитель имеет неоднократную возможность генерировать контейнеры и соответствующие им стего, пытаясь выяснить структуру стегоалгоритма. При этом имеется то ограничение, что вся процедура должна быть полиномиальной по длине ключа и размеру контейнера. После того, как он закончил работу, ему предъявляются два случайно выбранных контейнера: один пустой, другой — заполненный. Стегосистема называется условно стойкой, если у нарушителя нет возможности правильного определения стего с вероятностью, незначительно отличающейся от 1/2. В работе [20] дано определение понятия «незначительно отличающейся» и приведено математическое описание вербально изложенной выше модели. Условно стойкая стегосистема сохраняет это свойство для всех возможных ключей и всех возможных контейнеров.
Ясно, что понятие условно стойкой стегосистемы более слабое, чем понятие стегосистемы, стойкой с информационо-теоретической точки зрения и включает ее как частный случай. Безусловно стойкая стегосистема в приведенной выше модели получается в случае, если снять ограничение полиномиальности во времени игры.
Каким образом построить условно стойкую стегосистему? Одна из возможностей, широко используемая и в криптографии, заключается во взятии за основу какой-нибудь трудной в вычислительном смысле математической задачи, например, обращение односторонней функции (разложение на множители, дискретное логарифмирование и т. д.). Тогда останется показать связь между невозможностью решения этой задачи и невозможностью вскрытия стегосистемы — и условно стойкая стегосистема построена. Из криптографии известно, что, к сожалению, вопрос построения доказуемо односторонней функции нерешен. В работе [20] показано, как можно построить стегосистему на основе известного криптоалгоритма RSA.
4.6. Имитостойкость системы передачи скрываемых сообщений
Ранее была исследована стойкость стегосистем к попыткам пассивного нарушителя установления факта скрытия передаваемых сообщений. Дополнительно к требованиям скрытности связи могут предъявляться требования по исключению навязывания в стегоканале ложных сообщений активным нарушителем. Например, в работе Г.Симмонса описана так называемая задача заключенных [6]. В этой задаче арестованные Алиса и Боб пытаются по скрытому каналу связи договориться о побеге. Тюремщик Вилли пытается не только обнаружить факт обмена информации, но и от имени Алисы навязать Бобу ложную информацию. Потому рассмотрим особенности построения стегосистем с возможностью аутентификации передаваемых сообщений, возможные атаки нарушителя и определим оценки имитостойкости стегосистем.
Формально опишем построение стегосистемы с аутентификацией скрытно передаваемых сообщений. Пусть стегосистема использует секретный ключ, принимающий значения 
Множество контейнеров 
каждое из которых описывается своим вероятностным распределением 
Поставим подмножества 
контейнеров в соответствие секретным ключам 
При действующем ключе аутентификации 
сообщение, доставленное по каналу скрытой связи, считается получателем подлинным, если оно вложено в контейнер, принадлежащий подмножеству с распределением 
Если при действующем ключе заполненный контейнер не принадлежит подмножеству , то извлеченное из него сообщение признается получателем ложным. Таким образом, при действующем ключе все множество контейнеров разделено на допустимые, в которых подлинность вложенных в них сообщений признается получателем, и недопустимые, которые не могут быть выбраны для передачи отправителем скрываемых сообщений. Следовательно, получение таких контейнеров с вложенными сообщениями означает, что они навязаны нарушителем.
Если принятое стего 
, совпадающее с распределением 
множества допустимых контейнеров при действующем ключе , то функция проверки подлинности скрываемых в них сообщений 
принимает единичное значение и полученное сообщение признается подлинным, а если распределения не совпадают, то функция принимает нулевое значение и сообщение отвергается как имитонавязанное:
Функция проверки подлинности при построении стегосистемы с аутентификацией сообщений может быть задана аналитически, графически или в виде таблицы. При аналитическом задании каждому значению ключа ставится в соответствие свое подмножество допустимых контейнеров. Эти подмножества отличаются друг от друга законами распределения или их параметрами. Например, используются различные распределения вероятностей непрерывных контейнеров (нормальное, Райса, Накагами и
