# Efficiency of finding sub group order vs factorization

Suppose you got a prime $p = 2\mathbb\Pi_{i=0}^{n-1}q_i+1$, where $2^{k-1} \lt q_i \lt 2^k$ for some $k$ and all $0 \le i \lt n$, and that you also got a generator $g$ of one of the prime order sub groups of $\mathbb Z_p^*$. Also assume that the factorization of $\frac{p-1}{2}$ is unknown.

Question #1:

Are there ways to find the order of $g$ faster than using the elliptic curve and number field sieve methods for factoring $\frac{p-1}{2}$? The expected running time of the generic meet-in-the-middle algorithm for finding the order of $g$ is $O(\sqrt{2^k})$, which might be assumed to be greater than the running time of ECM.

Question #2:

Suppose Alice picks an element $x$ uniformly from $\mathbb Z_{q_0}$ and that $g$ is a generator of the $q_0$ order subgroup of $\mathbb Z_p^*$. Alice calculates $y = g^x \mod p$ and gives $(p,g,y)$ to Bob. Bob's goal is to find $q_0$ and he gets to do that either by factoring $\frac{p-1}{2}$, by finding the order of $g$ and $y$, or by collecting solutions $(a_j,b_j)$ to the equation $BS2I(a_j) \equiv xBS2I(b_j) \pmod {q_0}$ using the following protocol:

• Bob: Pick an element $a_j \in \{0,1\}^k$ and send it to Alice
• Alice: Calculate $c = x^{-1}BS2I(a_j) \mod {q_0}$. For some deterministic function $f:\mathbb Z_{q_0} \rightarrow \{0,1\}^k$ such that $BS2I(f(z))\equiv z \pmod {q_0}$ for all $z\in \mathbb Z_{q_0}$, calculate $b_j=f(c)$ and send $b_j$ to Bob.
• Bob: Verify that $g^{BS2I(a_j)} = y^{BS2I(b_j)} \mod p$.

Question #3:

If we regard the protocol in question #2 as a simple instance of polynomial evaluation, where Alice picks two polynomials $r(), s()$ with coefficients in $\mathbb Z_{q_0}$ and provides Bob with the means to verify if $r(BS2I(a_j)) \equiv s(BS2I(b_j)) \pmod {q_0}$, where Bob picks $a_j$ and Alice provides the solution $b_j$ - would choosing polynomials with higher degree than 1 make it significantly harder for Bob to solve $q_0$?

-
Interesting problem. Seems indeed hard to find the order of $g$ without factoring $p-1$, but I have not found any previous references to it. Did you have any application in mind ? – minar Jul 22 '13 at 14:55
@minar: Yes, I have made an attempt to add some context. – Henrick Hellström Jul 24 '13 at 9:06
Just to be sure. BS2I=bitstring to integer conversion ? And $f$ maps an element $x$ modulo $q_0$ to some bitstrings that encodes some fixed integer representation of $x$ ? – minar Jul 24 '13 at 9:50
If I correctly understand the notation, what prevents Bob from querying $a_1=1$ and $a_2=10$. By construction, $10b_1-b_2\equiv 0\pmod{q_0}$ and this number is at most $20$ times $q_0$, so it is easy to remove small factors and recover $q_0$. Or did I miss something ? Also, if Bob cannot choose small values, he could just gather two multiples of $q_0$ in the same way and compute their gcd. – minar Jul 24 '13 at 9:55
@minar: Yes, that answers the second question, which was there mostly to justify the third question. Would the degree of the polynomials have to be infeasibly large, to prevent getting a linear equation system where the only random noise is the multiples of $q_0$? – Henrick Hellström Jul 24 '13 at 10:10

Concerning question 3, here is an answer assuming that the coefficients of $r$ are known to Bob and the coefficients of $s$ hidden in an exponential representation. [This is unessential, it can be easily generalized to hidden $r$, but it simplifies the presentation].

To further simplify, let's also assume that $s$ contains no constant term. In this setting, each pair $(a_i,b_i)$ as in the question is equivalent to a pair $(A_i,b_i)$ together with the information that $s(b_i)\equiv A_i\pmod{q_0}$. This can be easily rewritten as a linear equation $$\sum_{k=1}^{\ell}s_kb_i^k\equiv A_i\pmod{q_0},$$where $\ell$ is the degree of $s$. Collect $\ell+1$ such equations and form the matrix: $$M=\left(\begin{array}{ccccc}-A_1 &b_1 & b_1^2 & \cdots &b_1^\ell\\ -A_2 & b_2 & b_2^2 & \cdots &b_2^\ell\\ \vdots &\vdots & \vdots & \ddots & \vdots\\ -A_{\ell+1}& b_{\ell+1} & b_{\ell+1}^2 & \cdots &b_{\ell+1}^\ell\\ \end{array}\right).$$ By construction the system $Mx=0$ has a non zero solution vector (formed by a '1' followed by the coefficients of $s$) modulo $q_0$. As a consequence, $\det(M)$ is a multiple of $q_0$. Form two such matrices, take gcd and you can recover $q_0$ directly.

