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

From

Vladimir Vassilevsky (2:5020/175.2)

To

Sergey Kabikov ()

Date

2003-03-04T15:00:06Z

Area

RU.ALGORITHMS

From: "Vladimir Vassilevsky" <vlv@fullnet.net>

Hi Sergey,


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

 Имеется наперед заданное множество ключей. Требуется функция F(ключ), 
 которая == 0 для любого из ключей, и гарантированно != 0 для всех прочих 
 случаев. Не так ли? :) 


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

 Рабоче - крестьянский метод:
 Можно построить { x1 } = Encrypt( {x0} )
 Соответственно проверять if(Encrypt(x)) in { x1 }
 В качестве Encrypt использовать RSA или другой несимметричный криптоалгоритм.
 
 SK> Мой пока единственный вариант таков :

 Боюсь, что для произвольно заданного { x } решения нет и быть не может.

 VLV

"Хотели как лучше - получилось как всегда.   (с) В. С. Черномырдин"

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