У математиці та обчислювальній техніці універсальне гешування (у рандомізованому алгоритмі чи структурі даних) означає випадковий вибір геш-функції з сімейства геш-функцій із певною математичною властивістю (див. визначення нижче). Це гарантує низьку кількість колізій в очікуванні, навіть якщо дані вибирає зловмисник. Відомо багато універсальних сімейств (для гешування цілих чисел, векторів, рядків), і їх оцінка часто дуже ефективна. Універсальне гешування має численні застосування в інформатиці, наприклад у реалізації геш-таблиць, рандомізованих алгоритмів і криптографії.

Вступ Припустимо, ми хочемо відобразити ключі з якогось універсуму в кошиків (позначених ). Алгоритм повинен буде обробляти певний набір даних з ключів, про які заздалегідь не відомо. Зазвичай метою гешування є отримання невеликої кількості колізій (ключів з які потрапляють в один кошик). Детермінована геш-функція не може запропонувати жодних гарантій у ситуації змагання, якщо , оскільки противник може вибрати , яке є саме прообразом кошика. Це означає, що всі ключі даних потрапляють в один кошик, що робить гешування марним. Крім того, детермінована геш-функція не допускає повторного гешування: іноді вхідні дані виявляються поганими для геш-функції (наприклад, забагато колізій), тому можна змінити геш-функцію.

Рішення цих проблем полягає у випадковому виборі геш-функції з сімейства геш-функцій. Сімейство геш-функцій називається універсальним, якщо

Іншими словами, будь-які два різні ключі універсуму утворюють колізію з максимальною ймовірністю коли геш-функція обирається рівноімовірно випадковим чином із . Це саме та ймовірність колізії, яку ми очікували б, якби геш-функція призначала справді випадкові геш-коди кожному ключу.

Іноді визначення пом'якшується постійним множником, коли вимагається лише ймовірність колізії а не . Ця концепція була введена Картером і Вегманом у 1977 році та знайшла численні застосування в інформатиці (див., .

Якщо верхня межа ймовірності колізії , говорять про -майже універсальність. Так, наприклад, універсальне сімейство є -майже універсальним.

Багато, але не всі універсальні родини мають наступну сильнішу властивість рівномірної різниці:

, коли вибирається випадковим чином із сімейства , різниця рівномірно розподілена в .

Слід зауважити, що визначення універсальності стосується лише випадку , по якому підраховуються колізії. Властивість рівномірної різниці сильніша.

Аналогічно універсальне сімейство може бути XOR-універсальним, якщо для значення рівномірно розподілене в , де  — операція побітового виключного АБО. Це можливо тільки якщо є степенем двійки.

Ще сильнішою умовою є : коли , то ймовірність, що гешування відобразить у будь-яку пару геш-значень ніби вони абсолютно випадкові: . Попарну незалежність іноді називають сильною універсальністю.

Ще одна властивість — однорідність. Кажуть, що сімейство однорідне, якщо всі геш-значення однаково імовірні: для будь-якого геш-значення . Універсальність не означає однорідності. Однак сильна універсальність передбачає однорідність.

Маючи сімейство з властивістю рівномірної відстані, можна створити попарно незалежне або сильно універсальне геш-сімейство шляхом додавання рівномірно розподіленої випадкової константи зі значеннями з до геш-функцій. (Так само, якщо є степенем двійки, ми можемо досягти попарної незалежності від XOR-універсального геш-сімейства за допомогою операції XOR з рівномірно розподіленою випадковою константою.) Оскільки зсув на константу іноді нерелевантний у програмах (наприклад, геш-таблиці), ретельне розрізнення між властивістю рівномірної відстані та попарною незалежністю іноді не робиться.

Для деяких застосувань (таких як геш-таблиці) важливо, щоб молодші біти геш-значень також були універсальними. Коли сімейство сильно універсальне, це гарантовано: якщо є сильно універсальним сімейством з , то сімейство, що складається з функцій для усіх , також є універсальним для . На жаль, це не стосується (просто) універсальних сімейств. Наприклад, сімейство з функції ідентичності є однозначно універсальним, але сімейство, яке складається з функції , не може бути універсальним.

