On the Hidden Number Problem over any Finite Fields of Large Characteristics

Abstract

In this paper, making use of the least significant bit and the most significant bits, we study Diffie-Hellman problem over any finite field of large characteristics and prove that hidden number problem with chosen multiplier is as hard as computational Diffie-Hellman problem. Furthermore, we prove the similar results of elliptic curve over any finite field and analyze bit security of tripartite Diffie-Hellman key exchange protocol.

Keywords

least (most) significant bit / elliptic curve / Weil pairing

1 Introduction

Discrete logarithm problem (DLP) relative to a base $\mathit{g}\in {\mathbf{Z}}_{\mathit{p}}^{\mathrm{*}}$ is to find x given g^x. Assuming this problem to be hard, we recall that Diffie-Hellman key exchange scheme works in the finite cyclic group $\mathcal{G}=<\mathit{g}>\le {\mathbf{Z}}_{\mathit{p}}^{\mathrm{*}}$ of order T. To establish a common key, two communicating parties, Alice and Bob execute the following protocol [12]: Alice chooses a random integer $\mathit{x}\in [1,\mathit{T}-1]$, computes and sends X=g^x to Bob. Bob chooses a random integer $\mathit{y}\in [1,\mathit{T}-1]$, computes and sends Y=g^y to Alice. Now both Alice and Bob can compute the common Diffie-Hellman secret K=Y^x=X^y=g^xy. Many believe that computing Diffie-Hellman function DH_g(g^x,g^y)=g^xy is as hard as DLP. After the secret key agreement, Alice and Bob can secure the session using encryption with a block cipher. A natural way to derive the key for the cipher would be to use a block of bits from g^xy. For example, if p is 1024 bit prime, one may use the 64 bit most significant bits of g^xy. An attacker, who may not be able to compute the whole g^xy, may nevertheless succeed in computing this part of the bits of g^xy and crack the session. Hence it is important to know if the most significant bits (MSB) of g^xy are secure from an adversary who knows both g^x and g^y. Boneh and Venkatesan [4] prove that computing the most significant bits of the secret key in a Diffie-Hellman key-exchange protocol from the public keys of the players is as hard as computing the secret key itself, by studying the following hidden number problem: Given an oracle ${\mathcal{O}}_{\mathit{\alpha }}\left(\mathit{x}\right)$ that on input x computes the k most significant bits of αg^xmodp, find αmodp.

On the other hand, the computational Diffie-Hellman assumption (CDH) in group $\mathcal{G}$ states that no efficient algorithm can compute g^xy given g,g^x,g^y. But this does not mean that one cannot compute a few bits of g^xy or perhaps predict some bits of g^xy. In fact, to use the Diffie-Hellman protocol in an efficient system one can usually relies on stronger Decisional Diffie-Hellman assumption (DDH)[2]. Ideally, one would like to show than an algorithm for DDH in group $\mathcal{G}$ implies an algorithm for CDH in $\mathcal{G}$. As a first step, Boneh and Shparlinski [3] show that, in the group of points of an elliptic curve over a finite field, predicting the least significant bit (LSB) of the Diffie-Hellman secret, for many curves in a family of curves, is as hard as computing the entire secret. The similar results were previously known for the RSA function [1] but not for Diffie-Hellman. Most of all work is based on the field Z_p for a sufficient large prime p.

As applications, a number of cryptographic schemes proposed are related to or based on Diffie-Hellman function DH_g(g^x,g^y)=g^xy. They depend on the "hidden" nature of g^xy. For examples, we refer to ElGamal's public key cryptosystem [5], Shamir's message passing scheme [6], Bellare-Micali non-interactive oblivious transfer [9] and Okamoto conference key sharing scheme [10], etc.
Contribution. Making use of the least significant bit and the most significant bits, we first study the Diffie-Hellman (DH) problem over a general finite field of large characteristics and prove that the hidden number problem with chosen multiplier (HNP-CM) is as hard as computational DH problem. Then we prove the same results of the elliptic curve over the general finite field and analyze the bit security of tripartite DH key exchange protocol.

2 Hidden number problem with trace

2.1 On the most significant bits

Let p be a sufficient large prime, $\lfloor \mathit{s}{\rfloor }_{\mathit{p}}$ denote the remainder of an integer s on division by p and $\lceil \mathrm{l}\mathrm{o}\mathrm{g}\mathit{x}\rceil $ be the length of x in binary. We use xmodp to denote unique integer a in the range [0,p-1] satisfying $\mathit{x}\equiv \mathit{a}\left(\mathrm{m}\mathrm{o}\mathrm{d}\mathit{p}\right)$. Let F_p=Z_p be a finite field of p elements and F_p^m be the finite extension of F_p. For an integer x, we define $\Vert \mathit{x}{\Vert }_{\mathit{p}}=\underset{\mathit{a}\in \mathbf{Z}}{\mathrm{m}\mathrm{i}\mathrm{n}} |\mathit{x}-\mathit{a}\mathit{p}|$ and for a given k>0, denote by MSB_k,p(x) as the integer u,0≤u≤p-1, such that $\Vert \mathit{x}-\mathit{u}{\Vert }_{\mathit{p}}\le \frac{\mathit{p}}{{2}^{\mathit{k}+1}}$. Roughly speaking, a value of MSB_k,p(x) gives the k most significant bits of the residue of x modulo p. We denote by $\mathrm{T}\mathrm{r}\left(\mathit{z}\right)=\sum _{\mathit{i}=0}^{\mathit{m}-1} {\mathit{z}}^{{\mathit{p}}^{\mathit{i}}}$ and $\mathrm{N}\mathrm{m}\left(\mathit{z}\right)=\prod _{\mathit{i}=0}^{\mathit{m}-1} {\mathit{z}}^{{\mathit{p}}^{\mathit{i}}}$ the trace and norm of $\mathit{z}\in {\mathbf{F}}_{{\mathit{p}}^{\mathit{m}}}$ to F_p respectively.

HNP-MSB The MSB hidden number problem with trace over a subgroup $\mathcal{G}\subseteq {\mathbf{F}}_{{\mathit{p}}^{\mathit{m}}}^{\mathrm{*}}$ can be formulated as follows: Given r elements ${\mathit{t}}_{1},\cdots,{\mathit{t}}_{\mathit{r}}\in \mathcal{G}$, chosen independently and uniformly at random, the values MSB_k,p(Tr(αt_i)) for $\mathit{i}=1,\cdots,\mathit{r}$ and some k>0, recover the number $\mathit{\alpha }\in {\mathbf{F}}_{{\mathit{p}}^{\mathit{m}}}^{\mathrm{*}}$.

