VSH

В криптографии очень гладкая хеш-функция (англ. Very Smooth Hash (VSH)) — n-битная эффективная криптографическая функция хеширования, разработанная в 2005 году Скоттом Котини, Лестрой Арьен и Роном Штайнфельдом. Является устойчивой к коллизиям в предположении большой вычислительной сложности нахождения нетривиального квадратного корня очень гладкого числа по модулю n. Под понятием очень гладкой функции подразумевается, что граница гладкости является фиксированной полиномиальной функцией от n. Данный алгоритм хеширования предполагает одиночное умножение на $\Omega (n)$ бит сообщения и использует арифметику RSA-типа, что избавляет от необходимости отдельного хранения кода хеш-функции. Поэтому данный алгоритм полезен во встроенных средах, где пространство кода ограничено. Очень гладкая хеш-функция также может быть использована для создания односторонней функции с потайным входом, которая может быть применена в схемах подписи для ускорения проверки и усиления конфиденциальности.

VSSR и VSN

Для VSH основной математической проблемой является устойчивость к коллизиям, которая по сути состоит в извлечении корней по модулю n из очень гладких чисел, называемых очень гладкими корнями (VSSR). В свою очередь, проблема вычисления очень гладкого корня по модулю n тесно связана с факторизацией целых чисел с использованием общего метода решета числового поля.

Для фиксированных постоянных c и n целое число m называется очень гладким числом, если все простые множители m не больше чем (log n)^c. Целое число b является очень гладким квадратичным остатком по модулю n, если наибольшее простой множитель b — не более чем (log n)^c и существует целое x такое что $b\equiv x^{2}\mod n$. Целое x называют очень корнем квадратным по модулю  b.

Нас интересуют только корни где x² ≥ n. Так как, если x² < n, то корень может быть легко вычислен, используя поле характеристики 0. Вычисление очень гладкого корня является следующей задачей: пусть n является произведением двух простых чисел примерно одного размера и пусть $k\leq (\log n)^{c}$, а $p_{1}=2,p_{2}=3,p_{3}=5,\dots$ последовательность простых чисел. По данному n необходимо найти $x\in \mathbb {Z} _{n}^{*}$, такое, что $\textstyle x^{2}\equiv \prod _{i=0}^{k}p_{i}^{e_{i}}$ и хотя бы один из e₀,…,e_k будет нечетным.

Пример VSN и VSSR

Пусть зафиксированы следующие параметры: $c=5$ и $n=31$.

Тогда $m_{1}=35=5\cdot 7$ очень гладкое число от данных параметров, потому что $(\log 31)^{5}~{\dot {=}}~7.37$ больше чем все простые множители $m_{1}$. С другой стороны, $m_{2}=55=5\cdot 11$ не является очень гладким числом от $c=5$ и $n=31$.

Целое число $b_{1}=9$ является очень гладким квадратичным остатком по модулю $n$, потому что это число очень гладкое (от $c,n$) и существует $x_{1}=3$, такое что $x_{1}^{2}=b_{1}$ (mod $n$). Это тривиальный квадратный корень, потому что $3^{2}\not \geq n$ и поэтому модуль при возведении в квадрат не учитывается.

Целое число $b_{2}=15$ также является квадратичным остатком по модулю $n$. Все простые множители меньше чем 7.37, а все квадратные корни по модулю равны $x_{2}=20$, так как $20^{2}=400\equiv 15$ (mod $n$). Задача VSSR состоит в том, чтобы найти $x_{2}$ по данным $b_{2}$ и $n$. И вычислительно так же сложна, как факторизация $n$.

VSH, базовый алгоритм

Пусть $p_{1}=2,p_{2}=3,\ldots$ последовательность простых чисел. Пусть $k$ длина блока, наибольшее целое число, такое, что $\textstyle \prod _{i=1}^{k}p_{i}<n$. Пусть $m$ есть $\ell$-битное сообщение, состоящее из $(m_{1},\ldots ,m_{\ell })$, которое должно быть хешировано, причем $\ell <2^{k}$.Чтобы вычислить хеш $m$:

1. x₀ = 1
2. Пусть $L$ наименьшее целое число, большее или равное $l/k$, будет числом блоков. Пусть $m_{i}=0$ для $l<i\leq Lk$
3. Пусть $\textstyle \ell =\sum _{i=1}^{k}l_{i}2^{i-1}$ с $\ell _{i}\in \{0,1\}$ — бинарное представление сообщения длины $\ell$ и определим $m_{Lk+i}=\ell _{i}$ для $1\leq i\leq k$.
4. для каждого j = 0, 1,…, L вычисляем $x_{j+1}=x_{j}^{2}\prod _{i=1}^{k}p_{i}^{m_{jk+i}}\mod n$
5. возвращаем x_{L + 1}.

Функция на шаге 4 называется функцией сжатия.

Свойства VSH

• Не нужно знать заранее длину сообщения.
• Сложность обнаружения коллизий равна сложности нахождения очень гладкого корня, поэтому VSH устойчива к коллизиям. Стойкость к коллизиям единственное доказанное свойство для VSH.
• Функция сжатия не является стойкой к коллизиям. Однако хеш-функция устойчива к коллизиям на основе VSSR-предположения. Следующая версия VSH* использует стойкую к коллизиям функцию сжатия и работает в 5 раз быстрее на коротких сообщениях.
• VSH мультипликативна:

Пусть x, y, and z — трехбитные строчки равной длины, где z состоит только из нулевых бит и удовлетворяет x AND y = z. Тогда H(z)H(x OR y) ≡ H(x)H(y) (mod n). VSH уступает классической атаке на временную память, которая применяется к мультипликативным и аддитивным хешам.

Вариации VSH

Было предложено несколько улучшений, ускорений и более эффективных вариантов VSH. Ни один из них не меняет основную концепцию функции:

• Кубический VSH (вместо квадратичного).
• VSH с увеличением количества простых чисел.
• VSH с вычисленным произведением простых чисел.
• Быстрый VSH.
• Быстрый VSH с увеличенным числом блоков.
• VSH-DL

VSH-DL - VSH с дискретным логарифмом, у которого нет односторонней функции с потайным входом, его безопасность зависит от сложности нахождения дискретного логарифма по модулю простого числа p.

Very Smooth Number Discrete Logarithm (VSDL) — это дискретный логарифм от некоторого VSN, взятый по модулю некоторого числа n.

Аналогично введенным ранее обозначениям, возьмем $p_{i}$ как $i$-е простое число. Пусть $c$ — фиксированная постоянная и $p$, $q$ — простые числа, такие, что $p=2q+1$ и $k\leq (\log p)^{c}$. VSDL-задача: по данному $p$ найти целые $e_{1},...,e_{k}$, такие, что $2^{e_{1}}\equiv \prod _{i=2}^{k}p_{i}^{e_{i}}\mod p$, где $|e_{i}|<q$ для всех $i=1,...,k$, причем, хотя бы один из $e_{1},...,e_{k}$ ненулевой.

Предположение VSDL состоит в том, что не существует вероятностного полиномиального по времени алгоритма, решающего VSDL. Существует тесная связь между сложностью вычисления VSDL и сложностью вычисления дискретного логарифма по модулю $p$.

См. также

• Криптографические хеш-функции
• Хеширование

Литература

• S.Contini, A.Lestra, R.Steinfield. VSH, an Efficient and Provable Collision-Resistant Hash Function. // Eurocrypt. — 2006. — С. 1—13.
• M.-J.O.Saarinen. Security of VSH in the real world // INDOCRYPT. — 2006.
• Bart Preneel. [https://www.esat.kuleuven.be/cosic/publications/article-1532.pdf The First 30 Years of Cryptographic Hash

Functions and the NIST SHA-3 Competition] // Cryptographers’ Track at the RSA Conference. — 2010. — С. 5. Архивировано 11 августа 2017 года.