Note that this can be made more efficient by taking a rectangular matrix $M$ (with extra equations) and computing a Hermite normal form.

-
Nice solution! It looks to me like this approach can be further generalized to the case where neither $r$ nor $s$ are known to Bob (not even a hidden version of the coefficients; nothing is known). You need $\deg r + \deg s + 2$ equations or so to get a multiple of $q_0$. Then we can continue as in your answer. – D.W. Jul 24 '13 at 21:38
This looks like neat solution indeed, but please explain this: If $det(M)$ is a multiple of $q_0$, it means that it is congruent to zero $\pmod {q_0}$. Doesn't that mean that there are no or an infinite number of solutions to the equation $Mx = 0$? – Henrick Hellström Jul 24 '13 at 23:20
@HenrickHellström If $\det(M)\equiv 0 \pmod{q_0}$, then $M$ has a non-trivial kernel modulo $q_0$. Here, the kernel will have dimension $1$ (unless some unexpected degeneracy occurs) and thus, there are $q_0-1$ non zero kernel elements which are obtained by multiplying the kernel element with a $1$ in first position (described in my answer) by an arbitrary non-zero constant modulo $q_0$. – minar Jul 25 '13 at 6:46
@D.W.Yes, this is what I meant when saying in brackets that it can by easily generalized to unknown $r$ (I should have written to the case where both $r$ and $s$ are unknown. Note that since the constant terms of $r$ and $s$ can be merged on one side, you only need $\deg{r}+\deg{s}+1$ equations. In addition, you don't really need to know the degrees of $r$ and $s$, an upper bound is enough. – minar Jul 25 '13 at 6:50
@HenrickHellström I don't get your counterexample, here is a PARI/GP script for this case. q0=nextprime(2000);ee=lift(1/Mod(3,q0-1)); q1=nextprime(3000) f(x)=lift(Mod(x/q1,q0))*q1+lift(Mod(lift(Mod(x,q0)^11)^3/q0,q1))*q0 M=matrix(10,4);for(i=1,10,M[i,1]=f(i);M[i,2]=f(i)^2;M[i,3]=f(i)^3;M[i,4]=-i);mat‌​hnf(M~) You can see that the first entry in the HNF is $12q_0$. Moreover, $f$ is no longer a function to a $k$-bit value as you initially specified. [The PARI/GP script should be on 3 lines, break line before and after defining $f$] – minar Jul 25 '13 at 9:35

Question #1: I know of no faster algorithms.

Question #2: Minar has answered this one (breaking the scheme).

Question #3: Yes, this is easy to break, assuming the polynomials $r,s$ are known. We have many $(a_i,b_i)$ that satisfy the equation $r(a_i) \equiv s(b_i) \pmod{q_0}$. Let $c_i = r(a_i) - s(b_i)$, where this is evaluated over the integers. Notice that we are guaranteed that $c_i$ is a multiple of $q_0$; we can treat it as a random multiple of $q_0$.

Now compute $\gcd(c_1,c_2,\dots,c_{100})$. With probability that is exponentially close to 1, this will be exactly $q_0$ (if we can model each $c_i$ as a random multiple of $q_0$). In fact, observing two pairs $(a_1,b_1),(a_2,b_2)$ is enough to recover $q_0$ with high probability: for example, $\gcd(c_1,c_2)$ will be $q_0$ with high probability (since the gcd of two random integers is $1$ with high probability, specifically, probability $\pi^2/6$).

-
Yes, if the polynomials are given to Bob, you get this simpler approach. Following the example of question 2, I assumed that at least $s$ was secret (or more precisely that the coefficients of $s$ were given in hidden form $g^{s_i}$ instead of $s_i$) and thus proposed a more complex strategy. One final remark, in your construction $gcd(c_1,c_2)$ is enough even when it is a multiple of $q_0$, since with high probability it is a small multiple and the cofactor is thus easy to compute. – minar Jul 24 '13 at 20:53
Yes, as minar guessed, if intepreted the way I intended, Bob only has access to an exponential representation of the polynomials. – Henrick Hellström Jul 24 '13 at 22:56