The case of m=1 and $\mathcal{G}={\mathbf{F}}_{\mathit{p}}^{\mathrm{*}}$ corresponds to the hidden number problem introduced in [4], and for the case $\mathcal{G}\subseteq {\mathbf{F}}_{\mathit{p}}^{\mathrm{*}}$ see [7]. The case of $\mathit{m}\ge 2$ is more difficult because one of the crucial ingredients, a bound on exponential sums with elements of small subgroups of F_p^m, is missing. nevertheless in some special cases results of a comparable strength have been obtained in [8]. In other cases, an alternative method from [11] can be used, leading to weaker results.

We denote by $\mathcal{N}$ the set of $\mathit{z}\in {\mathbf{F}}_{{\mathit{p}}^{\mathit{m}}}$ with norm equal to 1, thus $\left|\mathcal{N}\right|=\frac{{\mathit{p}}^{\mathit{m}}-1}{\mathit{p}-1}$. The following statement a partial case of Theorem 2 of [8].

Lemma 1. Let p be a sufficiently large prime and $\mathcal{G}$ be a subgroup of $\mathcal{N}$ of order l with $\mathit{l}\ge {\mathit{p}}^{(\mathit{m}-1)/2+\mathit{\rho }}$ for some fixed ρ>0. Then for $\mathit{k}=\lceil 2\sqrt{\mathrm{l}\mathrm{o}\mathrm{g}\mathit{p}}\rceil $ and r= $\lceil 4(\mathit{m}+1)\sqrt{\text{ }\text{logp}\text{ }}\rceil $, there is a deterministic polynomial time algorithm $\mathcal{A}$ as follows. For any $\mathit{\alpha }\in {\mathbf{F}}_{{\mathit{p}}^{\mathit{m}}}^{\mathrm{*}}$, if ${\mathit{t}}_{1},\cdots,{\mathit{t}}_{\mathit{r}}$ are chosen uniformly and independently at random from $\mathcal{G}$ and if u_i=MSB_k,p(Tr(αt_i)) for $\mathit{i}=1,\cdots,\mathit{r}$, the output of $\mathcal{A}$ on the 2r values (t_i,u_i) satisfies ${\mathrm{P}\mathrm{r}}_{{\mathit{t}}_{1},\cdots,{\mathit{t}}_{\mathit{r}}\in \mathcal{G}}\left[\mathcal{A}\left({\mathit{t}}_{1},\cdots,{\mathit{t}}_{\mathit{r}};{\mathit{u}}_{1},\cdots,{\mathit{u}}_{\mathit{r}}\right)=\mathit{\alpha }\right]\ge 1-{\mathit{p}}^{-1}$.

For smaller groups, a weaker result is given by Theorem 1 of [11].

Lemma 2. Let p be a sufficiently large prime and $\mathcal{G}$ be a subgroup of ${\mathbf{F}}_{{\mathit{p}}^{\mathit{m}}}^{\mathrm{*}}$ of prime order l with $\mathit{l}\ge {\mathit{p}}^{\mathit{\rho }}$ for some fixed ρ>0. Then for any ε>0, let $\mathit{k}=⌈\left(1-\frac{\mathit{\rho }}{\mathit{m}}+\mathit{\epsilon }\right)\mathrm{l}\mathrm{o}\mathrm{g}\mathit{p}⌉$ and $\mathit{r}=\lceil 4\mathit{m}/\mathit{\epsilon }\rceil $, there is a deterministic polynomial time algorithm $\mathcal{A}$ as follows. For any $\mathit{\alpha }\in {\mathbf{F}}_{{\mathit{p}}^{\mathit{m}}}^{\mathrm{*}}$, if ${\mathit{t}}_{1},\cdots,{\mathit{t}}_{\mathit{r}}$ are chosen uniformly and independently at random from $\mathcal{G}$ and if u_i=MSB_k,p(Tr(αt_i)) for $\mathit{i}=1,\cdots,\mathit{r}$, the output of $\mathcal{A}$ on the 2r values (t_i,u_i) satisfies ${\mathrm{P}\mathrm{r}}_{{\mathit{t}}_{1},\cdots,{\mathit{t}}_{\mathit{r}}\in \mathcal{G}}\left[\mathcal{A}\left({\mathit{t}}_{1},\cdots,{\mathit{t}}_{\mathit{r}};{\mathit{u}}_{1},\cdots,{\mathit{u}}_{\mathit{r}}\right)=\mathit{\alpha }\right]\ge 1-{\mathit{p}}^{-\mathit{m}}$.

Here we can give a generalization of Lemma 1. We first generalize the HNP-MSB problem to be MSB ^d hidden number problem (HNP-MSB ^d ). HNP-MSB ^d with trace over a subgroup $\mathcal{G}\subseteq {\mathbf{F}}_{{\mathit{p}}^{\mathit{m}}}^{\mathrm{*}}$ can be defined as follows: Given r elements ${\mathit{t}}_{1},\cdots,{\mathit{t}}_{\mathit{r}}\in \mathcal{G}$, chosen independently and uniformly at random, and the values $\mathit{M}\mathit{S}{\mathit{B}}_{\mathit{k},\mathit{p}}\left(\mathit{T}\mathit{r}\left(\mathit{\alpha }{\mathit{t}}_{\mathit{i}}^{\mathit{d}}\right)\right)$ for $\mathit{i}=1,\cdots,\mathit{r}$, some k>0 and integer d>0, recover the number $\mathit{\alpha }\in {\mathbf{F}}_{{\mathit{p}}^{\mathit{m}}}^{\mathrm{*}}$. Obviously, when d=1, it is HNP-MSB. We define ${\mathcal{O}}_{{\mathrm{M}\mathrm{S}\mathrm{B}}^{1}}$ to be an oracle for ${\mathrm{M}\mathrm{S}\mathrm{B}}_{\mathit{k},\mathit{p}}\left(\mathrm{T}\mathrm{r}\right(\mathit{t}\left)\right)$ for any t.

Lemma 3. Let p be a sufficiently large prime and $\mathcal{G}$ be a subgroup of $\mathcal{N}$ of order l with $\mathit{l}\ge {\mathit{p}}^{(\mathit{m}-1)/2+\mathit{\rho }}$ for some fixed ρ>0. Then for $\mathit{k}=\lceil 2\sqrt{\mathrm{l}\mathrm{o}\mathrm{g}\mathit{p}}\rceil $ and = $\lceil 4(\mathit{m}+1)\sqrt{\mathrm{l}\mathrm{o}\mathrm{g}\mathit{p}}\rceil $, given an oracle ${\mathcal{O}}_{\mathit{M}\mathit{S}{\mathit{B}}^{1}}$, there is a deterministic polynomial time algorithm ${\mathcal{A}}^{{\mathcal{O}}_{\mathit{M}\mathit{S}{\mathit{B}}^{1}}}$ for HNP-MSB ^d as follows. For any $\mathit{\alpha }\in {\mathbf{F}}_{{\mathit{p}}^{\mathit{m}}}^{\mathrm{*}}$, if ${\mathit{t}}_{1},\cdots,{\mathit{t}}_{\mathit{r}}$ are chosen uniformly and independently at random from $\mathcal{G}$ and make r calls to ${\mathcal{O}}_{\text{MSB}\text{ }}$, the output of ${\mathcal{A}}^{{\mathcal{O}}_{\mathit{M}\mathit{S}{\mathit{B}}^{1}}}$ on the r values t_i satisfies

