1 Introduction↩︎

The discrete logarithm problem in a finite prime field is an important computing problem in modern cryptography. In 1976, Diffie and Hellman built the first key exchange protocol on the discrete logarithm problem [1]. After that, massive cryptography schemes based their security on the hardness of solving the discrete logarithm problem in a finite prime field such as public-key encryption schemes [2], [3], digital signature schemes [4], deniable authenticated encryption schemes [5], and so on.

Several algorithms have been proposed to solve the discrete logarithm problem, including the baby-step giant-step algorithm [6], the PohligHellman algorithm [7], the rho together with kangaroo algorithm [8], and index calculus algorithm (which first appeared in [9]–[11], and which was rediscovered and analyzed by [8], [12], [13]). The index calculus algorithm is the state-of-the-art algorithm to solve the discrete logarithm problem in the finite prime field [14], [15].

The index calculus algorithm comprises two phases. In the first phase, discrete logarithms of all primes in factor base (which consists of all primes smaller than a bound named smoothness bound) are calculated. Specifically, assume that the target discrete logarithm problem is to find \(x\) such that \(g^x \mod p \equiv b\), where \(p\) is a large prime (the order of finite prime field) and \(g\) is the multiplication generator of field. Discrete logarithms of all primes in factor base are calculated by the equations system (2 ). To construct the equations system (2 ), massive integers are randomly generated to find \(n\;(n>k)\) integers \(t_i\;(1\leq i\leq n)\) such that \[g^{t_i} \mod p \equiv b_i = p_1^{e_1^i}p_2^{e_2^i}\dots p_k^{e_k^i} \label{equ95951},\tag{1}\] where \(p_1,p_2,\dots,p_m\) are all primes in factor base and also are all primes smaller than smoothness bound. The integer satisfying the equation (1 ) is named smooth integer. For example, \(b_i\) is \(p_k\)-smooth. \[\begin{cases} t_1 \equiv e_1^1\log_gp_1 + e_2^1\log_gp_2 \dots e_k^1\log_gp_k \mod p-1 \label{equ952}\\ \;\;\;\;\;\vdots \\ t_i \equiv e_1^i\log_gp_1 + e_2^i\log_gp_2 \dots e_k^i\log_gp_k \mod p-1 \\ \;\;\;\;\;\vdots \\ t_n \equiv e_1^n\log_gp_1 + e_2^n\log_gp_2 \dots e_k^n\log_gp_k \mod p-1\\ \end{cases}\tag{2}\] Here, \(\log_gp_i\;(1\leq i\leq k)\) represents the discrete logarithm of prime \(p_i\) base \(g\) modulo \(p\). In the second phase, the discrete logarithm of the given integer \(b\) is calculated by finding another random integer \(t\) such that \(bg^t \mod p \equiv p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}\). Specifically, the target discrete logarithm is calculated by the following equation (3 ), namely \[\begin{align} \log_gb &\equiv& e_1\log_gp_1+ e_2\log_gp_2 \nonumber \\ &+&\cdots e_k\log_gp_k-t \mod p-1. \label{equ953} \end{align}\tag{3}\]

Continuous efforts are dedicated to improving the index calculus algorithm and many variants of index calculus algorithm are proposed. The number field sieve [16] and the function field sieve [17] are famous variants of the index calculus algorithm and they are both sub-exponential time algorithms for solving the discrete logarithm problem in a finite prime field. Sieve methods improve the index calculus algorithm a lot because sieve methods can find random integers \(t_1\), \(t_2\), \(\cdots\), \(t_n\), \(t\) mentioned above much faster. In brief, the all famous successful variants of index calculus algorithm achieve faster solving discrete logarithm problem by constructing methods to find \(t_1\), \(t_2\), \(\cdots\), \(t_n\), \(t\) mentioned above faster.

In this paper, we speed up solving the discrete logarithm problem in a different and challenging way: reduce the number of discrete logarithms which must be obtained before the target discrete logarithm problem could be solved. In particular, to solve the target discrete logarithm problem, index calculus algorithm together with its all famous successful variants has to calculated \(k+1\) discrete logarithms (namely, \(\log_gp_1\), \(\log_gp_2\), \(\dots\), \(\log_gp_k\), \(\log_gb\)), where \(k\) is the number of primes in factor base. We construct an algorithm which can solve the target discrete logarithm problem, and the number of discrete logarithms our algorithm needs to obtain before solving the target discrete logarithm problem could be less than \(k+1\). Due to the decrease in the number of discrete logarithms that need to be obtained before solving the target discrete logarithm, our algorithm can solve the discrete logarithm problem much faster.

1.1 Our Contribution↩︎

We make a theoretical breakthrough. Specifically, in the index calculus algorithm as well as its all variants, the target discrete logarithm problem can be successfully solved under the condition that at least \(k+1\) discrete logarithms have to be found together. Here, \(k\) is the number of primes in factor base. However, the double index calculus algorithm proposed in this paper could solve the target discrete logarithm problem when the number of discrete logarithms obtained is less than \(k+1\). Due to the decrease in the number of discrete logarithms that have to be obtained, calculation speed of our algorithm increase a lot.

1.2 Advantages of Our Algorithm↩︎

Our algorithm has three advantages, namely fast calculation speed, high generality, and compatibility with tricks which other variants of index calculus algorithm utilize to speed up finding smooth integers (namely, integers satisfying equation (1 )).

First, our algorithm outperforms the state-of-the-art index calculus algorithm significantly in computing speed when solving the discrete logarithm problem in a finite prime field. We compare our algorithm with the index calculus algorithm theoretically in TABLE 3 and prove that our algorithm is faster. Through empirical experiments, we observe that our algorithm achieves a speed advantage exceeding 30 times (75426/2211\(\approx\)​34, these data are referenced in TABLE 4 ) in some cases over the fastest index calculus algorithm when the bit length of the order of prime field is relatively large 70 bits. Empirical experiment results also imply that our algorithm may be faster than the fastest index calculus algorithm more than 30 times as the bit length continues to increase from 70 bits.

Our algorithm is more general than the index calculus algorithm. Specifically, when the base of the discrete logarithm problem is not the multiplication generator of the finite prime field, the discrete logarithms of some primes in factor base may not exist, which may cause the index calculus algorithm to fail. However, our algorithm still can work even if the discrete logarithms of some primes do not exist. Thus, our algorithm is more general in terms of whether or not the base of the discrete logarithm problem needs to be a multiplication generator.

Our algorithm also can utilize tricks of speeding up finding smooth integers to speed up solving the discrete logarithm problem further. In particular, our algorithm can utilize all tricks (which speed up solving the discrete logarithm problem by speeding up finding smooth integer first) of other variants of index calculus algorithm to find smooth integers first. And then, the tricks constructed in this paper can be utilized to reduce the number of needed smooth integers further. This advantage makes our algorithm faster than the index calculus algorithm together with its all famous variants.

1.3 Technical Overview↩︎

