Efficiency of finding sub group order vs factorization

Question

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$?

Answer 1

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.

Answer 2

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$).