і , а також кілька інших алгоритмів кодів автентифікації повідомлень базуються на універсальному гешуванні.David Wagner, ed. «Advances in Cryptology — CRYPTO 2008». p. 145.Jean-Philippe Aumasson, Willi Meier, Raphael Phan, Luca Henzen. «The Hash Function BLAKE». 2014. p. 10. У таких застосуваннях програмне забезпечення вибирає нову геш-функцію для кожного повідомлення на основі унікального довільного числа для цього повідомлення.

Кілька реалізацій геш-таблиць засновані на універсальному гешуванні. У таких застосуваннях зазвичай програмне забезпечення вибирає нову геш-функцію лише після того, як помічає, що «забагато» ключів утворюють колізії; до того часу та сама геш-функція продовжує використовуватися знову і знову. (Деякі схеми вирішення колізій, такі як , вибирають нову геш-функцію кожного разу, коли виникає колізія. Інші схеми вирішення колізій, такі як зозулине гешування та , допускають кілька колізій перед вибором нової геш-функції). Огляд найшвидших відомих універсальних і сильно універсальних геш-функцій для цілих чисел, векторів і рядків можна знайти в джерелі.

Математичні гарантії Для будь-якого фіксованого набору з ключів, використання універсального сімейства гарантує такі властивості.

Для будь-якого фіксованого у очікуване число ключів у кошику дорівнює . При реалізації геш-таблиць методом ланцюжків це число пропорційне очікуваному часу роботи по ключу (наприклад запиту, вставляння чи видалення). Очікуване число пар ключів у з , які утворюють колізію () обмежене зверху , що є порядком . Коли число кошиків обране лінійно в (тобто визначене функцією у ), очікуване число колізій становить . При гешуванні у кошиків з імовірністю не менше 0.5 не існує колізій взагалі. Очікуване число ключів , які утворюють щонайменше колізій, обмежене зверху як . Таким чином, якщо ємність кожного кошика обмежена потрійним середнім розміром (), загальна кількість ключів у переповнених кошиках не більше . Це справедливо лише для геш-сімейства, ймовірність колізії якого обмежена згори . Якщо використовується слабше визначення з обмеженням імовірності колізій , результат перестає бути істинним.

Оскільки наведені вище гарантії справедливі для будь-якого фіксованого набору , вони зберігаються, якщо набір даних вибрано противником. Однак противник повинен зробити цей вибір до (або незалежно від) випадкового вибору алгоритму геш-функції. Якщо зловмисник може спостерігати за випадковим вибором алгоритму, випадковість не має сенсу, і ситуація така ж, як і з детермінованим гешуванням.

Друга і третя гарантія зазвичай використовуються в поєднанні з . Наприклад, може бути підготовлений рандомізований алгоритм для обробки деякої кількості колізій. Якщо він спостерігає занадто багато колізій, він вибирає іншу випадкову з родини і повторює гешування. Універсальність гарантує, що кількість повторень є геометричною випадковою величиною.

Конструкції Оскільки будь-які комп'ютерні дані можуть бути представлені як одне або більше машинних слів, зазвичай потрібні геш-функції для трьох типів доменів: машинні слова («цілі числа»); вектори машинних слів фіксованої довжини; і вектори змінної довжини («рядки»).

Гешування цілих чисел У цьому розділі розглядається випадок гешування цілих чисел, які вписуються в машинні слова; таким чином, такі операції, як множення, додавання, ділення тощо, є дешевими машинними інструкціями. Нехай універсум, що гешується .

Початкова пропозиція Картера і Вегмана полягала у виборі простого числа і визначенні

де випадково вибрані цілі числа за модулем з . (Це одна ітерація лінійного конгруентного генератора.)

Щоб побачити, що є універсальним сімейством, слід зауважити, що виконується лише коли

для деякого цілого числа між і . Оскільки , якщо їх різниця не дорівнює нулю і має оберенене за модулем число. Розв'язання для

.