New way solving discrete logarithm problem. Each different algorithm to solve the discrete logarithm problem builds its own unique equation related to the target discrete logarithm problem and the target discrete logarithm is obtained by the build equation. For example, the index calculus algorithm utilizes the equation (4 ), namely \[\begin{align} \log_gb &\equiv& e_1\log_gp_1+e_2\log_gp_2 \nonumber \\ &+& \cdots e_k\log_gp_k-t \mod p-1, \label{add95equ954} \end{align}\tag{4}\] to calculate the target discrete logarithm after the discrete logarithms of all primes in factor base are obtained. In the baby step giant step algorithm, the target discrete logarithm is obtained by fining \(a_1\), \(a_2\), and \(a_3\) such that \[(g^{a_1})^{a_2} \mod p \equiv bg^{a_3} \mod p\] when the target discrete logarithm problem is to find \(x\) such that \(g^x\mod p \equiv b\). In this paper, we utilize a new equations system to calculate the target discrete logarithm. Specifically, find \(\alpha\), \(\beta\), and \(\gamma\) such that \[\begin{cases} g^\alpha\mod p \equiv \gamma \\ b^\beta\mod p \equiv \gamma. \label{new95equ956} \end{cases}\tag{5}\] The target discrete logarithm is calculated by the equation (6 ) \[x \equiv \alpha\beta^{-1} \mod (p-1). \label{add95equation955}\tag{6}\]

The way finding needed integers. The key to success of our algorithm is to find \(\alpha\), \(\beta\), and \(\gamma\) in the equations system (5 ). Instead of fixing \(\gamma\) first, we build two equations systems to calculate discrete logarithms base \(g\) and \(b\), respectively. And then, identify the integer \(\gamma\) whose discrete logarithms base \(g\) and base \(b\) are both obtained. In particular, a series of random integers is generated to find \(t_i\) \((i=1, 2,\cdots, i, \cdots)\) such that \(g^{t_i}\mod p \equiv p_1^{e_1^i}p_2^{e_2^i}\dots p_k^{e_k^i}\), where \(p_1\), \(p_2\), \(\cdots\), \(p_k\) are primes in factor base. By solving equations system \[\begin{cases} t_1 \equiv e_1^1\log_gp_1 + e_2^1\log_gp_2 \cdots e_k^1\log_gp_k \mod p-1 \\ \;\;\;\; \vdots \\ t_i \equiv e_1^i\log_gp_1 + e_2^i\log_gp_2 \cdots e_k^i\log_gp_k \mod p-1, \label{equ9555} \end{cases}\tag{7}\] discrete logarithms of some primes could be obtained although not discrete logarithms of all primes in factor base are obtained when \(i\) is less than the number of primes in factor base. Similarly, by building the equations system \[\begin{cases} \bar{t}_1 \equiv \bar{e}_1^1\log_bp_1 + \bar{e}_2^1\log_bp_2 + \dots \bar{e}_k^1\log_bp_k\mod p-1 \\ \;\;\;\; \vdots \\ \bar{t}_j \equiv \bar{e}_1^j\log_bp_1 + \bar{e}_2^j\log_bp_2 + \dots \bar{e}_k^j\log_bp_k\mod p-1, \label{equ956} \end{cases}\tag{8}\] discrete logarithms of some primes base \(b\) could be obtained although not discrete logarithms of all primes in factor base are obtained. By comparing solutions of two equations systems, the prime whose discrete logarithms base \(g\) and \(b\) are both obtained can be identified.

Decrease the number of discrete logarithms needed. The key to speed up solving the target discrete logarithm problem is to reduce the total number of needed discrete logarithms to solve the target discrete logarithm. To solve the target discrete logarithm problem, the index calculus algorithm has to obtain \(k+1\) discrete logarithms of primes in factor base. Our algorithm can solve the target discrete logarithm problem through less than \(k+1\) discrete logarithms of primes in factor base.

In particular, the index calculus algorithm has to obtain discrete logarithms of all primes in factor base before it solves the target discrete logarithm problem. Thus, index calculus algorithm must calculate \(k+1\) discrete logarithms in total. Our algorithm can solve the target discrete logarithm problem when discrete logarithms of some primes not all primes in factor base are obtained. For example, as long as \(\log_gp_1\) and \(\log_bp_1\) are both obtained the target discrete logarithm problem can be solved. In this extremely nice case, only two discrete logarithms are needed to solve the target discrete logarithm problem through our algorithm.

In our algorithm, one nice case happens with an extremely small probability but the number of nice cases is extremely massive, resulting in that the total probability that nice cases happen is large. Here, the nice case is the case where the target discrete logarithm can be obtained through less than \(k+1\) discrete logarithms of primes in factor base. \(k\) is the number of primes in factor base. Specifically, when only one prime’s two discrete logarithms are calculated through the equations systems (7 ) and (8 ) respectively, the number of nice cases is \(k\). These cases are \(\{\log_gp_i,\log_bp_i\} (1\leq i\leq k)\). When two primes’ discrete logarithms are calculated through the equations systems (7 ) and (8 ) respectively, the number of nice cases is \(k(k+1)^2\). These cases are \(\{\log_gp_j\), \(\log_gp_i\), \(\log_bp_i\), \(\log_bp_m\}\) \((1\leq j,i,m \leq k)\). Roughly speaking, the number of nice cases are \[\begin{align} \sum_{\{1\leq i \leq k, 1\leq j,m\leq k-i \}}C_k^iC_{k-i}^jC_{k-i}^{m}, \label{equ957} \end{align}\tag{9}\] where \(k\) is the number of primes in factor base. The number represented by formula (9 ) is an extremely massive number, resulting in that nice cases happen with a large probability in total although each nice case happens with a small probability. In other words, our algorithm can solve the target discrete logarithm problem with a big probability through calculating less than \(k+1\) discrete logarithms of primes in factor. That is, our algorithm can solve the discrete logarithm problem faster than index calculus algorithm which is the fastest algorithm to solve the discrete logarithm problem.

2 Preliminaries↩︎

In this section, preliminaries are introduced, including the definition of discrete logarithm problem and the concept of smooth integer. At the last, the notations used in this paper are summarized in a table.

2.1 Discrete Logarithm Problem↩︎

The discrete logarithm problem in the finite prime field holds significant importance in modern cryptography. Numerous cryptographic schemes rely on the assumption that solving the discrete logarithm problem in the finite prime field is computationally difficult. The definition of the discrete logarithm problem is as follows:

Discrete logarithm problem: In a finite prime field with \(p\) elements, for given integers \(b\) and \(g\), find the smallest non-negative integer \(x\) such that \(g^{x} \equiv b \mod p\), where \(p\) usually is a large prime integer.

2.2 smooth Integer↩︎

The smooth integer is an important concept in cryptography and it relies on factorization of integers. The definition of smooth integer is as follows:

B-smooth integer: An integer is \(B\)-smooth if its all prime factors are less than or equal to \(B\).

