Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Information theoretically secure computation and inference in networks

Prakash Sharma Ishwar, Ye Wang

Published Jan 1, 2011• 0 citations
OpenAlex

Abstract

In the problem of Secure Multi-party Computation, the objective is to design a protocol that allows a group of parties to securely compute functions of their collective private data, while ensuring that no party reveals any more information about its private data other than what must be inherently revealed by the computation results (privacy) and that no parties can disrupt or influence the computation results beyond the effects of changing their input data (correctness and consistency). Information theoretic approaches toward this problem, that provide provable (unconditional) security guarantees even against adversarial parties that have unbounded computational power, have established that general computation is possible in a variety of scenarios. However, these general solutions are not always efficient or finely tuned to the requirements of specific problems and applications. The focus of this thesis is on the development of information theoretic approaches for multi-party computation applications with the common theme of secure and efficient computation and inference over a distributed data network. Specific applications include: 1) private information retrieval, where the objective is to privately retrieve data without revealing what was selected; 2) secure statistical analysis, the problem of extracting statistics without revealing anything else about the underlying data; 3) secure sampling, which is the secure generation of new data with a given distribution; and 4) secure authentication, where the identity of a party needs to authenticated via inference on his/her credentials and stored registration data. The contributions of this thesis toward addressing these applications include the following: The development of an Oblivious Transfer (OT) protocol, applicable to private information retrieval, that trades off a small amount of privacy while being several times more efficient than other OT protocols. The efficiency of general se- cure two-party computation via OT realized from noisy channels is also analyzed. A technique for approximate secure multi-party computation applicable to secure statistical analysis of large scale distributed databases is developed. By exploiting a dimensionality reduction and the structure of a broad class of functions based on the computed statistics, the feasibility of simultaneously achieving both arbitrarily high accuracy and arbitrarily high communication efficiency is demonstrated. The region of distributions that can be securely sampled in the two-party scenario is characterized. It is further established that for those distributions, it can be accomplished with a protocol that only sends one message. Inner and outer bounds on the region of distributions that can be securely sampled in the general multi-party scenario are also developed. A new three-party protocol, applicable to the problem of secure biometric authentication, that securely computes the Hamming distance even when one of the parties arbitrarily deviates from the protocol is proposed and analyzed. A two-factor secure biometric authentication system that is robust against the compromise of registered biometric data, allowing for revocability and resistance against cross-enrollment attacks is also proposed.

Related papers

A study of secure database access and general two-party computation

Tal Malkin, Shafi Goldwasser

In this thesis, we study two fundamental areas of secure computation over a network.First, we study general two-party secure computation, where two mutually distrustful parties are trying to compute an arbitrary function of their inputs, without revealing any extra information (even if one of them is malicious).We prove that, if any nontrivial function can be so computed, then so can every other function.That is, every non-trivial function is complete for two-party secure computation.Consequently, the complexity assumptions sufficient and/or necessary for securely computing f are the same for every non-trivial function f.Next, we study the concrete problem of secure database access, where the privacy of both the database and the user is to be protected from each other and from all other participating or eavesdropping parties.We are interested in practical and theoretical aspects of this problem, addressing issues of efficiency, security, and complexity.More specifically, we start from the model of private information retrieval (PIR), where users are trying to retrieve information from a database while keeping their queries private from the database owner.We then explore the following directions: * We study the necessary assumptions for single server PIR with low communication.We prove that oblivious transfer is necessary, implying that PIR is a complete primitive for secure computation, and that computational SPIR protocols (defined below) can be efficiently constructed from PIR protocols.* We introduce the model of SPIR, where the privacy of the data, as well as the user, is guaranteed.We show how to efficiently transform PIR protocols into SPIR protocols, for both the information-theoretic and computational settings. "We introduce the random server model for PIR, and show how to use it to achieve information theoretic solutions in which the database need not give away its data to be replicated, and with minimal on-line computation for the database.

•Jan 1, 2000•7 citations

Security, fault tolerance, and communication complexity in distributed systems

Michael O. Rabin, Donald Beaver

