Secure integer division with a private divisor

Authors: Thijs Veugen (TNO, The Netherlands), Mark Abspoel (CWI, The Netherlands)

Volume: 2021
Issue: 4
Pages: 339–349
DOI: https://doi.org/10.2478/popets-2021-0073

Download PDF

Abstract: We consider secure integer division within a secret-sharing based secure multi-party computation framework, where the dividend is secret-shared, but the divisor is privately known to a single party. We mention various applications where this situation arises. We give a solution within the passive security model, and extend this to the active model, achieving a complexity linear in the input bit length. We benchmark both solutions using the well-known MP-SPDZ framework in a cloud environment. Our integer division protocol with a private divisor clearly outperforms the secret divisor solution, both in runtime and communication complexity.

Keywords: secure multi-party computation, secret sharing, integer division, truncation

Copyright in PoPETs articles are held by their authors. This article is published under a Creative Commons Attribution-NonCommercial-NoDerivs license.