For example, 77=7*11 is an 11-smooth integer. Main notations used in this paper are summarized in TABLE 1.

3 membership reference attacks method↩︎

In this section, the main content is about how to perform membership reference attacks against Laplace mechanism. An introduction of idea is given before the detailed information of membership reference attacks method is given. Some notations are introduced for simplicity of description. Attackers want to judge whether a record \(x\) is in data set D. The background knowledge of attackers is denoted by \(D_{know}\) which is a subset of data set \(D\), namely \(D_{know} \subset D\) and attackers can issue query \(q_s(D)\) to Laplace mechanism \(M\), denoted by \(M(q_s,D,\epsilon)\). The \(q_s(D)\) means computing query \(q\) over records of data set \(D\) under conditions \(s\). In other words, the \(q_s(D)\) is equal to \(q(D\cap D_s)\) where the \(D_s\) is the set which satisfies conditions \(s\). For example "count the number of students whose age is greater than 10 in classroom". The query \(q\) is counting query, the data set \(D\) is the set of all the students in classroom and the condition \(s\) is that "age is greater than 10".

The membership reference attacks method consists of two subroutines. The first subroutine is to obtain multiple i.i.d. samples for linear query’s answer. The first subroutine is feasible because of the linear property of linear queries and the detailed reasons are given later. By the first subroutine, attackers can obtain \(m\) i.i.d. samples of \(M(q_s,D,\epsilon)\) where \(D_s=D_{know} \cup \{x\}\). When the \(x\) is in data set \(D\), \[\begin{align} q_s(D) &=& q(D_s\cap D) \\ &=& q((D_{know}\cup\{x\})\cap D)\\ &=& q(D_{know}\cup\{x\}) \end{align}\]

So the mean of output distribution of \(M(q_s,D,\epsilon)\) is \(q(D_{know}\cup\{x\})\).

When the \(x\) is not in data set \(D\) \[\begin{align} q_s(D) &=& q(D_s\cap D) \\ &=& q((D_{know}\cup\{x\})\cap D)\\ &=& q(D_{know}) \end{align}\]

So the mean of output distribution of \(M(q_s,D,\epsilon)\) is \(q(D_{know})\).

Attackers can judge whether the \(x\) is in the data set \(D\) by comparing \(q(D_{know})\) and the mean of \(M(q_s,D,\epsilon)\). The procedure of comparison is implemented by hypotheses test denoted by \(H\) in the second subroutine.

In the second subroutine, hypothesis test \(H\) is to judge whether the samples \(\hat{a}_1,\hat{a}_2,\dots,\hat{a}_m\) are drawn from a distribution with mean \(q(D_{know})\). When mean of distribution from which \(\hat{a}_1,\hat{a}_2,\dots,\hat{a}_m\) are drawn is judged to be \(q(D_{know})\), the assertion is that \(x\) is not in data set \(D\). Otherwise, the assertion is that \(x\) is in data set \(D\). Next, the detailed information of the two subroutine is given.

3.1 Multiple Independent Identical Distribution Samples for Linear Query’s Answer↩︎

The goal is to obtain multiple i.i.d. samples for linear query’s answers and these samples are used in hypothesis test in the second subroutine. We will introduce used notations first.

The \(x\) presents a record and we want to confirm whether \(x\) is in the data set \(D\). Query \(q\) is linear query and \(m\) i.i.d. samples for \(M(q_{s},D,\epsilon)\)’s answer are denoted by \(\hat{a}_1,\hat{a}_2,\dots,\hat{a}_m\) where \(s\) represents query condition such that \(D_s = D_{know}\cup\{x\}\).

The attackers randomly choose a data set \(D_i\) such that \(D_i \subset D_{know}\), construct query conditions \(s_i\) such that \(D_{s_i} = D_i\cup \{x\}\) where \(D_{s_i}\) is a set whose elements satisfy requirements of conditions \(s_i\), submit query \(q_{s_i}(D)\) to Laplace mechanism and obtain \(a_i = M(q_{s_i},D,\epsilon)\) as return. Let \(\hat{a}_i = q(D_{know}\setminus D_i) + a_i\). The data set \(D_i\) is a subset of \(D_{know}\) and the \(D_{know}\) is background knowledge of attackers so that the attacker can compute \(q(D_{know}\setminus D_i)\) locally by himself. The \(\hat{a}_i\) is an i.i.d. sample of \(M(q_{s},D,\epsilon)\).

Through another subset \(D_j\) such that \(D_j \subset D_{know}\), attackers can get the second sample of \(M(q_s,D,\epsilon)\)’s answer. So, the attackers can get \(m\) samples \(\hat{a}_1,\hat{a}_2,\dots,\hat{a}_m\) for query \(M(q_s,D,\epsilon)\) as above.

Theorem 1: \(\hat{a}_1,\hat{a}_2,\dots,\hat{a}_m\) are samples of \(M(q_{s},D,\epsilon)\).

Proof:

For \(\forall i\), we have \[\begin{align} \hat{a}_i &=& q(D_{know}\setminus D_i) + a_i \\ \hat{a}_i &=& q(D_{know}\setminus D_i) + M(q_{s_i},D,\epsilon) \\ \hat{a}_i &=& q(D_{know}\setminus D_i) + q_{s_i}(D) + Lap(0,\frac{\Delta D}{\epsilon})\\ \end{align}\]

We know that \(q_{s_i}(D) = q((D_i\cup \{x\})\cap D)\). The \((D_i\cup \{x\})\cap D\) is a subset of \(D_i\cup \{x\}\). And the \(D_i\cup \{x\}\) and \(D_{know}\setminus D_i\) are disjoint. So, the \((D_i\cup \{x\})\cap D\) and \(D_{know}\setminus D_i\) are disjoint. In addition, \(q\) is linear query. We have

\[\begin{align} & & q(D_{know}\setminus D_i) + q_{s_i}(D)\\ &=& q(D_{know}\setminus D_i) + q((D_i\cup \{x\})\cap D) \\ &=& q(D_u ) \\ \end{align}\]

Here \(D_u\) is union set of \(D_{know}\setminus D_i\) and \((D_i\cup \{x\})\cap D\). \[\begin{align} D_u &=& (D_{know}\setminus D_i) \cup ((D_i\cup \{x\})\cap D) \\ D_u &=& ((D_{know}\setminus D_i)\cap D) \cup ((D_i\cup \{x\})\cap D) \\ D_u &=& ((D_{know}\setminus D_i) \cup (D_i\cup \{x\}))\cap D) \\ D_u &=& (D_{know} \cup \{x\})\cap D) \\ \end{align}\]

So, we have \[\begin{align} q(D_u ) &=& q((D_{know} \cup \{x\})\cap D ) \\ q(D_u ) &=& q_s(D) \\ \end{align}\]

