Cryptography Reference
In-Depth Information
By repeatedly using this equation, we prove the first claim.
(
h
(
c
1
b
1
+
···
+
c
d
b
d
))
−
1
=(
h
(
b
1
+
···
+
b
1
))
−
1
+
···
+
b
d
+
···
+
b
d
c
1
times
c
d
times
=(
h
(
b
1
))
−
1
+(
h
(
b
1
+
))
−
1
−
(
h
(0))
−
1
+
b
1
(
c
1
−
1) times
···
+
···
+
b
d
+
···
+
b
d
c
d
times
=
c
1
(
h
(
b
1
))
−
1
+(
h
(
b
2
+
···
+
b
2
))
−
1
− c
1
(
h
(0))
−
1
+
···
+
b
d
+
···
+
b
d
c
d
times
(
c
2
)times
=
c
1
(
h
(
b
1
))
−
1
+
···
+
c
d
(
h
(
b
d
))
−
1
−
(
c
1
+
···
+
c
d
−
1)(
h
(0))
−
1
.
be a non-neutral group element and
k
=ord(
a
), i.e.,
ka
= 0. By the equation we have just shown, we know that
For the second claim, let
a
∈
A
\{
0
}
h
(0)
−
1
=
h
(
ka
)
−
1
=
kh
(
a
)
−
1
1)
h
(0)
−
1
−
(
k
−
k
(
h
(0)
−
1
h
(
a
)
−
1
)=0
−
Since
a
is not the neutral element, all elements of
h
are distinct, and the field
characteristic is prime, the second claim follows.
Since the field characteristic
p
divides the order of any element, only groups of
size
N
=
p
d
can be used. Conversely, let
b
1
,...,b
d
be group elements that form an
F
p
set of generators, then the sequence elements
h
(0)
,h
(
b
1
)
,...,h
(
b
d
) completely
determine the sequence. We call these values the essence of the sequence
h
.
For example, if
A
=
p
, then such a set of generators
b
1
,...,b
d
F
is given by
the generators of the
d
distinct copies of
F
p
in
A
. For a given set of generators,
we can sample a monoidic sequence uniformly at random with the algorithm in
Figure 2.
We will briefly argue why the algorithm in Figure 2 is correct. Assume that
it is not. The only situation resulting in an error is in line 7, if the computed
quantity is not invertible, so let us assume this to be the case. Since only zero is
not invertible, we have
0=
c
1
h
(
b
1
)+
···
+
c
d
h
(
b
d
)
−
(
c
1
+
···
+
c
d
−
1)
h
(0)
.
Now, not all coecients of
h
(0)
,h
(
b
1
)
,...,h
(
b
d
) can be zero simultaneously, so
there is an
F
p
-linear dependency among them. However, by our choice of
F
in
line 4, from which all
h
(
b
i
) are chosen, no such dependency can exist.
As a consequence of our algorithm, the total number of possible sequences is
p
→
F
Q
p
d
)
.
|{
h
:
F
|
M
(
h
) is monoidic and Cauchy
}|
=(
Q
−
···
(
Q
−
1)
Quasi-monoidic Generalized Srivastava codes.
Our final goal is to describe a
way of disguising the Cauchy block structures of the code that is used for error-
correction, while simultaneously keeping much of the monoidic structure intact
in the form of small monoidic blocks. This will allow us to obtain code-based
public-key schemes with small keys.
