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):enter image description here

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

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.