Універсальне гешування
У математиці та обчислювальній техніці універсальне гешування (у рандомізованому алгоритмі чи структурі даних) означає випадковий вибір геш-функції з сімейства геш-функцій із певною математичною властивістю (див. визначення нижче). Це гарантує низьку кількість колізій в очікуванні, навіть якщо дані вибирає противник. Відомо багато універсальних сімейств (для гешування цілих чисел, векторів, рядків), і їх оцінка часто дуже ефективна. Універсальне гешування має численні застосування в інформатиці, наприклад у реалізації геш-таблиць, рандомізованих алгоритмів і криптографії.
Вступ[ред. | ред. код]
Припустимо, ми хочемо відобразити ключі з якогось універсуму в кошиків (позначених ). Алгоритм повинен буде обробляти певний набір даних з ключів, про які заздалегідь не відомо. Зазвичай метою гешування є отримання невеликої кількості колізій (ключів з які потрапляють в один кошик). Детермінована геш-функція не може запропонувати жодних гарантій у ситуації змагання, якщо , оскільки противник може вибрати , яке є саме прообразом кошика. Це означає, що всі ключі даних потрапляють в один кошик, що робить гешування марним. Крім того, детермінована геш-функція не допускає повторного гешування: іноді вхідні дані виявляються поганими для геш-функції (наприклад, забагато колізій), тому можна змінити геш-функцію.
Рішення цих проблем полягає у випадковому виборі геш-функції з сімейства геш-функцій. Сімейство геш-функцій називається універсальним, якщо
Іншими словами, будь-які два різні ключі універсуму утворюють колізію з максимальною ймовірністю коли геш-функція обирається рівноімовірно випадковим чином із . Це саме та ймовірність колізії, яку ми очікували б, якби геш-функція призначала справді випадкові геш-коди кожному ключу.
Іноді визначення пом'якшується постійним множником, коли вимагається лише ймовірність колізії а не . Ця концепція була введена Картером і Вегманом[1] у 1977 році та знайшла численні застосування в інформатиці (див., приклад[2]) .
Якщо верхня межа ймовірності колізії , говорять про -майже універсальність. Так, наприклад, універсальне сімейство є -майже універсальним.
Багато, але не всі універсальні родини мають наступну сильнішу властивість рівномірної різниці:
- , коли вибирається випадковим чином із сімейства , різниця рівномірно розподілена в .
Слід зауважити, що визначення універсальності стосується лише випадку , по якому підраховуються колізії. Властивість рівномірної різниці сильніша.
Аналогічно універсальне сімейство може бути XOR-універсальним, якщо для значення рівномірно розподілене в , де — операція побітового виключного АБО. Це можливо тільки якщо є степенем двійки.
Ще сильнішою умовою є попарна незалежність[en]: коли , то ймовірність, що гешування відобразить у будь-яку пару геш-значень ніби вони абсолютно випадкові: . Попарну незалежність іноді називають сильною універсальністю.
Ще одна властивість — однорідність. Кажуть, що сімейство однорідне, якщо всі геш-значення однаково імовірні: для будь-якого геш-значення . Універсальність не означає однорідності. Однак сильна універсальність передбачає однорідність.
Маючи сімейство з властивістю рівномірної відстані, можна створити попарно незалежне або сильно універсальне геш-сімейство шляхом додавання рівномірно розподіленої випадкової константи зі значеннями з до геш-функцій. (Так само, якщо є степенем двійки, ми можемо досягти попарної незалежності від XOR-універсального геш-сімейства за допомогою операції XOR з рівномірно розподіленою випадковою константою.) Оскільки зсув на константу іноді нерелевантний у програмах (наприклад, геш-таблиці), ретельне розрізнення між властивістю рівномірної відстані та попарною незалежністю іноді не робиться.[3]
Для деяких застосувань (таких як геш-таблиці) важливо, щоб молодші біти геш-значень також були універсальними. Коли сімейство сильно універсальне, це гарантовано: якщо є сильно універсальним сімейством з , то сімейство, що складається з функцій для усіх , також є універсальним для . На жаль, це не стосується (просто) універсальних сімейств. Наприклад, сімейство з функції ідентичності є однозначно універсальним, але сімейство, яке складається з функції , не може бути універсальним.
UMAC[en] і Poly1305-AES[en], а також кілька інших алгоритмів кодів автентифікації повідомлень базуються на універсальному гешуванні.[4][5] У таких застосуваннях програмне забезпечення вибирає нову геш-функцію для кожного повідомлення на основі унікального довільного числа для цього повідомлення.
Кілька реалізацій геш-таблиць засновані на універсальному гешуванні. У таких застосуваннях зазвичай програмне забезпечення вибирає нову геш-функцію лише після того, як помічає, що «забагато» ключів утворюють колізії; до того часу та сама геш-функція продовжує використовуватися знову і знову. (Деякі схеми вирішення колізій, такі як динамічне ідеальне гешування[en], вибирають нову геш-функцію кожного разу, коли виникає колізія. Інші схеми вирішення колізій, такі як зозулине гешування та гешування з двома варіантами[en], допускають кілька колізій перед вибором нової геш-функції). Огляд найшвидших відомих універсальних і сильно універсальних геш-функцій для цілих чисел, векторів і рядків можна знайти в джерелі[6].
Математичні гарантії[ред. | ред. код]
Для будь-якого фіксованого набору з ключів, використання універсального сімейства гарантує такі властивості.
- Для будь-якого фіксованого у очікуване число ключів у кошику дорівнює . При реалізації геш-таблиць методом ланцюжків це число пропорційне очікуваному часу роботи по ключу (наприклад запиту, вставляння чи видалення).
- Очікуване число пар ключів у з , які утворюють колізію () обмежене зверху , що є порядком . Коли число кошиків обране лінійно в (тобто визначене функцією у ), очікуване число колізій становить . При гешуванні у кошиків з імовірністю не менше 0.5 не існує колізій взагалі.
- Очікуване число ключів , які утворюють щонайменше колізій, обмежене зверху як .[7] Таким чином, якщо ємність кожного кошика обмежена потрійним середнім розміром (), загальна кількість ключів у переповнених кошиках не більше . Це справедливо лише для геш-сімейства, ймовірність колізії якого обмежена згори . Якщо використовується слабше визначення з обмеженням імовірності колізій , результат перестає бути істинним.[7]
Оскільки наведені вище гарантії справедливі для будь-якого фіксованого набору , вони зберігаються, якщо набір даних вибрано противником. Однак противник повинен зробити цей вибір до (або незалежно від) випадкового вибору алгоритму геш-функції. Якщо зловмисник може спостерігати за випадковим вибором алгоритму, випадковість не має сенсу, і ситуація така ж, як і з детермінованим гешуванням.
Друга і третя гарантія зазвичай використовуються в поєднанні з перегешуванням[en]. Наприклад, може бути підготовлений рандомізований алгоритм для обробки деякої кількості колізій. Якщо він спостерігає занадто багато колізій, він вибирає іншу випадкову з родини і повторює гешування. Універсальність гарантує, що кількість повторень є геометричною випадковою величиною.
Конструкції[ред. | ред. код]
Оскільки будь-які комп'ютерні дані можуть бути представлені як одне або більше машинних слів, зазвичай потрібні геш-функції для трьох типів доменів: машинні слова («цілі числа»); вектори машинних слів фіксованої довжини; і вектори змінної довжини («рядки»).
Гешування цілих чисел[ред. | ред. код]
У цьому розділі розглядається випадок гешування цілих чисел, які вписуються в машинні слова; таким чином, такі операції, як множення, додавання, ділення тощо, є дешевими машинними інструкціями. Нехай універсум, що гешується .
Початкова пропозиція Картера і Вегмана[1] полягала у виборі простого числа і визначенні
де випадково вибрані цілі числа за модулем з . (Це одна ітерація лінійного конгруентного генератора.)
Щоб побачити, що є універсальним сімейством, слід зауважити, що виконується лише коли
для деякого цілого числа між і . Оскільки , якщо їх різниця не дорівнює нулю і має оберенене за модулем число. Розв'язання для
- .
Існує можливих варіантів для (оскільки виключається) і, варіюючи в допустимому діапазоні, можливо отримати ненульових значень для правої частини. Таким чином, ймовірність колізії дорівнює
- .
Інший спосіб побачити, що є універсальним сімейством використовує поняття статистичної відстані[en]. Різницю можна переписати як
- .
Оскільки не дорівнює нулю і рівномірно розподіляється в , з цього випливає, що по модулю також рівномірно розподіляється в . Розподіл таким чином є майже рівномірним, аж до різниці в ймовірності між зразками. У результаті статистична відстань до однорідної родини становить , яка стає незначною, коли .
Сімейство простіших геш-функцій
є лише приблизно універсальним: для усіх .[1] Крім того, цей аналіз є майже строгим; Картер і Вегман[1] показують що будь-коли .
Уникнення модульної арифметики[ред. | ред. код]
Найсучаснішим для гешування цілих чисел є схема множення-зсуву, описана Діцфельбінгером та ін. у 1997 р.[8] Завдяки уникненню модульної арифметики цей метод набагато легше реалізувати, а також він працює значно швидше на практиці (зазвичай щонайменше в чотири рази[9]). Схема припускає, що кількість кошиків є ступенем двійки, . Нехай буде кількістю бітів у машинному слові. Потім геш-функції параметризуються над непарними додатними цілими числами (що вписується в одне -бітове слово). Щоб оцінити , слід помножити на по модулю а потім зберегти старші бітів як геш-код. У математичній нотації це
Ця схема не задовольняє властивості рівномірної різниці і є єдиною -майже універсальною; для будь-якого , .
Щоб зрозуміти поведінку геш-функції, зауважимо, що якщо і мають однакові старші M бітів, тоді має всі одиниці або всі нулі у старших M бітах (залежно від того, що більше: чи ). Припустимо, що набір молодших бітів з'являється на позиції . Через те, що є випадковим непарним цілим числом, а непарні цілі числа мають обернені значення у кільці , слідує, що буде рівномірно розподілено серед -бітових цілих чисел з молодшим установленим бітом на позиції . Таким чином, імовірність того, що всі ці біти складаються з 0 або 1, не перевищує .
З іншого боку, якщо , тоді старші M бітів містять і 0, і 1, тому . Насамкінець, якщо то біт значення є 1, і тоді і тільки тоді, коли біти також є 1, що відбувається з імовірністю .
Цей аналіз є строгим, як можна показати на прикладі і . Щоб отримати дійсно «універсальну» геш-функцію, можна використати схему множення-додавання-зсуву, яка вибирає старші біти
де є випадковим натуральним числом з і є випадковим невід'ємним цілим числом з . Для цього потрібно виконувати арифметику -розрядних беззнакових цілих чисел. Ця версія множинного зсуву належить Діцфельбінгеру, а пізніше була більш точно проаналізована Вельфелем.[10]
Гешування векторів[ред. | ред. код]
Цей розділ стосується гешування вектора машинних слів фіксованої довжини. Вхідні дані інтерпретуються як вектор з машинних слів (цілі числа по бітів кожне). Якщо є універсальним сімейством з властивістю рівномірної різниці, наступне сімейство (походить від Картера і Вегмана[1]) також має властивість рівномірної різниці (і, отже, є універсальним):
- .
Якщо є степенем двійки, підсумовування можна замінити виключним або.[11]
На практиці, якщо доступна арифметика подвійної точності, вона створюється за допомогою сімейства геш-функцій із множним зсувом.[12] Якщо ніціалізувати геш-функцію вектором випадкових непарних цілих чисел по бітів кожне, тоді, якщо кількість кошиків дорівнює для :
- .
Можна вдвічі зменшити кількість множень, що на практиці приблизно означає подвійне прискорення.[11] Якщо ніціалізувати геш-функцію вектором випадкових непарних цілих чисел на біти кожне, то наступне сімейство геш-функцій є універсальним:[13]
- .
Якщо операції подвійної точності недоступні, можна інтерпретувати вхідні дані як вектор півслів ( -розрядні цілі числа). Далі буде використовуватися алгоритм множення, де — кількість півслів у векторі. Таким чином, алгоритм працює зі швидкістю одного множення на вхідне слово.
Цю ж схему також можна використовувати для гешування цілих чисел, інтерпретуючи їхні біти як вектори байтів. У цьому варіанті векторна техніка відома як табуляційне гешування[en] та забезпечує практичну альтернативу універсальним схемам гешування на основі множення.[14]
Також можлива сильна універсальність на високій швидкості.[15] Потрібно ініціалізувати геш-функцію вектором випадкових цілих чисел на бітів. Обчислити
- .
Результат сильно універсальний на бітах. Експериментально було встановлено, що він працює на швидкості на 0,2 цикла процесора на байт на останніх процесорах Intel для .
Гешування рядків[ред. | ред. код]
Це стосується гешування вектора машинних слів змінного розміру. Якщо довжину рядка можна обмежити невеликим числом, найкраще використовувати векторне рішення зверху (концептуально доповнюючи вектор нулями до верхньої межі). Потрібний простір — це максимальна довжина рядка, але час для оцінки це просто довжина . Поки нулі заборонені в рядку, доповнення нулями можна ігнорувати під час оцінювання геш-функції без впливу на універсальність.[11] Слід зауважити, що якщо в рядку дозволені нулі, тоді, можливо, найкраще буде додати фіктивний ненульовий символ (наприклад, 1) до всіх рядків перед доповненням: це гарантує, що це не вплине на універсальність.[15]
Тепер припустимо, що ми хочемо гешувати , де гарна межа апріорі невідома. Універсальне сімейство, запропоноване[16], розглядає рядок як коефіцієнти полінома за модулем великого простого числа. Якщо , прийняти просте число і визначити:
- , де є рівномірно випадковим і вибирається випадковим чином із універсального сімейства, що відображає: цілі числа .
Використовуючи властивості модульної арифметики, наведене вище можна обчислити без отримання великих чисел для великих рядків, як показано нижче:[17]
uint hash(String x, int a, int p)
uint h = INITIAL_VALUE
for (uint i=0 ; i < x.length ; ++i)
h = ((h*a) + x[i]) mod p
return h
Цей коткий геш Рабіна-Карпа базується на лінійному конгруентному генераторі.[18] Наведений вище алгоритм також відомий як мультиплікативна геш-функція.[19] На практиці оператора mod і параметра p можна взагалі уникнути, просто дозволивши цілочисельне переповнення, оскільки це еквівалентно mod (Max-Int-Value + 1) у багатьох мовах програмування. У таблиці нижче показано значення, вибрані для ініціалізації h і a для деяких популярних реалізацій.
Реалізація | Початкове значення | a |
---|---|---|
геш-функція Бернштайна djb2[20] | 5381 | 33 |
STLPort 4.6.2 | 0 | 5 |
геш-функція Кернігана та Річі[21] | 0 | 31 |
java.lang.String.hashCode() [22] | 0 | 31 |
Розглянемо два рядки і нехай бути довжиною довшого; для аналізу коротший рядок концептуально доповнюється нулями до довжини . Колізія при застосуванні означає, що є коренем многочлена з коефіцієнтами . Цей многочлен має не більше коренів по модулю , тому ймовірність колізії не більше . Імовірність колізії через випадковість доводить загальну ймовірність колізії до . Таким чином, якщо просте є достатньо великим порівняно з довжиною гешованих рядків, сімейство дуже близько до універсального (за статистичною відстанню).
Інші універсальні сімейства геш-функцій, які використовуються для гешування рядків невідомої довжини до геш-значень фіксованої довжини, включають відбиток Рабіна та Бужаш.
Уникнення модульної арифметики[ред. | ред. код]
Щоб пом'якшити обчислювальні витрати від модульної арифметики, на практиці використовуються три прийоми:[11]
- Обирається просте , близьке до степеня двійки, наприклад просте число Мерсенна[en]. Це дозволяє арифметику по модулю реалізувати без ділення (з використанням швидших операцій, таких як додавання та зсув). Наприклад, на сучасних архітектурах можна працювати з , поки є 32-розрядними значеннями.
- До блоків можна застосувати векторне гешування. Наприклад, можна застосувати гешування векторів до кожного блоку з 16 слів рядка, а також застосувати гешування рядка до результатів. Оскільки повільніше гешування рядків застосовується до значно меншого вектора, загальна швидкість, по суті, буде така ж, як і швидкість гешування векторів.
- Дільником вибирається ступінь двійки, що дозволяє виконувати арифметичні дії за модулем без ділення (з використанням швидших операцій маскування бітів). Сімейство геш-функцій NH[en] використовує цей підхід.
Див. також[ред. | ред. код]
- K-independent hashing[en]
- Коткий геш
- Tabulation hashing[en]
- Min-wise independence[en]
- Universal one-way hash function[en]
- Послідовність із низькою розбіжністю
- Perfect hashing[en]
Примітки[ред. | ред. код]
- ↑ а б в г д Carter, Larry; Wegman, Mark N. (1979). Universal Classes of Hash Functions. Journal of Computer and System Sciences. 18 (2): 143—154. doi:10.1016/0022-0000(79)90044-8. Conference version in STOC'77.
- ↑ Miltersen, Peter Bro. Universal Hashing (PDF). Архів оригіналу (PDF) за 24 May 2011. Процитовано 24 June 2009.
{{cite web}}
: Проігноровано невідомий параметр|df=
(довідка) - ↑ Motwani, Rajeev; Raghavan, Prabhakar (1995). Randomized Algorithms. Cambridge University Press. с. 221. ISBN 0-521-47465-5.
- ↑ 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.
- ↑ Thorup, Mikkel (2015). High Speed Hashing for Integers and Strings. arXiv:1504.06804 [cs.DS].
- ↑ а б Baran, Ilya; Demaine, Erik D.; Pătraşcu, Mihai (2008). Subquadratic Algorithms for 3SUM (PDF). Algorithmica. 50 (4): 584—596. doi:10.1007/s00453-007-9036-3.
- ↑ Dietzfelbinger, Martin; Hagerup, Torben; Katajainen, Jyrki; Penttonen, Martti (1997). A Reliable Randomized Algorithm for the Closest-Pair Problem (Postscript). Journal of Algorithms. 25 (1): 19—51. doi:10.1006/jagm.1997.0873. Процитовано 10 February 2011.
- ↑ Thorup, Mikkel (18 December 2009). Text-book algorithms at SODA.
- ↑ Woelfel, Philipp (1999). Efficient Strongly Universal and Optimally Universal Hashing. Mathematical Foundations of Computer Science 1999. LNCS. Т. 1672. с. 262—272. doi:10.1007/3-540-48340-3_24.
- ↑ а б в г
. ISBN 978-0-89871-680-1.
{{cite conference}}
: Пропущений або порожній|title=
(довідка), section 5.3 - ↑ Dietzfelbinger, Martin; Gil, Joseph; Matias, Yossi; Pippenger, Nicholas (1992). Polynomial Hash Functions Are Reliable (Extended Abstract). Proc. 19th International Colloquium on Automata, Languages and Programming (ICALP). с. 235—246.
- ↑ Black, J.; Halevi, S.; Krawczyk, H.; Krovetz, T. (1999). UMAC: Fast and Secure Message Authentication (PDF). Advances in Cryptology (CRYPTO '99)., Equation 1
- ↑ . ISBN 9781450306911.
{{cite conference}}
: Пропущений або порожній|title=
(довідка) - ↑ а б Kaser, Owen; Lemire, Daniel (2013). Strongly universal string hashing is fast. Computer Journal. Oxford University Press. 57 (11): 1624—1638. arXiv:1202.4961. doi:10.1093/comjnl/bxt070.
- ↑ Dietzfelbinger, Martin; Gil, Joseph; Matias, Yossi; Pippenger, Nicholas (1992). Polynomial Hash Functions Are Reliable (Extended Abstract). Proc. 19th International Colloquium on Automata, Languages and Programming (ICALP). с. 235—246.
- ↑ Hebrew University Course Slides (PDF).
- ↑ Robert Uzgalis. «Library Hash Functions». 1996.
- ↑ Kankowsk, Peter. Hash functions: An empirical comparison.
- ↑ Yigit, Ozan. String hash functions.
- ↑ Kernighan; Ritchie (1988). 6. The C Programming Language (вид. 2nd). Prentice Hall. с. 118. ISBN 0-13-110362-8.
- ↑ String (Java Platform SE 6). docs.oracle.com. Процитовано 10 червня 2015.
Подальше читання[ред. | ред. код]
- Knuth, Donald Ervin (1998). The Art of Computer Programming, Vol. III: Sorting and Searching (вид. 3rd). Reading, Mass; London: Addison-Wesley. ISBN 0-201-89685-0.