So, we have \[\begin{align} \hat{a}_i &=& q(D_{know}\setminus D_i) + q_{s_i}(D) + Lap(0,\frac{\Delta D}{\epsilon})\\ \hat{a}_i &=& q_s(D) + Lap(0,\frac{\Delta D}{\epsilon}) \;\;\;\;\;\;\;\;(1)\\ \hat{a}_i &=& M(q_s,D,\epsilon) \end{align}\] \(\hfill\Box\)

Theorem 2: \(\hat{a}_1,\hat{a}_2,\dots,\hat{a}_m\) are i.i.d. samples of \(M(q_{s},D,\epsilon)\).

Proof:

According to the equality (1) in proof of theorem 1, for \(\hat{a}_i\) we know \[\begin{align} \hat{a}_i &=& q_s(D) + Lap(0,\frac{\Delta D}{\epsilon}) \\ \end{align}\]

For all \(\hat{a}_1,\hat{a}_2,\dots,\hat{a}_m\), the noise \(Lap(0,\frac{\Delta D}{\epsilon})\) are i.i.d. samples of Laplace distribution so \(\hat{a}_1,\hat{a}_2,\dots,\hat{a}_m\) are i.i.d. samples. \(\hfill \Box\)

Theorem 3: The number of records in \(D_{know}\) needs to be greater than \(\log_2m\).

Proof:

As known before, a subset of \(D_{know}\) can generate an i.i.d. sample for query’s answer and the number of i.i.d. samples is denoted by \(m\). So, the number of records in \(D_{know}\) should guarantee that subset of \(D_{know}\) is equal to or greater than \(m\). The set of subset of \(D_{know}\) is called power set denoted by \(PA\) and the number of records in \(D_{know}\) is denoted by \(r\). We have, \[\begin{align} m &\le& |PA| \\ &\le& 2^{|D_{know}|} \\ &\le& 2^r \end{align}\]

Here, the \(|\;|\) presents the number of element for a set. We have \[\begin{align} r \ge \log_2m \end{align}\] \(\hfill\Box\)

The number \(m\) is small so the number \(r\) is smaller. As mentioned in the first paragraph of this subsection, the \(m\) i.i.d. samples are used in hypothesis test. Usually, the number of samples is small in hypothesis test. For example dozens of numbers are enough. So, the \(r\) can be small. For example, when \(m=1000\), the \(r\) could be 10.

Theorem 4: The totally consumed privacy budget of queries \(q_{S_1},q_{S_2},q_{S_3},\dots,q_{S_m}\) is \(\epsilon_t\).

Proof

For \(\forall i\), the consumed privacy budget of \(M(q_{S_i},D,\epsilon)\) is \(\epsilon\) and the \(\epsilon = \frac{\epsilon_t}{m}\). According to the Sequential Composition Theorem, the totally consumed privacy budget is equal to \[\begin{align} \sum_{i=1}^{m}\epsilon = \sum_{i=1}^{m}\frac{\epsilon_t}{m} = \epsilon_t \end{align}\] \(\hfill\Box\)

In a word, the proposed method in this subsection obtains \(m\) i.i.d. samples for a query with privacy budget \(\epsilon_t\).

3.2 Hypothesis Test↩︎

In this subsection, the goal is to determine whether a record \(x\) is in data set \(D\) through hypothesis test. The key is to find an appropriate statistics. That is, it is key to find an appropriate hypothesis test method. The one-sample t-test is chosen. The \(T\) statistics follows \(T\) distribution and the \(T\) statistics is as follows \[\begin{align} T &=& \frac{\bar{X} - \mu}{\frac{S}{\sqrt{m-1}}} \\ \end{align}\]

Next, we explain the process of reaching conclusion. Firstly, calculate the \(T\) statistics as above. Then according to the freedom \(m-1\), distribution of \(T\) statistics can be identified. Generally, there is a table related to \(T\) distribution. With value of \(T\) statistics and freedom \(m-1\), the \(p\) value can be found in the table which is step 5 of hypothesis test above. If the \(p\) value is less than significance level \(\alpha\), the alternative hypothesis is accepted, which means that samples \(\hat{a}_1,\hat{a}_2,\dots,\hat{a}_m\) don’t come from a distribution with mean \(\mu = q(D_{know})\). So, \(x\) is in data set \(D\). Otherwise, the \(x\) is not in data set \(D\).

The significance level \(\alpha\) is 0.05. There are two widely accepted choices for significance level, namely \(\alpha =0.01\) and \(\alpha = 0.05\). We desire that as long as difference is statistically significant, the alternative hypothesis could be accepted. So \(\alpha =0.05\) is chosen.

The one-sample t-test is the appropriate hypothesis test method because the one-sample t-test is used to judge whether some samples are drawn from a distribution with certain mean. The samples \(\hat{a}_1,\hat{a}_2,\dots,\hat{a}_m\) are \(m\) independent identical distribution samples of \(M(q_s,D,\epsilon)\). The distribution of \(M(q_s,D,\epsilon)\) is a Laplace distribution with mean \(q_s(D)\). And we know \[\begin{align} q_s(D) = q(D_s\cap D) = q((D_{know}\cup\{x\})\cap D) \end{align}\]

And \[\begin{align} D_{know} \subset D \end{align}\]

So, if \(x\) is in \(D\), \[\begin{align} q_s(D) = q(D_{know}\cup\{x\}) \end{align}\]

And if \(x\) is not in \(D\), \[\begin{align} q_s(D) = q(D_{know}) \end{align}\]

In other words, when \(x\) is not in \(D\), the mean of Laplace distribution \(M(q_s,D,\epsilon)\) is \(q(D_{know})\). When \(x\) is in \(D\), the mean of Laplace distribution \(M(q_s,D,\epsilon)\) is \(q(D_{know}\cup\{x\})\). So, if the samples \(\hat{a}_1,\hat{a}_2,\dots,\hat{a}_m\) are from distribution with mean \(q(D_{know})\), \(x\) is not in \(D\). This is the reason why the one-sample t-test is chosen to judge whether samples \(\hat{a}_1,\hat{a}_2,\dots,\hat{a}_m\) come from distribution with mean \(\mu = q(D_{know})\).

3.3 Accuracy analysis↩︎

The hypothesis test has two types error shown in Table 1.

Theorem 5 The success rate \(R\) of membership reference attacks is approximately equal to \(\frac{1}{2}(0.95+\int_{-\infty}^{\frac{S\epsilon_t T_{(m-1,0.05)}}{\sqrt{2}m\sqrt{m-1}}} \frac{1}{2\pi}e^{-\frac{t^2}{2}} dt)\).

Proof

According the Table 1, we have \[\begin{align} R&=&\frac{(1-\alpha)+(1-\delta)}{(1-\alpha) + \delta + \alpha + (1-\delta)} \\ &=& \frac{1}{2}(2-\alpha-\delta)\\ &=& \frac{1}{2}(1.95-\delta)\\ \end{align}\]

For the definition of one-sample T test, we have