We present efficient and practical algorithms for a large, distributed system of processors to achieve reliable computations in a secure manner. Specifically, we address the problem of computing a general function of several private inputs distributed among the processors of a network, while ensuring the correctness of the results and the privacy of the inputs, despite accidental or malicious faults in the system. Communication is often the most significant bottleneck in distributed computing. Our algorithms maintain a low cost in local processing time, are the first to achieve optimal levels of fault-tolerance, and most importantly, have low communication complexity. In contrast to the best known previous methods, which require large numbers of rounds even for fairly simple computations, we devise protocols that use small messages and a constant number of rounds regardless of the complexity of the function to be computed. Through direct algebraic approaches, we separate the communication complexity of secure computing from the computational complexity of the function to be computed. We examine security under both the modern approach of computational complexity-based cryptography and the classical approach of unconditional, information-theoretic security. We develop a clear and concise set of definitions that support formal proofs of claims to security, addressing an important deficiency in the literature. Our protocols are provably secure. In the realm of information-theoretic security, we characterize those functions which two parties can compute jointly with absolute privacy. We also characterize those functions which a weak processor can compute using the aid of powerful processors without having to reveal the instances of the problem it would like to solve. Our methods include a promising new technique called a locally random reduction, which has given rise not only to efficient solutions for many of the problems considered in this work but to several powerful new results in complexity theory.

•Jan 1, 1990•17 citations

Security, Fault Tolerance, and Communication Complexity in Distributed Systems

Donald Beaver

We present efficient and practical algorithms for a large, distributed system of processors to achieve reliable computations in a secure manner. Specifically, we address the problem of computing a general function of several private inputs distributed among the processors of a network, while ensuring the correctness of the results and the privacy of the inputs, despite accidental or malicious faults in the system. [...] Our algorithms maintain a low cost in local processing time, are the first to achieve optimal levels of fault-tolerance, and most importantly, have low communication complexity. In contrast to the best known previous methods, which require large numbers of rounds even for fairly simple computations, we devise protocols that use small messages and a constant number of rounds regardless of the complexity of the function to be computed. Through direct algebraic approaches, we separate the communication complexity of secure computing from the computational complexity of the function to be computed. We examine security under both the modern approach of computational complexity-based cryptography and the classical approach of unconditional, information-theoretic security. We [...] support formal proofs of claims to security, addressing an important deficiency in the literature. Our protocols are provably secure. In the realm of information-theoretic security, we characterize those functions which two parties can compute jointly with absolute privacy. We also characterize those functions which a weak processor can compute using the aid of powerful processors without having to reveal the instances of the problem it would like to solve. Our methods include a promising new technique called a locally random reduction, which has given rise not only to efficient solutions for many of the problems considered in this work but to several powerful new results in complexity theory.

arXiv:2101.12143•Jan 28, 2021•9 citations

Efficient Linear Secure Computation and Symmetric Private Information Retrieval Protocols

Yanliang Zhou

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.

•Dec 1, 2020•0 citations

Secure Computation in Heterogeneous Environments: How to Bring Multiparty Computation Closer to Practice?

Raykova, Mariana Petrova

