First, I want to know what is the logarithm used in the following system of equations (from the paper Flexible and Robust Privacy-Preserving Implicit
Authentication - Domingo-Ferrer, Wu, Blanco-Justicia):
Second I want to understand how one can obtain integer values $r^\prime_1, r^\prime_2, ..., r^\prime_s$ after using logarithm. Note: All the other values ($R^\prime,r^\prime_0, a_i;\forall i$) in the system are integers.
There are serious errors in the fragment quoted in the question, which is (an appendix of) the paper: Josep Domingo-Ferrer, Qianhong Wu, Alberto Blanco-Justicia, Flexible and Robust Privacy-Preserving Implicit Authentication (in ICT Systems Security and Privacy Protection, Volume 455 of the series IFIP Advances in Information and Communication Technology pp 18-34; also in arXiv:1503.00454).
We are invited to use the technique in [7]: James Demmel and Plamen Koev, The Accurate and Efficient Solution of a Totally Positive Generalized Vandermonde Linear System, in SIAM J. Matrix Anal. Appl. 27 (2005). But in that reference [7] the unknowns $a_i$ are real variables, and the critical issue is numerical stability; when the unknowns in the context are integers, and the system of equations to solve is $\bmod n$ (or at least modular). I'm thus inclined to believe reference [7] can't be directly applied. That might have to do with why reference [7] was not used; quoting section 6 of the paper
we used straightforward Gaussian elimination which takes time $O(s^3)$, although, as mentioned above, specific methods like [7] exist for generalized Vandermonde matrices that can run in $O(s^3)$ (such specific methods could be leveraged in case of smartphones with low computational power).
Even with Gaussian elimination, I am left puzzled at the description of how the authors proceed in the setup phase. My best guess is that their $\log$ really is discrete logarithm to base $g$ in the multiplicative group $\bmod n^2$ (where $g$ is some generator, possibly the same as in the public key); but in that case, the linear system obtained won't be $\bmod n$ as written: an appropriate modulus $m$ would be one with $g^m\equiv1\pmod{n^2}$, and there is no reason that $g^n\equiv1\pmod{n^2}$. I'm cautiously optimistic that using $m=\lambda(n^2)=p\cdot q\cdot\operatorname{lcm}(p-1,q-1)$ would be a step towards reason (note: $\lambda$ is the Carmichael function).
But I see another issue: computing discrete logarithm to base $g$ is computationally involved in the general case even with factorization of $n$ known, we have not been told in appendix B to choose $p$ and $q$ making that operation easier, thus I do not see how we could (as told in section 4.1, Set-up item 4)
randomly choose $R'\in\mathbb Z_{n^2}$. Find $r'_0,\dots,r'_s\in\mathbb Z_{n^2}$ such..
as to match the system of equations in the question, by the reduction to a linear problem that (my reinterpretation of) the paper suggests.
My best idea to reach the goal of Set-up item 4 is to assume that we can write $R'=g^u\bmod n^2$ and $r'_i=g^{v_i}\bmod n^2$ for $0\le i\le s$, and choose random $u$ and $v_0$ (yielding random-enough $R'$ and ${r'_0}$ with known logarithm). Having done this, $\log(R'/r_0)$ becomes the chosen $u-v_0$, $\log(r_i)$ is the unknown $v_i$ for $1\le i\le s$, and indeed if we can solve the linear system of $s$ equations $\bmod\lambda(n^2)$ with $s$ unknowns $v_i$ for $1\le i\le s$, then that solution yields what's wanted in Set-up item 4.
I find the paper lacking on many more points than exposed above; among such pitfalls:
If both parties are honest, then the carrier learns $|X\cap Y|$ but obtains no information about the elements in $X$ or $Y$.
