3
$\begingroup$

Given a natural number $n$ (of unknown factorization) and an arbitrary number $c \in \mathbb{Z}^*_n$ (the set of natural numbers smaller than $n$ and coprime to it), is there an efficient algorithm which outputs numbers $a \in \{2,\ldots,n-1\}$ and $b \in \mathbb{Z}^*_n$ such that:

$$b ^ a \equiv c \pmod n$$

Note 1: In my problem, $n$ is the product of two safe primes.

Example: Let $n=77$ and $c=2$. The set of all admissible pairs $(b,a)$ is:

$$\{ (18, 23), (30, 7), (39, 29), (46, 11), (51, 13), (72, 19), (74, 17) \} \,.$$

For the same $n$ and $c=15$, the set of all admissible pairs $(b,a)$ is:

$$\{ (2, 12), (3, 24), (4, 6), (5, 18), (6, 8), (8, 4), (9, 12), (13, 2), (16, 3), (17, 18), (18, 6), (19, 24), (20, 2), (24, 12), (25, 9), (26, 6), (27, 8), (29, 6), (30, 24), (31, 12), (36, 4), (37, 6), (38, 18), (39, 18), (40, 6), (41, 4), (46, 12), (47, 24), (48, 6), (50, 8), (51, 6), (52, 24), (53, 12), (57, 2), (58, 9), (59, 6), (60, 3), (61, 18), (62, 6), (64, 2), (68, 12), (69, 4), (71, 3), (72, 18), (73, 6), (74, 24), (75, 12) \} \,.$$

Note 2: One can assume that $c$ is chosen randomly, and the algorithm is probabilistic and may output the right answer with good probability.

$~$

Note 3: If $b$ is fixed, the problem is the discrete log, and is known to be hard. If $a$ is fixed, the problem might be a variant of RSA or Rabin cryptosystem, both of which are considered hard. I hope that by giving the algorithm the freedom of picking both $a,b$, it is solvable efficiently.

$\endgroup$
5
  • 1
    $\begingroup$ I presume that choosing $b=c$ and $a=(n-1)!+1$ is cheating? $\endgroup$ Mar 3 '20 at 10:37
  • 1
    $\begingroup$ From your examples, it looks like you are insisting on $a<n$ and $b<n$. Perhaps you should state your restrictions explicitly. $\endgroup$ Mar 3 '20 at 11:22
  • 2
    $\begingroup$ $b<n$ is without loss of generality. And an exponentially large $a$ will require an exponential-time algorithm, which does not count as efficient. If there is a polynomial-time algorithm (possibly randomized), that by itself imposes a bound $a\le2^{(\log n)^k}$ for some constant $k$. $\endgroup$ Mar 3 '20 at 12:01
  • $\begingroup$ @JeremyRickard: Not cheating, but it's not admissible as no efficient algorithm can output such a large number. See Emil's comment for further description. $\endgroup$ Mar 3 '20 at 13:56
  • 1
    $\begingroup$ @GerryMyerson: As per Emil's comment, it might be unnecessary, though I edited the question to reflect the conditions. $\endgroup$ Mar 3 '20 at 14:04
4
$\begingroup$

After much struggling, I found out that this is currently deemed a hard problem; so there is no known efficient algorithm to solve it.

From the Encyclopedia of Cryptography and Security (2011):

Strong RSA Assumption

The Strong RSA Assumption was introduced by Baric and Pfitzmann [3] and by Fujisaki and Okamoto [18] (see also [13]).

This assumption differs from the RSA Assumption in that the adversary can select the public exponent e. The adversary’s task is to compute, given a modulus n and a ciphertext C, any plaintext M and (odd) public exponent e ≥ 3 such that $C = M^e \pmod n$. This may well be easier than solving the RSA Problem, so the assumption that it is hard is a stronger assumption than the RSA Assumption. The Strong RSA Assumption is the basis for a variety of cryptographic constructions.

with references as follows:

  1. Barić N, Pfitzmann B (1997) Collision-free accumulators and fail-stop signature schemes without trees. In: Fumy W (ed) Advances in cryptology – EUROCRYPT’97. Lecture notes in computer science, vol 1233. Springer, Berlin, pp 480–494.

$~$

  1. Cramer R, Shoup V (2000) Signature schemes based on the strong RSA assumption. ACM Trans Inform Syst Sec 3(3): 161–185.

$~$

  1. Fujisaki E, Okamoto T (1997) Statistical zero knowledge protocols to prove modular polynomial relations. In: Kaliski BS Jr (ed) Advances in cryptology – CRYPTO’97. Lecture notes in computer science, vol 1294. Springer, Berlin, pp 16–30.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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