Fair exchange with a semi-trusted third party (extended abstract)

By M. Franklin, M. Reiter. 1997

We present new protocols for two parties to exchange documents with fairness, i.e., such that no party can gain an advantage by quitting prematurely or otherwise misbehaving. We use a third party that is L‘semi-trusted”, in the sense that it may misbehave on its own but will not conspire with either of the main parties. In our solutions, disruption by any one of the three parties will not allow the disrupter gain any useful new information about the documents. Our solutions are efficient and can be based on any of several cryptographic assumptions (e.g., factoring, discrete log, graph isomorpbism). We also discuss the application of our techniques to electronic commerce protocols to achieve fair payment.

Subfields: Privacy & Security

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Privacy & Security

Citations in the corpus

Real-World Image Datasets for Federated Learning (2019, neutral): “…the challenge of data privacy and security in 88 127 Figure 2: The distribution of labels per image. the machine learning process, many privacy-preserving machine learning methods have been proposed in the past, such as secure multi-party computing (MPC) in the 1980s [ Yao, 1982; Yao, 1986 ] .”
Distributed learning of deep neural network over multiple agents (2018, background): “Such algorithms form a subset inside the broader realm of multi-party protocol problems involving secure computation over several parties [26, 27].”
Private federated learning on vertically partitioned data via entity resolution and additively homomorphic encryption (2017, background): “…provided by more traditional cryptographic guarantees such as homomorphic encryption, e.g. Paillier [Paillier, 1999] or Brakerski-Gentry-Vaikuntanathan cryptosystems [Gentry, 2009], secure multi-party computation, e.g. as garbled circuits [Yao, 1986] and secret sharing [Ben-Or et al., 1988].”
Prio: Private, Robust, and Scalable Computation of Aggregate Statistics (2017, background): “In theory, secure multi-party computation (MPC) protocols [11, 15, 68, 90, 123] allow a set of servers, with some”
A Comprehensive Comparison of Multiparty Secure Additions with Differential Privacy (2015, methodology): “Secure two-party computations has been defined by Yao, who presented a solution to the Millionaires’ Problem, where two millionaires want to find out, who is richer without disclosing their actual wealth [55].”
Privacy Preserving Data Mining (2015, background): “Multi-party computation has been considered by the theoretical cryptography community for a long time, starting with the pioneering work of Yao [11] in 1986.”
Privacy-Preserving Ridge Regression on Hundreds of Millions of Records (2013, methodology): “The Evaluator learns β, the model describing the best linear curve fit to the data (x i , y i ), i = 1, . . . , n, without seeing the data in the clear. construction [3] to obtain the final model without learning anything else about user data (we further expand on these in Section VII).”
Secure Multiparty Computation for Privacy-Preserving Data Mining (2009, background): “Yao’s protocol works by having one of the parties (say, Alice) first generate an “encrypted” or “garbled” circuit computing f , and send its representation to Bob.”
ObliVM: A Programming Framework for Secure Computation (2015, background): “…with public topological structure but secret pernode data can be defined without using pointers (assuming its capacity is 1000 nodes): struct KeyValueTable<T> { secure int10[public 1000] keys; T[public 1000] values; }; In the above, the type int10 means that its value is a 10-bit signed integer.”
Data-oblivious graph algorithms for secure computation and outsourcing (2013, methodology): “The solution uses Yao’s protocol [41] as the primary building block and achieves better efficiency than naively applying Yao’s protocol to existing graph algorithms.”
A Privacy Preserving Probabilistic Neural Network for Horizontally Partitioned Databases (2007, background): “SMC has as one of its pillars Yao's work to solve the Millionaire's Problem [5].”
Foundations of garbled circuits (2012, methodology): “Garble1 and Garble2 are close to numerous other protocols (especially [46]) that incarnate Yao’s idea.”
EPIC: Efficient Private Image Classification (or: Learning from the Masters) (2019, background): “This line of research, much like ours, originates from Yao’s millionaire problem [56], describing two-party computation, and its extension to multiparty computation [21] to securely compute any generic function.”
Faster Secure Two-Party Computation Using Garbled Circuits (2011, methodology): “The second approach relies on completeness theorems for secure computation [7, 8, 34] which give protocols for computing any function f starting from a Boolean-circuit representation of f .”
Computationally Secure Oblivious Transfer (2004, background): “However, the efficiency of the resulting protocols is often not satisfactory since the number of cryptographic operations performed is proportional to the size of the circuit computing f (x, y) [51], [31].”
Scalable Private Set Intersection Based on OT Extension (2018, methodology): “Two of the most prominent generic secure computation protocols in the semi-honest model are the Goldreich-Micali-Wigderson (GMW) protocol [Goldreich et al. 1987] and Yao’s garbled circuits protocol [Yao 1986].”
Privacy-Preserving Inter-database Operations (2004, background): “Yao first investigated the secure two party computation problem [24].”