Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

share|improve this question
    
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
1  
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

2 Answers 2

up vote 3 down vote accepted
+50

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.

share|improve this answer
    
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$).

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.