Oblivious stable sorting protocol and oblivious binary search protocol for secure multi-party computation

Abstract

Multi-party computation (MPC) sorting and searching protocols are frequently used in different databases with varied applications, as in cooperative intrusion detection systems, private computation of set intersection and oblivious RAM. Ivan Damgard et al. have proposed two techniques i.e., bit-decomposition protocol and bit-wise less than protocol for MPC. These two protocols are used as building blocks and have proposed two oblivious MPC protocols. The proposed protocols are based on data-dependent algorithms such as insertion sort and binary search. The proposed multi-party sorting protocol takes the shares of the elements as input and outputs the shares of the elements in sorted order. The proposed protocol exhibits $O (1)$ constant round complexity and $O (n log n)$ communication complexity. The proposed multi-party binary search protocol takes two inputs. One is the shares of the elements in sorted order and the other one is the shares of the element to be searched. If the position of the search element exists, the protocol returns the corresponding shares, otherwise it returns shares of zero. The proposed multi-party binary search protocol exhibits $O (1)$ round complexity and $O (n log n)$ communication complexity. The proposed multi-party sorting protocol works better than the existing quicksort protocol when the input is in almost sorted order. The proposed multi-party searching protocol gives almost the same results, when compared to the general binary search algorithm.

Keywords

Multi-party computation oblivious sorting bit-wise sharing bit-decomposition protocol bit-wise less than protocol searching

1. Introduction

Andrew Yao [30] in 1982, has proposed a two-party computation (2PC), considered as Holy Grail of cryptography. The goal of 2PC is to create protocols allowing two parties to cooperatively compute an arbitrary function of their private inputs without sharing the clear value of their inputs with the opposing party. Yao gives evidence of feasibility with a solution to the so-called Millionaires’ problem. The problem is stated as follows: two millionaires wish to learn who is the richer without telling their actual wealth to the other.

A natural generalization of the secure two-party computation is the secure multiparty computation (MPC). Secure multi-party computation can be defined as the problem of n participants to compute an agreed function of their inputs in a secure way, where security means guaranteeing the correctness of the output as well as the privacy of the users’ inputs. The mathematical model for secure multi-party computation is formally defined as the parties $P_{1}, P_{2}, \dots, P_{n}$ attempt to jointly compute a function $y = f (x_{1}, x_{2}, \dots, x_{n})$ without disclosing their secret value $x_{i}$ to each other. In 1987, Goldreich et al. [9] have detailed the first general solution to secure multi-party computation. Their solution is based on secret sharing, which enables a participant to split his secret into several shares that will be sent to each of the participants, with the guarantee that any individual share does not leak any information about the secret value. The authors then show how to perform operations on these shares without revealing them.

Sorting and searching are the most important primitives used in computer science, specially in database operations, data mining and data analysis operations to preserve privacy. Multi-party computation sorting protocols are frequently used in different database operations and have many applications in cooperative intrusion detection systems [18], oblivious RAM [5], and private set intersection [16]. Multi-party sorting and searching protocols also have potential applications in IoT and Blockchain [7,17,29].

A sorting algorithm is said to be stable, if two objects with equal keys appear in the same order in sorted output as they appear in the input to be sorted. Some algorithms satisfy stable sorting by nature. Insertion sort is one of the stable sorting algorithm.

The multi-party computation protocols must be data oblivious. Most popular algorithms available are not data oblivious. An algorithm is said to be data oblivious, only when the algorithm’s control flow is independent of the input. Up to date there does not exist any efficient algorithm to transform data-dependent algorithms into data oblivious protocols. There are other various mechanisms involved to convert data-dependent algorithms into data oblivious protocols. As these mechanisms take an exponential amount of time to compute, they are not considered to be effective.

Any given function will be evaluated securely with the help of a circuit illustration of the given input function. The first circuit representation of a function is given in [10,11]. Using a circuit illustration of a given function, it is not an easy task to design effective multi-party protocols for a complex set of algorithms. Many proposals are made to construct effective multi-party protocols. Some building blocks of MPC protocols are the computation of bit-decomposition protocol, modulo reduction protocol and bit-wise less than protocol or comparison protocol.

1.1. Our contribution

In TCC 2006, Ivan Damgard et al. [4] have designed two naive techniques: bit-decomposition protocol and bit-wise less than protocol. Bit-decomposition protocol converts shares of a secret s into shares of the bits of s. Further, in PKC 2007, Takashi Nishide and Kazuo Ohta [22] have presented an improved and simplified version of the bit-decomposition protocol and comparison protocol. The proposed work has used these protocols [4,22] as building blocks for sorting and searching. It has also proposed oblivious multi-party sorting and binary search protocols from the data-dependent insertion sort and binary search algorithms. The proposed sorting protocol takes input as shares of the elements and outputs their shares in a sorted order. The proposed multi-party insertion sort protocol is best suited, when input is of almost sorting order. A complexity of $O (1)$ number of rounds and $O (n log n)$ communication is shown in the proposed sorting protocol, where n is the number of the input values of the parties in the synchronous network. The proposed binary search protocol takes shares of elements in a sorted order and shares of the element to be searched as inputs and produce an output irrespective of the existence of an element. The proposed multi-party binary search protocol exhibits a complexity of $O (1)$ rounds and $O (n log n)$ communications. The proposed sorting protocol performs better than the existing sorting protocol [14], when the input is almost in sorted order. The shares of the elements are distributed to n number of parties. These individual parties do their computations and finally t shares are enough to get the sorted elements.

1.2. Related work

Any circuit-based sorting algorithms are considered to be sorting networks. Since sorting networks are designed in circuit style and circuit-based algorithms are data-oblivious, so they can be efficiently extended to MPC protocols. Some of the sorting algorithms used for MPC system, are given as network sorting algorithms. In [1], Ajtai has introduced an efficient network sorting algorithm called the AKS sorting algorithm. The worst case complexity is given as $O (n log n)$ comparison gates, where n represents the total number of inputs. The AKS sorting algorithm requires approximately $C_{1} * n log n$ steps to sort n keys in worst case ( $O (n log n)$ ), where the constant factor $C_{1}$ is very large. But the proposed method is quite complicated, as it has a large constant factor. On the other hand, K. E. Batcher proposed a randomized merge-sorting network algorithm [2]. Which requires approximately $C_{2} * n {log}^{2} n$ steps to sort n keys in worst case ( $O (n {log}^{2} n)$ ). The constant factor $C_{2}$ is much less than the constant factor $C_{1}$ . Goodrich and Michael [13] demonstrated a technique to extend internal sorting schemes to the external memory sort. Guan et al. [28] implemented Fairplay [21] for the sorting algorithms in a MPC environment. Based on the MPC concept of Fairplay, randomized shell-sort [12] and merge sort [2] algorithms are proposed. With a new MPC system called Sharemind [3], Kristjan Valur Jonsson et al. [18] have implemented the Batcher’s merge sort. They have used a technique called vectorization, using which they have sorted data with secret shared values. Most of these corresponding algorithms are not efficient, which means they are characterized by the exponential time. Based on the concept of data oblivious, Koki Hamada et al. [14] have implemented a quick sort algorithm using MPC protocols.