${\mathit{P}\mathit{r}}_{{\mathit{t}}_{1},\cdots,{\mathit{t}}_{\mathit{r}}\in \mathcal{G}}\left[{\mathcal{A}}^{{\mathcal{O}}_{\mathit{M}\mathit{S}{\mathit{B}}^{1}}}\left({\mathit{t}}_{1},\cdots,{\mathit{t}}_{\mathit{r}}\right)=\mathit{\alpha }\right]\ge \frac{1}{{\mathit{e}}^{\mathit{r}}}\left(1-{\mathit{p}}^{-1}\right)+\left(1-\frac{1}{{\mathit{e}}^{\mathit{r}}}\right){\mathit{p}}^{-\mathit{m}},$

where e=gcd(d,l).

Proof. Set ${\mathit{u}}^{\mathit{d}}\left(\mathit{\lambda }\right):={\mathrm{M}\mathrm{S}\mathrm{B}}_{\mathit{k},\mathit{p}}^{\mathit{d}}\left(\mathrm{T}\mathrm{r}\right(\mathit{\alpha }\mathit{\lambda }\left)\right):={\mathrm{M}\mathrm{S}\mathrm{B}}_{\mathit{k},\mathit{p}}\left(\mathrm{T}\mathrm{r}\left(\mathit{\alpha }{\mathit{\lambda }}^{\mathit{d}}\right)\right)$. Let $\mathit{R}:\mathcal{G}⟶{\mathbf{F}}_{\mathit{p}}^{\mathrm{*}}$ be a random function chosen uniformly from the set of all functions from $\mathcal{G}$ to ${\mathbf{F}}_{\mathit{p}}^{\mathrm{*}}$, and $\mathit{S}:{\mathcal{G}}^{\mathit{d}}⟶\mathcal{G}$ be a function satisfying $\mathit{S}(\mathit{\lambda }{)}^{\mathit{d}}\equiv \mathit{\lambda }\left(\mathrm{m}\mathrm{o}\mathrm{d}{\mathit{p}}^{\mathit{m}}\right)$. Here ${\mathcal{G}}^{\mathit{d}}$ is the set of d^' th powers in $\mathcal{G}$. The function S is simply a function mapping a d 'th power $\mathit{x}\in {\mathcal{G}}^{\mathit{d}}$ to a randomly chosen d 'th root of x. Next, define the following function ${\mathrm{M}\mathrm{S}\mathrm{B}}_{\mathit{k},\mathit{p}}\left(\mathrm{T}\mathrm{r}\right(\mathit{\alpha }\mathit{\lambda }\left)\right)$ :

