Cryptography Reference
In-Depth Information
Table 1.
Time to recover the hidden vector space
T
for fixed field size
q
= 31, field
extension
n
= 17 and variable embedding degree
. The number of samples from the
vector space (#
ω
) is independent from
, but close to
qn
. Each line is based on 11
independent experiments. The line with previously secure parameters is
highlighted
in bold
.
time [sec]
q
n
#
ω
#
ω/n
min
avg
max
1
500
29.41
129
170
219
31
17
2
460
27.06
210
268
375
3
568
33.41
2416
3069
3903
4
651
38.30
87556
97911
117534
here, so Billet/Macario-Rat does not apply directly. However, we see by inspec-
tion that all monomials depending on
x
1
,...,x
n
+
come from the term
γ
,all
monomials depending both on
x
1
,...,x
n
+
and
x
n
+
+1
,...,x
2
n
+
come from
βX
; and the rest comes from
αX
2
. Applying Billet/Macario-Rat to these gives
us the complete variable change
S
and equation change
T
(up to equivalences,
[20]). Hence, we have reconstructed the private key and are therefore in the same
position as the legitimate user when computing
y
=
2
n
+
q
P
(
x
) for given
y
∈
F
.
4Squ e+
Another version of the Square cryptosystem is called Square+. It was also sug-
gested in the very same paper as Double-Layer Square by Clough and Ding [9].
As Square, it uses
X
2
over the extension field
F
q
n
+
as its central monomial.
In addition, we have
p
random equations that blind the differential struc-
ture of
X
2
in the public key. In total, we obtain
m
:=
n
+
+
p
equations for
Square+. Obviously, Square+ is overdetermined—both due to the embedding
of
variables and the
p
extra polynomials. In order to prevent Gröbner based
attacks, (
+
p
) has to be chosen relatively small compared to
n
. In the original
Square+ paper, proposed parameters are
q
=31
,n
=48
,
=3
,p
=5[9].
Let
ϕ
:
∈
N
n
+
q
F
→
F
q
n
+
be the standard isomorphism between the vector space
n
+
q
F
F
q
n
+
.Denotewith
a
1
,...,a
p
a total of
p
random,
quadratic polynomials over
and the finite field
F
q
, the so-called
plus-polynomials
. The mixing of the
equations is realized by a full-rank matrix
T
(
n
+
+
p
)
×
(
n
+
+
p
)
∈
F
. The embedding
q
(
n
+
)
×
n
q
modifier is realized via a matrix
S
∈
F
with rank(
S
)=
n
. The Square
part is expressed over the ground field as
C
, the plus polynomials are given in
A
,see
n
+
n
+
:(
u
1
,...,u
n
+
)
→
ϕ
−
1
◦
X
2
C
:
F
→
F
◦
ϕ
(
u
1
,...,u
n
+
)
=(
v
1
,...,v
n
+
)
,
n
+
p
:(
u
1
,...,u
n
+
)
A
:
F
→
F
→
(
a
1
(
u
1
,...,u
n
+
)
,...,a
p
(
u
1
,...,u
n
+
))
=(
v
n
+
+1
,...,v
n
+
+
p
)
