VSH (VSH)

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

VSSR и VSN

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

Для фиксированных постоянных 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$ ^[4]:

x₀ = 1
Пусть $L$ наименьшее целое число, большее или равное $l/k$ , будет числом блоков. Пусть $m_{i}=0$ для $l<i\leq Lk$
Пусть $\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$ .
для каждого j = 0, 1,…, L вычисляем $x_{j+1}=x_{j}^{2}\prod _{i=1}^{k}p_{i}^{m_{jk+i}}\mod n$
возвращаем x_{L + 1}.

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

Свойства VSH

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

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

Вариации VSH

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

Кубический 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—2. Архивировано 4 декабря 2018 года.
↑ S.Contini, A.Lestra, R.Steinfield. VSH, an Efficient and Provable Collision-Resistant Hash Function. // Eurocrypt. — 2006. — С. 3. Архивировано 4 декабря 2018 года.
↑ 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 года.
↑ S.Contini, A.Lestra, R.Steinfield. VSH, an Efficient and Provable Collision-Resistant Hash Function. // Eurocrypt. — 2006. — С. 6. Архивировано 4 декабря 2018 года.
↑ S.Contini, A.Lestra, R.Steinfield. VSH, an Efficient and Provable Collision-Resistant Hash Function. // Eurocrypt. — 2006. — С. 8. Архивировано 4 декабря 2018 года.
↑ M.-J.O.Saarinen. Security of VSH in the real world // INDOCRYPT. — 2006. — С. 2. Архивировано 8 августа 2017 года.
↑ S.Contini, A.Lestra, R.Steinfield. VSH, an Efficient and Provable Collision-Resistant Hash Function. // Eurocrypt. — 2006. — С. 14. Архивировано 4 декабря 2018 года.
↑ M.-J.O.Saarinen. Security of VSH in the real world // INDOCRYPT. — 2006. — С. 3—4. Архивировано 8 августа 2017 года.
↑ S.Contini, A.Lestra, R.Steinfield. VSH, an Efficient and Provable Collision-Resistant Hash Function. // Eurocrypt. — 2006. — С. 10—13. Архивировано 4 декабря 2018 года.

Литература

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 года.

[1] S.Contini, A.Lestra, R.Steinfield. VSH, an Efficient and Provable Collision-Resistant Hash Function. // Eurocrypt. — 2006. — С. 1—2. Архивировано 4 декабря 2018 года.

[2] S.Contini, A.Lestra, R.Steinfield. VSH, an Efficient and Provable Collision-Resistant Hash Function. // Eurocrypt. — 2006. — С. 3. Архивировано 4 декабря 2018 года.

[3] 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 года.

[4] S.Contini, A.Lestra, R.Steinfield. VSH, an Efficient and Provable Collision-Resistant Hash Function. // Eurocrypt. — 2006. — С. 6. Архивировано 4 декабря 2018 года.

[5] S.Contini, A.Lestra, R.Steinfield. VSH, an Efficient and Provable Collision-Resistant Hash Function. // Eurocrypt. — 2006. — С. 8. Архивировано 4 декабря 2018 года.

[6] M.-J.O.Saarinen. Security of VSH in the real world // INDOCRYPT. — 2006. — С. 2. Архивировано 8 августа 2017 года.

[7] S.Contini, A.Lestra, R.Steinfield. VSH, an Efficient and Provable Collision-Resistant Hash Function. // Eurocrypt. — 2006. — С. 14. Архивировано 4 декабря 2018 года.

[8] M.-J.O.Saarinen. Security of VSH in the real world // INDOCRYPT. — 2006. — С. 3—4. Архивировано 8 августа 2017 года.

[9] S.Contini, A.Lestra, R.Steinfield. VSH, an Efficient and Provable Collision-Resistant Hash Function. // Eurocrypt. — 2006. — С. 10—13. Архивировано 4 декабря 2018 года.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]