Хеш-функция с контролируемыми коллизиями

From

Sergey Kabikov (2:5020/175.2)

To

All ()

Date

2003-03-04T08:30:36Z

Area

RU.ALGORITHMS

From: "Sergey Kabikov" <kser@elsov.ru>

Hi All,

Необходимо построить функцию, y = f(x), где
 0 <= x < 2^nx
 0 <= y < 2^ny
 ny < nx
Т.е. мощность множества значений результата меньше мощности множества значений
аргумента, т.н. функцию с коллизиями.

Основное требование к ней : для любого х, принадлежащего некоему заранее
заданному множеству {x0}, результат функции должен быть некой величиной у0, а
для любого х, не принадлежащего этому множеству - величиной, отличной от у0.

Дополнительное требование : по виду самой функции должно быть невозможно
определить правильные у0 и {x0}, т.е. должно существовать множество
приблизительно равномощных пар yi и {xi}, в идеале 2^(nx - ny) таких пар.
Поэтому типовой ответ
  if x in {x0}
  then y := y0
  else y := random(2^ny)
не проходит.

Значения, составляющие множество {x0}, фиксированы заранее. Величину у0
допустимо определять на этапе "конструирования" функции.

В принципе, требования можно несколько ослабить :
- есть заданное множество {x0}, для любого х из которого f(x)=y0,
- есть заданное множество {x1}, для любого х из которого f(x)<>y0,
- для всех остальных значений х функция у может давать любое значение.

И еще одно пожелание - в идеале функция должна обладать свойствами
криптографического хеша : вычисление любого х из {x0} по известному у0 должно
быть вычислительно трудным (лучше всего - NP-полной задачей).

Мой пока единственный вариант таков :
- задаемся простым числом у0,
- вычисляем z = у0 + НОК {x0}
тогда искомая функция будет :
  y := z modulo x
Доказательство для {x0} очевидно. Недостатки - тоже. Если хотя бы одно число
из {x1} будет произведением сомножителей, уже входящих в НОК {x0} - алгоритм
не сработает.

Прошу помощи клуба ;-)

С уважением
Сергей

P.S. Я бы отправил это письмо в RU.CRYPT, но, похоже, все серьезные математики
из "там" уже здесь ;-)

...and the eyes in his head see the world spinning round... (c) Beatles

--- ifmail v.2.15dev5
 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)