\[\begin{align} & & \alpha \\ &=& P\{accetp\;H_1|H_0\;is\;ture\} \\ &=& P\{ \frac{\bar{X} - \mu_0}{\frac{S}{\sqrt{m-1}}}<T^*|H_0\;is\;ture \} \\ &=& 0.05 \end{align}\]

The \(\frac{\bar{X} - \mu_0}{\frac{S}{\sqrt{m-1}}}\) approximately obeys \(T\) distribution. So, the \(T^*\approx T_{(m-1,0.05)}\).

\[\begin{align} & & \delta \\ &=& P\{accetp\;H_0|H_1\;is\;ture\} \\ &=& P\{ \frac{\bar{X} - \mu_1}{\frac{S}{\sqrt{m-1}}}>T^*|H_1\;is\;ture \} \end{align}\]

The variance of noise distribution (namely Laplace distribution) is \(\sigma =\sqrt{2} \frac{\Delta D}{\epsilon} = \frac{\sqrt{2} }{\epsilon}\). So, we have \[\begin{align} & & \delta \\ &=& P\{ \frac{\bar{X} - \mu_1}{\sigma}>\frac{S\;T^*}{\sigma\sqrt{m-1}}|H_1\;is\;ture \} \\ \end{align}\]

The \(\frac{\bar{X} - \mu_1}{\sigma}\) approximately obeys \(N(0,1)\), So

\[\begin{align} & & P\{ \frac{\bar{X} - \mu_1}{\sigma}>\frac{S\;T^*}{\sigma\sqrt{m-1}}|H_1\;is\;ture \} \\ &\approx& \int_{\frac{S\;T^*}{\sigma\sqrt{m-1}}}^{+\infty} \frac{1}{2\pi}e^{-\frac{t^2}{2}} dt \\ &=& 1- \int_{-\infty}^{\frac{S\;T^*}{\sigma\sqrt{m-1}}} \frac{1}{2\pi}e^{-\frac{t^2}{2}} dt \\ \end{align}\]

So, \[\begin{align} & & R \\ &\approx&\frac{1}{2}(0.95+\int_{-\infty}^{\frac{S T_{(m-1,0.05)}}{\sigma\sqrt{m-1}}} \frac{1}{2\pi}e^{-\frac{t^2}{2}} dt) \\ &=& \frac{1}{2}(0.95+\int_{-\infty}^{\frac{S\epsilon T_{(m-1,0.05)}}{\sqrt{2}\sqrt{m-1}}} \frac{1}{2\pi}e^{-\frac{t^2}{2}} dt) \\ &=& \frac{1}{2}(0.95+\int_{-\infty}^{\frac{S\epsilon_t T_{(m-1,0.05)}}{\sqrt{2}m\sqrt{m-1}}} \frac{1}{2\pi}e^{-\frac{t^2}{2}} dt) \\ \end{align}\]

3.4 Correctness↩︎

In this subsection, we prove that our algorithm can output the target discrete logarithm first. And then, in the next subsection we compare our algorithm with the index calculus algorithm in terms of time complexity.

Theorem 1: For the finite prime field formed by modulo a large prime \(p\) with multiplication generator \(g\) and any given number \(b\), the double index calculus algorithm can find \(x\) such that \(g^x \mod p \equiv b\).

proof: Steps from 6 to 14 in the double index calculus algorithm obtain the vector \(X_g\) and matrix \(M_g\). Assume that there are \(i\) components in vector \(X_g\) and \(i\) rows in matrix \(M_g\). We add subscripts to distinguish different components in \(X_g\) and superscripts to distinguish different rows in \(M_g\). Then, we have \[\begin{align} X_g = \left[ \begin{array}{c} t_1 \\ t_2 \\ \vdots \\ t_i\\ \end{array} \right] {\rm and} \; M_g = \left[ \begin{array}{cccc} e_1^1 & e_2^1 & \cdots & e_k^1 \\ e_1^2 & e_2^2 & \cdots & e_k^2 \\ \vdots & \vdots& \ddots &\vdots \\ e_1^i & e_2^i & \cdots & e_k^i \\ \end{array} \right]. \end{align}\] We know that \(\forall i\) the equation \(g^{t_i} \mod p \equiv p_1^{e_1^i}p_2^{e_2^i}\cdots p_k^{e_k^i}\) holds. Therefore, we have the following equations system \[\begin{align} X_g = M_g \left[ \begin{array}{c} \log_gp_1 \\ \log_gp_2 \\ \vdots \\ \log_gp_k\\ \end{array} \right] \mod p-1 \label{equation95system9520}. \end{align}\tag{10}\] When the rank of \(M_g\) is smaller than \(k\), discrete logarithms of some primes in factor base may be obtained while discrete logarithms of the rest primes in factor base may not be obtained through equations system (10 ). As \(i\) increases, the rank of \(M_g\) becomes larger and will exceed \(k\). Discrete logarithms of all primes in factor base can be calculated through the equations system (10 ) when the rank of \(M_g\) becomes \(k\). Thus, we can get \[\begin{align} L_g = \left[ \begin{array}{c} \log_gp_1 \\ \log_gp_2 \\ \vdots \\ \log_gp_k\\ \end{array} \right]. \end{align}\]

Notably, when computing \(L_g\), it is likely to encounter non-invertible elements. For example, 2 is never invertible because \(p-1\) is even. Whenever this happens we can use a greatest common divisor algorithm to obtain a non-trivial factorization \(p-1 = \hat{p}_1\hat{p}_2\) with \(\hat{p}_1\) and \(\hat{p}_2\) relatively prime. Then, we process to work in \(Z_{\hat{p}_1} \times Z_{\hat{p}_2}\), and use Chinese Remainder Theorem to get the target value [18].

Similarly, we get \(L_b\) through steps from 15 to 23. \[\begin{align} L_b = \left[ \begin{array}{c} \log_bp_1 \\ \log_bp_2 \\ \vdots \\ \log_bp_k\\ \end{array} \right] \end{align}\]

Let \(\alpha \in L_g\) and \(\bar{p}\in \Omega\) such that \(g^\alpha \mod p \equiv \bar{p}\). Let \(\beta \in L_b\) such that \(b^\beta \mod p \equiv \bar{p}\). Then, we have \[\begin{align} g^\alpha \mod p \equiv \bar{p} \equiv b^\beta \mod p . \end{align}\] Therefore, \[\begin{align} g^\alpha \mod p \equiv \bar{p} \equiv g^{x\beta} \mod p. \end{align}\] Thus, the target discrete logarithm \(x\) is \[\begin{align} x \equiv \alpha\beta^{-1 } \mod (p-1). \end{align}\]

\(\hfill\Box\)

3.5 Time Complexity↩︎

Above, the correctness of the proposed double index calculus algorithm is proved. Next, the proposed algorithm is compared with the state-of-the-art index calculus algorithm in terms of time complexity.