Many services that people use daily require computation that depends on the private data of multiple parties. While the utility of the final result of such interactions outweighs the privacy concerns related to output release, the inputs for such computations are much more sensitive and need to be protected. Secure multiparty computation (MPC) considers the question of constructing computation protocols that reveal nothing more about their inputs than what is inherently leaked by the output. There have been strong theoretical results that demonstrate that every functionality can be computed securely. However, these protocols remain unused in practical solutions since they introduce efficiency overhead prohibitive for most applications. Generic multiparty computation techniques address homogeneous setups with respect to the resources available to the participants and the adversarial model. On the other hand, realistic scenarios present a wide diversity of heterogeneous environments where different participants have different available resources and different incentives to misbehave and collude. In this thesis we introduce techniques for multiparty computation that focus on heterogeneous settings. We present solutions tailored to address different types of asymmetric constraints and improve the efficiency of existing approaches in these scenarios. We tackle the question from three main directions: New Computational Models for MPC - We explore different computational models that enable us to overcome inherent inefficiencies of generic MPC solutions using circuit representation for the evaluated functionality. First, we show how we can use random access machines to construct MPC protocols that add only polylogarithmic overhead to the running time of the insecure version of the underlying functionality. This allows to achieve MPC constructions with computational complexity sublinear in the size for their inputs, which is very important for computations that use large databases. We also consider multivariate polynomials which yield more succinct representations for the functionalities they implement than circuits, and at the same time a large collection of problems are naturally and efficiently expressed as multivariate polynomials. We construct an MPC protocol for multivariate polynomials, which improves the communication complexity of corresponding circuit solutions, and provides currently the most efficient solution for multiparty set intersection in the fully malicious case. Outsourcing Computation - The goal in this setting is to utilize the resources of a single powerful service provider for the work that computationally weak clients need to perform on their data. We present a new paradigm for constructing verifiable computation (VC) schemes, which enables a computationally limited client to verify efficiently the result of a large computation. Our construction is based on attribute-based encryption and avoids expensive primitives such as fully homomorphic encryption andprobabilistically checkable proofs underlying existing VC schemes. Additionally our solution enjoys two new useful properties: public delegation and verification. We further introduce the model of server-aided computation where we utilize the computational power of an outsourcing party to assist the execution and improve the efficiency of MPC protocols. For this purpose we define a new adversarial model of non-collusion, which provides room for more efficient constructions that rely almost completely only on symmetric key operations, and at the same time captures realistic settings for adversarial behavior. In this model we propose protocols for generic secure computation that offload the work of most of the parties to the computation server. We also construct a specialized server-aided two party set intersection protocol that achieves better efficiencies for the two participants than existing solutions. Outsourcing in many cases concerns only data storage and while outsourcing the data of a single party is useful, providing a way for data sharing among different clients of the service is the more interesting and useful setup. However, this scenario brings new challenges for access control since the access control rules and data accesses become private data for the clients with respect to the service provide. We propose an approach that offers trade-offs between the privacy provided for the clients and the communication overhead incurred for each data access. Efficient Private Search in Practice - We consider the question of private search from a different perspective compared to traditional settings for MPC. We start with strict efficiency requirements motivated by speeds of available hardware and what is considered acceptable overhead from practical point of view. Then we adopt relaxed definitions of privacy, which still provide meaningful security guarantees while allowing us to meet the efficiency requirements. In this setting we design a security architecture and implement a system for data sharing based on encrypted search, which achieves only 30% overhead compared to non-secure solutions on realistic workloads.

•Jan 1, 2012•4 citations

A GEOMETRIC FRAMEWORK FOR DECIDING THE FEASIBILITY AND COMMUNICATION COMPLEXITY OF SECURE TWO-PARTY COMPUTATION

Hamidreza Amini Khorasgani

Secure multi-party computation (MPC) enables mutually distrusting parties to compute functions over private inputs without revealing additional information. A general MPC protocol is the one that can be used to securely compute any function. General MPC requires either an honest majority or oblivious transfer, which can be provided via computational assumptions, a black-box hybrid, or trusted hardware. However, in the setting of dishonest majority, there are still many tasks that can be computed securely in the information-theoretic plain model without relying on oblivious transfer or any other computational hardness assumptions. Such protocols are perfectly secure, fast, and do not require any setup or preprocessing.This thesis investigates the feasibility and complexity of secure two-party computation, which inherently falls under the dishonest majority setting, with randomized output in the information-theoretic plain model against honest-but-curious adversaries. For deterministic output functions, seminal work by Chor, Kushilevitz, and Beaver provided a complete characterization of which computations admit secure protocols. In contrast, randomized functionalities give rise to a substantially richer landscape, where questions of round complexity, communication complexity, and even decidability have remained unresolved for decades.The thesis develops a geometric framework for analyzing secure computation by encoding candidate private-coin secure protocols for a given functionality as points in high-dimensional spaces. Within this representation, the space of all secure protocols forms recursively defined geometric sets whose structure can be studied using tools from real algebraic geometry and convex analysis. This perspective enables feasibility, search, and optimization problems in secure computation to be reduced to structural properties of these sets.Using this framework, the thesis establishes that determining whether a given two-party functionality with randomized output admits a secure protocol is decidable. A finite procedure is provided that either constructs a secure protocol with optimal round and communication complexity or identifies a geometric obstruction to security, resolving a foundational open problem in secure computation and information complexity. These results rely on showing that certain lamination hulls arising in the analysis are semi-algebraic, which is achieved by reducing the problem to solving systems of linear inequalities over convex sets. To this end, the thesis introduces a Gaussian-elimination-inspired algorithm and a new set operator, the positive geometric join, leading to a class of algebraically well-behaved geometric objects called hemihedra.The thesis also studies the round and communication complexity of secure computation with randomized output and disproves a longstanding folklore conjecture asserting that round complexity depends only on the cardinalities of the input and output domains. Explicit constructions demonstrate the existence of securely realizable functions with arbitrarily high round complexity, even for fixed size inputs and outputs, while matching upper bounds are proved for small output alphabets. These results reveal a close connection between secure computation and lamination hulls originally studied in hydrodynamics, highlighting unexpected geometric structure underlying information-theoretic security.

