# Hyperelliptic Curves for the Vector Decomposition Problem over Fields of Even Characteristic

Authors: Seungkook Park
Journal: Journal of Applied Mathematics
 (2015)

---

## Abstract

We present an infinite family of hyperelliptic curves of genus two over a finite field of even characteristic which are suitable for the vector decomposition problem.


---

## Body

## 1. Introduction

Intractable mathematical problems such as the integer factorization problem, the discrete logarithm problem (DLP), and the computational Diffie-Hellman problem (CDHP) are being used to provide secure protocols for cryptosystems. A new hard problem which is called the vector decomposition problem (VDP) was proposed by Yoshida et al. [1]. The VDP on a two-dimensional vector space can serve as the underlying intractable problem for cryptographic protocols. Galbraith and Verheul presented an application of trapdoor VDP where a trapdoor is used to construct a public key encryption scheme [2]. In 2009, Yoshida and Fujiwara introduced a new watermarking scheme designed for cryptographic data such as keys, ciphertexts, and signatures [3, 4]. The proposed scheme utilizes a two-dimensional vector space where one of the one-dimensional subspaces is used as the domain of cryptographic date and the other one-dimensional subspace is used to embed a watermark. The security of the scheme is based on the infeasibility of the VDP. In [5], Yoshida stated the conditions that are required for the VDP on a two-dimensional vector space to be at least as hard as the CDHP on a one-dimensional subspace and suggested a particular family of elliptic curves to be used for the VDP. Duursma and Kiyavash [6] showed that the family of elliptic curves chosen by Yoshida is not secure and moreover none of the elliptic curves have the property that is needed for the VDP to be a hard problem. In order to resolve this problem Duursma and Kiyavash introduced an infinite family of genus two hyperelliptic curves suitable for the VDP. Galbraith and Verheul analyzed the VDP and showed that the VDP on a two-dimensional vector space is equivalent to CDHP on a one-dimensional subspace for the Duursma-Kiyavash curves [2]. The family of hyperelliptic curves proposed by Duursma and Kiyavash are defined over a finite field of odd characteristic. Curve operations are performed using arithmetic operations in the underlying field. Hence the efficient implementation of finite field arithmetic is an important prerequisite in hyperelliptic curve systems. Smart showed that the general multiplication algorithm on the Jacobian for curves defined over odd characteristic fields ended up being around twice as slow as that for even characteristic fields, of an equivalent size, in genus two [7]. Thus curves defined over even characteristic fields have an advantage in computation time over curves defined over odd characteristic fields. Hence one would prefer curves defined over a finite field of even characteristic for the VDP. In this paper, we present an infinite family of hyperelliptic curves of genus two over a finite field of even characteristic and show that it satisfies all the conditions that are needed for the VDP to be a hard problem. The paper is organized as follows: The definitions of CDHP and VDP are given in Section 2. Also we state the conditions for the VDP to be a hard problem and describe the applications of the VDP given in [2–4]. In Section 3, we propose a family of hyperelliptic curves over fields of even characteristic such that the Jacobian of the curves is a product of two elliptic curves. In Section 4, we prove that the two elliptic curves found in Section 3 are 3-isogenous and we find the 3-isogeny. In Section 5, we give the setting of the VDP on the hyperelliptic curves given in Section 3 and show that the VDP defined on these curves can serve as an intractable problem in cryptographic protocols.


## 2. Vector Decomposition Problem

