Security of Poseidon hash function against non-binary differential and linear attacks
In this work we build the security estimations of Poseidon hash function against non-binary linear and differential attacks. We adduce the general parameters for the Poseidon hash function that allow using this hash function in recurrent SNARK-proofs based on MNT-4 and MNT-6 triplets. We also analys...
Збережено в:
| Дата: | 2021 |
|---|---|
| Автори: | , , |
| Формат: | Стаття |
| Мова: | English |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2021
|
| Назва видання: | Кібернетика та системний аналіз |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/190653 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Security of Poseidon hash function against non-binary differential and linear attacks / L. Kovalchuk, R. Oliynykov, M. Rodinko // Кібернетика та системний аналіз. — 2021. — Т. 57, № 2. — С. 115–127. — Бібліогр.: 20 назв. — англ. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-190653 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1906532023-06-17T22:14:37Z Security of Poseidon hash function against non-binary differential and linear attacks Kovalchuk, L. Oliynykov, R. Rodinko, M. Системний аналіз In this work we build the security estimations of Poseidon hash function against non-binary linear and differential attacks. We adduce the general parameters for the Poseidon hash function that allow using this hash function in recurrent SNARK-proofs based on MNT-4 and MNT-6 triplets. We also analysed how to choose S-boxes for such function for this choice to be optimal from the point of view of the number of constraints and security. We also showed how many full rounds is sufficient to guarantee security of such hash function against non-binary linear and differential attacks and calculated the number of constraints per bit that is achieved in the proposed realizations demonstrating a considerable gain was demonstrated, as compared to the Pedersen hash function. Побудовано оцінки стійкості геш-функції Poseidon до небінарних лінійних і різницевих атак. Визначено загальні параметри для геш-функції Poseidon, які забезпечують можливість її використання у рекурентних SNARK-доведеннях, що базуються на триплетах MNT-4 і MNT-6. Проаналізовано, як потрібно обирати S-блоки для цієї геш-функції, щоб цей вибір був оптимальним з погляду як стійкості, так і кількості констрейнтів. Показано, яка кількість раундів є достатньою, щоб гарантувати стійкість такої геш-функції до небінарних лінійних і різницевих атак, та обчислено кількість констрейнтів на біт інформації для запропонованих реалізацій цієї функції з демонстрацією суттєвого виграшу у порівнянні з геш-функцією Педерсена. Построены оценки стойкости хеш-функции Poseidon к небинарным линейным и разностным атакам. Определены общие параметры хеш-функции Poseidon, позволяющие использовать её в рекуррентных SNARK-доказательствах, базирующихся на триплетах MNT-4 и MNT-6. Выполнен анализ того, как нужно выбирать S-блоки для этой хеш-функции, чтобы этот выбор был оптимальным с точки зрения как стойкости, так и количества констрейнтов. Показано, какое количество раундов является достаточным, чтобы гарантировать стойкость этой хеш-функции к небинарным линейным и разностным атакам, вычислено количество констрейнтов на бит информации для предложенных реализаций этой функции с демонстрацией существенного выигрыша в сравнении с хеш-функцией Педерсена. 2021 Article Security of Poseidon hash function against non-binary differential and linear attacks / L. Kovalchuk, R. Oliynykov, M. Rodinko // Кібернетика та системний аналіз. — 2021. — Т. 57, № 2. — С. 115–127. — Бібліогр.: 20 назв. — англ. 1019-5262 http://dspace.nbuv.gov.ua/handle/123456789/190653 681.3.06:006.354 en Кібернетика та системний аналіз Інститут кібернетики ім. В.М. Глушкова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| topic |
Системний аналіз Системний аналіз |
| spellingShingle |
Системний аналіз Системний аналіз Kovalchuk, L. Oliynykov, R. Rodinko, M. Security of Poseidon hash function against non-binary differential and linear attacks Кібернетика та системний аналіз |
| description |
In this work we build the security estimations of Poseidon hash function against non-binary linear and differential attacks. We adduce the general parameters for the Poseidon hash function that allow using this hash function in recurrent SNARK-proofs based on MNT-4 and MNT-6 triplets. We also analysed how to choose S-boxes for such function for this choice to be optimal from the point of view of the number of constraints and security. We also showed how many full rounds is sufficient to guarantee security of such hash function against non-binary linear and differential attacks and calculated the number of constraints per bit that is achieved in the proposed realizations demonstrating a considerable gain was demonstrated, as compared to the Pedersen hash function. |
| format |
Article |
| author |
Kovalchuk, L. Oliynykov, R. Rodinko, M. |
| author_facet |
Kovalchuk, L. Oliynykov, R. Rodinko, M. |
| author_sort |
Kovalchuk, L. |
| title |
Security of Poseidon hash function against non-binary differential and linear attacks |
| title_short |
Security of Poseidon hash function against non-binary differential and linear attacks |
| title_full |
Security of Poseidon hash function against non-binary differential and linear attacks |
| title_fullStr |
Security of Poseidon hash function against non-binary differential and linear attacks |
| title_full_unstemmed |
Security of Poseidon hash function against non-binary differential and linear attacks |
| title_sort |
security of poseidon hash function against non-binary differential and linear attacks |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| publishDate |
2021 |
| topic_facet |
Системний аналіз |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/190653 |
| citation_txt |
Security of Poseidon hash function against non-binary differential and linear attacks / L. Kovalchuk, R. Oliynykov, M. Rodinko // Кібернетика та системний аналіз. — 2021. — Т. 57, № 2. — С. 115–127. — Бібліогр.: 20 назв. — англ. |
| series |
Кібернетика та системний аналіз |
| work_keys_str_mv |
AT kovalchukl securityofposeidonhashfunctionagainstnonbinarydifferentialandlinearattacks AT oliynykovr securityofposeidonhashfunctionagainstnonbinarydifferentialandlinearattacks AT rodinkom securityofposeidonhashfunctionagainstnonbinarydifferentialandlinearattacks |
| first_indexed |
2025-07-16T13:40:19Z |
| last_indexed |
2025-07-16T13:40:19Z |
| _version_ |
1837811074577989632 |
| fulltext |
UDC 681.3.06:006.354
L. KOVALCHUK, R. OLIYNYKOV, M. RODINKO
SECURITY OF POSEIDON HASH FUNCTION AGAINST NON-BINARY
DIFFERENTIAL AND LINEAR ATTACKS1
Abstract. In this work we build the security estimations of Poseidon hash
function against non-binary linear and differential attacks. We adduce the
general parameters for the Poseidon hash function that allow using this hash
function in recurrent SNARK-proofs based on MNT-4 and MNT-6 triplets.
We also analysed how to choose S-boxes for such function for this choice to be
optimal from the point of view of the number of constraints and security. We
also showed how many full rounds is sufficient to guarantee security of such
hash function against non-binary linear and differential attacks and calculated the
number of constraints per bit that is achieved in the proposed realizations
demonstrating a considerable gain was demonstrated, as compared to the
Pedersen hash function.
Keywords: SNARK, constraints, Poseidon hash function, non-binary linear and
differential cryptanalysis.
INTRODUCTION
One of the most important problems arising in construction of SNARK-proofs and
STARK-proofs [1–3] is reduction of the number of constraints describing
algorithms in the respective SNARK-system. The construction of such proofs
begins with the fact that a certain transformation (for example, a hash function)
should be described as a system of certain equations of many variables over a
finite field, the left part of which contains a polynomial of many second degree
variables, and the right part — a polynomial of many variables of the first degree.
These equations are called constraints, and their complexity determines the
complexity of constructing the appropriate SNARK-proof. Most often
SNARK-proofs are used to prove knowledge of the pre-image of some hash
function. Therefore, the hash functions used in such blockchains should be
designed so that they can be described by as few constraints as possible.
One of the first hash functions convenient for constructing SNARK-proofs was
the Pedersen hash function [4, page 134]. It is based on operations in a group of points
of an elliptic curve, which, in turn, can be reduced to operations in the corresponding
finite field. Since constraints are polynomials just over such a field, the number of
constraints required to specify such a hash function is ten times less than for
“classical” hash functions that operate with byte and bit operations (about 1.68
constraints per 1 bit of input). This number of constraints is quite acceptable, but the
question of reducing it still remains relevant. The Poseidon hash function proposed
in [5] appeared to be quite a good construction with respect to the number of
constraints. For this function, the number of constraints is up to 15 times smaller than
for the Pedersen hash function. Utilization of this function in SNARK-systems requires
provision of a full substantiation of its security against the main applicable
cryptographic attacks. The Poseidon hash function is based upon the SPONGE
construction [6] that uses the HADES block cipher algorithm [7] as the inner
permutation. For this reason, the main part of the security substantiation for the
Poseidon hash function is to show that the HADES algorithm is indistinguishable from
ISSN 1019-5262. ʳáåðíåòèêà òà ñèñòåìíèé àíàë³ç, 2021, òîì 57, ¹ 2 115
1 This work was supported in part by the National Research Foundation of Ukraine under Grant
2020.01/0351.
© L. Kovalchuk, R. Oliynykov, M. Rodinko, 2021
a random permutation [5, 6]. The authors of the HADES algorithm, and later the
authors of the Poseidon hash function adduced very detailed substantiations for
security of these constructions against some class of attacks they called “algebraic
attacks”. However, for these algorithms, substantiation of security against linear and
differential cryptoanalysis attacks was to a large extent empirical, and requires further
analysis to achieve a strict formal substantiation. E.g. in substantiation of the algorithm
security against linear attacks, the authors considered coordinate functions of S-boxes
demonstrating that in fact they analyzed its security against classical linear attacks.
However, as shown in [8, 9], for non-binary ciphers it is necessary to analyze security
specifically against non-binary linear cryptoanalysis, as both the key adder and the
linear layer use operations in the prime field instead of binary operations. The similar
situation takes place with respect to the differential cryptanalysis.
The purpose of this paper is to obtain security estimates of Poseidon hash function
against non-binary linear and differential attacks, show how many full rounds would
be sufficient to guarantee security of such hash function against these attacks, adduce
the general parameters for the Poseidon hash function that allows using this hash
function in recurrent SNARK-proofs.
1. MATHEMATICAL MODEL OF POSEIDON.
The Poseidon hash function [5] uses SPONGE construction [6] with a permutation
named HadesMiMC [7] inside it (see Fig. 1).
Three parameters describe this construction: capacity c, rate r, and permutation
length N , where N c r� � . From some practical consideration, we are interested in
case when N p� 3[log ] , c p� 2[log ] , r p� [log ] , where prime p is of the special
form, which provides compatibility with triplets MNT-4 or MNT-6 in CODA (now —
MINA) [10. 11]. Any permutation or block cipher may be used inside SPONGE. The
authors of [7] suggested to use HadesMiMC as the permutation that needs the least
number of constraints per bit, when used in SNARK-systems. HadesMiMC may be
considered as a block cipher whose round functions are different in different rounds.
The main idea of HadesMiMC is to use rounds with full number of S-boxes and rounds
with partial number of S-boxes (for example, only 1 S-box). The general scheme of
Hades is given in the Fig. 2 (this Figure is taken from [7] with all its designations,
which are wide used for block ciphers). Such construction allows reducing the number
of constraints, while preserving security level against different (statistical and
algebraic) attacks.
116 ISSN 1019-5262. ʳáåðíåòèêà òà ñèñòåìíèé àíàë³ç, 2021, òîì 57, ¹ 2
Fig. 1. SPONGE construction
Now we describe the mathematical
model of the permutation HadesMiMC
on which Poseidon is based.
Let p be a large prime, l is its bit
length, l p� log .
Define a bijection s F Fp p: � as
s x x pu( ) � mod , where ( , )u p� �1 1.
For some t N� define values
x C Fp
t, ( )� as x x xt� � �( )� 1 ,
C c ct� ( , ..., )1 , where x c Fi i p, � ,
i t�1, . For x Fp
t�( ) define two
mappings: S F Fp
t
p
tfull :( ) ( )� and
S F Fp
t
p
tpart :( ) ( )� as
S x s x s xt
full ( ) ( ( ) ( ))� � �� 1 ,
S x x x s xt
part ( ) ( , ( ))� � �� 2 1 .
(1)
Finally, define an MDS-matrix
A F Fp
t
p
t:( ) ( )� of the size t t .
Define the round functions for
the permutation HadesMiMC. They
are of two types: the round function
with a full S-box layer that is defined
as f F F
C p
t
p
tfull :( ) ( )� , where for arbitrary C Fp
t�( ) :
f x A S x C
C
full full( ) ( * )� � , (2)
and the round function with a partial S-box layer that is defined as
f F F
C p
t
p
tpart :( ) ( )� , where for arbitrary C Fp
t�( ) :
f x A S x C
C
part part( ) ( * )� � , (3)
where x C x c x ct t* ( )� � � � �� 1 1 and “+” is field addition (addition modulo p) and
S full , S part were defined in (1).
Definition 1. A HadesMiMC-like permutation with parameters p t u r, , , full , and
rpart is the family of permutations H F F
p t u r r
p
t
p
t
C
( , , , , )
:( ) ( )full part � parameterized by
the set of round constants C � � � �( )C C r r1 2�
full part
, C Fi p
t�( ) that are defined as
H x
p t u r r
C
( , , , , )
( )full part �
�
� � �
f f f
C C Cr r r r r2 1 2full part full part full
full full
��� �
� �r r r
f f f x
C C C
part full full
part part full full
��� � �
1 1
( ) . (4)
If parameters p t u r, , , full , and rpart are set, we will write HC , for simplicity.
Note. The transformation (4) means that, for fixed set of constraints
C � � � �( )C C r r1 2�
full part
, we first apply functions f f
C Cr1
full full
full
� �� , i.e., functions of the
ISSN 1019-5262. ʳáåðíåòèêà òà ñèñòåìíèé àíàë³ç, 2021, òîì 57, ¹ 2 117
Fig. 2. HadesMiMC
type (2) with a full S-box layer and with corresponding “round keys” C Cr1� ��
full
, and
they are the first rfull rounds of the transformation. Then we apply functions of the
type (3) with a partial S-box layer during rpart round and with corresponding “round
keys;” and then again apply rfull rounds with functions of the type (2).
2. CRYPTOGRAPHICAL SECURITY OF POSEIDON
2.1. Security in the random Oracle model. Security of SPONGE construction
depends mostly on the security of its internal permutation, HadesMiMC in our
case. So we will pay a lot of attention to security of HadesMiMC. It was proven
in [12] that if an internal permutation is modeled as a randomly chosen
permutation, then the SPONGE function is indistinguishable from the random
oracle up to 2 2ñ/ calls to it.
For some practical aspects, it is convenient to set c l p� 2 ( ) , so the maximal
security level of the SPONGE construction is l p( ) . It means that we should prove that
the security level of the internal permutation is also not less than l p( ) . But we will use
stronger requirement to find the number of rounds of the permutation.
In what follows, under security estimations against differential and linear
cryptanalysis of block cipher we will understand the maximum of average (on keys)
probabilities of its differential and linear characteristics, respectively.
2.2. Security against linear and differential attacks. In this chapter we
construct, rigorously proved, security estimates for HadesMiMC against these two
types of statistical attacks. Note that to construct estimates against differential attacks,
we mostly use known results or their generalizations. But to construct the similar
estimates against linear attacks, we had to prove a few non-trivial statements on sums
of characters of the additive group of the finite field.
2.2.1. Security estimates of non-binary cipher HadesMiMC against
differential cryptanalysis. To construct security estimations against differential
cryptanalysis, we consider HadesMiMC as a block cipher. Further we use the
following results.
Definition 2 [13]. The block cipher E with the round function
f M K M: �
(where M is an Abelian group w.r.t. some operation “*, ” 0 is its neutral element)
is called a Markov cipher w.r.t. “* ” if
�x M, ,� � :
1 1
01
| |
( ( , * )* ( , ) , )
| |
( ( , )* ( , )
K
f k x f k x
K
f k f k
k K
� � � � ��
�
�� �
�
� 1, )�
k K
, (5)
where � is the Kronecker symbol: �( , )
,
, .
x y
x y� ��
�
1
0
if
else
Note. This definition can be easily generalized for the case when the round
functions are different.
Definition 3 [14]. The branch number of the matrix A F Fp
t
p
t:( ) ( )� of the size
t t is
br A wt Ax wt x
x Fp
t
( ) min ( ) ( )
( ) \( ,..., )
� �
� 0 0
{ },
where wt is the Hamming weight.
118 ISSN 1019-5262. ʳáåðíåòèêà òà ñèñòåìíèé àíàë³ç, 2021, òîì 57, ¹ 2
Note that if A is an MDS-matrix, then its branch number is maximal possible (for
its size) and is equal to br A t( ) � �1. For example, in our case t � 3 and br A( ) � 4 .
Proposition 1. The block cipher (4) is a Markov cipher.
This proposition may be proven directly, by checking (5) for its round functions.
Proposition 2 (easily derived from [15]). For the Markov cipher (4), its security
against differential cryptanalysis is upper estimated with the value �b , where
� � � �
� �
�max ( ( ) ( ), )
, *� �
� � �
F x Fp p
p
s x s x
1
, (6)
“+” is the field addition, b is the number of active S-boxes in all rounds.
Proposition 3 [14]. The number of active S-boxes in 2 sequential rounds with the
round function (2) is not less than br A( ) .
In the case if A is an MDS-matrix of the size t t , br A( ) � �1 and, according to
Proposition 3, the number of active S-boxes in 2 sequential rounds with full S-box
layer is not less than t �1. But if there are several rounds, each with only one S-box,
between two rounds with a full S-box layer, we cannot state anything about the
number of active S-boxes in these rounds, except that this number is not less than the
number of rounds. It should be noted that the authors of [5] did not take this detail into
account when constructing security estimates against linear and differential
cryptanalysis, and, as a result, incorrect estimates were obtained.
Proposition 4 (obvious). The number of active S-boxes in all rounds of (4) is not
less than the number of active S-boxes in rounds with a full S-box layer.
Proposition 5 (corollary of Prop. 2 and Prop. 3). The number b of active S-boxes
in (4) is not less than
b t
r
� � �
�
�
�
�
�
�2 1
2
( ) full , (7)
and, if rfull is even, is not less than
b t r� �( )1 full .
Note. The inequality (7) implies that it is more efficient to have an even value
rfull , because one extra round that makes rfull odd does not increase the value in (7).
So, in what follows we will choose rfull to be even.
In this chapter we construct security estimates for HadesMiMC-like permutations
with two types of S-boxes: power functions and inverse S-boxes. Before proving the
main results, we will need the following auxiliary statement about parameters (6).
Proposition 6 [16].
1. Let s x x pu( ) � mod , where ( , )u p� �1 1. Then � �
�( )u
p
1
.
2. Let s x x p x( ) if ;
,
� ��
�
�1 0
0
mod
else.
Then � �
4
p
.
Theorem 1. 1. Let rfull be even, s x x pu( ) � mod , A F Fp
t
p
t:( ) ( )� be an MDS
matrix of the size t t . Then the security estimate of the block cipher (4) against
differential cryptanalysis is upper bounded with the value
u
p
t r
��
�
��
�
�
��
�
1
1( ) full
. (8)
ISSN 1019-5262. ʳáåðíåòèêà òà ñèñòåìíèé àíàë³ç, 2021, òîì 57, ¹ 2 119
2. Let rfull be even, s x x p( ) � �1mod , A F Fp
t
p
t:( ) ( )� is an MDS matrix of the
size t t . Then security estimate of the block cipher (4) against differential
cryptanalysis is upper bounded with the value
4
1
p
t r
�
�
��
�
�
��
�( ) full
.
Proof. It is obvious using Propositions 1–6 and the fact that in this case
r r
rfull full
full
2 2
�
�
�
�
�
� �
�
�
�
�
�
� � . �
Usually a block cipher is considered to be practically secure against differential
cryptanalysis, if its security estimate is not more than 2�N , where N is its block size.
But in our case, as we showed in 2.1, the maximal security level of SPONGE
construction is l p p( ) log� . So the weaker requirement may be formulated as
�b p �2 log .
However, we will use stronger requirement. Moreover, to increase the security
and make it closer to the theoretical one, we require
�b N �2 2 ,
which means
u
p
t r
N��
�
��
�
�
��
�
�1
2
1
2
( ) full
or
4
2
1
2
p
t r
N�
�
��
�
�
��
�
�
( ) full
, (9)
using statements 1 and 2 of Theorem 1 for powered and inverse S-boxes,
respectively. Also in [5] the authors proposed to add two extra full rounds, just for
any case. But adding two full rounds (one at the beginning, and one at the end)
makes rfull odd and does not increase security. So if we decide to add some extra
rounds, we should add them in such a way that rfull is even (i.e., when adding
additional rounds we should provide even parity of rfull ).
As we can see from (9), a permutation with power S-boxes with u! 5 requires
more rounds than with inverse ones, for the same level of security. In the next chapter,
we will discuss a type of S-boxes that is preferable from different points of view.
2.2.2. Security estimates of non-binary cipher HadesMiMC against linear
cryptanalysis. According to [9], the parameters that characterize practical security of a
block cipher against linear attacks, essentially depend on the structure of this cipher, and
first of all, on the operation in the key adder. Thus, the practical security estimate (with
respect to the field addition in Fp ) of a cipher E against linear cryptanalysis is the value
max ( , )
, �� �
� �
�
�
F
E b
p
ELP L ,
where b is the number of active S-boxes, and the parameter L depends on the
S-box (see Definition 15 and explanation on the page 25 in [9]):
L L s
p
x s x
F x Fp
p
� �
� �
�( ) max ( ( ), ( ( )))
, �� �
� �
1
2
, (10)
where � and � are additive characters of Fp (characters of the additive group of
this field).
120 ISSN 1019-5262. ʳáåðíåòèêà òà ñèñòåìíèé àíàë³ç, 2021, òîì 57, ¹ 2
The value b is the same as for the differential cryptanalysis, i.e. it is the number of
all active S-boxes in the cipher. Using the same consideration as in 2.1, we get
b t r� �( )1 full if rfull is even (we consider only this case).
Proposition 7.
1. Let s x x pu( ) � mod , where ( , )u p� �1 1 . Then L s
u
p
( )
( )
�
�1 2
.
2. Let s x x p x( ) if ;
, .
� ��
�
�1 0
0
mod
else
Then L s
p
( ) �
16
.
Proof.
1. First, let us estimate the value
( ( ) ( ( ))) ( ( ) ( ))� � � �x s x x x
x F x Fp p
�
� �
� � 13 . (11)
Note that the group ( , )Fp � is cyclic (with the generator g �1), so the
corresponding group of characters ( � , )Fp is also cyclic. Let � be the generator of
( � , )Fp . Then any element from this group, particularly characters � and �, can be
represented as
� � �� , � � �� ,
for some appropriate 0 1� � �� �, p .
Then
� � � � � � � � � � �� �( ) ( ) ( ) ( ) ( ) ( ) ( )x x x x x x x x13 13 13 13� � � � � � , (12)
using the fact that � is a homomorphism.
Now we can rewrite (11) using (12) as
( ( ) ( )) ( )� � � � �x x x x
x F x Fp p
13 13
� �
� �� � . (13)
Applying the Weil Theorem ([17], Theorem 5.38) to (13), we obtain
� � � � �
x Fp
x x x x p p
�
� � � � � � �( ) ( ( ) )13 13 1 12deg . (14)
After application of (11)–(14) to (10), we obtain
L L s
p
x s x
F x Fp
p
� � �
� �
�( ) max ( ( ), ( ( )))
, �� �
� �
1
2
� � � � � �
�
�max ( )
,� �
� � �
1 1
12
14413
2
2
p
x x
p
p
px Fp
.
2. First, let us estimate the value
( ( ) ( ( ))) ( ( ) ( ))
*
� � � �x s x x x
x F x Fp p
� �
�
�
�
� � 1 1. (15)
Note that the group ( , )Fp � is cyclic (with the generator g �1), so the
corresponding group of characters ( � , )Fp is also cyclic. Let � be the generator
ISSN 1019-5262. ʳáåðíåòèêà òà ñèñòåìíèé àíàë³ç, 2021, òîì 57, ¹ 2 121
of ( � , )Fp . Then any element from this group, particularly characters � and �, can be
represented as
� � �� , � � �� ,
for some appropriate 0 1� � �� �, p .
Then
� � � � � � � � � � �� �( ) ( ) ( ) ( ) ( ) ( ) ( )x x x x x x x x� � � �� � � � � �1 1 1 1 , (16)
using the fact that � is a homomorphism.
Now we can rewrite (15) using (16) as
( ( ) ( )) ( )
* *
� � � � �x x x x
x F x Fp p
�
� �
�� �� �1 1 . (17)
Applying the theorem about the Kloosterman sum ([17], Theorem 1.5) to (17), we
obtain
� � � �
��x F x x F x x
p p
x x x x p
�
�
� �
� �� � � � � � �
*
( ) ( )
, :
1
1 22 2 2
1 2 1 2
4 p. (18)
After application of (15)–(18) to (10), we obtain
L L s
p
x s x
F x Fp
p
� � �
� �
�( ) max ( ( ), ( ( )))
, �� �
� �
1
2
� � �
�
�
�
�
�
�
�
�
�
�
� � � �
�
��max (
, *� �
� � �
1
1
1
4
161
2
2
p
x x
p
p
p
x Fp
. �
Theorem 2. 1. Let rfull be even, s x x pu( ) � mod , A F Fp
t
p
t:( ) ( )� is an MDS
matrix of the size t t . Then the security estimate of the block cipher (4) against linear
cryptanalysis is upper bounded with the value
( )
( )
u
p
t r
��
�
�
�
�
�
�
�
�
1 2
1 full
.
2. Let rfull be even, s x x p( ) � �1mod , A F Fp
t
p
t:( ) ( )� is an MDS matrix of the
size t t . Then security estimate of the block cipher (4) against linear cryptanalysis is
upper bounded with the value
16
1
p
t r
�
�
��
�
�
��
�( ) full
.
Proof. It is obvious using Propositions 1–5, Proposition 7 and the fact that in this
case
r r
rfull full
full
2 2
�
�
�
�
�
� �
�
�
�
�
�
� � . �
3. CHOICE OF S-BOXES
Choice of S-boxes should take into account the following aspects:
— the mapping s F Fp p: � should be bijective, i.e., for a power S-box the
requirement ( , )p u� �1 1 should be met;
122 ISSN 1019-5262. ʳáåðíåòèêà òà ñèñòåìíèé àíàë³ç, 2021, òîì 57, ¹ 2
— for reasons of security against linear and differential cryptanalysis, the
parameters � and L (which depend only on the S-box) should be as small as possible;
— in terms of SNARKs implementation complexity, the number of constraints (which
also depends only on the number and type of S-boxes) should be as small as possible.
Recall that for the inverse S-boxes, the parameters � and L are estimated by upper
bound as � �
4
p
and L
p
�
16
, and for the power ones – as � �
�( )u
p
1
and L
u
p
�
�( )1 2
(Propositions 6 and 7). So for the power S-boxes it makes sense to choose the
parameter u as u N v p� � � �min :( , ){ }� 1 1 .
For the inverse S-boxes the parameters � and L will be smaller than for the power
ones if u � 3. So, in terms of the cryptographic security, the most appropriate are either
inverse or cubic S-boxes, if the latest ones define a bijective mapping. If p�1 is
divided by 3, then inverse S-boxes have no competitors.
In terms of minimizing the number of constraints, inverse and power S-boxes with
a small value of the parameter u are also the most appropriate. Indeed, to describe an
inverse S-box, 3 constraints are needed; to describe a cubic S-box – 2 constraints:
x x x
x x x
1 1 2
1 2 3
�
�
�
�
;
,
to describe an S-box s x x p( ) ,� 5b mod 3 constraints are needed:
x x x
x x x
x x x
1 1 2
2 2 3
1 3 4
�
�
�
�
"
�"
;
;
,
etc., with an increase in the exponent u the number of constraints grows
approximately as 2 log u. So, if p�1 is divided by all relatively “small” prime 3, 5,
7, 11, …, then both the security requirements and the requirements for simplicity
of implementation lead to the choice of inverse S-boxes.
However, on the other hand, implementation of an inverse S-box is costly, since
requires execution of the Euclid’s algorithm, that, in turn, requires the order of
#(log )p divisions with a remainder. Therefore, when choosing an S-box, all factors
must be taken into account and an acceptable compromise must be sought.
In the next section 5, when calculating the algorithm parameters for specific
values of the field characteristics, we will consider two options for choosing of
S-boxes — inverse and power, with the smallest exponent providing bijection.
4. NUMBER OF ROUNDS WITH FULL AND PARTIAL S-BOX LAYERS
AND FULL NUMBER OF CONSTRAINTS
Following [5, 7], we define the number of rounds with a full S-box layer, rfull , as
the minimal number of rounds that guarantee security against differential and linear
cryptanalysis (forward and backward). Then determine the number of rounds with
a partial layer of S-boxes, based on considerations of the security against algebraic
attacks.
As noted, the authors of [5] also recommend adding two rounds just in case.
However, after adding two rounds (one at the beginning, one at the end), the value rfull
will become odd, i.e. adding two rounds will not increase the security against statistical
attacks. If we add two rounds at the beginning and end, it will significantly increase
the number of constraints. We do not see a reasonable need to increase the number of
rounds with a full layer of S-boxes, especially in a situation where the number of
constraints is critical.
ISSN 1019-5262. ʳáåðíåòèêà òà ñèñòåìíèé àíàë³ç, 2021, òîì 57, ¹ 2 123
The number of constraints per bit is determined as follows. The number of
constraints required to specify one S-box must be multiplied by the number of all
S-boxes, which is completely determined by the number of rounds of both types and
their structure. Then the resulting value must be divided by the value r that determines
the length of the output on one iteration of the SPONGE construction.
5. NUMERICAL RESULTS FOR MNT-COMPATIBLE PARAMETERS
We calculated the number of rounds with a full layer of S-boxes for a prime field
of characteristic p , where the bit length of the characteristic is equal to 753. As
a prime field, we chose one of the fields for which triplets MNT-4 and MNT-6 are
defined [11]. In rounds with a full layer of S-boxes, we will place 3 S-boxes, in
rounds with a partial layer — one S-box. We define a linear operator as an MDS
matrix of dimension 3 3 . In this case, the capacity c � � �2 752 1504 and rate
r � 752 if you use a byte representation. Power S-boxes were chosen as
s x x p( ) � 13mod , because of min :( , ){ } = 13� �� � �N p 1 1 . For inverse S-boxes and
power S-boxes of the form s x x p( ) � 13mod the number of rounds with a full layer
of S-boxes is 4 (2 rounds at the beginning, 2 at the end, to eliminate the
possibility of both attacks with the chosen plaintext and attacks with the chosen
ciphertext). The number of rounds with a partial layer of S-boxes, according to
(4.1) and (4.2) in [5], will be about 60. In this case, the number of constraints per
bit is equal to 0.48 for power S-boxes and 0.29 for inverse S-boxes, which is
3.5–5.8 times less than the same indicator for the Pedersen function.
The number of full rounds for the Poseidon we find from the inequality
144
2 2
4
2 6
p
r
N p�
�
��
�
�
�� � �� �
full
,
whence we obtain
rfull �
�
�
�
��
�
��
�
6 753
4 745
2,
i.e., we have two rounds with a full layer of S-boxes at the beginning and at the
end of the algorithm.
The same number of rounds is enough to guarantee security against linear
cryptanalysis.
Note than in case of adding 2 extra rounds (one to the beginning, one to the end)
and 2 rounds to make rfull even, we obtain
rfull � 4 ,
so the whole number of full rounds is 8.
CONCLUSIONS
The paper contains the following results.
1. Security estimates were considered against non-binary linear and differential
attacks. Let us note that construction of such estimates uses serious algebraic
techniques, in particular, some properties of sums of characters for an additive group
of the finite field, and properties of sums of such characters.
2. We adduce the general parameters for the Poseidon hash function that allows
using this hash function in recurrent SNARK-proofs based on MNT-4 and MNT-6
triplets.
3. We analyzed how to choose S-boxes for such function, for this choice to be
optimal from the point of view of the number of constraints and of security.
124 ISSN 1019-5262. ʳáåðíåòèêà òà ñèñòåìíèé àíàë³ç, 2021, òîì 57, ¹ 2
4. We showed how many full rounds would be sufficient to guarantee security of
such hash function against non-binary linear and differential attacks.
5. We calculated the number of constraints per bit that is achieved in the proposed
realization; a considerable gain was demonstrated, as compared to the Pedersen hash
function.
We provided strict formal proofs for all listed results.
Following [5] and [7], we chose the round functions for random permutations and
their parameters in the following way:
— the number of rounds with a full S-box layer is chosen as the minimal number
that guarantees security against generalized differential and linear attacks;
— the number of rounds with a partial S-box layer is chosen as the minimal
number that guarantees security against other attacks, called “algebraic” in [5, 7];
— S-BOXes are chosen as power functions in the field that set bijection in this field.
Considering specific features of the hash function application and the need for its
compatibility with MNT-4 or MNT-6 triplets [10], we chose the following parameters
of the round functions:
— a prime field Fp where p is a prime number that is used in MNT-4, of the
length of 753 bits;
— exponent of the function describing the S-BOX was chosen so as from one
side, to guarantee the required level of security against attacks, and from the other side,
to minimize the number of constraints;
— one round with a full S-box layer contains three S-BOXes, and a round with a
partial S-box layer contains one S-BOX.
Such selection of parameters in the case of the prime field with the characteristic
bitlength of about 750 bits (MNT-fields, [11]) allows obtaining of the following
characteristics of the hash function at the set security level of �128 bits:
— 4 rounds with a full S-box layer (two rounds at the beginning and two at the end);
— about 60 rounds with a partial S-box layer;
— from 0.28 to 0.48 constraints per bit.
The results obtained show that the Poseidon hash function is secure against
non-binary linear and differential attacks. Given the security level, we can choose
parameters of this hash that guarantee its cryptographical security. An indisputable
advantage of the hash function with such structure is its efficiency in utilization for
SNARK-proofs. For completeness of our investigations it should be noted that very
similar results concerning of differential and linear attacks on block ciphers with
non-binary operations were obtained in [18-20]. But algorithms and transformations,
considered in these works, were not SNARK-oriented, like HadesMiMC and Poseidon.
REFERENCES
1. Ben-Sasson E., Bentov I., Horesh Y., Riabzev M. Scalable, transparent, and post-quantum secure
computational integrity. IACR Cryptology ePrint Archive. 2018. URL: https://eprint.iacr.org/2018/046.pdf.
2. Groth J. On the size of pairing-based non-interactive arguments. Proc. Advances in
Cryptology — EUROCRYPT 2016. (8–12 May 2016, Vienna, Austria). Vienna, 2016. LNCS.
Vol. 9666, P. 305–326. https://doi.org/10.1007/978-3-662-49896-5_11.
3. Parno B., Howell J., Gentry C., Raykova M. Pinocchio: nearly practical verifiable computation.
Proc. IEEE Symposium on Security and Privacy. (19–22 May 2013, Berkeley, CA, USA). Berkeley,
2013. P. 238–252. https://doi.org/10.1109/SP.2013.47.
4. Hopwood D., Bowe S., Hornby T., Wilcox N. Zcash protocol specification: Version 2020.1.15
[Overwinter+Sapling+Blossom+Heartwood+Canopy]. Tech. rep., Electric Coin Company. 2020.
URL: https://github.com/zcash/zips/blob/master/protocol/protocol.pdf.
ISSN 1019-5262. ʳáåðíåòèêà òà ñèñòåìíèé àíàë³ç, 2021, òîì 57, ¹ 2 125
5. Grassi L., Kales D., Khovratovich D., Roy A., Rechberger C., Schofnegger M. Starkad and
Poseidon: New hash functions for zero knowledge proof systems, IACR Cryptology ePrint Archive.
2019. URL: https://eprint.iacr.org/2019/458.pdf.
6. Bertoni G., Joan D., Micha��el P., Gilles V.A. Cryptographic sponge functions. 2011: 93 p.
URL: https://keccak.team/files/CSF-0.1.pdf.
7. Grassi L., L��uftenegger R., Rechberger C., Rotaru D., Schofnegger M. On a generalization of
substitution-permutation networks: the HADES design strategy. IACR Cryptology ePrint Archive.
2019. URL: https://eprint.iacr.org/2019/1107.pdf.
8. Abdelraheem M.A., A
�
gren M., Beelen P., and Leander G. On the distribution of linear biases: Three
instructive examples. Proc. Advances in Cryptology — CRYPTO 2012. (19–23 August 2012, Santa
Barbara, CA, USA). Santa Barbara, 2012. LNCS. Vol. 7417. P. 50–67. https://doi.org/
10.1007/978-3-642-32009-5_4.
9. Baigneres T., Stern J., Vaudenay S. Linear cryptanalysis of non binary ciphers. Proc. 14th
International Workshop, SAC 2007. (16-17 August 2007, Ottawa, Canada). Ottawa, 2007. LNCS.
Vol. 4876. P. 184–211. https://doi.org/10.1007/978-3-540-77360-3_13.
10. Miyaji A., Nakabayashi M., Takano Sh. New explicit conditions of elliptic curve traces for
FR-reduction. IEICE Transactions on Fundamentals of Electronics, Communications and Computer
Sciences. 2001. Vol. E84-A, N 5. P. 1234–1243. URL: http://citeseerx.ist.psu.edu/viewdoc/
download?doi=10.1.1.20.8113&rep=rep1&type=pdf.
11. Constructing optimal pairing-friendly curves. Coinlist [online]. URL: https://coinlist.co/build/
coda/pages/theory.
12. Bertoni G., Daemen J., Peeters M., Assche G.V. On the indifferentiability of the sponge construction.
Proc. Advances in Cryptology — EUROCRYPT 2008. (13-17 April 2008, Istanbul, Turkey) Istanbul,
2008. LNCS. Vol. 4965. P. 181–197. https://doi.org/10.1007/978-3-540-78967-3_11.
13. Lai X., Massey J.L., Murphy S. Markov ciphers and differential cryptanalysis. Proc. Advances in
Cryptology — EUROCRYPT’91. (8–11 April 1991, Brighton, UK). Brighton, 1991. Vol. 547.
P. 17–38. https://doi.org/10.1007/3-540-46416-6_2.
14. Youssef A.M., Mister S., Tavares S.E.: On the design of linear transformations for substitution permutation
encryption networks. Workshop on Selected Areas of Cryptography (SAC’96): Workshop Record. 1997.
P. 40–48. URL: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.17.1208&rep=rep1&type=pdf.
15. Vaudenay S. On the security of CS-cipher. Proc. 6th International Workshop, FSE’99. (24–26 March
1999, Rome, Italy). Rome, 1999. P. 260–274. https://doi.org/10.1007/3-540-48519-8_19.
16. Nyberg K. Differentially uniform mappings for cryptography. Proc. Advances in Cryptology —
EUROCRYPT ’93. (23–27 May 1993, Lofthus, Norway). Lofthus, 1993. LNCS. Vol. 765. P. 55–64
(1994). https://doi.org/10.1007/3-540-48285-7_6.
17. Lidl R., Niederreiter H. Introduction to finite fields and their applications. UK: Cambridge
University Press, 1994. https://doi.org/10.1017/CBO9781139172769.
18. Kovalchuk L.V. Upper-bound estimation of the average probabilities of integer-valued differentials
in the composition of key adder, substitution block, and shift operator. Cybernetics and Systems
Analysis. 2010. Vol. 46, N 6. P. 936–944. https://doi.org/10.1007/s10559-010-9274-2.
19. Kovalchuk L.V., Bezditnyi V.T. Upper bounds for the average probabilities of difference
characteristics of block ciphers with alternation of Markov transformations and generalized Markov
transformations. Cybernetics and Systems Analysis. 2014. Vol. 50, Iss. 3. P. 386–393.
https://doi.org/10.1007/s10559-014-9627-3.
20. Alekseychuk A.N., Kovalchuk L.V., Shevtsov A.S., Yakovliev S.V. Cryptographic properties of
a new national encryption standard of Ukraine. Cybernetics and Systems Analysis. 2016. Vol. 52,
Iss. 3. P. 351–366. https://doi.org/10.1007/s10559-016-9835-0.
Íàä³éøëà äî ðåäàêö³¿ 19.10.2020
126 ISSN 1019-5262. ʳáåðíåòèêà òà ñèñòåìíèé àíàë³ç, 2021, òîì 57, ¹ 2
Ë.Â. Êîâàëü÷óê, Ð.Â. Îë³éíèêîâ, Ì.Þ. Ðîä³íêî
ÑÒ²ÉʲÑÒÜ ÃÅØ-ÔÓÍÊÖ²¯ POSEIDON ÄÎ ÍÅÁ²ÍÀÐÍÈÕ Ð²ÇÍÈÖÅÂÈÕ
ÒÀ ˲ͲÉÍÈÕ ÀÒÀÊ
Àíîòàö³ÿ. Ïîáóäîâàíî îö³íêè ñò³éêîñò³ ãåø-ôóíêö³¿ Poseidon äî íåá³íàðíèõ
ë³í³éíèõ òà ð³çíèöåâèõ àòàê. Âèçíà÷åíî çàãàëüí³ ïàðàìåòðè äëÿ ãåø-ôóíêö³¿
Poseidon, ÿê³ çàáåçïå÷óþòü ìîæëèâ³ñòü ¿¿ âèêîðèñòàííÿ ó ðåêóðåíòíèõ
SNARK-äîâåäåííÿõ, ùî ´ðóíòóþòüñÿ íà òðèïëåòàõ MNT-4 òà MNT-6. Ïðî-
àíàë³çîâàíî, ÿê ïîòð³áíî îáèðàòè S-áëîêè äëÿ ö³º¿ ãåø-ôóíêö³¿, ùîá öåé
âèá³ð áóâ îïòèìàëüíèì ç ïîãëÿäó ÿê ñò³éêîñò³, òàê ³ ê³ëüêîñò³ êîíñòðåéíò³â.
Ïîêàçàíî, ÿêà ê³ëüê³ñòü ðàóíä³â º äîñòàòíüîþ, ùîá ãàðàíòóâàòè ñò³éê³ñòü òà-
êî¿ ãåø-ôóíêö³¿ äî íåá³íàðíèõ ë³í³éíèõ òà ð³çíèöåâèõ àòàê, îá÷èñëåíî
ê³ëüê³ñòü êîíñòðåéíò³â íà á³ò ³íôîðìàö³¿ äëÿ çàïðîïîíîâàíèõ ðåàë³çàö³é ö³º¿
ôóíêö³¿ ç äåìîíñòðàö³ºþ ñóòòºâîãî âèãðàøó ïîð³âíÿíî ç ãåø-ôóíêö³ºþ Ïå-
äåðñåíà.
Êëþ÷îâ³ ñëîâà: SNARK, êîíñòðåéíòè, ãåø-ôóíêö³ÿ Poseidon, íåá³íàðíèé
ë³í³éíèé òà ð³çíèöåâèé êðèïòîàíàë³ç.
Ë.Â. Êîâàëü÷óê, Ð.Â. Îëåéíèêîâ, Ì.Þ. Ðîäèíêî
ÑÒÎÉÊÎÑÒÜ ÕÅØ-ÔÓÍÊÖÈÈ POSEIDON Ê ÍÅÁÈÍÀÐÍÛÌ ÐÀÇÍÎÑÒÍÛÌ
È ËÈÍÅÉÍÛÌ ÀÒÀÊÀÌ
Àííîòàöèÿ. Ïîñòðîåíû îöåíêè ñòîéêîñòè õåø-ôóíêöèè Poseidon ê íåáèíàð-
íûì ëèíåéíûì è ðàçíîñòíûì àòàêàì. Îïðåäåëåíû îáùèå ïàðàìåòðû
õåø-ôóíêöèè Poseidon, ïîçâîëÿþùèå èñïîëüçîâàòü å¸ â ðåêóððåíòíûõ
SNARK-äîêàçàòåëüñòâàõ, áàçèðóþùèõñÿ íà òðèïëåòàõ MNT-4 è MNT-6. Âû-
ïîëíåí àíàëèç òîãî, êàê íóæíî âûáèðàòü S-áëîêè äëÿ ýòîé õåø-ôóíêöèè,
÷òîáû ýòîò âûáîð áûë îïòèìàëüíûì ñ òî÷êè çðåíèÿ êàê ñòîéêîñòè, òàê è
êîëè÷åñòâà êîíñòðåéíòîâ. Ïîêàçàíî, êàêîå êîëè÷åñòâî ðàóíäîâ ÿâëÿåòñÿ äîñ-
òàòî÷íûì, ÷òîáû ãàðàíòèðîâàòü ñòîéêîñòü ýòîé õåø-ôóíêöèè ê íåáèíàðíûì
ëèíåéíûì è ðàçíîñòíûì àòàêàì, âû÷èñëåíî êîëè÷åñòâî êîíñòðåéíòîâ íà áèò
èíôîðìàöèè äëÿ ïðåäëîæåííûõ ðåàëèçàöèé ýòîé ôóíêöèè ñ äåìîíñòðàöèåé
ñóùåñòâåííîãî âûèãðûøà â ñðàâíåíèè ñ õåø-ôóíêöèåé Ïåäåðñåíà.
Êëþ÷åâûå ñëîâà: SNARK, êîíñòðåéíòû, õåø-ôóíêöèÿ Poseidon, íåáèíàð-
íûé ëèíåéíûé è ðàçíîñòíûé êðèïòîàíàëèç.
Kovalchuk Lyudmila,
Dr. Habil, professor, National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute”,
Kyiv; Research Fellow, IOHK, Hong Kong, e-mail: lusi.kovalchuk@gmail.com.
Oliynykov Roman,
Dr. Habil, professor, V.N. Karazin Kharkiv National University; visiting professor, Kharkiv National Uni-
versity of Radio Electronics; Research Fellow, IOHK, Hong Kong, e-mail: roliynykov@gmail.com.
Rodinko Mariia,
PhD student, lecture assistant, V.N. Karazin Kharkiv National University; Researcher, IOHK, Hong Kong
e-mail: m.rodinko@gmail.com.
ISSN 1019-5262. ʳáåðíåòèêà òà ñèñòåìíèé àíàë³ç, 2021, òîì 57, ¹ 2 127
|