In both index calculus algorithm and double index calculus algorithm, equations systems are constructed to compute discrete logarithms of primes in factor base, and then computing the target discrete logarithm is achieved through the obtained discrete logarithms. Assume that the time complexity of calculating discrete logarithm of one prime is the same in both algorithms, and the time complexity of the two algorithms can be compared with each other.

Theorem 2: The time complexity of double index calculus algorithm is lower than index calculus algorithm if calculating discrete logarithm of one prime is assumed to be the same.

Proof: Let \(T\) be the time complexity of calculating discrete logarithm of one prime. Assume that there are \(k\) primes in factor base, and the target discrete logarithm problem is to find \(x\) such that \(g^x \mod p \equiv b\), where \(p\) is a large prime (the order of finite prime field) and \(g\) is a multiplication generator of field.

In the index calculus algorithm, discrete logarithms of \(k\) primes are calculated by constructing equations system in the first phase and the target discrete logarithm is calculated by constructing an equation in the second phase. Therefore, the time complexity of index calculus algorithm is \((k+1)T\) in total.

In the double index calculus algorithm, discrete logarithms base \(g\) and base \(b\) are calculated by constructing two equations systems, and the target discrete logarithm problem is solved under the condition that discrete logarithms of one prime base \(g\) and base \(b\) are both obtained. Assume that \(i\) discrete logarithms base \(g\) are obtained and \(j\) discrete logarithms base \(b\) are obtained. Because there are \(k\) different primes in factor base, according to pigeon-hole principle, the discrete logarithms base \(g\) and base \(b\) of at least one prime are obtained when \(i+j=k+1\). Therefore, the time complexity of double index calculus algorithm is smaller than \((k+1)T\). In other words, the time complexity of double index calculus algorithm is lower than that of index calculus algorithm.

\(\hfill\Box\)

In brief, the double index calculus algorithm reduces its time complexity by only computing discrete logarithms of some primes in the factor base instead of discrete logarithms of all primes in the factor base.

The index calculus algorithm needs to find discrete logarithms of all primes in the factor base in the first phase so that the target discrete logarithm can be obtained in the second phase. To that end, index calculus algorithm needs to calculate \(|\Omega|=k\) discrete logarithms of all primes in factor base. In addition, the second phase needs to calculate the target discrete logarithms. Thus, the index calculus algorithm needs \(k+1\) discrete logarithms in total.

Our algorithm only needs to calculate discrete logarithms of some primes in the factor base. Assume that our algorithm calculates \(i\) primes’ discrete logarithms base \(g\) and these primes are denoted by \(\Omega_g=\{ p_1,p_2,\cdots,p_i \}\). Our algorithm also calculates \(j\) primes’ discrete logarithms base \(b\) and these primes are denoted by \(\Omega_b=\{ \bar{p}_1,\bar{p}_2,\cdots,\bar{p}_j \}\). According to Algorithm \(\ref{dicm}\), the target discrete logarithm can be calculated if \(\Omega_g \cap \Omega_b \neq \emptyset\). For example, our algorithm can obtain the target discrete logarithm if \(\Omega_g = \{2,3\}\) and \(\Omega_b = \{2,5\}\). How many discrete logarithms of prime in factor base are needed to guarantee that our algorithm can obtain the target discrete logarithm in the worst case? We know \(\Omega_g \subseteq \Omega\), \(\Omega_b \subseteq \Omega\), and \(|\Omega|=k\). Thus, \(\Omega_g \cap \Omega_b \neq \emptyset\) as long as \(|\Omega_g|+|\Omega_b| \ge |\Omega|+1 = k+1\). That is, our algorithm at most needs to calculate \(k+1\) discrete logarithms of primes in factor base to obtain the target discrete logarithm. In other cases, the number of needed discrete logarithms of primes in factor base is less than \(k+1\).

To further reduce the running time of our algorithm, we introduce another trick: parallel computing. Specifically, computing discrete logarithms of primes base \(g\) and computing discrete logarithms of primes base \(b\) are independent of each other. Thus, these two computing processes can be performed simultaneously. The running time of our algorithm is the greater running time between the running time of computing discrete logarithms base \(g\) and the running time of computing discrete logarithms base \(b\), instead of the sum running time of them. The comparison of the index calculus algorithm and the double index calculus algorithm is demonstrated in Figure \(\ref{time95complexity}\) and the time complexity comparison is summarized in TABLE 3.

Notably, the time complexity of solving equations systems in step 13 and step 22 in our algorithm is polynomial. When the bit length of the order of finite prime field is large, the running time of solving equations systems is negligible so we do not take it into consideration in TABLE 3. Similarly, we do not take time of solving equations systems into consideration when analyzing time complexity of the index calculus algorithm in TABLE 3.

Notably, the target discrete logarithm can be obtained in our algorithm under the condition that both discrete logarithms base \(g\) and base \(b\) of one prime are obtained. The condition is satisfied with a high probability and we will prove this claim in the next Theorem 4.

Theorem 3: If \(u\) primes’ discrete logarithms base \(g\) and \(v\) primes’ discrete logarithms base \(b\) are obtained in the first phase, the double index calculus algorithm obtains the target discrete logarithm with the probability \[Pr_{(u,v)} > 1+ \frac{1}{2^{uv}} -\frac{1}{2^v} -\frac{1}{2^u}.\]

Proof: Assume that \(u\) primes whose discrete logarithms base \(g\) are obtained form the set \(\Omega_g = \{p_1, p_2, \cdots, p_u \}\), and \(v\) primes whose discrete logarithms base \(b\) are obtained form set \(\Omega_b = \{\bar{p}_1, \bar{p}_2, \cdots, \bar{p}_v\}\). As long as \(\Omega_g \cap \Omega_b \ne \emptyset\), the double index calculus algorithm can obtain the target discrete logarithm. We have \[\begin{align} Pr_{(u,v)} &=& Pr\{\Omega_g \cap \Omega_b \ne \emptyset\} \\ &=& Pr\{\Omega_g \cap \Omega_b =\{2\}, {\rm other\;cases}\} \\ &>& Pr\{\Omega_g \cap \Omega_b =\{2\}\}. \end{align}\]

The “other cases" refers to the cases where \(\Omega_g \cap \Omega_b \ne \emptyset\) while \(\Omega_g \cap \Omega_b \ne \{2\}\), for example \(\Omega_g \cap \Omega_b = \{3\}\), \(\Omega_g \cap \Omega_b = \{2, 3\}\), and so on. Whether 2 belongs to \(\Omega_g\) is independent of whether it belongs to \(\Omega_b\). Therefore, we have \[\begin{align} Pr_{(u,v)} &>& Pr\{\Omega_g \cap \Omega_b =\{2\}\} \\ &=& Pr\{2 \in \Omega_g\}Pr\{2 \in \Omega_b\}. \end{align}\]