We state the definition of VDP and the conditions for the VDP on a two-dimensional vector space to be at least as hard as the CDHP on a one-dimensional subspace given by Yoshida [5].Definition 1.
The VDP onV (a two-dimensional vector space over F) is as follows: “given e
1
,
e
2
,
v
∈
V such that {
e
1
,
e
2
} is an F-basis for V, find the vector u
∈
V such that u
∈
e
1 and v
-
u
∈
e
2.”Definition 2.
The CDHP onV
′ (a one-dimensional vector space over F) is as follows: “given e
∈
V
′
∖
{
0
} and a
e
,
b
e
∈
e, find a
b
e
∈
e.”Theorem 3 (Yoshida [5]).
The vector decomposition problem onV is at least as hard as the computational Diffe-Hellman problem on V
′
⊂
V if for any e
∈
V
′ there are linear isomorphisms ϕ
e
,
F
e
:
V
→
V which satisfy the following three conditions:(1)
For anyv
∈
V, ϕ
e
(
v
) and F
e
(
v
) are effectively defined and can be computed in polynomial time.
(2)
{
e
,
ϕ
e
(
e
)
} is an F-basis for V.
(3)
There areα
1
,
α
2
,
α
3
∈
F with (1)
F
e
e
=
α
1
e
,
F
e
(
ϕ
e
(
e
)
)
=
α
2
e
+
α
3
ϕ
e
(
e
)
,and α
1
,
α
2
,
α
3
≠
0. The elements α
1, α
2, α
3 and their inverses can be computed in polynomial time.Proof.
The proof is in [5] and is also included in [6].The VDP is hard in general but for certain bases the VDP can be solved in polynomial time even if it satisfies Yoshida’s conditions [2, 8]. In fact, the bases chosen by Duursma and Kiyavash are easy instances of the VDP. The fact that there are easy instances of VDP does not affect the VDP conjecture that the VDP should be hard for randomly chosen basis. In [8], Kwon and Lee provided criteria for choosing a basis such that the VDP can serve as an intractable problem in cryptographic protocols. In [2], Galbraith and Verheul showed that if {
e
1
,
e
2
} is distortion eigenvector base for V then the VDP on a two-dimensional vector V is equivalent to the CDHP on one-dimensional vector space e
1.We give the definition of eigenvector base and distortion eigenvector base.Definition 4.
LetV be a group of exponent m and order m
2. Let F
:
V
→
V be a group isomorphism computable in polynomial time. A pair of elements e
1
,
e
2
∈
V is an eigenvector base with respect to F if V
=
e
1
,
e
2; that is, each element v
∈
V can be uniquely written as a linear combination in e
1 and e
2 and if F
(
e
1
)
=
α
1
e
1 and F
(
e
2
)
=
α
2
e
2 for some distinct, nonzero α
1
,
α
2
∈
Z
/
m
Z.Definition 5.
An eigenvector base{
e
1
,
e
2
} is said to be a distortion eigenvector base if there are group homomorphisms ϕ
1
:
e
1
→
e
1 and ϕ
2
:
e
2
→
e
1 computable in polynomial time and if an integer d
≢
0
(
mod
⁡
m
) is given such that ϕ
2
(
ϕ
1
(
e
1
)
)
=
d
e
1.Remark 6.
The VDP with respect to an eigenvector base is solvable in polynomial time.Two applications of the VDP are watermarking scheme designed for cryptographic date given in [3, 4] and public key encryption scheme given in [2]. In the watermarking scheme a cryptographic date which can be considered as a “vector” is watermarked by adding a linearly independent random vector. Embedding and removing a watermark correspond to adding a one-dimensional vector and decomposing a two-dimensional vector, respectively. Due to the infeasibility of the VDP, removing the watermark is hard unless one has some trapdoor information. The core idea of the public key encryption scheme given in [2] is that for certain bases the VDP is easy but for general bases the VDP is hard. Let V be a two-dimensional vector space isomorphic to Z
/
m
Z
×
Z
/
m
Z with a distortion eigenvector base {
e
1
,
e
2
}. If u
1
=
α
11
e
1
+
α
12
e
2 and u
2
=
α
21
e
1
+
α
22
e
2, where α
11
,
α
12
,
α
21
,
α
22
∈
Z
/
m
Z and α
11
α
22
-
α
12
α
21
≢
0
(
mod
⁡
m
), then for any v
∈
V, if one knows the α
11
,
α
12
,
α
21
,
α
22 then one can solve the VDP of v to the base {
u
1
,
u
2
}. Using α
11, α
12, α
21, α
22 as a trapdoor we obtain a trapdoor VDP scheme. An application of the trapdoor VDP is the public key encryption scheme with public key (
e
1
,
v
=
α
1
e
1
+
α
2
e
2
) and private key (
α
1
,
α
2
). A message m
∈
e
1 is encrypted as c
=
m
+
β
v for a random β with 1
≤
β
<
m.


## 3. Hyperelliptic Curves over Fields of Even Characteristic