•Mar 9, 2026•0 citations
In the problem of Secure Multi-party Computation, the objective is to design a protocol that allows a group of parties to securely compute functions of their collective private data, while ensuring that no party reveals any more information about its private data other than what must be inherently revealed by the computation results (privacy) and that no parties can disrupt or influence the computation results beyond the effects of changing their input data (correctness and consistency). Information theoretic approaches toward this problem, that provide provable (unconditional) security guarantees even against adversarial parties that have unbounded computational power, have established that general computation is possible in a variety of scenarios. However, these general solutions are not always efficient or finely tuned to the requirements of specific problems and applications.
The focus of this thesis is on the development of information theoretic approaches for multi-party computation applications with the common theme of secure and efficient computation and inference over a distributed data network. Specific applications include: 1) private information retrieval, where the objective is to privately retrieve data without revealing what was selected; 2) secure statistical analysis, the problem of extracting statistics without revealing anything else about the underlying data; 3) secure sampling, which is the secure generation of new data with a given distribution; and 4) secure authentication, where the identity of a party needs to authenticated via inference on his/her credentials and stored registration data.
The contributions of this thesis toward addressing these applications include the following: The development of an Oblivious Transfer (OT) protocol, applicable to private information retrieval, that trades off a small amount of privacy while being several times more efficient than other OT protocols. The efficiency of general se- cure two-party computation via OT realized from noisy channels is also analyzed. A technique for approximate secure multi-party computation applicable to secure statistical analysis of large scale distributed databases is developed. By exploiting a dimensionality reduction and the structure of a broad class of functions based on the computed statistics, the feasibility of simultaneously achieving both arbitrarily high accuracy and arbitrarily high communication efficiency is demonstrated. The region of distributions that can be securely sampled in the two-party scenario is characterized. It is further established that for those distributions, it can be accomplished with a protocol that only sends one message. Inner and outer bounds on the region of distributions that can be securely sampled in the general multi-party scenario are also developed. A new three-party protocol, applicable to the problem of secure biometric authentication, that securely computes the Hamming distance even when one of the parties arbitrarily deviates from the protocol is proposed and analyzed. A two-factor secure biometric authentication system that is robust against the compromise of registered biometric data, allowing for revocability and resistance against cross-enrollment attacks is also proposed.
In this thesis, we study two fundamental areas of secure computation over a network.First, we study general two-party secure computation, where two mutually distrustful parties are trying to compute an arbitrary function of their inputs, without revealing any extra information (even if one of them is malicious).We prove that, if any nontrivial function can be so computed, then so can every other function.That is, every non-trivial function is complete for two-party secure computation.Consequently, the complexity assumptions sufficient and/or necessary for securely computing f are the same for every non-trivial function f.Next, we study the concrete problem of secure database access, where the privacy of both the database and the user is to be protected from each other and from all other participating or eavesdropping parties.We are interested in practical and theoretical aspects of this problem, addressing issues of efficiency, security, and complexity.More specifically, we start from the model of private information retrieval (PIR), where users are trying to retrieve information from a database while keeping their queries private from the database owner.We then explore the following directions: * We study the necessary assumptions for single server PIR with low communication.We prove that oblivious transfer is necessary, implying that PIR is a complete primitive for secure computation, and that computational SPIR protocols (defined below) can be efficiently constructed from PIR protocols.* We introduce the model of SPIR, where the privacy of the data, as well as the user, is guaranteed.We show how to efficiently transform PIR protocols into SPIR protocols, for both the information-theoretic and computational settings. "We introduce the random server model for PIR, and show how to use it to achieve information theoretic solutions in which the database need not give away its data to be replicated, and with minimal on-line computation for the database.
We present efficient and practical algorithms for a large, distributed system of processors to achieve reliable computations in a secure manner. Specifically, we address the problem of computing a general function of several private inputs distributed among the processors of a network, while ensuring the correctness of the results and the privacy of the inputs, despite accidental or malicious faults in the system. Communication is often the most significant bottleneck in distributed computing. Our algorithms maintain a low cost in local processing time, are the first to achieve optimal levels of fault-tolerance, and most importantly, have low communication complexity. In contrast to the best known previous methods, which require large numbers of rounds even for fairly simple computations, we devise protocols that use small messages and a constant number of rounds regardless of the complexity of the function to be computed. Through direct algebraic approaches, we separate the communication complexity of secure computing from the computational complexity of the function to be computed. We examine security under both the modern approach of computational complexity-based cryptography and the classical approach of unconditional, information-theoretic security. We develop a clear and concise set of definitions that support formal proofs of claims to security, addressing an important deficiency in the literature. Our protocols are provably secure. In the realm of information-theoretic security, we characterize those functions which two parties can compute jointly with absolute privacy. We also characterize those functions which a weak processor can compute using the aid of powerful processors without having to reveal the instances of the problem it would like to solve. Our methods include a promising new technique called a locally random reduction, which has given rise not only to efficient solutions for many of the problems considered in this work but to several powerful new results in complexity theory.
We present efficient and practical algorithms for a large, distributed system of processors to achieve reliable computations in a secure manner. Specifically, we address the problem of computing a general function of several private inputs distributed among the processors of a network, while ensuring the correctness of the results and the privacy of the inputs, despite accidental or malicious faults in the system. [...] Our algorithms maintain a low cost in local processing time, are the first to achieve optimal levels of fault-tolerance, and most importantly, have low communication complexity. In contrast to the best known previous methods, which require large numbers of rounds even for fairly simple computations, we devise protocols that use small messages and a constant number of rounds regardless of the complexity of the function to be computed. Through direct algebraic approaches, we separate the communication complexity of secure computing from the computational complexity of the function to be computed. We examine security under both the modern approach of computational complexity-based cryptography and the classical approach of unconditional, information-theoretic security. We [...] support formal proofs of claims to security, addressing an important deficiency in the literature. Our protocols are provably secure. In the realm of information-theoretic security, we characterize those functions which two parties can compute jointly with absolute privacy. We also characterize those functions which a weak processor can compute using the aid of powerful processors without having to reveal the instances of the problem it would like to solve. Our methods include a promising new technique called a locally random reduction, which has given rise not only to efficient solutions for many of the problems considered in this work but to several powerful new results in complexity theory.
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.
Many services that people use daily require computation that depends on the private data of multiple parties. While the utility of the final result of such interactions outweighs the privacy concerns related to output release, the inputs for such computations are much more sensitive and need to be protected. Secure multiparty computation (MPC) considers the question of constructing computation protocols that reveal nothing more about their inputs than what is inherently leaked by the output. There have been strong theoretical results that demonstrate that every functionality can be computed securely. However, these protocols remain unused in practical solutions since they introduce efficiency overhead prohibitive for most applications. Generic multiparty computation techniques address homogeneous setups with respect to the resources available to the participants and the adversarial model. On the other hand, realistic scenarios present a wide diversity of heterogeneous environments where different participants have different available resources and different incentives to misbehave and collude. In this thesis we introduce techniques for multiparty computation that focus on heterogeneous settings. We present solutions tailored to address different types of asymmetric constraints and improve the efficiency of existing approaches in these scenarios. We tackle the question from three main directions: New Computational Models for MPC - We explore different computational models that enable us to overcome inherent inefficiencies of generic MPC solutions using circuit representation for the evaluated functionality. First, we show how we can use random access machines to construct MPC protocols that add only polylogarithmic overhead to the running time of the insecure version of the underlying functionality. This allows to achieve MPC constructions with computational complexity sublinear in the size for their inputs, which is very important for computations that use large databases. We also consider multivariate polynomials which yield more succinct representations for the functionalities they implement than circuits, and at the same time a large collection of problems are naturally and efficiently expressed as multivariate polynomials. We construct an MPC protocol for multivariate polynomials, which improves the communication complexity of corresponding circuit solutions, and provides currently the most efficient solution for multiparty set intersection in the fully malicious case. Outsourcing Computation - The goal in this setting is to utilize the resources of a single powerful service provider for the work that computationally weak clients need to perform on their data. We present a new paradigm for constructing verifiable computation (VC) schemes, which enables a computationally limited client to verify efficiently the result of a large computation. Our construction is based on attribute-based encryption and avoids expensive primitives such as fully homomorphic encryption andprobabilistically checkable proofs underlying existing VC schemes. Additionally our solution enjoys two new useful properties: public delegation and verification. We further introduce the model of server-aided computation where we utilize the computational power of an outsourcing party to assist the execution and improve the efficiency of MPC protocols. For this purpose we define a new adversarial model of non-collusion, which provides room for more efficient constructions that rely almost completely only on symmetric key operations, and at the same time captures realistic settings for adversarial behavior. In this model we propose protocols for generic secure computation that offload the work of most of the parties to the computation server. We also construct a specialized server-aided two party set intersection protocol that achieves better efficiencies for the two participants than existing solutions. Outsourcing in many cases concerns only data storage and while outsourcing the data of a single party is useful, providing a way for data sharing among different clients of the service is the more interesting and useful setup. However, this scenario brings new challenges for access control since the access control rules and data accesses become private data for the clients with respect to the service provide. We propose an approach that offers trade-offs between the privacy provided for the clients and the communication overhead incurred for each data access. Efficient Private Search in Practice - We consider the question of private search from a different perspective compared to traditional settings for MPC. We start with strict efficiency requirements motivated by speeds of available hardware and what is considered acceptable overhead from practical point of view. Then we adopt relaxed definitions of privacy, which still provide meaningful security guarantees while allowing us to meet the efficiency requirements. In this setting we design a security architecture and implement a system for data sharing based on encrypted search, which achieves only 30% overhead compared to non-secure solutions on realistic workloads.
Secure multi-party computation (MPC) enables mutually distrusting parties to compute functions over private inputs without revealing additional information. A general MPC protocol is the one that can be used to securely compute any function. General MPC requires either an honest majority or oblivious transfer, which can be provided via computational assumptions, a black-box hybrid, or trusted hardware. However, in the setting of dishonest majority, there are still many tasks that can be computed securely in the information-theoretic plain model without relying on oblivious transfer or any other computational hardness assumptions. Such protocols are perfectly secure, fast, and do not require any setup or preprocessing.This thesis investigates the feasibility and complexity of secure two-party computation, which inherently falls under the dishonest majority setting, with randomized output in the information-theoretic plain model against honest-but-curious adversaries. For deterministic output functions, seminal work by Chor, Kushilevitz, and Beaver provided a complete characterization of which computations admit secure protocols. In contrast, randomized functionalities give rise to a substantially richer landscape, where questions of round complexity, communication complexity, and even decidability have remained unresolved for decades.The thesis develops a geometric framework for analyzing secure computation by encoding candidate private-coin secure protocols for a given functionality as points in high-dimensional spaces. Within this representation, the space of all secure protocols forms recursively defined geometric sets whose structure can be studied using tools from real algebraic geometry and convex analysis. This perspective enables feasibility, search, and optimization problems in secure computation to be reduced to structural properties of these sets.Using this framework, the thesis establishes that determining whether a given two-party functionality with randomized output admits a secure protocol is decidable. A finite procedure is provided that either constructs a secure protocol with optimal round and communication complexity or identifies a geometric obstruction to security, resolving a foundational open problem in secure computation and information complexity. These results rely on showing that certain lamination hulls arising in the analysis are semi-algebraic, which is achieved by reducing the problem to solving systems of linear inequalities over convex sets. To this end, the thesis introduces a Gaussian-elimination-inspired algorithm and a new set operator, the positive geometric join, leading to a class of algebraically well-behaved geometric objects called hemihedra.The thesis also studies the round and communication complexity of secure computation with randomized output and disproves a longstanding folklore conjecture asserting that round complexity depends only on the cardinalities of the input and output domains. Explicit constructions demonstrate the existence of securely realizable functions with arbitrarily high round complexity, even for fixed size inputs and outputs, while matching upper bounds are proved for small output alphabets. These results reveal a close connection between secure computation and lamination hulls originally studied in hydrodynamics, highlighting unexpected geometric structure underlying information-theoretic security.