1.3. Organization

The organization of rest of the paper is as follows: Section 2 provides basic background to be used later. Section 3 introduces the oblivious insertion sort protocol to sort out the given list of elements in a shared environment. Section 4 introduces the oblivious binary search protocol to search an element in a shared environment. Section 5 discloses the evaluation of the implemented results and comparison with existing protocols and Section 6, concludes the work.

2. Preliminaries

Some standard notations and some well-known techniques are used in this part. This work presumes that n parties in a synchronous network are connected by perfectly secure channels. This work focuses on the standard MPC scheme named a secret sharing scheme. The proposed work considers all input values and output values for the secret sharing scheme that belong to the field $Z_{p} = {0, 1, \dots, p - 1}$ .

2.1. Notations and assumptions

Multi-party Computation / Multiparty Computation.

The secret value is named as s.

The shares of a given secret s.

Shares of the secret A in matrix form.

The party i, i.e $P_{1}, \dots, P_{m}$ .

The share of secret a to the party $P_{i}$ .

Addition of shares of secret p and secret q.

Shares of p multiplied by a constant public parameter c.

Shares of either 1 or 0 depending on the condition.

Shares of either 1 or 0 depending on the equal condition.

A finite field with the elements ${0, 1, \dots, p - 1}$ , where p is a prime.

2.2. Building blocks

The proposed work introduces some already existing protocols, which are used as building blocks for the proposed protocols.

2.2.1. Shamir’s secret sharing scheme

Liu [20] has found an issue which is given below. “Eleven scientists are working on a secret project. They wish to lock up documents in a cabinet so that the cabinet can be opened if and only if six or more of the scientists are present. What is the smallest number of locks needed? What is the smallest number of keys to the locks each scientist must carry?”

“The answer for these problems are 462 locks and 252 keys per scientist. This is not a practical solution for this kind of problem”. The notes is adapted from [6,15,26] to describe the secret-sharing concept.

Shamir’s scheme of secret communication provides a generalized solution to the above problem. It takes the secret as data D and breaks it into number of pieces. To rebuild the data, it takes at least t- pieces. But information about D is not revealed from $t - 1$ number of pieces or less than that. It describes the following theorem.

Theorem 1.
Let $(x_{1}, y_{1}), \dots, (x_{t}, y_{t})$ be t points in a 2-D plane. For distinct values of $x_{i}$ there exists a unique polynomial with a degree of $t - 1$ , that satisfies $q (x_{i}) = y_{i} \forall i$ .

Shamir’s secret sharing protocol: The protocol consists of two sub-protocols named share_construct protocol used to construct shares and reconstruct protocol used to rebuild the secret.

Share_construct sub-protocol takes input as the secret s and produces the output as shares of the secret s. It can be represented as $\begin{matrix} ⟦ s ⟧ \leftarrow share_construct (s) . \end{matrix}$

The objective of this protocol is to generate u – number of shares of secret s. It can be computed using at least $t - 1$ number of shares.
Third-party D picks a polynomial $q (x) = a_{0} + a_{1} x + \dots + a_{t - 1} x^{t - 1}$ of a random degree with $t - 1$ , where $a_{0} = s$ is the secret. All coefficients $a_{i}$ $(1 ⩽ i ⩽ t - 1)$ are randomly chosen from a field ( $Z_{p}$ : p is prime).

The third-party D distributes to each player j the share $q (x_{j})$ by computing the values $q (x_{1}), q (x_{2}), \dots, q (x_{u})$ . Here the shares are represented as $q (x_{1}), q (x_{2}), \dots, q (x_{u})$ .
Reconstruct sub-protocol takes input as the share of secret s and produces the output as the secret s. It can be represented as $\begin{matrix} s \leftarrow share_Reconstruct (⟦ s ⟧) . \end{matrix}$

From the t – number of shares one can build the polynomial $q (x)$ with degree $t - 1$ by using Lagrange polynomial and find the secret $s = q (0)$ .

Lagrange polynomial. Let $(a_{1}, b_{1}), \dots, (a_{t}, b_{t})$ be t points in a 2-D plane. For distinct vales of $a_{i}$ , the Lagrange form of the polynomial which crosses through those points is a linear combination. $\begin{matrix} q (a) = L (a) = \sum_{i = 1}^{t} b_{i} l_{i} (b) \end{matrix}$ Basis polynomials of Lagrange are: $\begin{matrix} l_{i} (a) = \prod_{1 ⩽ m ⩽ t, m \neq i} \frac{(a - a_{m})}{(a_{i} - a_{m})} = \frac{(a - a_{1})}{(a_{i} - a_{1})} \dots \frac{(a - a_{i - 1})}{(a_{i} - a_{i - 1})} \frac{(a - a_{i + 1})}{(a_{i} - a_{i + 1})} \dots \frac{(a - a_{t})}{(a_{i} - a_{t})} \end{matrix}$

The oracle invocation of this sub protocol can be represented as $f_{π}^{reconstruct}$ .

Shamir’s secret sharing scheme properties:

Perfect Security: With $t - 1$ number of shares or less, an adversary cannot find any information about the secret. This can be written as $\begin{matrix} Pr [Secret = s before secret sharing] = Pr [Secret = s after secret sharing] \end{matrix}$ This proof is adapted from lecture notes taken from [23].
Proof.
With $t - 1$ number of players with their shares cannot get any information about the secret. The random variables $S H$ are used to denote the $t - 1$ shares of the parties and S to denote the random variable for the secret itself. $\begin{array}{l} P [S = s_{1} | Given any t - 1 shares of the secret] \\ = P [S = s_{1} | S H = {f (x_{i})}_{i \in C}] A posteriori probability, given t - 1 shares . C \in {0, \dots, n} \\ = \frac{P [(S = s_{1}) \cap (S H = f (x_{i}))}{P [S H = {f (x_{i})}_{i \in C}]} Bayes’ Rule \\ = \frac{P [S = s_{1}] . P [S H = {f (x_{i})}_{i \in C} | S = s_{1}]}{P [S H = {f (x_{i})}_{i \in C}]} Bayes’ Rule \\ = \frac{P [S = s_{1}] . \frac{1}{| F_{p}^{t} |}}{P [S H = {f (x_{i})}_{i \in C}]} Uniform distribution in F_{p}^{t} for fixed secret \\ = \frac{P [S = s_{1}] . \frac{1}{| F_{p}^{t} |}}{\sum_{s_{j} \in S} P [S H = {f (x_{i})}_{i \in C} | S = s_{j}] . P [S = s_{j}]} Properties of conditional probability \\ = \frac{P [S = s_{1}] . \frac{1}{| F_{p}^{t} |}}{\sum_{s_{j} \in S} \frac{1}{| F_{p}^{t} |} . P [S = s_{j}]} Uniform distribution i n F_{p}^{t} for fixed secret \\ = \frac{P [S = s_{1}] . \frac{1}{| F_{p}^{t} |}}{\frac{1}{| F_{p}^{t} |} . \sum_{s_{j} \in S} P [S = s_{j}]} \\ = P [S = s_{1}] Denominator goes to 1 \\ = P [S = s_{1} before secret sharing] A priori probability . \end{array}$ Hence proved. □

Ideal: The size of the share of the secret is the same as the size of the secret.

Extendable: The addition of shares is calculated by computing extra points in the polynomial.

Homomorphic Property:

The addition or multiplication of shares of a secret with a constant provides a new secret.

Consider two secret values m and n. Their shares are $f (1), \dots, f (n)$ for the polynomial $f (x)$ in the same way $g (1), \dots, g (n)$ for the polynomial $g (x)$ . The kth share is $f (k) + g (k) (k \in [1 \dots n])$ . The new secret is $m + n$ for the newly generated function $o (x) = f (x) + g (x)$ as $o (0) = f (0) + g (0)$ .

2.2.2. Secure multiplication protocol (MULT) [11,27]

Ben-Or et al. [11] have proposed a multiplication protocol. Suppose there are two secrets $s_{1}$ , $s_{2}$ and n parties have the shares of these secrets. Given the shares of t parties ( $n ⩾ 2 t + 1$ ), this protocol computes the multiplication of secrets ( $s_{1} . s_{2}$ ).

Using Shamir’s secret sharing, for secret $s_{1}$ , Dealer D picks a polynomial of $t - 1$ degree $\begin{array}{l} (1) & f_{1} (x) = a_{0} + a_{1} x + \dots + a_{t - 1} x^{t - 1} where a_{0} = s_{1} . \end{array}$ Here all the coefficients $a_{i}$ ( $1 ⩽ i ⩽ t - 1$ ) are randomly taken from the field ( $Z_{p} : prime p$ ). Dealer D, computes share $f_{1}$ (j) and secretly forwards it to each player j, where $j \in {1, \dots, n}$ .

Similarly, for secret $s_{2}$ , D picks a random polynomial with $t - 1$ degree $\begin{array}{l} (2) & f_{2} (x) = b_{0} + b_{1} x + \dots + b_{t - 1} x^{t - 1} in which b_{0} = s_{2} . \end{array}$

Dealer D, computes $f_{2} (j)$ and secretly forwards it to each player j, where $j \in {1, \dots, n}$ . Now the party $P_{i}$ has shares $f_{1} (i)$ and $f_{2} (i)$ such that $f_{1} (0) = s_{1}$ and $f_{2} (0) = s_{2}$ . Multiplying these polynomials the output of the multiplication of shares is received.

Therefore $f_{1} (x) * f_{2} (x) = f (x)$ .

If we observe clearly, we get polynomial f(x) as $\begin{array}{l} (3) & f (x) = f_{1} (x) . f_{2} (x) = C_{2 (t - 1)} x^{2 (t - 1)} + C_{2 t} x^{2 t} + \dots + s_{1} s_{2} . \end{array}$ The secret $= f (0) = s_{1} s_{2}$ . The shares of $2 t - 1$ parties can be $\begin{matrix} [f (1), f (2), \dots, f (2 t - 1)] = [C_{0}, C_{1}, \dots, C_{2 t}] . [\begin{matrix} 1 & 1 & \dots & 1 \\ 1 & 2 & \dots & 2 t - 1 \\ 1 & 2^{2} & \dots & {(2 t - 1)}^{2} \\ ⋮ & ⋮ & \dots & ⋮ \\ 1 & 2^{2 t} & \dots & {(2 t - 1)}^{2 t} \end{matrix}] \end{matrix}$ It can be written as [f(1), f(2),…,f(2t-1)]. $A^{- 1} = [C_{0}, C_{1}, \dots, C_{2 t}]$ , where $\begin{matrix} A = [\begin{matrix} 1 & 1 & \dots & 1 \\ 1 & 2 & \dots & 2 t - 1 \\ 1 & 2^{2} & \dots & {(2 t - 1)}^{2} \\ ⋮ & ⋮ & \dots & ⋮ \\ 1 & 2^{2 t} & \dots & {(2 t - 1)}^{2 t} \end{matrix}] \end{matrix}$ we need the first column of our inverse matrix $A^{- 1}$ , so that it can be computed easily. $\begin{matrix} Let A^{- 1} = [\begin{matrix} ψ_{1} & . & . & . \\ ψ_{2} & . & . & . \\ ⋮ & ⋮ & ⋮ & ⋮ \\ ψ_{2 t - 1} & . & . & . \end{matrix}] \end{matrix}$ Presently secret $C_{0} = s_{1} s_{2} = ψ_{1} . f (1) + ψ_{2} . f (2) + \dots + ψ_{2 t - 1} . f (2 t - 1)$ . But, it is necessary for any $2 t$ parties to compute the multiplication of secret i.e. $s_{1} . s_{2}$ without any interaction between the parties.

In this protocol t (not $2 t + 1$ ) is required to compute the secret $s_{1} s_{2}$ but at some extra cost such as secure interaction between parties. The protocol works as follows

Now each party $P_{i}$ constructs $t - 1$ degree random polynomial $h_{i} (x) = f (i) + a_{1} x + \dots + a_{t - 1} x^{t - 1}$ , where $f (i)$ is the secret.

Party $P_{i}$ computes the shares $h_{i} (1), h_{i} (2), \dots h_{i} (u)$ and transfers it to others.

Let us define the new polynomial $h (x)$ as follows

h (x) = ψ_{1} . h_{1} (x) + ψ_{2} . h_{2} (x) + \dots + ψ_{2 t - 1} . h_{2 t - 1} (x)

. The degree of this polynomial

h (x)

t - 1

and the constant term

h (0) = ψ_{1} . h_{1} (0) + ψ_{2} . h_{2} (0) + \dots + ψ_{2 t - 1} . h_{2 t - 1} (0)

, substituting the values of

h_{i} (0)

i.e.

f (i)

. Now

h (0) = ψ_{1} . f (1) + ψ_{2} . f (2) + \dots + ψ_{2 t - 1} . f (2 t - 1) = s_{1} . s_{2}

. All parties have shares of

h (x)

, for example, party i has share

h (i)

such that

h (i) = ψ_{1} . h_{1} (i) + \dots + h_{i} (i) + \dots + ψ_{2 t - 1} . h_{2 t - 1} (i)

, he gets the values

h_{1} (i), \dots, h_{i - 1} (i), \dots, h_{i + 1} (i), \dots, h_{2 t - 1} (i)

from the other parties and

h_{i} (i)

is his share. Any t party can construct polynomial

h (x)

and compute the shares of secret

s_{1} s_{2}

In the implementation of the MULT protocol it uses a constant number of rounds and $O (l log l)$ invocations, where l represents the bit-length. The oracle invocation of this sub-protocol is represented as $f_{π}^{MULT}$ .

Let us consider a simple example to demonstrate the multiplication protocol.

Let prime value be $p = 13$ , $s_{1} = 3$ and $s_{2} = 4$ . Let $s_{1}$ ’s random polynomial be $f_{1} (x) = 3 + x + 2 . x^{2} \mod 13$ and $s_{2}$ ’s random polynomial be $f_{2} (x) = 4 + x + 2 . x^{2} \mod 13$ . Shares of $f_{1} (x) = {6, 0, 11, 0, 6}$ . Shares of $f_{2} (x) = {7, 1, 12, 1, 7}$ .

Now $f_{1} (x) . f_{2} (x) = 12 + 7 . x + 2 . x^{2} + 4 . x^{3} + 4 . x^{4} \mod 13$ , where $s_{1} = 3$ and $s_{2} = 4$ $\begin{array}{l} [f (1), f (2), \dots, f (5)] = [12 7 2 4 4] . [\begin{matrix} 1 & 1 & 1 & 1 & 1 \\ 1 & 2 & 3 & 4 & 5 \\ 1 & 4 & 9 & 3 & 12 \\ 1 & 8 & 1 & 12 & 8 \\ 1 & 3 & 3 & 9 & 1 \end{matrix}] \\ [f (1), f (2), \dots, f (5)] = [3 0 2 0 3] \\ A^{- 1} = [\begin{matrix} 5 & . & . & . \\ - 10 & . & . & . \\ 10 & . & . & . \\ - 5 & . & . & . \\ 1 & . & . & . \end{matrix}] \end{array}$ Therefore $[ψ_{1}, ψ_{2}, ψ_{3}, ψ_{4}, ψ_{5}] = [5, - 10, 10, - 5, 1]$ . Each party constructs $t - 1$ degree random polynomial with a secret as multiplication of shares, i.e., $f_{1} (i) . f_{2} (i)$ . The first party computes the shares for the random polynomial $h_{1} (x) = 6 \times 7 + x + 2 x^{2}$ . It will send $h_{1} (1)$ to the first party, $h_{1} (2)$ to the second party, $h_{1} (3)$ to the third party, $h_{1} (4)$ to the fourth party and $h_{1} (5)$ to the fifth party, secretly.

Similarly, the second party computes the shares of the random polynomial $h_{2} (x) = 0 \times 1 + x + 2 . x^{2}$ , the third party computes the shares of the random polynomial $h_{3} (x) = 11 \times 12 + x + 2 . x^{2}$ . The fourth party computes the shares of the random polynomial $h_{4} (x) = 0 \times 1 + x + 2 . x^{2}$ and the fifth party computes the shares of the random polynomial $h_{5} (x) = 6 \times 7 + x + 2 . x^{2}$ and sends to other parties.

The following table indicates the shares according to their random polynomials.

Let us consider the polynomial $h (x)$ with degree $t - 1 = ψ_{1} . h_{1} (x) + ψ_{2} . h_{2} (x) + ψ_{3} . h_{3} (x) + ψ_{4} . h_{4} (x) + ψ_{5} . h_{5} (x)$ Here $h (0) = ψ_{1} . h_{1} (0) + ψ_{2} . h_{2} (0) + ψ_{3} . h_{3} (0) + ψ_{4} . h_{4} (0) + ψ_{5} . h_{5} (0) = s_{1} s_{2} .$ Given three shares of $h (x)$ one can compute the secret $h (0) = s_{1} . s_{2}, h (1) = 5 \times 6 + (- 10 \times 3) + 10 \times 5 + (- 5 \times 3) + 1 \times 6 = 2$ , $h (3) = 5 \times 11 + (- 10 \times 8) + 10 \times 10 + (- 5 \times 8) + 1 \times 11 = 7$ , $h (5) = 5 \times 6 + (- 10 \times 3) + 10 \times 5 + (- 5 \times 3) + 1 \times 6 = 2$ .

Presently, the proposed shares are $(1, 2)$ , $(3, 7)$ and $(5, 2)$ . By applying the Lagrange interpolation formula, the secret is found as 12. Therefore the secret $\begin{array}{l} = 2 . \frac{3}{3 - 1} . \frac{5}{5 - 1} + 7 . \frac{1}{1 - 3} . \frac{5}{5 - 3} + 2 . \frac{1}{1 - 5} . \frac{3}{3 - 5} \mod 13 \\ = 2 . \frac{3}{2} . \frac{5}{4} + 7 . \frac{1}{- 2} . \frac{5}{2} + 2 . \frac{1}{- 4} . \frac{3}{- 2} \mod 13 \\ = {2.15.8}^{- 1} + {7.5.4}^{- 1} + {2.3.8}^{- 1} \mod 13 \\ = 12. \end{array}$

This is a simple example demonstrating the multiplication of two secrets.

2.2.3. Bit-decomposition protocol (BITS) [4,22]

In [4], a naive MPC protocol is proposed and later it is simplified in [22]. Bit-decomposition protocol converts a polynomial sharing of secret s into the shares of the bits of s. This technique is proposed with a constant number of rounds.

The bit-decomposition protocol will take the input as shares of the elements in a finite field and produce the output as shares of the bits of the given element. $\begin{array}{l} {{{(⟦ a_{0} ⟧}_{p}, ⟦ a_{1} ⟧}_{p}, \dots, ⟦ a_{l - 1} ⟧}_{p}) = BITS {(⟦ a ⟧}_{p}) where a_{0}, a_{1}, \dots, a_{l - 1} \in {0, 1} and \\ a = \sum_{i = 0}^{l - 1} a_{i} 2^{i}, a \in Z_{p} . \end{array}$

The main aim of this protocol is to fill the gap between the arithmetic and Boolean circuits of a function. Arithmetic circuits take the input in integer form, whereas Boolean circuits take input in bit form. Bit-decomposition protocol is an important and powerful tool to represent shared secrets of Boolean circuits as well as arithmetic circuits. This protocol takes the complexity of $O (l log l)$ invocations of multiplication and $O (1)$ number of constant rounds, where l is the length of the specified bit field. The bit-decomposition protocol proposed by Ivan Damgard et al. is given above.

In the above protocol, Solved_Bits() is a sub-protocol that generate a random number of shares, OPEN is a reconstruction protocol to reveal the secret. In the above protocol, Bit_Addition is a sub-protocol which takes two inputs as bits of the shares of two different secrets. The output is bit shares of addition of secrets. The present work has implemented the bit-decomposition protocol given by Ivan Damgard et al. [4] on $(t, n)$ -Shamir’s secret-sharing scheme which is secured against a semi-honest adversary. In the implementation of the protocol, BITS is the name used to represent bit-decomposition protocol, in which the subroutine takes shared values as input and converts them into shared bits of input values. In the implementation of the BITS sub-protocol, it is understood that the protocol takes $O (1)$ number of constant rounds and $O (l log l)$ multiplication invocations, where l is the bit-length of the specified field. The oracle invocation of this sub-protocol is represented as $f_{π}^{BITS}$ .

2.2.4. Bit-wise less than protocol (BIT-LT) [4,22]

This protocol takes two inputs and produces one output. One of the inputs for the sub-protocol are shares of bits of m represented as ${⟦ m ⟧}_{B}$ and another input is shares of bits of n represented as ${⟦ n ⟧}_{B}$ .

The output is shares of the bit 1 or 0 depending on the condition ( $a \overset{?}{<} b$ ) without revealing ( $a < b$ ) itself. This is represented as $\begin{matrix} {⟦ c ⟧ \leftarrow BIT - LT {(⟦ m ⟧}_{B}, ⟦ n ⟧}_{B}) \end{matrix}$

The proposed work has implemented the bit-wise less than protocol on $(t, n)$ -Shamir’s secret-sharing scheme which is secured, in contrast to the semi-honest adversary.

In the above protocol XOR, is the exclusive-OR operation between the shares parties. ${PRE}_{V}$ is the Prefix OR operation between the shares of parties and MULT is the multiplication of the parties shares. The implementation of MULT is given in 2.2.2. The proposed work has implemented all these sub-protocols, where the name BIT-LT is used to represent the comparison of shares of the bits. The inputs for BIT-LT are the shares of the bits of shared values of the parties with a length l. BIT-LT gives output as the shares of the bit value which is either 1 or 0. The BIT-LT function complexity is described as $O (1)$ number of constant rounds and $O (l)$ number of invocations in the prescribed MULT protocol.

2.3. Adversarial behavior in MPC [24,25]

Semi-honest adversaries: These adversaries are not deviating the protocol, they are just following the protocol. The adversary can study the internal information of the corrupted parties. These are also called passive adversarial models. In this, dishonest parties are also exactly following the specification of the protocol. While executing transcript messages in the protocol, there is a chance of leaking additional information when attempts are made to learn. It is a weak adversary model. These are also named as “honest-but-curious.”

Malicious adversaries: The adversary can take complete control over the parties and can make them misbehave in any desired manner. In the malicious model, restrictions are not placed on any of the participants. Thus parties are completely free to spoil the actions that are placed in the protocol. These are active adversaries. These adversaries may deviate from the protocol execution.

2.4. Oblivious security model

This security model is considered against a semi-honest adversary with $t - 1$ number of corrupted parties. A protocol is said to be secure and oblivious, if it does not reveal anything about data in the presence of the semi-honest adversary with at most $t - 1$ number of corrupted parties.

Formally, security in the semi-honest adversary model is defined as follows. Let $x = {x_{1}, x_{2}, \dots, x_{n}}$ , $x_{I} = {x_{i_{1}}, x_{i_{2}}, \dots, x_{i_{t - 1}}}$ , $f (x)$ be the output, $f_{i} (x)$ will be the ith output and $f_{I} (x) = (f_{i_{1}} (x), f_{i_{2}} (x), \dots, f_{i_{t - 1}} (x))$ . Signifying view of $P_{i}$ while executing the ρ protocol on the input values x as ${VIEW}_{P_{i}}^{ρ} (x) = (x_{i}, r_{i}; μ_{1}, μ_{2}, \dots, μ_{l})$ , where $r_{i}$ is the $P_{i}$ ’s random tape, $μ_{j}$ is the jth message received by $P_{i}$ . Finally the output of party $P_{i}$ can be specified as ${OUTPUT}_{P_{i}}^{ρ} (x)$ .

Definition 1 ([8]).

A probabilistic polynomial n-ary function $f : {({0, 1} *)}^{n} \to {({0, 1} *)}^{n}$ , a protocol will be ρ, then ${VIEW}_{I}^{ρ} (x) = ({VIEW}_{P_{i_{1}}}^{ρ} (x), {VIEW}_{P_{i_{2}}}^{ρ} (x)), \dots, {VIEW}_{P_{i_{n}}}^{ρ} (x)$ , and $\begin{matrix} {OUTPUT}^{ρ} (x) = ({OUTPUT}_{P_{1}}^{ρ} (x), {OUTPUT}_{P_{2}}^{ρ} (x), \dots, {OUTPUT}_{P_{n}}^{ρ} (x)) . \end{matrix}$

Which can simulate the $view$ of the protocol. The protocol is secure and oblivious, if there exists a simulator S for all $I \subset U$ of cardinality at most $t - 1$ and for all x, following holds. Or $\begin{matrix} {(S (I, x_{I}, f_{I} (x)), f (x))} \equiv {({VIEW}_{I}^{ρ} (x), {OUTPUT}^{ρ} (x))} \end{matrix}$ Satisfying the above notions of protocol’s security, the protocols can be specified in a semi-honest adversary model.

3. Oblivious insertion sort protocol

There is a problem with most general sorting algorithms, as they are data-dependent. It is difficult to convert data-dependent algorithms into a MPC environment.

Protocol 1:

Oblivious insertion sort protocol

The work has proposed an oblivious sorting protocol to convert the data-dependent insertion sort algorithm into an oblivious sorting protocol. The proposed work has used the existing protocols such as bit-decomposition and bit-wise less than protocols as building blocks. The proposed oblivious insertion sort protocol is shown as Protocol 1. The input for this protocol are shares of the elements. It returns the shares of sorted values as output. The shares of the input are generated by using Shamir’s secret sharing scheme. The proposed oblivious insertion sort protocol starts from line 6. The bit-decomposition protocol is first applied to the shares of the key and converted into bit shares. The same procedure is repeated in line 7 for the shares of $a_{j}$ , where $j \in 2, \dots, m$ . In the line 8, of the proposed protocol there is a comparison protocol, named BIT-LT. The inputs for this protocol are the outputs of lines 6 and 7. These are the bit shares. The BIT-LT sub-protocol outputs the shares of 1 or 0 depending on the condition. Line 9 reveals the value. A sub-protocol named reconstruct is used to open the value. Though the c value is revealed, it is a share value. The shares are arranged depending on the value of c. Finally, the proposed protocol returns the sorted shared elements.

Security: The proposed protocols do not leak any intermediate results shared among n number of parties secretly. The proposed protocol consists of secured and already proved sub-protocols, named bit-decomposition protocol and bit-wise less than protocol. The two sub-protocols are already proved to be secure, so the proposed protocol is also secure. The only possibility of information leaking would be in the reconstruction step which reveals the value of c. However, the revealed c is a share of the value, not the original value. Therefore, the proposed protocol leaks no additional information.

Theorem 2.

The proposed protocol 1 is oblivious and preserves privacy in the semi-honest adversary model.

Proof.

A protocol should not reveal anything about data in presence of the semi-honest adversary model with $t - 1$ corrupted parties. This can be proved using the simulator concept. As already proved, bit-decomposition protocol and bit-less than protocol are secure [4,22]. The view of these protocols can be simulated. The simulation of these protocols, simulates the protocol. The view of the proposed protocol has to be proved and simulated view of the existing protocol are computationally indistinguishable. It means that, if the protocol is not secured and oblivious in the semi-honest adversary model, then bit-decomposition and bit-less than protocols are also not secure and oblivious in the semi-honest adversary model. It is understood that these protocols are secure and oblivious, our protocol also must be secure and oblivious.

The simulator simulates the views of the protocols. Let $⟦ a_{1} ⟧, ⟦ a_{2} ⟧, \dots, ⟦ a_{m} ⟧$ be the share values which are input to the proposed insertion sort protocol. The view of the adversaries consist of their inputs as ${{{⟦ a_{1} ⟧}_{I}, ⟦ a_{2} ⟧}_{I}, \dots, ⟦ a_{m} ⟧}_{I}$ , outputs are ${{{⟦ b_{1} ⟧}_{I}, ⟦ b_{2} ⟧}_{I}, \dots, ⟦ b_{m} ⟧}_{I}$ , ${⟦ c ⟧}_{I}$ and c. Note that the adversaries have no view of the sub-protocols BITS, BIT-LT and reconstruct, as the execution of these protocols are substituted by the oracle invocation of functions named as $f_{π}^{BITS}$ , $f_{π}^{BIT - LT}$ and $f_{π}^{reconstruct}$ respectively.

The simulator Υ is constructed as follows. Inputs and outputs are the same as those of the adversaries. Simulator Υ select inputs uniformly at random. For the input values $⟦ a_{1} ⟧, ⟦ a_{2} ⟧, \dots, ⟦ a_{m} ⟧$ simulator Υ sets $⟦ a_{1} ⟧, ⟦ a_{2} ⟧, \dots, ⟦ a_{m} ⟧$ as the simulated values. This perfectly simulates the values $⟦ a_{1} ⟧, ⟦ a_{2} ⟧, \dots, ⟦ a_{m} ⟧$ as the correctness of the sub-protocols guarantees that these are equal to $⟦ a_{1} ⟧, ⟦ a_{2} ⟧, \dots, ⟦ a_{m} ⟧$ . For the values $⟦ a_{1} ⟧, ⟦ a_{2} ⟧, \dots, ⟦ a_{m} ⟧$ , ${{{⟦ a_{1} ⟧}_{I}, ⟦ a_{2} ⟧}_{I}, \dots, ⟦ a_{m} ⟧}_{I}$ , $⟦ b_{1} ⟧, ⟦ b_{2} ⟧, \dots, ⟦ b_{m} ⟧$ except for ${{{⟦ b_{1} ⟧}_{I}, ⟦ b_{2} ⟧}_{I}, \dots, ⟦ b_{m} ⟧}_{I}$ , the simulator Υ selects uniformly random numbers and sets them as the simulated values for the shares. Actually, the shares are the outputs of either the BITS sub-protocol, BIT-LT sub-protocol or the reconstruct sub-protocol. These sub-protocols generate the outputs uniformly with random shares. Therefore the above simulation is perfect. Thus simulator Υ perfectly simulates the view of the adversaries. □

Complexity: In multi-party computation, protocols are evaluated based on the round complexity and communication complexity.

Round complexity: The round complexity of a protocol defines the number of rounds of parallel invocations of the communication. In the proposed work we have used the Laura et al. shuffling protocol [19]. The round complexity of shuffling protocol [19] is $O (\frac{2^{m}}{\sqrt{m}} . l)$ rounds, where m is the number of parties and l is the field bit-length of the element. Other sub-protocols used in the proposed protocol take $O (1)$ number of rounds. So the round complexity of the proposed protocol is $O (\frac{2^{m}}{\sqrt{m}} . l)$ .

Communication complexity: The communication complexity of a protocol defines the amount of data transmitted by the parties. The proposed protocol takes $O (\frac{2^{m}}{\sqrt{m}} l^{2} m^{3} n log n)$ communication complexity, where n is number of input values.

For practical implementation, it is assumed that the number of parties m, the field bit-length l is constant, then the proposed protocol exhibits $O (1)$ (constant) round complexity and $O (n log n)$ communication complexity.

4. Oblivious binary search protocol

The binary search algorithm is based on divide-and-conquer design technique. In this design technique the problem is divided into small problems. Recursively, solve small problems and combine these solutions, to obtain a solution to the original (larger) problem. To find a key k, in a large database file containing keys $z [0, 1, \dots n - 1]$ in sorted order. Initially k is compared with $z [\frac{n}{2}]$ . Based on the outcome, recursively binary search algorithm is called for either first half of the database ( $z [0, \dots, \frac{n}{2} - 1]$ ) or second half of the database ( $z [\frac{n}{2}, \dots, n - 1]$ ).

The general binary search is a data dependent algorithm. An oblivious searching protocol is proposed to convert a data-dependent binary search algorithm into an oblivious binary search protocol. A recursive version of the oblivious binary search protocol is proposed. The existing protocols such as bit-decomposition protocol, reconstruct protocol and bit-wise less than protocol are used as building blocks to design the oblivious binary search protocol. The proposed oblivious binary search protocol is shown as Protocol 2. In the proposed protocol, the initialization in line number 1 i.e., $a a_{x} [l] [m], a a_{m} [l] [m]$ is the bit-wise share representation of the number, where l is the number of bits of the share value with each bit having m number of shares.

Protocol 2:

Oblivious binary search protocol

The input for the proposed oblivious binary search protocol consists in shares of the already sorted elements and the shares of the element to be searched. In line 3, mid value is calculated. The actual oblivious searching protocol starts from line 6. In line 6 of the proposed protocol, the shares of the array of the mid element are converted to bit shares. In line 7, the shares of the element to be searched are converted into bit shares of the element. Line 8 is the comparison of the bit shares of line 6 and line 7. Line 8, will generate the shares of either 1 or 0 depending on the condition. Line 9 reveals the value of c. However, when the value of c is revealed, there is no information leakage. It is the only share value. Hence leakage of information is prevented. Depending on c, if it is equal to 1 then there is a recursive call from $0^{t h}$ position to ${(mid - 1)}^{t h}$ position, otherwise a recursive call from ${(mid + 1)}^{t h}$ position to the last position shares. Finally, the output will be shares of the position of the searched element, if it exists in the array or else it will return shares of 0 i.e, $⟦ 0 ⟧$

Theorem 3.

The proposed protocol 2 is oblivious and secure in the semi-honest adversary model.

Proof.

The security of the proposed protocol relies on the security of the MPC primitives such as, bit-decomposition protocol and bit-wise less than protocol. These two sub-protocols are already proved to be secure and so the proposed protocol is also secure. The only possibility of information leakage would be the reconstruction step which reveals the value of c. However, the revealed c is a share of the value and not the original value. Therefore, the proposed protocol leaks no additional information. □

5. Evaluation of our schemes

The proposed work has been compared with the complexity of the existing quick sort protocol. The comparison result is given in Table 1. From a communication point of view, the same results are achieved. On average case the proposed work is better than existing protocol [14]. Experimental results shows that the proposed oblivious sorting protocol works better than the [14], when the input is given in almost sorted order.

Table 1
Comparison of the complexities of already available sorting protocols, where n is the number of input values

Name of Sorting Protocol Rounds Invocations of comparisons

Average Worst Average Worst

AKS Sorting network [1] $O (log n)$ $O (log n)$ $O (n log n)$ $O (n log n)$

Balanced Sort [2] $O ({log}^{2} n)$ $O ({log}^{2} n)$ $O (n {log}^{2} n)$ $O (n {log}^{2} n)$

Quicksort [14] $O (log n)$ $O (n)$ $O (n log n)$ $O (n^{2})$

Our work [section: 3] $O (1)$ $O (n)$ $O (n log n)$ $O (n^{2})$

Name of Sorting Protocol	Rounds	Invocations of comparisons
AKS Sorting network [1]	$O (log n)$	$O (log n)$	$O (n log n)$	$O (n log n)$
Balanced Sort [2]	$O ({log}^{2} n)$	$O ({log}^{2} n)$	$O (n {log}^{2} n)$	$O (n {log}^{2} n)$
Quicksort [14]	$O (log n)$	$O (n)$	$O (n log n)$	$O (n^{2})$
Our work [section: 3]	$O (1)$	$O (n)$	$O (n log n)$	$O (n^{2})$

5.1. Experimental results

The practical efficiency of the proposed sorting protocol is demonstrated in this work. Also, for the comparison of the experimental results, the proposed oblivious insertion sort and traditional quick sort protocols are implemented. The implementation is carried out with (2, 3) Shamir’s secret sharing scheme. Also the bit-decomposition protocol, bit-wise less than protocol [4,22], multiplication protocol, share_construct and reconstruct protocols are implemented as building blocks for the proposed schemes. Here all the values are elements of $Z_{p}$ , a finite field with the elements ${0, 1, \dots, p - 1}$ where p is a prime in the range of $2^{31} < p < 2^{32}$ .

Fig. 1.

Comparison of oblivious insertion sort protocol with existing quick sort [14], when the elements are given in almost sorted order. The sub-figure is a clear view of a comparison of up to 512 elements.

Fig. 2.

Comparison of the oblivious insertion sort protocol with the existing quick sort protocol, when the elements are given in random order. The sub-figure is a clear view of a comparison of up to 512 elements.

All the experiments are implemented on machines configured with an Intel(R) i7-6700 3.41 GHz processor, 16 GB RAM and 64-bit Operating system. The implementation is held in a visual studio code C $+ +$ and TDM g $+ +$ with 1.1309.0 for compiling and running the programs. The comparisons of sorting protocols given in Fig. 1 show that the proposed sorting protocol gives good results in the above setting, when the number of elements is limited and those elements are almost in sorted order. Further, the comparison results are presented for the case where the elements to be sorted are randomly placed, as given in Fig. 2. The number of items to be sorted along the x-axis, and the total execution time in seconds along the y-axis are considered.

Fig. 3.

Performance comparison of the proposed binary search protocol with the general binary search algorithm.

Figure 3 exhibits the comparison of the proposed oblivious binary search protocol with the general binary search algorithm. It shows that the proposed binary search protocol gives good results along with the general binary search algorithm in the above setting. The number of items already sorted to search the element are taken along the x-axis and total execution time in seconds along the y-axis. The proposed oblivious insertion sort protocol is the suitable choice, when the number of elements is limited and the elements are almost in a sorted order. The proposed binary search protocol gives good result, when compared with the general binary search algorithm in a secret-sharing concept.

6. Conclusion

The present work has proposed simple and secure oblivious protocols based on the sorting principles, searching principles, and MPC primitives as building blocks. It is proved that the oblivious insertion sort protocol works better than quick sort protocol, when input elements are almost in sorted order. The proposed oblivious binary search protocol gives almost the same results compared to the general binary search algorithm. The feasibility of the proposed protocols has been demonstrated by an implementation of the MPC scheme based on $(2, 3)$ -Shamir’s secret-sharing scheme with an input length of 32 bits.

References

Ajtai,

Komlós and

Szemerédi, An O(n log n) sorting network, in: Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, 1983, pp. 1–9, ACM.

K.E.

Batcher, Sorting networks and their applications, in: Proceedings of the April 30–May 2, 1968, Spring Joint Computer Conference, 1968, pp. 307–314, ACM.

Bogdanov,

Laur and

Willemson, Sharemind: A framework for fast privacy-preserving computations, in: European Symposium on Research in Computer Security, 2008, pp. 192–206, Springer.

Damgård,

Fitzi,

Kiltz,

J.B.

Nielsen and

Toft, Unconditionally secure constant-rounds multi-party computation for equality, comparison, bits and exponentiation, in: Theory of Cryptography Conference, 2006, pp. 285–304, Springer. doi:10.1007/11681878_15.

Damgård,

Meldgaard and

J.B.

Nielsen, Perfectly secure oblivious RAM without random oracles, in: Theory of Cryptography Conference, 2011, pp. 144–163, Springer. doi:10.1007/978-3-642-19571-6_10.

Dikshit and

Singh, Efficient weighted threshold ECDSA for securing bitcoin wallet, in: 2017 ISEA Asia Security and Privacy (ISEASP), 2017, pp. 1–9, IEEE.

Eslami,

Noroozi and

Baek, On the security of a privacy-preserving ranked multi-keyword search scheme, Journal of Wireless Mobile Networks, Ubiquitous Computing, and Dependable Applications (JoWUA) 10(1) (2019), 75–85.

Goldreich, Foundations of Cryptography: Volume 2, Basic Applications, Cambridge University Press, 2009.

Goldreich,

Micali and

Wigderson, How to play any mental game, in: Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, 1987, pp. 218–229, ACM.

10.

Goldwasser, How to play any mental game, or a completeness theorem for protocols with an honest majority, in: Proc. the Nineteenth Annual ACM STOC’87, 1987, pp. 218–229.

11.

Goldwasser,

Ben-Or and

Wigderson, Completeness theorems for non-cryptographic fault-tolerant distributed computing, in: Proc. of the 20th STOC, 1988, pp. 1–10.

12.

M.T.

Goodrich, Randomized shellsort: A simple oblivious sorting algorithm, in: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010, pp. 1262–1277, Society for Industrial and Applied Mathematics.

13.

M.T.

Goodrich and

Mitzenmacher, Privacy-preserving access of outsourced data via oblivious RAM simulation, in: International Colloquium on Automata, Languages, and Programming, 2011, pp. 576–587, Springer. doi:10.1007/978-3-642-22012-8_46.

14.

Hamada,

Kikuchi,

Ikarashi,

Chida and

Takahashi, Practically efficient multi-party sorting protocols from comparison sort algorithms, in: International Conference on Information Security and Cryptology, 2012, pp. 202–216, Springer.

15.

L.J.

Helsloot,

Tillem and

Erkin, BAdASS: Preserving privacy in behavioural advertising with applied secret sharing, Journal of Wireless Mobile Networks, Ubiquitous Computing, and Dependable Applications (JoWUA) 10(1) (2019), 23–41.

16.

Huang,

Evans and

Katz, Private set intersection: Are garbled circuits better than custom protocols?, in: NDSS, 2012.

17.

Hui,

An,

Wang,

Ju,

Yang,

Gao and

Lin, Survey on blockchain for Internet of things, Journal of Internet Services and Information Security (JISIS) 9(2) (2019), 1–30.

18.

K.V.

Jónsson,

Kreitz and

Uddin, Secure multi-party sorting and applications., IACR Cryptology ePrint Archive 2011 (2011), 122.

19.

Laur,

Willemson and

Zhang, Round-efficient oblivious database manipulation, in: International Conference on Information Security, 2011, pp. 262–277, Springer. doi:10.1007/978-3-642-24861-0_18.

20.

C.L.

Liu, Elements of Discrete Mathematics, Tata McGraw-Hill Education, 1986.

21.

Malkhi,

Nisan,

Pinkas,

Sella et al., Fairplay-secure two-party computation system, in: USENIX Security Symposium, Vol. 4, 2004, p. 9, San Diego, CA, USA.

22.

Nishide and

Ohta, Multiparty computation for interval, equality, and comparison without bit-decomposition protocol, in: International Workshop on Public Key Cryptography, 2007, pp. 343–360, Springer.

23.

Patra, Cryptography, https://www.csa.iisc.ac.in/~arpita/Cryptography15.html, 2015.

24.

C.K.

Rao and

Singh, Securely solving privacy preserving minimum spanning tree algorithms in semi-honest model, International Journal of Ad Hoc and Ubiquitous Computing 34(1) (2020), 1–10. doi:10.1504/IJAHUC.2020.107501.

25.

Singh,

C.P.

Rangan,

Agrawal and

Sheshank, Provably secure lattice based identity based unidirectional PRE and PRE+ schemes, Journal of Information Security and Applications 54 (2020), 102569.

26.

Singh,

C.P.

Rangan and

A.K.

Banerjee, Lattice-based identity-based resplittable threshold public key encryption scheme, International Journal of Computer Mathematics 93(2) (2016), 289–307. doi:10.1080/00207160.2014.928286.

27.

Tal Rabin Technion Secure Multiparty Computation, https://www.youtube.com/watch?v=NOtsxHoIcWQ, 2014.

28.

Wang,

Luo,

M.T.

Goodrich,

Du and

Zhu, Bureaucratic protocols for secure two-party sorting, selection, and permuting, in: Proceedings of the 5th ACM Symposium on Information, Computer and Communications Security, 2010, pp. 226–237, ACM. doi:10.1145/1755688.1755716.

29.

Wang,

Xiao,

Miao,

Liu and

Huang, Signature scheme from trapdoor functions, Journal of Internet Services and Information Security (JISIS) 9(2) (2019), 31–41.

30.

A.C.-C.

Yao, Protocols for secure computations, in: FOCS, Vol. 82, 1982, pp. 160–164.