By Theorem3, the VDP is hard if the CDHP on a one-dimensional subspace is hard. Yoshida suggested to use the full group of m-torsion points on the elliptic curve E
:
y
2
=
x
3
+
1 over F
p as the two-dimensional vector space V
=
E
[
m
] and the subgroup of F
p-rational m-torsion points as the one-dimensional subspace V
′
=
E
(
F
p
)
∩
E
[
m
]. The elliptic curve E
:
y
2
=
x
3
+
1 given by Yoshida is supersingular. Thus the elliptic curve discrete logarithm problem (ECDLP), and hence the CDHP on the one-dimensional subspace, is vulnerable to the MOV attack. Duursma and Kiyavash [6] showed that any elliptic curve that satisfies the conditions of Theorem 3 is supersingular. Thus, using the VDP with the full m-torsion points on an elliptic curve introduces a vulnerability that needs to be compensated by choosing larger parameters. To avoid this, the VDP may be used with higher genus curves. Duursma and Kiyavash introduced an infinite family of genus two hyperelliptic curves suitable for the VDP defined over a finite field of odd characteristic. In this section, we provide an infinite family of genus two hyperelliptic curves suitable for the VDP defined over a finite field of even characteristic. Unless specified otherwise all the fields will be of even characteristic and all the curves will be over fields of even characteristic. For our purpose, we need a hyperelliptic curve such that the Jacobian of the hyperelliptic curve decomposes into two isogenous elliptic curves. Let K be a finite field of even characteristic. We consider the following hyperelliptic curve of genus two over K:(2)
C
:
y
2
+
y
=
a
x
3
+
1
,where a
=
α
2
+
α for some α
∈
K
¯. Let ω and ω
¯ be the roots of x
2
+
x
+
1
=
0. The automorphism group of (2) is D
12 and the automorphisms are(1)
x
,
y
↦
id
x
,
y,
(2)
x
,
y
↦
ι
x
,
y
+
1,
(3)
x
,
y
↦
u
ω
/
x
,
y
+
α,
(4)
x
,
y
↦
ι
u
ω
/
x
,
y
+
α
+
1,
(5)
x
,
y
↦
v
ω
x
,
y,
(6)
x
,
y
↦
ι
v
ω
x
,
y
+
1,
(7)
x
,
y
↦
v
2
ω
¯
x
,
y,
(8)
x
,
y
↦
ι
v
2
ω
¯
x
,
y
+
1,
(9)
x
,
y
↦
v
u
ω
¯
/
x
,
y
+
α,
(10)
x
,
y
↦
ι
v
u
ω
¯
/
x
,
y
+
α
+
1,
(11)
x
,
y
↦
v
2
u
1
/
x
,
y
+
α,
(12)
x
,
y
↦
ι
v
2
u
1
/
x
,
y
+
α
+
1.We state a theorem given by Kani and Rosen [9] without proof which we use to show that the Jacobian of the hyperelliptic curve given by (2) decomposes into two isogenous elliptic curves.Theorem 7 (Kani and Rosen [9]).
Given a curveC, let G be a finite subgroup of Aut(C) such that G
=
H
1
∪
⋯
∪
H
t where the subgroups H
i of G satisfy H
i
∩
H
j
=
1
G if i
≠
j. Then one has the following isogeny relation:(3)
J
C
t
-
1
×
J
C
/
G
g
~
J
C
/
H
1
h
1
×
⋯
×
J
C
/
H
t
h
t
,where g
=
G and h
i
=
H
i and J
m means the product of J with itself m times.Theorem 8.
The Jacobian of the hyperelliptic curve(4)
C
:
y
2
+
y
=
a
x
3
+
1
w
h
e
r
e
a
=
α
2
+
α
f
o
r
s
o
m
e
α
∈
K
¯
,is isogenous to a product of elliptic curves E
1 and E
2,(5)
E
1
:
y
2
+
(
α
+
1
)
y
=
α
4
+
α
2
x
3
+
x
,
E
2
:
y
2
+
α
y
=
α
4
+
α
2
x
3
+
x
.Proof.
Letσ
∶
=
v
2
u and τ
∶
=
ι
v
2
u be automorphisms. We compute C
/
σ and C
/
τ. Since x
+
x
-
1 and y
2
+
α
y are invariants under σ, we set x
+
x
-
1
=
s, y
2
+
α
y
=
t and find the relation between s and t. We have(6)
t
2
+
α
+
1
t
=
α
4
+
α
2
s
3
+
s
.Thus C
/
σ is(7)
t
2
+
α
+
1
t
=
α
4
+
α
2
s
3
+
s
.By Hurwitz genus formula, (7) is a genus 1 curve. Similarly, we can compute C
/
τ. Since x
+
x
-
1 and y
2
+
(
α
+
1
)
y are invariants under τ, to compute C
/
τ we plug in α
+
1 instead of α in (7) to get(8)
t
2
+
α
t
=
α
4
+
α
2
s
3
+
swhich is also a genus 1 curve. By applying Theorem 7 with Aut
(
C
)
=
D
12, G
=
ι
∪
σ
∪
τ, and g
=
4, we have(9)
Jac
C
2
×
Jac
P
1
4
~
Jac
P
1
2
×
E
1
2
×
E
2
2
.By applying Poincaré’s complete reducibility theorem, we conclude that Jac
(
C
) is isogenous to the product of the two elliptic curves (7) and (8).For ease of computation we transform the elliptic curvesE
1 and E
2 into Weierstrass form. First, we consider(10)
E
1
:
y
2
+
α
+
1
y
=
α
4
+
α
2
x
3
+
xwith elliptic function field as in Figure 1.Figure 1
Elliptic function field.In Figure1, P
i is the zero of x
-
i and P
∞ is the pole of x in K
(
x
). Q
i is the extension of P
i and ∞
0, ∞
α
+
1 are extensions of P
∞. Since(11)
div
1
(
x
+
1
)
y
=
-
2
∞
0
+
∞
α
+
1
+
Q
0
∈
L
2
∞
0
,
div
1
y
=
-
3
∞
0
+
Q
0
+
2
Q
1
∈
L
3
∞
0
,we set(12)
1
(
x
+
1
)
y
=
X
,
1
y
=
Yor(13)
x
=
Y
X
+
1
,
y
=
1
Y
.By plugging in x and y into E
1, we get(14)
Y
2
+
X
Y
+
1
α
+
1
Y
=
α
2
(
α
+
1
)
X
3
+
1
α
+
1
X
.By the transformation(15)
(
X
,
Y
)
⟼
X
α
2
α
+
1
,
Y
α
2
α
+
1
,the curve given by (14) is transformed into(16)
Y
2
+
X
Y
+
α
2
Y
=
X
3
+
α
2
X
.By the transformation(17)
X
,
Y
⟼
X
+
α
2
,
Y
+
α
2
+
α
4
,the curve given by (16) is transformed into(18)
Y
2
+
X
Y
=
X
3
+
α
2
X
2
+
α
8
+
α
6
.By the above transformations, we have the elliptic curve(19)
E
3
:
y
2
+
x
y
=
x
3
+
α
2
x
2
+
α
8
+
α
6which is isomorphic to E
1 with j-invariant j
=
α
8
+
α
6
-
1. We plug in α
+
1 into α in (19) to obtain the elliptic curve(20)
E
4
:
y
2
+
x
y
=
x
3
+
α
+
1
2
x
2
+
α
8
+
α
6
+
α
4
+
α
2which is isomorphic to E
2 with j-invariant j
=
α
8
+
α
6
+
α
4
+
α
2
-
1. From now on we consider the two elliptic curves(21)
E
3
:
y
2
+
x
y
=
x
3
+
α
2
x
2
+
α
8
+
α
6with j
1
=
α
8
+
α
6
-
1 and(22)
E
4
:
y
2
+
x
y
=
x
3
+
α
+
1
2
x
2
+
α
8
+
α
6
+
α
4
+
α
2with j
2
=
α
8
+
α
6
+
α
4
+
α
2
-
1.


