Опишите семейство явных универсальных хеш-функций

Question

В этой задаче мне было дано следующее отображение

 U = {0, 1, 2, 3, 4, 5, 6, 7} to {0, 1}

Исходя из этого, существует явная универсальная хеширующая функция, которая должна быть получена, с подсказкой, что это можно сделать с помощью набора из 4функции.К сожалению, несмотря на поиск статей о том, как это сделать, я все еще в замешательстве.Любая помощь в понимании того, как найти эту функцию хеширования и двигаться в правильном направлении, очень ценится!

РЕДАКТИРОВАТЬ:

После некоторых размышлений, это то, что я придумал;это будет правильно?

     0  1  2  3  4  5  6  7
---------------------------
h1 | 1  1  0  0  0  0  0  0 
h2 | 0  0  1  1  0  0  0  0
h3 | 0  0  0  0  1  1  0  0
h4 | 0  0  0  0  0  0  1  1

Answer 1

Используя определение из Википедии:

Семейство функций H = {h: U → [m]} называется универсальным семейством, если, ∀ x, y ∈ U, x ≠ y: Pr _h∈H [h (x) = h (y)] ≤ ¹ / _m .

В вашемВ этом случае это означает, что для любых двух значений x и y в наборе {0, 1, 2, 3, 4, 5, 6, 7}, не болеедве из ваших четырех хеш-функций могут отображать их в один и тот же бит.

Ваше предложение:

     0  1  2  3  4  5  6  7
---------------------------
h1 | 1  1  0  0  0  0  0  0 
h2 | 0  0  1  1  0  0  0  0
h3 | 0  0  0  0  1  1  0  0
h4 | 0  0  0  0  0  0  1  1

не работает , а не , потому что есть четыре пары( x , y ), а именно (0,1), (2,3), (4,5) и (6,7) - где все четыре хеш-функции отображают их в один и тот же бит.

Вместо этого, вот некоторые опции, которые делают работают:

     0  1  2  3  4  5  6  7
---------------------------
h1 | 0  0  0  0  1  1  1  1
h2 | 0  0  1  1  0  0  1  1
h3 | 0  1  0  1  0  1  0  1
h4 | 0  1  1  0  1  0  0  1

     0  1  2  3  4  5  6  7
---------------------------
h1 | 0  0  0  1  0  1  1  1
h2 | 0  0  1  0  1  0  1  1
h3 | 0  1  0  0  1  1  0  1
h4 | 1  0  0  0  1  1  1  0