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

IEEE Transactions on Information Forensics and Security

Unconditionally Secure, Universally Composable Privacy Preserving Linear Algebra

Bernardo David, Rafael Dowsley, Jeroen van de Graaf, Davidson Marques, Anderson C. A. Nascimento, Adriana C. B. Pinto

Published Sep 3, 2015• 17 citations
Publisher

Abstract

Linear algebra operations on private distributed data are frequently required in several practical scenarios (e.g., statistical analysis and privacy preserving databases). We present universally composable two-party protocols to compute inner products, determinants, eigenvalues, and eigenvectors. These protocols are built for a two-party scenario where the inputs are provided by mutually distrustful parties. After execution, the protocols yield the results of the intended operation while preserving the privacy of their inputs. Universal composability is obtained in the trusted initializer model, ensuring information theoretical security under arbitrary protocol composition in complex environments. Furthermore, our protocols are computationally efficient since they only require field multiplication and addition operations.

DOI
10.1109/tifs.2015.2476783

Related papers

Comments on “Unconditionally Secure, Universally Composable Privacy Preserving Linear Algebra”

Babak Siabi, Mehdi Berenjkoub

In this paper, we discuss the security of a distributed inner product (DIP) protocol [IEEE Trans. Inf. Forensics Security, 11.1, 59, (2016)]. We show information leakage in this protocol that does not happen in an ideal execution of the DIP functionality. In some scenarios, this information leakage enables one of the parties to completely learn the other party's input. We will give examples of such scenarios.

arXiv:1809.08441•IEEE Transactions on Information Forensics and Security•May 23, 2019•2 citations

A Two-Party Protocol with Trusted Initializer for Computing the Inner Product.

Rafael Dowsley, Jeroen van de Graaf, Davidson Marques +1 more

Abstract. We propose the first protocol for securely computing the inner product modulo an integer m between two distrustful parties based on a trusted initializer, i.e. a trusted party that interacts with the players solely during a setup phase. We obtain a very simple protocol with universally composable security. As an application of our protocol, we obtain a solution for securely computing linear equations. 1

•Jan 1, 2010•0 citations

From Input Private to Universally Composable Secure Multi-party Computation Primitives

Dan Bogdanov, Peeter Laud, Sven Laur +1 more

Secure multi-party computation systems are commonly built from a small set of primitive components. The compos ability of security notions has a central role in the analysis of such systems, as it allows us to deduce security properties of complex protocols from the properties of its components. We show that the standard notions of universally compos able security are overly restrictive in this context and can lead to protocols with sub-optimal performance. As a remedy, we introduce a weaker notion of privacy that is satisfied by simpler protocols and is preserved by composition. After that we fix a passive security model and show how to convert a private protocol into a universally compos able protocol. As a result, we obtain modular security proofs without performance penalties.

IEEE Computer Security Foundations Workshop (CSFW)•Jul 1, 2014•25 citations

Information theoretically secure computation and inference in networks

Prakash Sharma Ishwar, Ye Wang

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.

•Jan 1, 2011•0 citations

Oblivious and Fair Server-Aided Two-Party Computation

Amir Herzberg

We show efficient, practical (server-aided) secure two-party computation protocols ensuring privacy, correctness and fairness in the presence of malicious (Byzantine) faults. Our requirements from the server are modest. To ensure privacy and correctness, we only assume trusted execution service, executing an initialization program provided by both parties. To further ensure fairness, we further assume a trusted-decryption service, providing decryption service using known public key. Both of these trusted services are feasible in practice, and may be useful for additional tasks; both can also be distributed, with linear overhead, for redundancy. Formally, we model them as ideal functionalities, allowing proof of security using the hybrid model. Our fairness-ensuring protocol is optimistic, i.e., the decryption service is invoked only in case of faults. We believe that the protocols are sufficiently efficient, to allow deployment, in particular for financial applications.

•Jan 1, 2012•1 citation

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
Linear algebra operations on private distributed data are frequently required in several practical scenarios (e.g., statistical analysis and privacy preserving databases). We present universally composable two-party protocols to compute inner products, determinants, eigenvalues, and eigenvectors. These protocols are built for a two-party scenario where the inputs are provided by mutually distrustful parties. After execution, the protocols yield the results of the intended operation while preserving the privacy of their inputs. Universal composability is obtained in the trusted initializer model, ensuring information theoretical security under arbitrary protocol composition in complex environments. Furthermore, our protocols are computationally efficient since they only require field multiplication and addition operations.
Secure multi-party computation systems are commonly built from a small set of primitive components. The compos ability of security notions has a central role in the analysis of such systems, as it allows us to deduce security properties of complex protocols from the properties of its components. We show that the standard notions of universally compos able security are overly restrictive in this context and can lead to protocols with sub-optimal performance. As a remedy, we introduce a weaker notion of privacy that is satisfied by simpler protocols and is preserved by composition. After that we fix a passive security model and show how to convert a private protocol into a universally compos able protocol. As a result, we obtain modular security proofs without performance penalties.
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.
We show efficient, practical (server-aided) secure two-party computation protocols ensuring privacy, correctness and fairness in the presence of malicious (Byzantine) faults. Our requirements from the server are modest. To ensure privacy and correctness, we only assume trusted execution service, executing an initialization program provided by both parties. To further ensure fairness, we further assume a trusted-decryption service, providing decryption service using known public key. Both of these trusted services are feasible in practice, and may be useful for additional tasks; both can also be distributed, with linear overhead, for redundancy. Formally, we model them as ideal functionalities, allowing proof of security using the hybrid model. Our fairness-ensuring protocol is optimistic, i.e., the decryption service is invoked only in case of faults. We believe that the protocols are sufficiently efficient, to allow deployment, in particular for financial applications.
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.