## 4. Three-Isogeny ofE
3 and E
4

The modular equation of level three is(23)
Φ
3
x
,
y
=
x
4
+
x
3
y
3
+
y
4which is the modular curve reduced modulo 2. Since Φ
3
(
j
1
,
j
2
)
=
0, E
3 and E
4 are 3-isogenous. In this section we find a 3-isogeny from E
3 to E
4. We use the following theorem in [10] to find an isogeny.Theorem 9 (Lercier [10]).
LetF be a subgroup (of odd order) of an elliptic curve E
a. If b
=
a
+
Σ
(
X
s
,
Y
s
)
∈
F
*
Y
s
+
Y
s
2, then there exist isogenies between E
a and E
b of kernel F. One of these isogenies is given by (24)
(
X
,
Y
)
⟼
X
+
∑
S
∈
F
*
‍
X
P
+
S
,
Y
+
∑
S
∈
F
*
‍
Y
P
+
S
,where E
a
:
y
2
+
x
y
=
x
3
+
a, a
∈
F
2
n
*.In order to find a 3-isogeny using Theorem9 we first find the 3-torsion points of the elliptic curve E
3. Let P
=
(
x
,
y
) be a point of the elliptic curve E
:
y
2
+
x
y
=
x
3
+
a
2
x
2
+
a
6 over a field of even characteristic with a point O at infinity. Then -
P
=
(
x
,
x
+
y
) and the formula for doubling a point P
=
(
x
,
y
) is(25)
2
P
=
x
2
+
a
6
x
2
,
x
+
y
x
x
2
+
a
6
x
2
+
a
6
x
2
.
P
=
(
x
,
y
) is a 3-torsion point if and only if 3
P
=
O; that is, 2
P
=
-
P. To find the 3-torsion points we set x
2
+
a
6
x
2
-
1
=
x or x
4
+
x
3
+
a
6
=
0. If the equation x
4
+
x
3
+
a
6
=
0 has four roots, say, x
1
,
x
2
,
x
3, and x
4, then (26)
E
[
3
]
=
O
,
x
1
,
±
y
1
,
x
2
,
±
y
2
,
x
3
,
±
y
3
,
x
4
,
±
y
4
,where y
i
2
+
x
i
y
i
=
x
i
3
+
a
2
x
i
2
+
a
6. Now we find two of the 3-torsion points of E
3. Since α
2 is a root for x
4
+
x
3
+
α
8
+
α
6 we plug in x
=
α
2 in E
3 and solve for y to get y
=
α
4 or α
2
+
α
4. The two points R
1
=
(
α
2
,
α
4
) and Q
1
=
(
α
2
,
α
2
+
α
4
) are 3-torsion points of E
3
:
y
2
+
x
y
=
x
3
+
α
2
x
2
+
α
8
+
α
6. Let F
=
{
O
,
R
1
,
Q
1
} be a subgroup of the elliptic curve E
3 and let(27)
E
3
′
:
y
2
+
x
y
=
x
3
+
α
8
+
α
6
,
E
4
′
:
y
2
+
x
y
=
x
3
+
α
8
+
α
6
+
α
4
+
α
2be two elliptic curves. There exists an isomorphism φ
1
:
E
3
→
E
3
′ defined by φ
1
(
x
,
y
)
=
(
x
,
y
+
s
x
), where s
2
+
s
=
α
2. Then(28)
φ
1
(
R
1
)
=
R
1
′
=
α
2
,
α
4
+
s
α
2
,
φ
1
(
Q
1
)
=
Q
1
′
=
α
2
,
α
2
+
α
4
+
s
α
2
,
φ
1
(
O
)
=
O
.Then F
′
=
{
O
,
R
1
′
,
Q
1
′
} is a subgroup of an elliptic curve E
3
′. We can apply Theorem 9 to E
3
′ and E
4
′ with subgroup F
′ to get a 3-isogeny φ
2
:
E
3
′
→
E
4
′ defined as(29)
φ
2
x
,
y
=
x
+
α
2
x
+
α
2
+
α
4
x
+
α
2
2
,
h
h
h
y
+
α
4
x
+
α
2
+
α
2
y
2
+
α
4
y
+
α
10
+
α
6
x
+
α
2
3
.Define φ
3
:
E
4
′
→
E
4 by(30)
φ
3
x
,
y
=
x
,
y
+
s
+
ω
x
.Then φ
3 is an isomorphism from E
4
′ to E
4.Letφ
=
φ
3
∘
φ
2
∘
φ
1
:
E
3
→
E
4. Then(31)
φ
x
,
y
=
x
+
α
2
x
+
α
2
+
α
4
x
+
α
2
2
,
h
h
h
h
y
+
ω
x
+
α
4
x
+
α
2
h
h
h
+
α
2
y
+
s
x
2
+
α
4
(
y
+
s
x
)
+
α
10
+
α
6
x
+
α
2
3
,where s
2
+
s
=
α
2 is a 3-isogeny over the extension field of K. Thus we have proved the following theorem.Theorem 10.
LetE and E
′ be two elliptic curves defined over F
2
n by(32)
E
:
y
2
+
x
y
=
x
3
+
α
2
x
2
+
α
8
+
α
6
w
i
t
h
j
=
α
8
+
α
6
-
1
,
E
′
:
y
2
+
x
y
=
x
3
+
α
+
1
2
x
2
+
α
8
+
α
6
+
α
4
+
α
2
hhhhhhhhhhhhhhhh
w
i
t
h
j
=
α
8
+
α
6
+
α
4
+
α
2
-
1
.Then(33)
φ
x
,
y
=
x
+
α
2
x
+
α
2
+
α
4
x
+
α
2
2
,
h
h
h
h
y
+
ω
x
+
α
4
x
+
α
2
h
h
h
+
α
2
y
+
s
x
2
+
α
4
(
y
+
s
x
)
+
α
10
+
α
6
x
+
α
2
3
,where ω is a primitive third root of unity and s
2
+
s
=
α
2 is a 3-isogeny over the extension field of F
2
n.


