# Implicit authentication aritcle

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:

• No argument is given that what's disclosed at Set-up item 5 does not allow factoring $n$ or finding information about the user's profile, which is essential to the stated goal; the closest thing being an assertion without proof (made quite moot by what I emphasized)

If both parties are honest, then the carrier learns $|X\cap Y|$ but obtains no information about the elements in $X$ or $Y$.

• There are striking similarities with earlier work blinding set operations (including counting the intersection) using the Paillier cryptosystem; at least the seminal reference [9] (Michael J. Freedman, Kobbi Nissim, Benny Pinkas, Efficient private matching and set intersection, in proceedings of Eurocrypt 2004) is in the bibliography, but the text makes no reference to it.
• We are given benchmarks of the setup phase, but no way to reproduce or analyze these, and not even a clear description (hence the question);
• The performance numbers are given for a CPU only specified as "Intel i7", which leaves performance unspecified by a wide factor, given the variety of processors sold under this label;
• In appendix B, the decryption for the Paillier cryptosystem has a number of small issues, and two serious ones:
• the final formula uses the wrong modulus $n^2$, rather than $n$;
• it is missing the critical Euclidian division by $n$ step!