Однонаправленная функция с секретом на базе КАМСИ




Условия сохраняемости (lossiness) информации


Машина, которая не сохраняет информацию называется не сохраняющей (lossy) информацию. 

Простой пример не сохраняющей машины – это такая, в которой для некоторого состояния Si

и двух отличных входных символов Ip  и IqIp- и  Iq-преемники и соответствующие им выходы идентичны. Ясно, что в таком случае знание выхода, начального и конечного состояния не достаточно, чтобы определить, какой из Ip ,Iq были поданы на вход машины.

Рис. 3

Потеря информации происходит тогда, когда существуют два состояния Si и Sj, которые могут быть достигнуты от одного и того же состояния Sс, которые могут быть достигнуты при различных входных последовательностях, которые переводят машину в одно и то же состояние Sf

и генерируют одинаковые выходные последовательности (см. Рис. 3).

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

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

PS

NS,z

x=0

x=1

A

A,0

B,0

B

B,0

A,1

a)

b)

Рис. 4




Содержание  Назад  Вперед