To compute \(u\) prime integers’ discrete logarithms, at least \(u\) smooth integers are needed. Each found smooth integer is odd with probability \(1/2\). That is, each found smooth integer does not have factor 2 with probability \(1/2\). Thus, all found smooth integers do not have factor 2 with probability \(1/2^u\). Thus, \[\begin{align} Pr\{2 \notin \Omega_g\} \le \frac{1}{2^u}. \end{align}\] Similarly, we have \[\begin{align} Pr\{2 \notin \Omega_b\} \le \frac{1}{2^v}. \end{align}\] Therefore, \[\begin{align} & & Pr\{2 \in \Omega_g\}Pr\{2 \in \Omega_b\} \\ &=& (1-Pr\{2 \notin \Omega_b\} )(1-Pr\{2 \notin \Omega_g\} )\\ &\ge& 1+ \frac{1}{2^{uv}} -\frac{1}{2^v} -\frac{1}{2^u}. \end{align}\] Thus, we have \[\begin{align} Pr_{(u,v)} = Pr\{\Omega_g \cap \Omega_b \ne \emptyset\} > 1+ \frac{1}{2^{uv}} -\frac{1}{2^v} -\frac{1}{2^u}. \end{align}\]

\(\hfill\Box\)

The probability bound we obtain in Theorem 3 is large. For example, if \(u=v=5\), then the probability is \(1+ \frac{1}{2^{25}} -\frac{1}{2^5} -\frac{1}{2^5} \approx 0.94\).

4 Discussion↩︎

In this section, we compare our algorithm with the index calculus algorithm in terms of generality. Then, we discuss the differences together with connections between our algorithm and the variants of index calculus algorithm.

4.1 Generality Comparison↩︎

The index calculus algorithm has a minor limitation when it is directly used to solve the discrete logarithm problem in the case where the base of the discrete logarithm is not the multiplication generator. Specifically, the index calculus algorithm chooses a set of primes as its factor base and computes discrete logarithms of all chosen primes first. But, the discrete logarithms of some primes may not exist when the base of discrete logarithm is not the multiplication generator of the target finite prime field. For example, find \(x\) such that \(g^x \mod p \equiv b\) by the index calculus algorithm, when \(g=340003\), \(b=50064\), \(p=1040483\). If prime 2 is in the chosen factor base, then the index calculus algorithm can not work because the \(\log_p2\) does not exist in the given setting.

The key point is: the given \(g\) is not a multiplication generator in the given finite prime field so some primes’ discrete logarithms do not exist. In addition, there is no fast way to determine whether the discrete logarithm of a given prime exists or not. Thus, only choosing the prime with discrete logarithm into the factor base is difficult to achieve. In a word, if the given base \(g\) is not a multiplication generator of the given finite prime field, directly computing discrete logarithms of some integers by the index calculus algorithm may fail.

Our algorithm can work even if the given base \(g\) is not a multiplication generator of the given finite prime field. Our algorithm also chooses a set of primes as its factor base and computes discrete logarithms of chosen primes first. However, our algorithm does not require that discrete logarithms of all primes in the factor base exist. In the above example, the equation \(g^{321790} \mod p \equiv 3\) together with \(b^{400459}\mod p \equiv 3\) hold. Thus, our algorithm can find out \(x=6\) even if prime 2 is in the factor base as long as prime 3 is also in the factor base. The key point is: our algorithm only uses the discrete logarithms of one same prime. In a word, our algorithm only requires the existence of some primes’ discrete logarithms instead of the existence of all primes’ discrete logarithms.

In brief, in the case where discrete logarithms of some primes in the factor base do not exist, the index calculus algorithm may fail while our algorithm still can work. From the perspective of whether the base needs to be a multiplication generator of the target field, our algorithm is more general.

4.2 Differences↩︎

There are many variants of the index calculus algorithm. In this subsection, we discuss the key differences between our algorithm and these variant algorithms.

To make the exposition easier, we introduce a notation. Let \(Q=p^n\) and \(L_Q(a; c)\) with \(0 < a < 1\) and \(c > 0\) denote the sub-exponential expression \[\begin{align} L_Q(a; c) = e^{(c+o(1))(lnQ)^a(lnlnQ)^{1-a}}. \end{align}\] There are several cases for computing the discrete logarithm: \(a > 2/3\) is called the large characteristic case, \(a = 2/3\) is called the boundary case, \(1/3 \le a < 2/3\) is called the medium prime case while \(a < 1/3\) is called the small characteristic case.

The number field sieve [16] and the function field sieve [17] are two important variants of the index calculus algorithm and they are both sub-exponential time algorithms for solving the discrete logarithm problem in a finite prime field. Sieve methods improve the computing speed of index calculus algorithm a lot. Coppersmith [19] gave an estimation of time complexity of a sieve method when \(Q=p^n\) (here \(p\) is a prime integer) as follows \[\begin{align} e^{C(\log Q)^{1/3}(\log \log Q)^{2/3}}. \end{align}\] Where, the C varied slightly, depending on the distance from \(n\) to the nearest power of \(p\), and in the limit as \(n\rightarrow \infty\) it oscillated between two bounds [20]. To our best knowledge, the number field sieve is used for large characteristic cases while the function field sieve is used for the rest cases.

There is a lot of progress in the number field sieve method and the function field sieve method such as [21]–[25]. The reason why sieve methods can speed up solving the discrete logarithm problem is that they can obtain smooth integers faster. In particular, obtaining enough smooth integers to compute discrete logarithms of all primes in factor base is the most time-consuming part of the index calculus algorithm. Roughly speaking, the “enough" means the number of smooth integers needs to be more than the number of primes in the factor base. The sieve methods can reduce the time of obtaining one smooth integer so the whole time complexity of index calculus algorithm is reduced.

What sets our algorithm apart from the sieve methods is that: our algorithm reduces the whole time complexity of solving the discrete logarithm problem by reducing the number of discrete logarithms needed, which can be seen from TABLE 3. In particular, the number of needed discrete logarithms could be less than the number of primes in the factor base in our algorithm.

Another key difference between our algorithm and the sieve methods is that: the sieve methods work for special cases while our algorithm can work on all cases. Specifically, as mentioned before, the number field sieve is used for the large characteristic case while the function field sieve is used for the rest cases.

4.3 Connections↩︎

The connection between our algorithm and the sieve methods is that: our method can be combined with the sieve methods to improve the computing speed further. In particular, step 6 and step 16 in our algorithm is to find smooth integers. The sieve methods can replace these two steps so that the time complexity of our algorithm can be reduced further through finding smooth integers fast.

5 Experiments↩︎

To demonstrate the efficiency of our algorithm, we comprehensively compare our algorithm with the state-of-the-art and classical algorithms through extensive experiments.