## 5. VDP on Hyperelliptic Curves over Fields of Even Characteristic

In this section, we set up the VDP on the hyperelliptic curveC and prove that the VDP defined on the hyperelliptic curve C is hard in general by showing the existence of a distortion eigenvector base. We have shown that the Jacobian of(34)
C
:
y
2
+
y
=
a
x
3
+
1decomposes into a product of two elliptic curves E
3 and E
4 which are 3-isogenous over the extension field that contains the third roots of unity and s, where s
2
+
s
=
α
2. E
3 and E
4 have the same number of points over the extension field. We set up the VDP on C as follows.Choose(35)
C
:
y
2
+
y
=
a
x
3
+
1such that E
3 has a large cyclic subgroup Z
/
m
Z of rational points over F
q, where q
=
2
n, n is odd, and m is a prime greater than 3. Then we choose as two-dimensional vector space V the m-torsion points Z
/
m
Z
×
Z
/
m
Z in the Jacobian of the hyperelliptic curve C over the extension field F
q
2 and choose as one-dimensional subspace V
′ the subspace Z
/
m
Z of V that is rational over F
q.The following is a summary of the VDP setting:(36)
C
:
y
2
+
y
=
a
x
3
+
1
,
a
=
α
2
+
α
.
Jac
(
C
) is Jacobian of the curve C, as(37)
V
=
Z
m
Z
×
Z
m
Z
⊂
Jac
(
C
)
F
q
2
,where q
=
2
n, n is odd, and m is a prime greater than 3. Consider(38)
V
′
=
Z
m
Z
⊂
Jac
C
F
q
.Let ω be a primitive third root of unity and let(39)
ϕ
:
(
x
,
y
)
⟼
(
ω
x
,
y
)
,
F
:
(
x
,
y
)
⟼
(
x
q
,
y
q
)
.Let e
∈
Jac
(
C
)
(
F
q
) and let l
=
2
-
1
(
mod
⁡
m
). We will show that (
e
,
ϕ
′
(
e
)
) is a distortion eigenvector base, where ϕ
′
=
l
+
ϕ.Lemma 11.
For any elemente
∈
J
a
c
(
C
)
(
F
q
), q
=
2
n,(40)
ϕ
ϕ
e
=
-
e
-
ϕ
e
,and if n is odd then(41)
F
ϕ
e
=
-
F
(
e
)
-
ϕ
F
e
=
-
e
-
ϕ
e
.Proof.
LetP be a point in C. Since ϕ
(
ϕ
2
(
P
)
+
ϕ
(
P
)
+
P
)
=
P
+
ϕ
2
(
P
)
+
ϕ
(
P
), ϕ
2
(
P
)
+
ϕ
(
P
)
+
P is fixed by ϕ. Thus ϕ
2
(
P
)
+
ϕ
(
P
)
+
P
∈
C
/
ϕ. Since ϕ
(
x
3
)
=
x
3, C
/
ϕ is(42)
y
2
+
y
=
a
x
+
1
.Equation (42) has genus 0. Therefore the class number of the Jacobian of (42) is 1 and hence ϕ
2
+
ϕ
+
1
=
0. We have proved (40).
We need to show thatϕ
2
∘
F
=
F
∘
ϕ:(43)
ϕ
2
∘
F
x
,
y
=
ω
2
x
q
,
y
q
,
F
∘
ϕ
x
,
y
=
ω
q
x
q
,
y
q
.If n is odd, then 2
≡
2
n
(
mod
⁡
3
) and hence ϕ
2
∘
F
=
F
∘
ϕ.Theorem 12.
For an elemente
∈
J
a
c
(
C
)
(
F
q
) of prime order m
>
3, {
e
,
ϕ
′
(
e
)
} is a distortion eigenvector base for V.Proof.
We begin by showing that{
e
,
ϕ
′
(
e
)
} is an eigenvector base for V. Suppose that l
e
+
ϕ
(
e
)
=
ϕ
′
(
e
)
∈
e; that is, ϕ
(
e
)
=
β
e for some β
∈
Z
/
m
Z. Thus ϕ
(
e
)
∈
Jac
(
C
)
(
F
q
). By (40) of Lemma 11, we have β
2
e
=
-
e
-
β
e; that is, β
2
=
-
1
-
β. By (41) of Lemma 11, we have β
e
=
-
e
-
β
e; that is, (
2
β
+
1
)
e
=
0. Thus(44)
0
=
2
β
+
1
2
β
+
1
e
=
4
β
2
+
4
β
+
1
=
-
4
-
4
β
+
4
β
+
1
e
=
-
3
e
.This is a contradiction to the assumption m
>
3. Hence {
e
,
ϕ
′
(
e
)
} is a basis for V. Note that F
(
e
)
=
e. By Lemma 11, we have(45)
F
ϕ
′
e
=
F
l
e
+
ϕ
e
=
l
e
-
e
-
ϕ
e
=
l
e
-
e
+
l
e
-
ϕ
′
(
e
)
=
ϕ
′
e
.Thus {
e
,
ϕ
′
(
e
)
} is an eigenvector base. Now we show that {
e
,
ϕ
′
(
e
)
} is a distortion eigenvector base by showing the existence of a homomorphism ϕ
′′ and an integer d
≢
0
(
mod
⁡
m
) with the property ϕ
′′
ϕ
′
=
d on e. Let ϕ
′′
=
l
+
ϕ
2 and let d
=
l
2
-
l
+
1. Since the dual isogeny ϕ
^ of ϕ is ϕ
^
=
ϕ
2, we have(46)
ϕ
′′
ϕ
′
=
l
+
ϕ
2
l
+
ϕ
=
l
2
+
l
ϕ
2
+
ϕ
+
ϕ
2
ϕ
=
l
2
-
l
+
1
=
d
.We have shown that the basis{
e
,
ϕ
′
(
e
)
} is a distortion eigenvector base and hence proved that the VDP for the proposed family of hyperelliptic curves is hard in general. It is permitted that the VDP be easy for some bases. In fact, for the bases {
e
,
ϕ
(
e
)
} and {
e
,
ϕ
′
(
e
)
} the VDP can be solved easily. Using the criteria for strong bases for the VDP given in [8], we may choose {
e
1
,
e
2
} with e
1
,
e
2
∉
e
∪
ϕ
e as our basis for the VDP, for example, e
1
=
α
11
e
+
α
12
ϕ
(
e
) and e
2
=
α
21
e
+
α
22
ϕ
(
e
), where α
11
,
α
12
,
α
21
,
α
22
∈
Z
/
m
Z are nonzero and α
11
α
22
-
α
12
α
21
≢
0
(
mod
⁡
m
).


## 6. Conclusion

Yoshida and Fujiwara introduced a new watermarking scheme for cryptographic data which is based on VDP. Duursma and Kiyavash showed that elliptic curves are not suitable for VDP and presented an infinite family of genus two hyperelliptic curves suitable for the VDP defined over a finite field of odd characteristic. In this paper, we introduce an infinite family of genus two hyperelliptic curves suitable for the VDP defined over a finite field of even characteristic.



---

*Source: 197097-2015-03-04.xml*