$\mathit{u}\left(\mathit{\lambda }\right)={\mathrm{M}\mathrm{S}\mathrm{B}}_{\mathit{k},\mathit{p}}\left(\mathrm{T}\mathrm{r}\right(\mathit{\alpha }\mathit{\lambda }\left)\right)=\left\{\begin{array}{ll}{\mathit{u}}^{\mathit{d}}\left(\mathit{S}\right(\mathit{\lambda }\left)\right),& \text{ }\text{if}\text{ }\mathit{\lambda }\in {\mathcal{G}}^{\mathit{d}}\\ \mathit{R}\left(\mathit{\lambda }\right),& \text{ }\text{otherwise}\text{ }\end{array}\right.$

If gcd(d,l)=1, then ${\mathcal{G}}^{\mathit{d}}=\mathcal{G}$. Choose ${\mathit{t}}_{1},\cdots,{\mathit{t}}_{\mathit{r}}$ uniformly and independently at random from $\mathcal{G}$, then ${\mathit{t}}_{1}^{\mathit{\text{'}}}={\mathit{t}}_{1}^{\mathit{d}},\cdots,{\mathit{t}}_{\mathit{r}}^{\mathit{\text{'}}}={\mathit{t}}_{\mathit{r}}^{\mathit{d}}$ is also distributed uniformly and independently in $\mathcal{G}$. Calling the oracle ${\mathcal{O}}_{{\mathrm{M}\mathrm{S}\mathrm{B}}^{1}}$ on ${\mathit{t}}_{\mathit{i}}^{\mathit{\text{'}}}$, we get ${\mathit{u}}_{1}^{\mathit{d}}:={\mathit{u}}^{\mathit{d}}\left({\mathit{t}}_{1}^{\mathit{\text{'}}}\right),\cdots,{\mathit{u}}_{\mathit{r}}^{\mathit{d}}:={\mathit{u}}^{\mathit{d}}\left({\mathit{t}}_{\mathit{r}}^{\mathit{\text{'}}}\right)$. For the pairs $\left({\mathit{t}}_{1}^{\mathit{\text{'}}},{\mathit{u}}_{1}^{\mathit{d}}\right),\cdots,\left({\mathit{t}}_{\mathit{r}}^{\mathit{\text{'}}},{\mathit{u}}_{\mathit{r}}^{\mathit{d}}\right)$, by Lemma 1, there is a deterministic polynomial time algorithm $\mathcal{B}$ such that

${\mathrm{P}\mathrm{r}}_{{\mathit{t}}_{1},\cdots,{\mathit{t}}_{\mathit{r}}\in \mathcal{G}}\left[\mathcal{B}\left({\mathit{t}}_{1}^{\mathit{\text{'}}},\cdots,{\mathit{t}}_{\mathit{r}}^{\mathit{\text{'}}};{\mathit{u}}_{1}^{\mathit{d}},\cdots,{\mathit{u}}_{\mathit{r}}^{\mathit{d}}\right)=\mathit{\alpha }\right]\ge 1-{\mathit{p}}^{-1}.$

Now we define a algorithm ${\mathcal{A}}_{{\mathrm{M}\mathrm{S}\mathrm{B}}^{1}}$ to call the oracle ${\mathcal{O}}_{{\mathrm{M}\mathrm{S}\mathrm{B}}^{1}}$ and algorithm $\mathcal{B}$, then ${\mathcal{A}}^{{\mathcal{O}}_{\mathrm{M}\mathrm{S}\mathrm{B}1}}\left({\mathit{t}}_{1},\cdots,{\mathit{t}}_{\mathit{r}}\right)=\mathcal{B}\left({\mathit{t}}_{1}^{\mathit{\text{'}}},\cdots,{\mathit{t}}_{\mathit{r}}^{\mathit{\text{'}}};{\mathit{u}}_{1}^{\mathit{d}},\cdots,{\mathit{u}}_{\mathit{r}}^{\mathit{d}}\right)$. So ${\mathcal{A}}^{{\mathcal{O}}_{\mathrm{M}\mathrm{S}\mathrm{B}1}}$ is a deterministic polynomial time algorithm satisfying

${\mathrm{P}\mathrm{r}}_{{\mathit{t}}_{1},\cdots,{\mathit{t}}_{\mathit{r}}\in \mathcal{G}}\left[{\mathcal{A}}^{{\mathcal{O}}_{{\mathrm{M}\mathrm{S}\mathrm{B}}^{1}}}\left({\mathit{t}}_{1},\cdots,{\mathit{t}}_{\mathit{r}}\right)=\mathit{\alpha }\right]\ge 1-{\mathit{p}}^{-1}.$

If gcd(d,l)=e>1, then ${\mathcal{G}}^{\mathit{d}}={\mathcal{G}}^{\mathit{e}}$ and $\left|{\mathcal{G}}^{\mathit{e}}\right|=\frac{\mathit{l}}{\mathit{e}}$. Similar to the above, we have a algorithm ${\mathcal{A}}^{{\mathcal{O}}_{\text{MSB}\text{ }}{\mathit{ }}^{1}}$ such that

$\begin{array}{rr}& {\mathrm{P}\mathrm{r}}_{{\mathit{t}}_{1},\cdots,{\mathit{t}}_{\mathit{r}}\in \mathcal{G}}\left[{\mathcal{A}}_{{\mathrm{M}\mathrm{S}\mathrm{B}}^{1}}\left({\mathit{t}}_{1},\cdots,{\mathit{t}}_{\mathit{r}}\right)=\mathit{\alpha }\right]=\frac{1}{{\mathit{e}}^{\mathit{r}}}{\mathrm{P}\mathrm{r}}_{{\mathit{t}}_{1},\cdots,{\mathit{t}}_{\mathit{r}}\in \mathcal{G}}\left[\mathcal{B}\left({\mathit{t}}_{1}^{\mathit{\text{'}}},\cdots,{\mathit{t}}_{\mathit{r}}^{\mathit{\text{'}}};{\mathit{u}}_{1}^{\mathit{d}},\cdots,{\mathit{u}}_{\mathit{r}}^{\mathit{d}}\right)=\mathit{\alpha }\right]\\ & \mathit{ }+\left(1-\frac{1}{{\mathit{e}}^{\mathit{r}}}\right){\mathrm{P}\mathrm{r}}_{{\mathit{t}}_{1},\cdots,{\mathit{t}}_{\mathit{r}}\in \mathcal{G}}\left[\mathcal{B}\left({\mathit{t}}_{1}^{\mathit{\text{'}}},\cdots,{\mathit{t}}_{\mathit{r}}^{\mathit{\text{'}}};{\mathit{u}}_{1}^{\mathit{d}},\cdots,{\mathit{u}}_{\mathit{r}}^{\mathit{d}}\right)=\mathit{\alpha }\right]\ge \frac{1}{{\mathit{e}}^{\mathit{r}}}\left(1-{\mathit{p}}^{-1}\right)+\left(1-\frac{1}{{\mathit{e}}^{\mathit{r}}}\right){\mathit{p}}^{-\mathit{m}}.\end{array}$

This completes the proof.

2.2 On the least significant bit

We denote by LSB(z) the least significant bit of an integer $\mathit{z}\ge 0$. When $\mathit{z}\in {\mathbf{F}}_{\mathit{p}}$, we let LSB(z) be LSB(x) for the unique integer $\mathit{x}\in [0,\mathit{p}-1]$ such that $\mathit{x}\equiv \mathit{z}\mathrm{m}\mathrm{o}\mathrm{d}\mathit{p}$. Now we define the following variant of the Hidden Number Problem (HNP) presented in [4].

HNP-CM  ^d : Fix an integer d>0 and an ε>0. Let p be a prime. For an $\mathit{\alpha }\in {\mathbf{F}}_{\mathit{p}}^{\mathrm{*}}$, let ${\mathit{L}}^{\left(\mathit{d}\right)}:{\mathbf{F}}_{\mathit{p}}^{\mathrm{*}}⟶\left\{\mathrm{0,1}\right\}$ be a function satisfying

(*) $\begin{array}{c}{\mathrm{P}\mathrm{r}}_{\mathit{t}\in {\mathbf{F}}_{\mathit{p}}^{\mathrm{*}}}\left[{\mathit{L}}^{\left(\mathit{d}\right)}\left(\mathit{t}\right)=\mathrm{L}\mathrm{S}\mathrm{B}\left({⌊\mathit{\alpha }{\mathit{t}}^{\mathit{d}}⌋}_{\mathit{p}}\right)\right]\ge \frac{1}{2}+\mathit{\epsilon }.\end{array}$

The HNP-CM  ^d problem is: Given an oracle for L^(d)(t), find α in polynomial time. For small ε there might be multiple α satisfying condition (*) (polynomially many in ε^-1 ). In this case the list-HNP-CM  ^d problem is to find all such that $\mathit{\alpha }\in {\mathbf{F}}_{\mathit{p}}^{\mathrm{*}}$. Note that it is easy to verify that a given α belongs to the list of solutions by picking polynomially many random samples $\mathit{x}\in {\mathbf{F}}_{\mathit{p}}$ (say, O(1/ε²) samples suffice) and testing that L^(d)(x)=LSB(⌊αx^d⌋_p) holds sufficiently often. We usually set d=1,2 or 3. We refer to the above problem as HNP-CM  ^d to denote the fact that we are free to evaluate L^(d)(t) at any multiplier t of our choice (the CM stands for Chosen Multiplier). When d=1, it is the well-known algorithm (ACGS algorithm) due to Alexi, Chor, Goldreich, and Schnorr [1]. In the original HNP studies in [4] one is only given samples (t,L¹(t)=L(t)) for random t. The following result shows how to solve the HNP-CM^d problem for any ε>0. The proof of it can be found in [1] and [3].

Lemma 4. Fixed an integer d>0. Let p be a n-bit prime and let ε>0. Then given ε, the HNP-CM  ^d problem can be solved in expected polynomial time in logp and d/ε.

Notice. In particularly, in the following we usually set α=MSB_k,p(Tr(ut_i)).

3 Security of bits of Diffie-Hellman scheme over a finite field

In this section, we make use of solutions, as shown in the preceding, to HNP of the most significant bits and the least significant bit respectively to prove that predicting the LSB of Diffie-Hellman secret is as hard as solving computational Diffie-Hellman problem. The following result show us that predicting LSB is not easier than trying to find MSB. We define ${\mathcal{O}}^{\mathit{L}}$ to be an oracle for L⁽¹⁾(t):=L(t).

Theorem 1. Given oracle ${\mathcal{O}}^{\mathit{L}}$ and a sufficient large prime p. Then, given ε>0, HNP-MSB can be solved in expected polynomial time $\mathit{m}\cdot \mathit{T}\left(\mathrm{l}\mathrm{o}\mathrm{g}\mathrm{p},\frac{1}{\mathit{\epsilon }}\right)$, where T is a fixed polynomial and m is the degree of extension of finite fields as above.

Proof. For $\mathit{\alpha }\in {\mathbf{F}}_{{\mathit{p}}^{\mathit{m}}}^{\mathrm{*}}$, we choose independently and uniformly at random r elements ${\mathit{t}}_{1},\cdots,{\mathit{t}}_{\mathit{r}}\in \mathcal{G}$. By Lemma 1, if we find the values u_i=MSB_k,p(Tr(αt_i)) for $\mathit{i}=1,\cdots,\mathit{r}$ and some k>0, then we can recover the number $\mathit{\alpha }\in {\mathbf{F}}_{{\mathit{p}}^{\mathit{m}}}^{\mathrm{*}}$ by a deterministic polynomial time algorithm $\mathcal{A}$, such that

${\mathrm{P}\mathrm{r}}_{{\mathit{t}}_{1},\cdots,{\mathit{t}}_{\mathit{r}}\in \mathcal{G}}\left[\mathcal{A}\left({\mathit{t}}_{1},\cdots,{\mathit{t}}_{\mathit{r}};{\mathit{u}}_{1},\cdots,{\mathit{u}}_{\mathit{r}}\right)=\mathit{\alpha }\right]\ge 1-{\mathit{p}}^{-1}.$

So we get the result.

Now we try to determine u_i for $\mathit{i}=1,\cdots,\mathit{r}$. By the definition, we know that 0≤u_i≤p-1. For any i and any $\mathit{t}\in {\mathbf{F}}_{\mathit{p}}^{\mathrm{*}}$, we do with L(t)=LSB(⌊u_it⌋_p). Making use of the ACGS algorithm (the case d=1 of Lemma 3 ) and oracle ${\mathcal{O}}^{\mathit{L}},{\mathit{u}}_{\mathit{i}}$ could be found in expected polynomial time in n=logp and $\frac{1}{\mathit{\epsilon }}$. After repeating the procedure r times, we could find ${\mathit{u}}_{1},\cdots,{\mathit{u}}_{\mathit{r}}$ in expected polynomial time $\mathit{r}{\mathit{T}}^{\mathit{\text{'}}}\left(\mathit{n},\frac{1}{\mathit{\epsilon }}\right)$ for a fixed polynomial T^'. This completes the proof.

In the following, given (g,g^x,g^y), we show that if there is an efficient algorithm for predicting the LSB of Tr(g^ab)t for $\mathit{t}\in {\mathbf{F}}_{\mathit{p}}^{\mathrm{*}}$, then there is an algorithm for computing the Diffie-Hellman function, i.e., finding g^ab.

Corollary 1. Given (g,g^x,g^y) for $\mathit{g}\in {\mathbf{F}}_{{\mathit{p}}^{\mathit{m}}}^{\mathrm{*}}$, if there is an efficient algorithm for predicting LSB(Tr(g^ab)t) for $\mathit{t}\in {\mathbf{F}}_{\mathit{p}}^{\mathrm{*}}$, then there is an algorithm for computing the Diffie-Hellman function, i.e., finding g^ab in expected polynomial time.

Proof. It is easily to get the result by Theorem 3.1.

Remark 1. For smaller group, by Lemma 2, we can get similar results. these results also show that solving the hidden number problem with chosen multiplier (HNP-CM) is as hard as computing DH function. Furthermore, we know that if computing DH function is hard, then the least significant bits are unpredictable.

4 Security of bits of elliptic curve Diffie-Hellman scheme

In this section, we discuss the relations between Diffie-Hellman problem and LSB over elliptic curves. Let E be an elliptic curve over finite field F_p^m of size p^m, which is the finite extension of F_p, given by an affine Weierstrass equation of the form

(4.1)${\mathit{Y}}^{2}={\mathit{X}}^{3}+\mathit{A}\mathit{X}+\mathit{B},\mathrm{ }4{\mathit{A}}^{3}+27{\mathit{B}}^{2}\ne 0.\#$

It is well known that the set E(F_p^m) of F_p^m-rational points of E form an Abelian group under an appropriate composition rule and with the point at infinity O as the neutral element.

Let $\mathit{G}\in \mathbf{E}$ be a point of order q for some prime q. Then the common key established at the end of the Diffie-Hellman protocol with respect to the curve E and the point G is $\mathit{a}\mathit{b}\mathit{G}=(\mathit{x},\mathit{y})\in \mathbf{E}$ for some integers $\mathit{a},\mathit{b}\in [1,\mathit{q}-1]$. Throughout the rest, we use the fact that the representation of E contains the field of definition of E. With the convention, an algorithm given the representation of E/F_p^m as input does not need to also be given p^m and p. The algorithm obtains p^m and p from the representation of E.

Diffie-Hellman Function: Let E be an elliptic curve over F_p^m and let $\mathit{G}\in \mathbf{E}$ be a point of prime order q. We define Diffie-Hellman function as: DH_E,G(aG,bG)=abG, where a,b are integers in [1,q-1]. The Diffie-Hellman problem on E is to compute DH_E,G(P,Q) given E,P,G and Q. Usually, we mostly focus on curves in which Diffie-Hellman problem is believed to be hard. Throughout we say that a randomized algorithm $\mathcal{A}$ computes the Diffie-Hellman function if $\mathcal{A}(\mathbf{E},\mathit{G},\mathit{a}\mathit{G},\mathit{b}\mathit{G})=\mathit{a}\mathit{b}\mathit{G}$ holds with probability at least 1-1/p^m. The probability is over the random bits used by $\mathcal{A}$.

Twists on elliptic curves: Let $\mathcal{G}$ be a subgroup of F_p^m with $\left|\mathcal{G}\right|\ge {\mathit{p}}^{\mathit{\rho }}$ for ρ>0. For any $\mathit{\lambda }\in \mathcal{G}$, define ${\mathit{\varphi }}_{\mathit{\lambda }}\left(\mathbf{E}\right)$ to be the twisted elliptic curve:

(4.2)${\mathit{Y}}^{2}={\mathit{X}}^{3}+\mathit{A}{\mathit{\lambda }}^{4}\mathit{X}+\mathit{B}{\mathit{\lambda }}^{6},\mathrm{ }4{\left(\mathit{A}{\mathit{\lambda }}^{4}\right)}^{3}+27{\left(\mathit{B}{\mathit{\lambda }}^{6}\right)}^{2}\ne 0.\#$

Hence, ${\mathit{\varphi }}_{\mathit{\lambda }}\left(\mathbf{E}\right)$ is an elliptic curve for any $\mathit{\lambda }\in \mathcal{G}$. Throughout this section, we are working with the family of curves ${\left\{{\mathit{\varphi }}_{\mathit{\lambda }}\left({\mathbf{E}}_{0}\right)\right\}}_{\mathit{\lambda }\in \mathcal{G}}$ associated with a given curve E₀. It is easy to verify that for any point $\mathit{P}=(\mathit{x},\mathit{y})\in \mathbf{E}$ and any $\mathit{\lambda }\in \mathcal{G}$ the point P_λ= $\left(\mathit{x}{\mathit{\lambda }}^{2},\mathit{y}{\mathit{\lambda }}^{3}\right)\in {\mathit{\varphi }}_{\mathit{\lambda }}\left(\mathbf{E}\right)$ (see [3]). Moreover, for any points $\mathit{P},\mathit{Q},\mathit{R}\in \mathbf{E}$ with P+Q= R we also have P_λ+Q_λ=R_λ. In particular, for any $\mathit{G}\in \mathbf{E}$ we have: xG_λ=(xG)_λ, yG_λ=(yG)_λ,xyG_λ=(xyG)_λ. So map ${\mathit{\varphi }}_{\mathit{\lambda }}:\mathbf{E}⟶{\mathit{\varphi }}_{\mathit{\lambda }}\left(\mathbf{E}\right)$ mapping $\mathit{P}\in \mathbf{E}$ to ${\mathit{P}}_{\mathit{\lambda }}\in {\mathit{\varphi }}_{\mathit{\lambda }}\left(\mathbf{E}\right)$. Indeed, it is easy to verify that ${\mathit{\varphi }}_{\mathit{\lambda }}$ is an isomorphism of groups. So we also have ${\mathrm{D}\mathrm{H}}_{{\mathit{\varphi }}_{\mathit{\lambda }}\left(\mathbf{E}\right),{\mathit{G}}_{\mathit{\lambda }}}\left({\mathit{P}}_{\mathit{\lambda }},{\mathit{Q}}_{\mathit{\lambda }}\right)={\mathit{\varphi }}_{\mathit{\lambda }}\left[{\mathrm{D}\mathrm{H}}_{\mathbf{E},\mathit{G}}(\mathit{P},\mathit{Q})\right]$, i.e. if the Diffie-Hellman function is hard to compute in E then it is also hard to compute for all curves in ${\left\{{\mathit{\varphi }}_{\mathit{\lambda }}\left(\mathbf{E}\right)\right\}}_{\mathit{\lambda }\in \mathcal{G}}$.

For any $\mathit{z}\in {\mathbf{F}}_{\mathit{p}}$, we let LSB(z) be LSB(x) for the unique integer $\mathit{x}\in [0,\mathit{p}-1]$ such that $\mathit{x}\equiv \mathit{z}\mathrm{m}\mathrm{o}\mathrm{d}\mathit{p}$. We say that an algorithm $\mathcal{A}$ has advantage ϵ in predicting the LSB of the trace of the x-coordinate of the Diffie-Hellman function on E if:

${\mathrm{A}\mathrm{d}\mathrm{v}}_{\mathbf{E},\mathit{G}}^{\mathit{X}}\left(\mathcal{A}\right)=\left|{\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{b}}_{\mathit{a},\mathit{b}}\left[\mathcal{A}(\mathbf{E},\mathit{G},\mathit{a}\mathit{G},\mathit{b}\mathit{G})=\mathrm{L}\mathrm{S}\mathrm{B}\left({\mathrm{M}\mathrm{S}\mathrm{B}}_{\mathit{k},\mathit{p}}\left(\mathrm{T}\mathrm{r}\right(\mathit{x}\left)\right)\right)\right]-\frac{1}{2}\right|>\mathit{ϵ},$

where $\mathit{a}\mathit{b}\mathit{G}=(\mathit{x},\mathit{y})\in \mathbf{E},\mathit{k}=\lceil 2\sqrt{\mathrm{l}\mathrm{o}\mathrm{g}\mathit{p}}\rceil $ and a,b are chosen uniformly at random in [1,q-1]. We write ${\mathrm{A}\mathrm{d}\mathrm{v}}_{\mathbf{E},\mathit{G}}^{\mathit{X}}\left(\mathcal{A}\right)>\mathit{ϵ}$. Similarly, we say that algorithm $\mathcal{A}$ has advantage
ϵ in predicting the LSB of the trace of the y-coordinate of the Diffie-Hellman function on E if:

${\mathrm{A}\mathrm{d}\mathrm{v}}_{\mathbf{E},\mathit{G}}^{\mathit{Y}}\left(\mathcal{A}\right)=\left|{\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{b}}_{\mathit{a},\mathit{b}}\left[\mathcal{A}(\mathbf{E},\mathit{G},\mathit{a}\mathit{G},\mathit{b}\mathit{G})=\mathrm{L}\mathrm{S}\mathrm{B}\left({\mathrm{M}\mathrm{S}\mathrm{B}}_{\mathit{k},\mathit{p}}\left(\mathrm{T}\mathrm{r}\right(\mathit{y}\left)\right)\right)\right]-\frac{1}{2}\right|>\mathit{ϵ},$

where $\mathit{a}\mathit{b}\mathit{G}=(\mathit{x},\mathit{y})\in \mathbf{E}$. We write ${\mathrm{A}\mathrm{d}\mathrm{v}}_{\mathbf{E},\mathit{G}}^{\mathit{Y}}\left(\mathcal{A}\right)>\mathit{ϵ}$.

Due to some modification of proof of main theorem in [3], we can prove the following results which show that no algorithm can have a non-negligible advantage in predicting the LSB of the traces of the x or y coordinates of the Diffie-Hellman secret for many curves in ${\left\{{\mathit{\varphi }}_{\mathit{\lambda }}\left({\mathbf{E}}_{0}\right)\right\}}_{\mathit{\lambda }\in \mathcal{G}}$, unless Diffie-Hellman problem is easy on E₀.

Theorem 2. Let $\mathit{ϵ},\mathit{\delta }\in \left(\mathrm{0,1}\right)$. Let E₀ be an elliptic curve over F_p^m and $\mathit{G}\in {\mathbf{E}}_{0}$ be a point of prime order. Suppose there is a t-time algorithm $\mathcal{A}$ such that either:

1. $\mathit{A}\mathit{d}{\mathit{v}}_{{\mathit{\varphi }}_{\mathit{\lambda }}\left({\mathbf{E}}_{0}\right),{\mathit{\varphi }}_{\mathit{\lambda }}\left(\mathit{G}\right)}^{\mathit{X}}\left(\mathcal{A}\right)>\mathit{ϵ}$ for at least a $\mathit{\delta }$-fraction of the $\mathit{\lambda }\in {\mathbf{F}}_{\mathit{p}}^{\mathrm{*}}$, or

2. $\mathit{A}\mathit{d}{\mathit{v}}_{{\mathit{\varphi }}_{\mathit{\lambda }}}^{\mathit{Y}}\left({\mathbf{E}}_{0}\right),{\mathit{\varphi }}_{\mathit{\lambda }}\left(\mathit{G}\right)\left(\mathcal{A}\right)>\mathit{ϵ}$ for at least a $\mathit{\delta }$-fraction of the $\mathit{\lambda }\in {\mathbf{F}}_{\mathit{p}}^{\mathrm{*}}$.

Then the most significant bits of the traces of DH function DH_E0,G(P,Q) can be computed in expected time $\mathit{t}\cdot \mathit{T}\left(\mathrm{l}\mathrm{o}\mathrm{g}\mathit{p},\frac{1}{\mathit{ϵ}\mathit{\delta }}\right)$, where T is some fixed polynomial independent of p and E₀.

For any $\mathit{\mu }\in \mathcal{G}$ and $\mathit{k}=\lceil 2\sqrt{\mathrm{l}\mathrm{o}\mathrm{g}\mathit{p}}\rceil $, let algorithm

${\mathcal{A}}^{\mathit{\mu }}\left({\mathbf{E}}_{\mathit{\mu }},{\mathit{G}}_{\mathit{\mu }},(\mathit{a}\mathit{G}{)}_{\mathit{\mu }},(\mathit{b}\mathit{G}{)}_{\mathit{\mu }}\right)=\mathrm{L}\mathrm{S}\mathrm{B}\left({\mathrm{M}\mathrm{S}\mathrm{B}}_{\mathit{k},\mathit{p}}\left(\mathrm{T}\mathrm{r}\left(\mathit{x}{\mathit{\mu }}^{2}\right)\right)\right)$

(respectively, LSB(Tr(yμ³)) for the x-coordinate (resp. y-coordinate). We consider the curve ${\mathit{\varphi }}_{\mathit{\mu }}\left(\mathbf{E}\right)={\mathbf{E}}_{\mathit{\mu }}={\mathbf{E}}_{0}$ for any $\mathit{\mu }\in {\mathbf{F}}_{{\mathit{p}}^{\mathit{m}}}^{\mathrm{*}}$, by Theorem 2, we get the following result:

Theorem 3. Let $\mathit{ϵ},\mathit{\delta }\in \left(\mathrm{0,1}\right)$. Let E₀ be an elliptic curve over ${\mathbf{F}}_{{\mathit{p}}^{\mathit{m}}},\mathit{G}\in {\mathbf{E}}_{0}$ be a point of prime order q and $\mathcal{G}\le {\mathbf{F}}_{{\mathit{p}}^{\mathit{m}}}^{\mathrm{*}}$ of order $\mathit{l},\mathit{l}\ge {\mathit{p}}^{\mathit{\rho }}$ for ρ>0. For any $\mathit{\mu }\in \mathcal{G}$, suppose there is a t-time algorithm ${\mathcal{A}}^{\mathit{\mu }}$ such that either:

1. $\mathit{A}\mathit{d}{\mathit{v}}_{{\mathit{\varphi }}_{\mathit{\lambda }}\left({\mathbf{E}}_{0}\right),{\mathit{\varphi }}_{\mathit{\lambda }}\left({\mathit{G}}_{\mathit{\mu }}\right)}^{{\mathit{X}}_{\mathit{\mu }}}\left({\mathcal{A}}^{\mathit{\mu }}\right)>\mathit{ϵ}$ for at least a $\mathit{\delta }$-fraction of the $\mathit{\lambda }\in {\mathbf{F}}_{\mathit{p}}^{\mathrm{*}}$, or

2. $\mathit{A}\mathit{d}{\mathit{v}}_{{\mathit{\varphi }}_{\mathit{\lambda }}\left({\mathbf{E}}_{0}\right),{\mathit{\varphi }}_{\mathit{\lambda }}\left({\mathit{G}}_{\mathit{\mu }}\right)}^{{\mathit{Y}}_{\mathit{\mu }}}\left({\mathcal{A}}^{\mathit{\mu }}\right)>\mathit{ϵ}$ for at least a $\mathit{\delta }$-fraction of the $\mathit{\lambda }\in {\mathbf{F}}_{\mathit{p}}^{\mathrm{*}}$.

Then Diffie-Hellman function DH_E0,G(P,Q) can be computed in expected time ⋅t⋅ $\mathit{T}\left(\mathrm{l}\mathrm{o}\mathrm{g}\mathit{p},\frac{1}{\mathit{ϵ}\mathit{\delta }}\right)\cdot \frac{{2}^{\mathit{r}}}{1-{\mathit{p}}^{-1}}$, where T is some fixed polynomial independent of p and E₀ and $\mathit{r}=\lceil 4(\mathit{m}+1)\sqrt{\mathrm{l}\mathrm{o}\mathrm{g}\mathit{p}}\rceil $.

Remark 2. If $\left|\mathcal{G}\right|=\mathit{l}$ is a prime, then by Lemma 3, we get abG=(x,y) with probability $\ge \left(1-{\mathit{p}}^{-1}\right)$.

5 Bit security of tripartite Diffie-Hellman

In this section, we study the bit security of keys obtained using protocol based on pairings. Let p be a prime and F_p be the field of p elements, which we identify with the set $\{\mathrm{0,1},\cdots,\mathit{p}-1\}$. Let l be a prime which is coprime to p and l>p^ρ for some ρ>0, and define m to be the smallest positive integer such that ${\mathit{p}}^{\mathit{m}}\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}\mathit{l}$. Now
we consider a non-degeneration bilinear pairing $\mathit{e}:{\mathbf{G}}_{1}\times {\mathbf{G}}_{2}⟶\mathcal{G}\subseteq {\mathbf{F}}_{{\mathit{p}}^{\mathit{m}}}^{\mathrm{*}}$, where G₁,G₂ and $\mathcal{G}$ are cyclic groups of order l.

Pairing have found many application in cryptography including the tripartite key exchange protocol of Joux [12]. We recall the tripartite Diffie-Hellman protocol in the original formulation:

To Set up the system, three communicating parties A,B and C choose suitable groups G₁ and G₂ of order l and points $\mathit{P}\in {\mathbf{G}}_{1}$ and $\mathit{Q}\in {\mathbf{G}}_{2}$ with $1\ne \mathit{e}(\mathit{P},\mathit{Q})\in $${\mathbf{F}}_{{\mathit{p}}^{\mathit{m}}}^{\mathrm{*}}$.

To create a common secret key, A,B and C choose secret numbers $\mathit{a},\mathit{b},\mathit{c}\in $ [0,l-1] and publish pairs (aP,aQ),(bP,bQ) and (cP,cQ).

Now each of them is able to compute the common key K=e(P,Q)^abc. For example, A can compute K as follows,

$\mathit{e}(\mathit{b}\mathit{P},\mathit{c}\mathit{Q}{)}^{\mathit{a}}=\mathit{e}(\mathit{P},\mathit{c}\mathit{Q}{)}^{\mathit{a}\mathit{b}}=\mathit{e}(\mathit{P},\mathit{Q}{)}^{\mathit{a}\mathit{b}\mathit{c}}=\mathit{K}\in {\mathbf{F}}_{{\mathit{p}}^{\mathit{m}}}^{\mathrm{*}}.$

Note that K is an element of order l.

For $\mathit{k}=⌈\left(1-\frac{\mathit{\rho }}{\mathit{m}}+\mathit{\epsilon }\right)\mathrm{l}\mathrm{o}\mathrm{g}\mathit{p}⌉$, let u=MBS_k,p(Tr(e(P,Q)^abc)). We define an oracle ${\mathcal{O}}^{\mathcal{L}}{\mathit{ }}_{\mathit{k}}$ as follows: For any $\mathit{a},\mathit{b},\mathit{c}\in [0,\mathit{l}-1]$ and $\mathit{t}\in {\mathbf{F}}_{\mathit{p}}^{\mathrm{*}}$, takes as input the pairs (P,Q), (aP,aQ),(bP,bQ) and (cP,cQ), and outputs L(t)=LSB(ut).

Theorem 4. Let $\mathit{ϵ}\in \left(\mathrm{0,1}\right),\mathit{p}$ be a sufficient large prime, and l is the order of groups G₁,G₂ and $\mathcal{G}$ such that gcd(l,p^m-1(p-1))=1 and $\mathit{l}\ge {\mathit{p}}^{\frac{\mathit{m}-1}{2}+\mathit{\rho }}$ for some fixed ρ>0. Then there exists an algorithm $\mathcal{A}$ which, given the pairs (P,Q),(aP,aQ),(bP,bQ) and (cP,cQ), makes $\mathit{r}=⌈4(\mathit{m}+1)\sqrt{\mathrm{l}\mathrm{o}\mathrm{g}\mathit{p}}$ calls of the oracle ${\mathcal{O}}^{\mathcal{L}}{\mathit{ }}_{\mathit{k}}$ and computes e(P,Q)^abc correctly in expected time $\mathit{r}\cdot \mathit{T}\left(\mathrm{l}\mathrm{o}\mathrm{g}\mathit{p},\frac{1}{\mathit{ϵ}}\right)$, where T is an fixed polynomial.

Proof. The case when $\mathit{a}\mathit{b}\equiv 0\mathrm{m}\mathrm{o}\mathrm{d}\mathit{l}$ is trivial. In the general case, i.e., $\mathit{b}\not\equiv $ 0modl, choose a random $\mathit{d}\in \{0,\cdots,\mathit{l}-1\}$ and call the oracle ${\mathcal{O}}_{\mathit{k}}$ on the pairs (P,Q),(aP,aQ),(bP,bQ) and $\left(\right(\mathit{c}+\mathit{d})\mathit{P},(\mathit{c}+\mathit{d}\left)\mathit{Q}\right)$. Let α=e(P,Q)^abc be the hidden number. By Theorem 3.1, we get ${\mathrm{M}\mathrm{B}\mathrm{S}}_{\mathit{k},\mathit{p}}\left(\mathrm{T}\mathrm{r}\left(\mathit{e}(\mathit{P},\mathit{Q}{)}^{\mathit{a}\mathit{b}\mathit{c}}\mathit{e}(\mathit{P},\mathit{Q}{)}^{\mathit{a}\mathit{b}\mathit{d}}\right)\right)=$ MBS_k,p(Tr(αe(P,Q)^abd)) in expected time $\mathit{T}\left(\mathrm{l}\mathrm{o}\mathrm{g}\mathit{p},\frac{1}{\mathit{ϵ}}\right)$, where T is an fixed polynomial. Since l is a prime and $\mathit{a}\mathit{b}\not\equiv 0\mathrm{m}\mathrm{o}\mathrm{d}\mathit{l},\mathit{e}(\mathit{P},\mathit{Q}{)}^{\mathit{a}\mathit{b}\mathit{d}}$ are uniformly and independently distributed in $\mathcal{G}\in {\mathbf{F}}_{{\mathit{p}}^{\mathit{m}}}^{\mathrm{*}}$ of order l, when the shifts d are chosen uniformly and independently at random in $\{0,\cdots,\mathit{l}-1\}$. By Lemma 1, we can find alpha in expected time $\mathit{r}\cdot \mathit{T}\left(\mathrm{l}\mathrm{o}\mathrm{g}\mathit{p},\frac{1}{\mathit{ϵ}}\right)$. This completes the proof.

Remark 3. For a small group $\mathcal{G}$, by Lemma 2, we can get similar result.

6 Conclusion

Making use of the reduction between the least significant bit and the most significant bits, we showed that, over a general finite field of large characteristics, the hidden number problem with chosen multiplier is as hard as computational DH problem. Furthermore, we prove the same results of the elliptic curve over the general finite field and analyze the bit security of tripartite Diffie-Hellman key exchange protocol. We believe the technique of this reduction could be benefit to problem of bit security over any finite field.

References

[1] Alex, W., Chor, B., Goldreich, O., Schnorr, C.: RSA and Rabin functions: Certain parts are as hard as the whole. In SIAM J. Computing, Vol. 17 (1988) 194-209

[2] Boneh, D.: The decision Diffie-Hellman problem. In Proc. 3rd Algorithmic Number Theory Symposium, LNCS, Vol. 1423 (1998) 48-63

[3] Boneh, D., Shparlinski, I.E.: On the unpredictability of bits of the elliptic curve Diffie-Hellman scheme. In Crypto'01, LNCS, Vol. 2139 (2001) 201-212

[4] Boneh, D., Venkatesan, R.: Hardness of computing the most significant bits of secret keys in Diffie-Hellman and related scheme. In Proc. Crypto'96, LNCS, Vol. 1109 (1996) 129-142

[5] ElGamal, T.: A public key cryptosystem and a signature scheme based on the discrete logarithm. In IEEE Transactions on Information Theory, 31(4) (1985) 469-472

[6] Fiat, A., Shamir, A.: How to prove yourself: practical solutions to identification and signature schemes. In Advance in Cryptology-Proceedings Crypto'86, LNCS, Vol. 263 (1986) 186-194

[7] González Vasco, M.I., Shparlinski, I.E.: On the security of Diffie-Hellman bits. In Proc. Workshop on Cryptography and Computational Number Theory, Birkhäuser, (2001) 227-256

[8] Li, W-C.W., Näslund, M., Shparlinski, I.E.: The hidden number problem with the trace and bit security of XTR and LUC. In Proc. Crypto'02, LNCS, Vol. 2442 (2002) 433-448

[9] Micali, S., Bellare, M.: Non-interactive oblivious transfer and applications. In Proc. CRYPTO'89, (1989) 547-557

[10] Okamoto, T.: Encryption and authentication schemes based on public key systems. PhD thesis, Univ. of Tokyo, 1988

[11] Shparlinski, I.E.: On the generalized hidden number problem and bit security of XTR. In Proc. AAECC-14, LNCS, Vol. 2227 (2001) 268-277

[12] Stinson, D.R.: Cryptography:Theory and practice. CRC Press, Boca Raton, FL, 1995

Funding

President's Foundation of Graduate University of CAS(yzjj2003010)