Abstract. We consider the problem of secure integer division: given two Paillier encryptions of ℓ-bit values n and d, determine an encryption of ⌊ n ⌋ without leaking any information about n or d. We propose two new d protocols solving this problem. The first requires O(ℓ) arithmetic operation on encrypted values (secure addition and multiplication) in O(1) rounds. This is the most efficient constant-rounds solution to date. The second protocol requires only O ( (log 2 ℓ)(κ + loglog ℓ) ) arithmetic operations in O(log 2 ℓ) rounds, where κ is a correctness parameter. Theoretically, this is the most efficient solution to date as all previous solutions have required Ω(ℓ) operations. Indeed, the fact that an o(ℓ) solution is possible at all is highly surprising. Keywords: Secure two-party computation, Secure integer division, Constantrounds, Bit-Length
Abstract. We consider the problem of secure integer division: given two Paillier encryptions of ℓ-bit values n and d, determine an encryption of ⌊ n ⌋ without leaking any information about n or d. We propose two new d protocols solving this problem. The first requires O(ℓ) arithmetic operation on encrypted values (secure addition and multiplication) in O(1) rounds. This is the most efficient constant-rounds solution to date. The second protocol requires only O ( (log 2 ℓ)(κ + loglog ℓ) ) arithmetic operations in O(log 2 ℓ) rounds, where κ is a correctness parameter. Theoretically, this is the most efficient solution to date as all previous solutions have required Ω(ℓ) operations. Indeed, the fact that an o(ℓ) solution is possible at all is highly surprising. Keywords: Secure two-party computation, Secure integer division, Constantrounds, Bit-Length
Integer division is one of the most fundamental arithmetic operators and is ubiquitously used. However, the existing division protocols in secure multi-party computation (MPC) are inefficient and very complex, and this has been a barrier to applications of MPC such as secure machine learning. We already have some secure division protocols working in ℤ2n. However, these existing results have drawbacks that those protocols needed many communication rounds and needed to use bigger integers than in/output. In this paper, we improve a secure division protocol in two ways. First, we construct a new protocol using only the same size integers as in/output. Second, we build efficient constant-round building blocks used as subprotocols in the division protocol. With these two improvements, communication rounds of our division protocol are reduced to about 36% (87 rounds → 31 rounds) for 64-bit integers in comparison with the most efficient previous one.
Abstract. When secure arithmetic is required, computation based on secure multiplication (MULT) is much more efficient than computation based on secure boolean circuits. However, a typical application can also require other building blocks, such as comparison, exponentiation and the modulo (MOD) operation. Secure solutions for these functions proposed in the literature rely on bit-decomposition or other bit-oriented methods, which require O(ℓ) MULTs for ℓ-bit inputs. In the absence of a known bit-length independent solution, the complexity of the whole computation is often dominated by these non-arithmetic functions. To resolve the above problem, we start with a general modular conversion, which converts secret shares over distinct moduli. For this, we proposed a probabilistically correct protocol for this with a complexity that is independent of ℓ. Then, we show that when these non-arithmetic functions are based on secure modular conversions, they can be computed in constant rounds and O(k) MULTs, where k is a parameter for an error rate of 2 −Ω(k). To promote our protocols to be actively secure, we apply O(k) basic zero-knowledge proofs, which cost at most O(k) exponentiation computation, O(1) rounds and O(k(ℓ + κ)) communication bits, where κ is the security parameter used in the commitment scheme.
We study the complexity of securely evaluating arithmetic circuits over finite rings. This question is motivated by natural secure computation tasks. Focusing mainly on the case of two-party protocols with security against malicious parties, our main goals are to: (1) only make black-box calls to the ring operations and standard cryptographic primitives, and (2) minimize the number of such black-box calls as well as the communication overhead. We present several solutions which differ in their efficiency, generality, and underlying intractability assumptions. These include: • An unconditionally secure protocol in the OT-hybrid model which makes a black-box use of an arbitrary ring R, but where the number of ring operations grows linearly with (an upper bound on) log |R|. • Computationally secure protocols in the OT-hybrid model which make a black-box use of an underlying ring, and in which the number of ring operations does not grow with the ring size. The protocols rely on variants of previous intractability assumptions related to linear codes. In the most efficient instance of these protocols, applied to a suitable class of fields, the (amortized) communication cost is a constant number of field elements per multiplication gate and the computational cost is dominated by O(log k) field operations per gate, where k is a security parameter. These results extend a previous approach of Naor and Pinkas for secure polynomial evaluation (SIAM J. Comput., 35(5), 2006). • A protocol for the rings Zm = Z/mZ which only makes a black-box use of a homomorphic encryption scheme. When m is prime, the (amortized) number of calls to the encryption scheme for each gate of the circuit is constant. All of our protocols are in fact UC-secure in the OT-hybrid model and can be generalized to multiparty computation with an arbitrary number of malicious parties.
In this paper we are interested in efficient and secure constant round multi-party protocols which provide unconditional security against so called honest-but-curious adversaries. In particular, we design a novel constant round protocol that converts from shares over Z_q to shares over the integers working for all shared inputs from Z_q. Furthermore, we present a constant round protocol to securely evaluate a shared input on a public polynomial whose running time is linear in the degree of the polynomial. The proposed solution makes use of Chebyshev Polynomials. We show that the latter two protocols can be used to design efficient constant round protocols for the following natural problems: (i) Equality: Computing shares of the bit indicating if a shared input value equals zero or not. This provides the missing building blocks for many constant round linear algebra protocols from the work of Cramer and Damgård [CD01]. (ii) Comparison: Computing shares of a bit indicating which of two shared inputs is greater. (iii) Bits: Computing shares of the binary representation of a shared input value. (iv) Exponentiation: Computing shares of x^a mod q given shares of x, a and q. Prior to this paper, for all the above mentioned problems, there were in general no efficient constant round protocols known providing unconditional security.
Considering constant-round protocols for generating random shared values, for secure multiplication and for addition of shared values, etc are available and can be met by known techniques in all standard models of communication. Protocols are presented allowing the players to securely solve standard computational problems in linear algebra. In particular, securely, efficiently and in constant-round compute determinant of matrices product, rank of a matrix, and determine similarity between matrices. If the basic protocols (addition and multiplication, etc) are unconditionally secure, then so are our protocols. Furthermore our protocols offer more efficient solutions than previous techniques for secure linear algebra.
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.