Secure multiparty computation refers to the problem where a number of users wish to securely compute a function on their inputs without revealing any unnecessary information. This dissertation focuses on the fundamental limits of secure summation under different constraints. We first focus on the minimal model of secure computation, in which two users each hold an input and wish to securely compute a function of their inputs at the server. We propose a novel scheme base on the algebraic structure of finite field and modulo ring of integers. Then we extend the minimal model of secure computation, in which K users wish to securely compute the sum of their inputs at the server. We prove a folklore result on the limits of communication cost and randomness cost. Then we characterized the optimal communication cost with user dropouts constraint, when some users may lose connection to the server and the server wishes to compute the sum of remaining inputs. Next, we characterize the optimal communication and randomness cost for symmetric groupwise keys and find the feasibility condition for arbitrary groupwise keys. Last, we study the secure summation with user selection, such that the server may select any subset of users to compute the sum of their inputs. This leads us to the MDS variable generation problem. We characterize the optimal individual key rate and the result is interestingly the harmonic number.
Secure multiparty computation refers to the problem where a number of users wish to securely compute a function on their inputs without revealing any unnecessary information. This dissertation focuses on the fundamental limits of secure summation under different constraints. We first focus on the minimal model of secure computation, in which two users each hold an input and wish to securely compute a function of their inputs at the server. We propose a novel scheme base on the algebraic structure of finite field and modulo ring of integers. Then we extend the minimal model of secure computation, in which K users wish to securely compute the sum of their inputs at the server. We prove a folklore result on the limits of communication cost and randomness cost. Then we characterized the optimal communication cost with user dropouts constraint, when some users may lose connection to the server and the server wishes to compute the sum of remaining inputs. Next, we characterize the optimal communication and randomness cost for symmetric groupwise keys and find the feasibility condition for arbitrary groupwise keys. Last, we study the secure summation with user selection, such that the server may select any subset of users to compute the sum of their inputs. This leads us to the MDS variable generation problem. We characterize the optimal individual key rate and the result is interestingly the harmonic number.
A collection ofKrandom variables are called(K,n)-MDS if anynof theKvariables are independent and determine all remaining variables. In the MDS variable generation problem,Kusers wish to generate variables that are(K,n)-MDS using a randomness variable owned by each user. We show that to generate 1 bit of(K,n)-MDS variables for eachn∈{1,2,⋯,K}, the minimum size of the randomness variable at each user is1+1/2+⋯+1/Kbits. An intimately related problem is secure summation with user selection, where a server may select an arbitrary subset ofKusers and securely compute the sum of the inputs of the selected users. We show that to compute 1 bit of an arbitrarily chosen sum securely, the minimum size of the key held by each user is1+1/2+⋯+1/(K−1)bits, whose achievability uses the generation of(K,n)-MDS variables forn∈{1,2,⋯,K−1}.
In secure summation,Kusers, each holds an input, wish to compute the sum of the inputs at a server without revealing any information aboutall the inputseven if the server may collude withan arbitrary subset of users. In this work, we relax the security and colluding constraints, where the set of inputs whose information is prohibited from leakage is from a predetermined collection of sets (e.g., any set of up toSinputs) and the set of colluding users is from another predetermined collection of sets (e.g., any set of up toTusers). For arbitrary collection of security input sets and colluding user sets, we characterize the optimal randomness assumption, i.e., the minimum number of key bits that need to be held by the users, per input bit, for weakly secure summation to be feasible, which generally involves solving a linear program.
Secure summation is one of the most applicable functions of secure multiparty computation (MPC) in which a group of users securely computes the summation value of their private inputs. The current solutions to this problem are basically on adding a random number to private inputs or splitting the inputs among users which need secure channel among members. Moreover, to be resistant against collusion of n − 2 players, they impose high communication cost. In this paper, we propose three cryptography-based protocols for secure sum that do not need secure channel and are secure against collusion of n − 2 players. Also, the communication cost of the proposed protocols is of complexity O(n). Based on the privacy requirements, the proposed protocols can provide the final result privacy as well as the private input privacy.
Secure summation is one of the most applicable functions of secure multiparty computation (MPC) in which a group of users securely computes the summation value of their private inputs. The current solutions to this problem are basically on adding a random number to private inputs or splitting the inputs among users which need secure channel among members. Moreover, to be resistant against collusion of n − 2 players, they impose high communication cost. In this paper, we propose three cryptography-based protocols for secure sum that do not need secure channel and are secure against collusion of n − 2 players. Also, the communication cost of the proposed protocols is of complexity O(n). Based on the privacy requirements, the proposed protocols can provide the final result privacy as well as the private input privacy.
Security and privacy are of paramount importance in the modern information age. Secure multi-party computation and private information retrieval are canonical and representative problems in cryptography that capture the key challenges in understanding the fundamentals of security and privacy. In this dissertation, we use information theoretic tools to tackle these two classical cryptographic primitives. In the first part, we consider the secure multi-party computation problem, where multiple users, each holding an independent message, wish to compute a function on the messages without revealing any additional information. We present an efficient protocol in terms of randomness cost to securely compute a vector linear function. In the second part, we discuss the symmetric private information retrieval problem, where a user wishes to retrieve one message from a number of replicated databases while keeping the desired message index a secret from each individual database. Further, the user learns nothing about the other messages. We present an optimal protocol that achieves the minimum upload cost for symmetric private information retrieval, i.e., the queries sent from the user to the databases have the minimum number of bits.
In secure summation, K parties each hold an input, and the sum of the inputs is computed at one party, securely against at most T colluding parties. Communication typically takes one hop: each party sends one message directly to the party that computes the sum, using correlated randomness that is independent of the inputs and held in advance. We consider interactive secure summation, where every pair of parties is connected by a secure link, so that each party can send messages to every other party, each party has only independent local randomness, and the messages may depend on the inputs and on earlier messages over multiple rounds. We characterize the capacity region, the set of achievable rates of communication, counting all messages exchanged among the parties over all rounds, and of the randomness of every party, counted in symbols per symbol of the sum. For 0≤T≤K−2, the optimal communication rate is K(K−1)/(K−T), and the randomness rates form a polyhedron with, up to a relabeling of the parties, a single extreme point: T parties have the randomness rates (K+T−2t)/(K−T), t=1,…,T, and the others none. In particular, the optimal total randomness rate is T(K−1)/(K−T). Linear schemes achieve every extreme point together with the optimal communication rate. The same techniques give the capacity region when every party recovers the sum and when the sum is computed at a server without input.