Cryptography Reference
In-Depth Information
Conditions for which monoidic implies Cauchy.
Theorem 1.
Let
M
(
h
)
be
A
-adic for a sequence
h
of length
N
over
F
.Then
M
is Cauchy iff
(1)
h
(
a
i
)
are distinct and invertible in
F
for all
0
≤
i<N
,and
a
j
))
−
1
=(
h
(
a
i
))
−
1
+(
h
(
a
j
))
−
1
(
h
(0))
−
1
(2)
(
h
(
a
i
−
−
−
for all
0
≤
i, j < N
.
In this case
M
(
h
)=
C
(
β, γ
)
,where
β
(
a
i
)=(
h
(
a
i
))
−
1
and
γ
(
a
i
)=(
h
(0))
−
1
−
a
i
))
−
1
.
(
h
(
−
Proof.
We start by showing that our conditions indeed imply that
M
is Cauchy.
For the disjointness, assume that there are indices
i
and
j
, such that
β
(
a
i
)=
γ
(
a
j
). In this case we get 0 =
β
(
a
i
)
a
j
), which is a con-
tradiction. Finally we compare the matrices
M
(
h
)and
C
(
β, γ
) resulting in the
equality
−
γ
(
a
j
)=1
/h
(
a
i
−
M
i,j
=
h
(
a
i
−
a
j
)=1
/
(1
/h
(
a
i
)+1
/h
(
−
a
j
)
−
1
/h
(0)) = 1
/
(
β
(
a
i
)
−
γ
(
a
j
)) =
C
i,j
.
We continue by showing that if
M
is Cauchy, i.e.,
M
(
h
)=
C
(
β
,γ
), then indeed
our conditions must hold. Since
C
(
β
,γ
)=
C
(
β
+
ω, γ
+
ω
) for any
ω
,we
can choose the sequences in such a way that
γ
(0) = 0. Now,
M
i,
0
=
C
i,
0
for all
i
,whichmeans
h
(
a
i
)=1
/β
(
a
i
). By the properties of
β
this gives us condition
(1), i.e., that all
h
(
a
i
) are distinct and invertible, as well as
β
=
β
.Weuse
similarly that
M
0
,i
=
C
0
,i
which implies
h
(
∈
F
γ
(
a
i
)). Solving for
γ
revealsthatitequals
γ
.Since
β
=
β
and
γ
=
γ
,wegetthat
M
(
h
)=
C
(
β, γ
)
implying condition (2).
−
a
i
)=1
/
(
β
(0)
−
Note that if the
A
-adic matrix of a sequence
h
is also Cauchy, then the se-
quence of
r
-th powers, i.e.,
h
r
=(
h
0
,h
a
1
,...,h
a
n
−
1
) yields the correspond-
ing Cauchy power matrix. In other words, for any number
r>
0wehave
M
(
h
)=
C
(
β, γ
)=
M
(
h
r
)=
C
(
β, γ, r
).
Now, we will show how to construct random monoidic Cauchy matrices.
⇒
Construction of monoidic Cauchy matrices.
Corollary 1.
Let
A
be a finite, abelian group with set of generators
b
1
,...,b
d
and
M
(
h
)
be
A
-adic and Cauchy for a sequence
h
over
F
, then for all
c
1
,...,c
d
∈
Z
,
+
c
d
b
d
))
−
1
=
c
1
(
h
(
b
1
))
−
1
+
+
c
d
(
h
(
b
d
))
−
1
1)(
h
(0))
−
1
.
(
h
(
c
1
b
1
+
···
···
−
(
c
1
+
···
+
c
d
−
Furthermore, the field characteristic
char(
F
)
divides the order of any element in
A
\{
0
}
.
Proof.
By Theorem 1, we know that for all
a, a
∈
A
the following holds
(
h
(
a
+
a
))
−
1
=(
h
(
a
))
−
1
+(
h
(
a
))
−
1
(
h
(0))
−
1
.
−
