Paper 2021/207

Secure Fast Evaluation of Iterative Methods: With an Application to Secure PageRank

Daniele Cozzo, Nigel P. Smart, and Younes Talibi Alaoui

Abstract

Iterative methods are a standard technique in many areas of scientific computing. The key idea is that a function is applied repeatedly until the resulting sequence converges to the correct answer. When applying such methods in a secure computation methodology (for example using MPC, FHE, or SGX) one either needs to perform enough steps to ensure convergence irrespective of the input data, or one needs to perform a convergence test within the algorithm, and this itself leads to a leakage of data. Using the Banach Fixed Point theorem, and its extensions, we show that this data-leakage can be quantified. We then apply this to a secure (via MPC) implementation of the PageRank methodology. For PageRank we show that allowing this small amount of data-leakage produces a much more efficient secure implementation, and that for many underlying graphs this `leakage' is already known to any attacker.

Metadata
Available format(s)
PDF
Publication info
Preprint. Minor revision.
Contact author(s)
daniele cozzo @ kuleuven be
nigel smart @ kuleuven be
younes talibialaoui @ kuleuven be
History
2021-03-01: received
Short URL
https://ia.cr/2021/207
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/207,
      author = {Daniele Cozzo and Nigel P.  Smart and Younes Talibi Alaoui},
      title = {Secure Fast Evaluation of Iterative Methods: With an Application to Secure PageRank},
      howpublished = {Cryptology ePrint Archive, Paper 2021/207},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/207}},
      url = {https://eprint.iacr.org/2021/207}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.