0
$\begingroup$

Sorry for the haphazard title: really not sure what this should be called

Suppose we have a set of $z$ random values $S = r_1, \dots, r_z$ drawn from $\mathbb{Z}_N$ (where $N$ is some large prime).

Now, suppose we have $n+1$ variables $R_1, \dots, R_n, R_{n+1}$, such as for each $R_i$: $R_i = r_{i_1} r_{i_2} \dots r_{i_k}$ where $r_{i_j}$ are $k$ randomly drawn values from $S$ with replacement$^*$.

We consider the problem of expressing $R_{n+1}$ as a quotient of $R_i$ ($i < n+1$). That is, find $S_1$, $S_2$ such that:

$R_{n+1} = \frac{\prod_{i \in S_1}{R_i}}{\prod_{i \in S_2}{R_i}}$

(ideally, we are looking in $\mathbb{Z}_N$, but I doubt it makes a big difference, provided $N$ is large enough compared to the other parameters)

  1. How "difficult" is this problem?

  2. (Assuming the previous answer to be: "not so easy" or worse) What about even deciding on the existence of a solution?

  3. Does this problem (or something it can be trivially reduced to) have a formal name? [guess this should be my first question, huh]

  4. Bonus question (depending on the above): Can any hypothesis be made about the uniqueness of $S_1$/$S_2$ elements (by default, it does not sound like elements should be unique in either collection) or the maximum size of either collection...

My intuition is that there is no easy solution, but I cannot see a simple reduction to any NP-Hard problem that I can think of... (there's an obvious parallel set-theory problem, but I'm not sure I see an easier answer for it)

$^*$: or without replacement, if it makes a major difference to the questions/proofs...

$\endgroup$
  • $\begingroup$ Neglecting the possibility that any of the $r_i$ are zero, can you assume that the residues $r_i$ are generated by selecting some $a \in \mathbb Z_N^\times$, randomly generating $d_i \in {[0,N-1)}$, and assigning $r_i := a^{d_i} \pmod{N}$? Neglecting the possibility that $r_1 = 1$, could you go further and let $a = r_1$? $\endgroup$ – Niel de Beaudrap Jan 23 '15 at 1:04
  • $\begingroup$ @NieldeBeaudrap: I think I understand your idea (reducing to an additive problem), but not sure I understand your formulation. Wouldn't it be rather: find an $a$ and $d_i$ such that $r_i = a^{d_i} \mod N$ and rewrite all $r_i$ that way? This seems doable assuming $N$ prime (but number theory is not my biggest strength). Not actually sure that the resulting problem has a non-exponential solution, though... $\endgroup$ – Dave Jan 23 '15 at 3:06
  • $\begingroup$ @NieldeBeaudrap: I see. In that case, no: we cannot make any assumption about the generations of $r_i$. In fact, the framework I am working in is adversarial (security proof) and I'll be particularly happy if I can show that the above problem (which is a very generous relaxation of the original conditions) is intractable or (better yet) NP-complete. Original conditions involve actually not even knowing the $r_i$ (only the resulting $R_j$). $\endgroup$ – Dave Jan 23 '15 at 4:11
  • $\begingroup$ Off-hand comment: It seems like a restriction of your problem is exactly a Subset Product instance. Consider only a (worst-case) list of numbers $R_1 ... R_n$ and a target number $T = R_{n+1}$. The question is, is there a subset $S$ of $\{R_1, ..., R_n\}$ whose product $\prod_{i\in S} R_i \stackrel{?}{=} T,$ which is NP-complete. $\endgroup$ – Daniel Apon Feb 8 '15 at 18:50

Your Answer

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

Browse other questions tagged or ask your own question.