The first experiment focuses on the influences of smoothness bound on the time complexity of our algorithm and the index calculus algorithm. In the index calculus algorithm, smoothness bound \(B\) significantly influences its computing speed because the smoothness bound \(B\) determines the size of factor base. As smoothness bound \(B\) increases, the factor base becomes larger, and the computation speed of index calculus algorithm increases first and then decreases. In previous work of Andrew [18], it is proved that the optimal value of \(B\) is \[e^{\sqrt{\frac{\log{p} \log{\log{p}}}{2} }}, \label{equ9522}\tag{11}\] here \(p\) is the order of finite prime field. That is, the index calculus algorithm achieves its maximal computation speed when \(B\) is set according to (11 ).

To explore the influences of smoothness bound on time complexity of algorithms, many random discrete logarithm problems are generated and then different smoothness bound is used to solve these discrete logarithm problems. In particular, the bits length of order of finite prime field is from 30 bits to 50 bits with step size 2 and the smoothness bound is set \(\{ 0.1B_i, 0.5B_i, 1B_i, 1.5B_i, 2B_i \}\) where \[\begin{align} B_i = e^{\sqrt{\frac{\log{p} \log{\log{p}}}{2} }}, \end{align}\] and \(p\) is the order of finite prime field. The average running time of solving these discrete logarithm problems are calculated and shown in Table [table95all].

According to the experiment results in Table [table95all], the average running time increases as the bits length increases in both our double index calculus algorithm and the index calculus algorithm. The experiment results also indicate that the running time decreases first and then increases as the smoothness bound increases for each bits length. When the smoothness bound is \[0.5e^{\sqrt{\frac{\log{p} \log{\log{p}}}{2} }},\] the average running time of all algorithms achieves the minimal value. To demonstrate the comparison among algorithms more clearly, the average running time of all algorithms with smoothness bound \(0.5e^{\sqrt{\frac{\log{p} \log{\log{p}}}{2} }}\) is shown in Figure 5.

According to the experiment results in Figure 5, our algorithm is much fast than the index calculus algorithm. In particular, our algorithm is about three times (\(29.6083/9.9497 \approx 3\)) faster than the index calculus algorithm.

In the second experiment, we compare our algorithm with other classic and state-of-the-art algorithms, including index calculus algorithm, baby step giant step algorithm, PohligHellman algorithm and Rho algorithm. The bits length of order of the finite prime field is from 30 bits to 50 bits with step size of 2. The smoothness bound is \(0.5e^{\sqrt{\frac{\log{p} \log{\log{p}}}{2} }}\). Many random discrete logarithm problems are generated and the average running times of solving these discrete logarithm problems are shown in Figure 6.

The experiment results in Figure 6 indicate that our algorithm is the most efficient algorithm to solve discrete logarithm problems. In particular, the running time of index calculus algorithm, baby step giant step algorithm, and PohligHellman algorithm are about 3 times, 7 times and 12 times that of our algorithms. The average running time of rho algorithm is far more than 20 times that of our algorithm.

The third experiment focuses on the minimum of average running time. According to the experiment results in the first experiment, the average running time may be minimal when the smoothness bound is \(0.5e^{\sqrt{\frac{\log{p} \log{\log{p}}}{2} }}\). To explore the minimum of the average running time, the smooth bounds are set to be \(0.25B_i\), \(0.30B_i\), \(0.35B_i\), \(0.40B_i\), \(0.45B_i\), \(0.50B_i\), \(0.55B_i\), \(0.60B_i\), \(0.65B_i\), \(0.70B_i\), where \(B_i = e^{\sqrt{\frac{\log{p} \log{\log{p}}}{2} }}\). The bit length is from 40 to 55 with step size 5. Many random discrete logarithm problems are generated and average running time of solving these discrete logarithm problems are shown in Fig 8.

The experiment results in Fig. 8 demonstrate obvious trends. First, the average running time decreases and then increases after a specific value as the smoothness bound increases from \(0.25B_i\) to \(0.75B_i\), where \(B_i=e^{\sqrt{\frac{\log{p} \log{\log{p}}}{2} }}\). For example, the average running time of index calculus algorithm decreases when smoothness bound is smaller than \(0.45B_i\). And then, the average running time of index calculus algorithm increases when smoothness bound is larger than \(0.45B_i\). Second, our algorithm is faster than index calculus algorithm. In particular, when solving random discrete logarithm problems, the minimal average running time of index calculus algorithm is three times that of our algorithm. For example, the minimal average running time of index calculus algorithm is about 105s when the bit length is 55 bits. The minimal average running time of our algorithm is only about 1/3 (105/35.3) that of index calculus algorithm when the bit length is 55 bits. Third, the value of smoothness bound that makes the average running time minimal is become larger as the bit length increase. For example, the average running time is minimal of all algorithms when smoothness bounds is \(0.45B_i\) if the bit length is 40. However, the average running time is minimal of our algorithm and index calculus algorithm when smoothness bounds is \(0.65B_i\) and \(0.50B_i\) respectively if the bit length is 55.

The fourth experiment compares the average running time when the bit length is large. In particular, bit length is from 50 bits to 75 bits with step size 5. As demonstrated in the third experiment, the smoothness bound has large influence on the average running time. For the index calculus algorithm, the average running time is minimal when smoothness bound is \(0.5B_i\), where \(B_i=e^{\sqrt{\frac{\log{p} \log{\log{p}}}{2} }}\). And for our algorithm, the average running time is minimal when smoothness bound is \(0.65B_i\). Thus, in the fourth experiment, smoothness bounds of index calculus algorithm and our algorithm are \(0.5B_i\) and \(B_i\), respectively. Many random discrete logarithm problems are generated and the average running time of solving these problems is shown in Fig. 7.

According to the experiment results in Fig. 7, the computing speed of our algorithm is higher than that of index calculus algorithm. As the bit length becomes large, the difference on average running time becomes large too, which indicates that the performance of our algorithm becomes more better than the performance of the state-of-the-art index calculus algorithm.

To demonstrate that our algorithm could be much faster than the state-of-the-art index calculus algorithm, we randomly set smooth bound to be \[\begin{align} B_i = e^{\frac{\sqrt{\log p\log\log p}}{2}} \label{euq9572} \end{align}\tag{12}\] and \[\begin{align} B_d = e^{\sqrt{\frac{\log p\log\log p}{2}}} \label{euq9573} \end{align}\tag{13}\] for index calculus algorithm and our algorithm. The comparison of average running time is shown in Table 4 and the comparison indicates that our algorithm could be 30 times faster than the state-of-the-art index calculus algorithm.

In brief, our algorithm is compared with classical and state-of-the-art algorithms comprehensively, and the comparison indicates that our algorithm is better than existing algorithms.

6 Conclusion↩︎

In this paper, we propose the double index calculus algorithm to solve the discrete logarithm problem in the finite prime field. Our algorithm is faster than the fastest algorithm available. We give theoretical analyses and perform experiments to back up our claims. Empirical experiment results indicate that our algorithm could be more than 30 times faster than the fastest algorithm available when the bit length of the size of the prime field is large. Our improvement in solving the discrete logarithm problem in the finite prime field may influence how researchers choose security parameters of cryptography schemes whose security is based on the discrete logarithm problem.

References↩︎