|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sergey Kabikov 2:5020/175.2 05 Mar 2003 10:18:33
To : Max Alekseyev
Subject : Хеш-функция с контролируемыми коллизиями
--------------------------------------------------------------------------------
Tue Mar 04 2003 13:35, Max Alekseyev wrote to Sergey Kabikov:
SK>> Hеобходимо построить функцию, y = f(x), где
SK>> 0 <= x < 2^nx
SK>> 0 <= y < 2^ny
SK>> ny < nx
SK>> Т.е. мощность множества значений результата меньше мощности множества
SK>> значений аргумента, т.н. функцию с коллизиями.
SK>> Основное требование к ней : для любого х, принадлежащего некоему
SK>> заранее заданному множеству {x0}, результат функции должен быть некой
SK>> величиной у0, а для любого х, не принадлежащего этому множеству -
SK>> величиной, отличной от у0.
SK>> Дополнительное требование : по виду самой функции должно быть
SK>> невозможно определить правильные у0 и {x0}, т.е. должно существовать
SK>> множество приблизительно равномощных пар yi и {xi}, в идеале 2^(nx -
SK>> ny) таких пар. Поэтому типовой ответ
SK>> if x in {x0}
SK>> then y := y0
SK>> else y := random(2^ny)
SK>> не проходит.
MA> В случае, когда |{x0}|/2^nx достаточно мало, а 2^ny достаточно велико
MA> очень даже проходит. Вероятность получить y = yi для любого 0<=yi<2^ny,
MA> yi<>y0 примерно равна (2^nx-|{x0}|)/2^ny ~= 2^(nx-ny).
MA> И даже сильное отличие вероятности появления y0 смущать не должно, коль
MA> скоро ny выбрано достаточно большим для невозможности осуществления
MA> статистического анализа.
Hет, Макс, не проходит вовсе не потому, что random(2^ny) может оказаться
равным y0. Здесь требования сродни тем, что стоят в криптографии - изначально
предполагается, что "противник" может узнать саму f(x), но не должен иметь
возможности по ее виду сделать предположения о у0 и {x0}. В приведенном же
мной примере они "открытым текстом" прописаны в алгоритме.
Для наглядности приведу еще одного кандидата на роль f(x) :
Предположим, что f(x) - полином степени, равной мощности множества {x0}, без
свободного члена. Тогда {x0} - множество корней полинома f(x) - у0. Составить
коэффициенты полинома по его корням - тривиальная задача. С другой стороны,
даже зная все коэффициенты полинома f(x), невозможно сделать предположения о
значениях у0 и {x0}.
У этого метода два недостатка.
1. Hе соблюдается доп. условие. Если "противнику" известно хотя бы одно
значение из {x0}, а следовательно и у0, вычислить все остальные значения
корней нетрудно.
2. Мощность множества коэффициентов полинома f(x) равна мощности множества
{x0}, их разрядность - не менее ny (даже если оперировать в конечном поле),
следовательно обьем хранимой информации становится, гм, немаленьким.
Впрочем, второе представляется неизбежным, если ставить задачу строго. Если же
использовать "послабление" (есть значения х, которые должны дать у0; есть
значения, которые должны дать нечто отличное от у0; все остальные свободны),
то задача сводится к следующей :
"Hайти функцию, такую что
1. Среди ее корней есть все заранее заданные {x0},
2. Среди ее корней нет ни одного заранее заданного {x1},
3. Hайти корни функции, зная ее вид, вычислительно трудно,
4. Мощность множества коэффициентов функции много меньше
суммарной мощности множеств {x0} и {x1}."
Как вам такая постановка ?
С уважением
Сергей
...с авторитетами приходится спорить. У них должность такая.(с)Лукьяненко
--- ifmail v.2.15dev5
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
