Permutations over
𝔽
2
2
k
with low differential uniformity, high algebraic degree and high nonlinearity are of great cryptographic importance since they can be chosen as the substitution boxes ...(S-boxes) for many block ciphers with SPN (Substitution Permutation Network) structure. A well known example is that the S-box of the famous Advanced Encryption Standard (AES) is derived from the inverse function on
𝔽
2
8
, which has been proved to be a differentially 4-uniform permutation with the optimal algebraic degree and known best nonlinearity. Recently, Zha et al. proposed two constructions of differentially 4-uniform permutations over
𝔽
2
2
k
, say
G
t
and
G
s
,
t
with
T
r
(
s
−1
) = 1, by applying affine transformations to the inverse function on some subfields of
𝔽
2
2
k
(Zha et al. Finite Fields Appl.
25
, 64–78,
2014
). In this paper, we generalize their method by applying other types of EA (extended affine) equivalent transformations to the inverse function on some subfields of
𝔽
2
2
k
and present two new constructions of differentially 4-uniform permutations, say
F
α
and
F
β
,
α
with
T
r
(
β
−1
) = 1. Furthermore, we prove that all the functions
G
t
with different
t
are CCZ (Carlet-Charpin-Zinoviev) equivalent to our subclass
F
0
, while all the functions
G
s
,
t
with different
t
are CCZ-equivalent to our subclass
F
s
,0
. In addition, both our two constructions give many new CCZ-inequivalent classes of such functions, as checked by computer in small numbers of variables. Moreover, all these newly constructed permutations are proved to have the optimal algebraic degree and high nonlinearity.
Recently, Horlemann-Trautmann and Weger (Adv Math Commun,
https://doi.org/10.3934/amc.2020089
, 2020) proposed a general framework for a Quaternary McEliece cryptosystem over the ring
Z
4
, and ...generalized the construction over the ring
Z
p
m
where
p
is a prime integer. By considering the Lee metric, the public key size for the McEliece cryptosystems can be substantially smaller than their counterparts in the Hamming metric. Furthermore, the hardness of the McEliece cryptosystems over
Z
p
m
is based on the Lee Syndrome Decoding problem, which was shown to be NP-complete. This paper aims to analyze the design and security of the Lee metric McEliece cryptosystem over
Z
p
m
in the Lee metric. We derive some necessary conditions for the quaternary codes used in the Lee metric McEliece cryptosystem, and show that the theoretical quaternary codes proposed in (Adv Math Commun,
https://doi.org/10.3934/amc.2020089
, 2020) do not exist. Furthermore, we propose a plaintext recovery attack on the Lee metric McEliece cryptosystem over
Z
p
m
, when the minimum Lee distance of the underlying codes with certain structures is greater than twice the Lee weight of the error. Our plaintext recovery attack is applicable to the cryptosystems over
Z
p
m
when
m
>
1
. We apply our plaintext recovery attack on the Quaternary McEliece cryptosystem, and manage to recover partial plaintext of length
k
1
within
O
2
min
{
k
1
,
0.0473
n
}
operations, where
n
is the length of ciphertext. Hence, the proposed theoretical parameters for the Quaternary McEliece over
Z
4
in (Adv Math Commun,
https://doi.org/10.3934/amc.2020089
, 2020) do not achieve 128-bit security, as we can recover the partial plaintext within 0.591 s. This also implies that the use of quaternary codes in the McEliece cryptosystem may not reduce the public key size significantly. Furthermore, for some parameters of the Lee metric McEliece cryptosystems over
Z
4
, our plaintext recovery attack can be more efficient than the Lee-Brickell’s and Stern’s Information Set Decoding Algorithm over
Z
4
.
The Explicit Dual of Leander's Monomial Bent Function LI, Yanjun; KAN, Haibin; PENG, Jie ...
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences,
09/2021, Volume:
E104.A, Issue:
9
Journal Article
Peer reviewed
Permutation polynomials and their compositional inverses are crucial for construction of Maiorana-McFarland bent functions and their dual functions, which have the optimal nonlinearity for resisting ...against the linear attack on block ciphers and on stream ciphers. In this letter, we give the explicit compositional inverse of the permutation binomial $f(z)=z^{2^{r}+2}+\alpha z\in\mathbb{F}_{2^{2r}}z$. Based on that, we obtain the dual of monomial bent function $f(x)={\rm Tr}_1^{4r}(x^{2^{2r}+2^{r+1}+1})$. Our result suggests that the dual of f is not a monomial any more, and it is not always EA-equivalent to f.
In this letter, we present a construction of bent functions which generalizes a work of Zhang et al. in 2016. Based on that, we obtain a cubic bent function in 10 variables and prove that, it has no ...affine derivative and does not belong to the completed Maiorana-McFarland class, which is opposite to all 6/8-variable cubic bent functions as they are inside the completed Maiorana-McFarland class. This is the first time a theoretical proof is given to show that the cubic bent functions in 10 variables can be outside the completed Maiorana-McFarland class. Before that, only a sporadic example with such properties was known by computer search. We also show that our function is EA-inequivalent to that sporadic one.
The hidden weighted bit function (HWBF) is a well-known benchmark function in the branching program literature. In Wang et al. (2014),authors investigated the cryptographic properties of the HWBF and ...found that it seems to be a very good candidate for being used in real ciphers. In this paper, we make the following contributions:
(1) We study the behavior of the HWBF against the quadratic approximation attack and give an upper bound on its second-order nonlinearity, which is much lower than the maximum possible second-order nonlinearity of Boolean functions. Therefore, the HWBF may be weak for being used in real ciphers to resist quadratic approximation attacks. But, how to launch the quadratic approximation attack effectively is still in the research stage.
(2) Two bounds on the higher-order nonlinearities were given by C. Carlet in Carlet (2008). In general, one bound is better than the other one. But it was unknown whether it is always better. We give an example to show that it is not always better.
Recently, Kim et al. proposed a modified Dual-Ouroboros public-key encryption (
PKE
) using Gabidulin codes to overcome the limitation of having decryption failure in the original Dual-Ouroboros ...using low rank parity check codes. This modified Dual-Ouroboros
PKE
using Gabidulin codes is proved to be IND–CPA secure, with very compact public key size of 738 bytes achieving 128-bit security level. However, they did not specify on their choice of the secret key
S
used in their
PKE
. In this paper, we analyze different possible choices for
S
in the modified Dual-Ouroboros
PKE
using Gabidulin codes. More specifically, we show that if
S
is invertible over
F
q
m
without any restriction, then the decryption algorithm will fail. Furthermore, we show that Kim et al.’s proposal of the modified Dual-Ouroboros
PKE
using Gabidulin codes has secret key
S
over
F
q
for its decryption algorithm to be correct. Then, we proposed two attacks: key recovery attack and plaintext recovery attack on their
PKE
with
S
over
F
q
. We are able to recover the secret key for all the proposed parameters within 235 seconds. Moreover, we show that the public key matrix in their proposal generates a subcode of Gabidulin code. As a consequence, we can apply the Frobenius weak attack on their proposal and recover the plaintext for all the proposed paramters within 0.614 second. Finally, we give a proposal for the modified Dual-Ouroboros
PKE
using Gabidulin codes such that it is correct and secure, by considering certain restrictions on
S
over
F
q
m
.
We propose a new rank metric code based encryption based on the hard problem of rank syndrome decoding problem. We consider a generator matrix for Gabidulin codes in the form of
k
-partial circulant ...matrix. We distort the matrix
G
by adding it with another random
k
-partial circulant matrix and multiplying the product with a random circulant matrix. We also convert our encryption into an IND-CCA2 secured encryption scheme under assumption of Rank Syndrome Decoding problem. Our encryption has the smallest key size (of 4.306 KB) at 256-bit security level as compared to all the other rank code based encryption schemes with zero decryption failure and hidden structure for the decodable codes.
Research on permutation polynomials over the finite field F22k with significant cryptographical properties such as possibly low differential uniformity, possibly high nonlinearity and algebraic ...degree has attracted a lot of attention and made considerable progress in recent years. Once used as the substitution boxes (S-boxes) in the block ciphers with Substitution Permutation Network (SPN) structure, this kind of polynomials can have a good performance against the classical cryptographic analysis such as linear attacks, differential attacks and the higher order differential attacks. In this paper we put forward a new construction of differentially 4-uniformity permutations over F22k by modifying the inverse function on some specific subsets of the finite field. Compared with the previous similar works, there are several advantages of our new construction. One is that it can provide a very large number of Carlet-Charpin-Zinoviev equivalent classes of functions (increasing exponentially). Another advantage is that all the functions are explicitly constructed, and the polynomial forms are obtained for three subclasses. The third advantage is that the chosen subsets are very large, hence all the new functions are not close to the inverse function. Therefore, our construction may provide more choices for designing of S-boxes. Moreover, it has been checked by a software programm for k=3 that except for one special function, all the other functions in our construction are Carlet-Charpin-Zinoviev equivalent to the existing ones.
The covering radius of the third order Reed–Muller code of length 128 has been an open problem for many years. The best upper bound of it is known to be 22. In this paper, we give a sufficient and ...necessary condition for the covering radius of
RM
(3, 7) to be equal to 22. Using this condition, we prove that the covering radius of
RM
(3, 7) in
RM
(4, 7) is 20. Therefore, if the third-order nonlinearity of a 7-variable Boolean function is greater than 20, then its algebraic degree is at least 5. As a corollary, we conclude that the covering radius of
RM
(3, 7) in the set of 2-resilient Boolean functions is at most 20 which improves the bound given by Borissov et al. (IEEE Trans Inf Theory 51:1182–1189,
2005
).
PDF