Існує можливих варіантів для (оскільки виключається) і, варіюючи в допустимому діапазоні, можливо отримати ненульових значень для правої частини. Таким чином, ймовірність колізії дорівнює

.

Інший спосіб побачити, що є універсальним сімейством використовує поняття . Різницю можна переписати як

.

Оскільки не дорівнює нулю і рівномірно розподіляється в , з цього випливає, що по модулю також рівномірно розподіляється в . Розподіл таким чином є майже рівномірним, аж до різниці в ймовірності між зразками. У результаті статистична відстань до однорідної родини становить , яка стає незначною, коли .

Сімейство простіших геш-функцій

є лише приблизно універсальним: для усіх . Крім того, цей аналіз є майже строгим; Картер і Вегман показують що будь-коли .

Уникнення модульної арифметики Найсучаснішим для гешування цілих чисел є схема множення-зсуву, описана Діцфельбінгером та ін. у 1997 р. Завдяки уникненню модульної арифметики цей метод набагато легше реалізувати, а також він працює значно швидше на практиці (зазвичай щонайменше в чотири рази). Схема припускає, що кількість кошиків є ступенем двійки, . Нехай буде кількістю бітів у машинному слові. Потім геш-функції параметризуються над непарними додатними цілими числами (що вписується в одне -бітове слово). Щоб оцінити , слід помножити на по модулю а потім зберегти старші бітів як геш-код. У математичній нотації це

Ця схема не задовольняє властивості рівномірної різниці і є єдиною -майже універсальною; для будь-якого , .

Щоб зрозуміти поведінку геш-функції, зауважимо, що якщо і мають однакові старші M бітів, тоді має всі одиниці або всі нулі у старших M бітах (залежно від того, що більше: чи ). Припустимо, що набір молодших бітів з'являється на позиції . Через те, що є випадковим непарним цілим числом, а непарні цілі числа мають обернені значення у кільці , слідує, що буде рівномірно розподілено серед -бітових цілих чисел з молодшим установленим бітом на позиції . Таким чином, імовірність того, що всі ці біти складаються з 0 або 1, не перевищує .

З іншого боку, якщо , тоді старші M бітів містять і 0, і 1, тому . Насамкінець, якщо то біт значення є 1, і тоді і тільки тоді, коли біти також є 1, що відбувається з імовірністю .

Цей аналіз є строгим, як можна показати на прикладі і . Щоб отримати дійсно «універсальну» геш-функцію, можна використати схему множення-додавання-зсуву, яка вибирає старші біти

де є випадковим натуральним числом з і є випадковим невід'ємним цілим числом з . Для цього потрібно виконувати арифметику -розрядних беззнакових цілих чисел. Ця версія множинного зсуву належить Діцфельбінгеру, а пізніше була більш точно проаналізована Вельфелем.

Гешування векторів Цей розділ стосується гешування вектора машинних слів фіксованої довжини. Вхідні дані інтерпретуються як вектор з машинних слів (цілі числа по бітів кожне). Якщо є універсальним сімейством з властивістю рівномірної різниці, наступне сімейство (походить від Картера і Вегмана) також має властивість рівномірної різниці (і, отже, є універсальним):

.

Якщо є степенем двійки, підсумовування можна замінити виключним або., section 5.3

На практиці, якщо доступна арифметика подвійної точності, вона створюється за допомогою сімейства геш-функцій із множним зсувом. Якщо ніціалізувати геш-функцію вектором випадкових непарних цілих чисел по бітів кожне, тоді, якщо кількість кошиків дорівнює для :

.

Можна вдвічі зменшити кількість множень, що на практиці приблизно означає подвійне прискорення. Якщо ніціалізувати геш-функцію вектором випадкових непарних цілих чисел на біти кожне, то наступне сімейство геш-функцій є універсальним:, Equation 1

.

Якщо операції подвійної точності недоступні, можна інтерпретувати вхідні дані як вектор півслів ( -розрядні цілі числа). Далі буде використовуватися алгоритм множення, де  — кількість півслів у векторі. Таким чином, алгоритм працює зі швидкістю одного множення на вхідне слово.