Project topics and materials
Get Complete Project Material File(s) Now! »
Background and related work
This chapter establishes a base for this thesis by explaining the major pillars which support the the proposed model. The three major sections in this chapter explain Secure Multi-Party Computation, the Virtual Ideal Functionality Framework, and the Open Authentication Protocol. The chapter also provides a brief review of the work already done in these areas.
Secure Multi-Party Computation
Multi-party Computation (MPC) involves multiple parties who want to compute a specific agreed function based on certain inputs from each party in such a way that none of the parties know the input of any other party. The only information each party acquires from the computation is the public output of the MPC. The first MPC problem introduced was the Millionaire problem where two millionaires want to know who is richer but do not want to reveal any information about their wealth to each other [3].
Trusted third party and SMPC
These types of problems can be solved by involving a trusted third party by each of the parties providing their inputs to the trusted third party and the third party reveals the public output of the commonly agreed function based on the inputs provided by the participating parties. However, MPC replaces the trusted third party thereby avoiding the problematic issues of a third party solution. The individual inputs are shared with the other parties in such a way that every party is able to compute the agreed function and learn the desired output but still remains unaware of the actual inputs of the other parties. This is made possible with the help of a concept called verifiable secret sharing [4][5].
Each of the parties splits its secret, before sharing it, into as many parts as the number of parties take part in the MPC. In this way every party gets a share of that secret, but not the complete. All the parties share their secrets in the same manner. A secret can only be reconstructed if a party has more than a specific number of shares greater than a certain threshold. However, every party is capable of performing computations such as addition, multiplication, and comparison on the secret shared values without knowing the actual secrets. These computations are used to compute the commonly agreed function.
Secret Management
The main feature of MPC is to hide the individual’s secret values from one other, while still providing them with a method to do computations based on these secrets values. This is done using a secret management process. This process manages the splitting and sharing of the secrets as well their reconstruction.
Secret Sharing
Secrets are shared among the participants in such a manner that the individual shares do not reveal any information about the secret. Consider the case of three parties named User1, User2, and User3 taking part in a MPC as shown in Figure 2.1. X, Y, and Z are the secrets of User1, User2, and User3 respectively. Each of these parties divides its secret in three parts, e.g. User1 divides its secrets X into three parts x1, x2, and x3. User1 keeps x1 to itself and sends x2 and x3 to User2 and User3 respectively. After the exchange, every party has a share of every other party’s secret which it can use to do certain kinds of computations as part of the commonly agreed function.
There are various schemes available for secret sharing. Splitting a secret directly into multiple parts is one of the easiest schemes, but it is not a secure because an adversary an adversary can reconstruct the secret if the adversary learns some of the shares. Therefore the secrets must be divided in a such a way that the secret can only be reconstructed when a certain number of shares greater than a specific threshold are known. Each individual share also must not reveal any information about the secret.
Some restrictions on the secret sharing scheme can help in fulfilling the aforementioned conditions as stated in [6]. One restriction is that the size of each share must be equal to the original secret and no information can be obtained until more than a certain number of shares are known. The sharing scheme must also use random bits in the formation of shares.
The number of shares required to reconstruct the secret is termed the threshold t in most of the literature. This implies that we can have less than t adversaries in a MPC without affecting the final result. In an n-party computation, t varies from n to n/2 to n/3 depending upon the sharing scheme used and the nature of adversaries [7][8][9]. The following two subsections describe two sharing schemes: Additive Sharing Scheme and Threshold Sharing Scheme [10][11].
Additive Sharing Scheme
The additive sharing scheme is the simplest sharing scheme. It is an absolutely secure sharing scheme if done with care. It requires a knowledge of all the shares to reconstruct the secret and therefore this scheme is also called the perfect secret sharing scheme. Additive sharing schemes are methods for creating shares and reconstructing the secret from the shares [12].
If there is a secret s to be shared among n parties, n-1 random numbers r1 to rn−1 are selected. The random values will be used to compute the shares corresponding to the n-1 parties. A prime number p greater than all the random numbers and the secret is selected and then the secret s and the random numbers r1 to rn−1 are considered to be element from within the set S mod p in order to make the selection of the values equally likely. The share for the nth party is computed using equation 2.1 [12].
The secret can be reconstructed using equation 2.2 only when all the shares are known [12].
A variant of the additive sharing scheme is the XOR sharing scheme which works in exactly the same manner as the additive sharing scheme. The n-1 shares are random numbers and the nth share is computed such that the XOR of all the shares is equal to the secret s, i.e., the nth share is the XOR of all the n-1 shares and the secret s itself. The secret s can be reconstructed by XORing all the n shares [13].
The reconstruction of the secret requires the knowledge of all the n shares, so an adversary having the knowledge of less than n shares will not be able to reconstruct the secret. However, there is a problem if even one share is missing, as no one is able to reconstruct the secret. This problem can be solved by the sharing scheme described in the next section.
Threshold Sharing Scheme
Threshold sharing schemes uses a polynomial to create shares from a secret and to reconstruct the secret from these shares. Such a scheme is also be called a polynomial sharing scheme or a (t,n)-threshold scheme where n is number of parties in a n-party computation among whom the secret s is shared in such a way that any number of parties less than the threshold t cannot reconstruct the secret [12].
Shamir came up with a sharing scheme based on polynomial interpolation known now as the Shamir sharing scheme. The Shamir sharing scheme is used in a framework for MPC called Virtual Ideal Functionality Framework (VIFF). VIFF will be discussed later in section 2.2 [15]. In the Shamir sharing scheme, a secret is represented by a polynomial where all the numbers in the polynomials are from a finite field, i.e., a field with a finite number of elements and having a prime number or power of a prime number p as its degree. A modulo p secret sharing scheme ensures that the secret can be any element from the ring of integers modulo p, whereas the same cannot be stated for all the real numbers because the secrets may not be uniformly distributed across all the real numbers.
The polynomial is constructed based the variable t in the (t,n)-threshold scheme. A (t,n)-threshold scheme can be represented by a polynomial of degree t -1 [11]. The secret s is represented by a point (0,s) on the y-axis where the polynomial intersects the y-axis. For example a (2,n)-threshold scheme is represented by line where (0,s) is the point on y-axis representing the secret and a (3,n)-threshold scheme is represented by a quadratic equation where (0,s) is a point on the y-axis, representing the secret, where the curve represented by the quadratic equation intersects the y-axis. The n shares are any other n points that satisfy the polynomial. Similarly higher threshold schemes require higher degree polynomials.
The secret can be reconstructed having the knowledge of any t shares using Lagrange’s formula as shown by equation 2.3 where s is the secret, f represents the polynomial and f(x) = sx is the share corresponding to x th player [14]. s =si −xj /(xi − xj ) mod p (2.3) i=1 j=1 j!=i
Arithmetic on secret shared values
The commonly agreed functions used in MPCs are based on arithmetic operations such as addition, multiplication, etc. VIFF, to be discussed later, provides support for all these arithmetic operations.
Addition
Addition of secret shared values is very simple. Each party can find the sum of the secrets by adding their individual shares of the secrets. Secrets are shared using particular polynomials. The sum of two or more polynomials generate a new polynomial which has the coefficients equal to the sum of the corresponding coefficients in the polynomials to be added up. The sum of the polynomials intersect the y-axis at the same point as the sum of the secrets represented by them.
Multiplication
Multiplication of secret shared values is more complicated as compared to addition of the secret shared values. It requires multiple layers of sharing and some extra calculations to compute the product of two secret shared values
[6]. The details are not discussed here because that is not relevant to the goal the thesis.
Comparison
Comparison of secret shared values is much more complicated than either addition or multiplication of secret shared values. A comparison operation consists of multiple multiplication operations which makes it a very slow and expensive process although researcher are trying to make the comparison operation faster and cheaper.
This thesis focuses on one variant of comparison, specifically the equality of secret shared values. There are different methods to find out whether the secret shared number are equal or not. A bitwise XOR operation or computing the difference of two secret shared numbers help in determining whether these number are equal or not.
SMPC Work flow
We can now organize the above concepts and procedures to form a work flow of the SMPC. SMPC is performed in three steps: input sharing, computing the desired function, and revealing the output.
Input Sharing The secret are divided into shares and shared with other parties according the sharing scheme, the number of parties, and the requirements of the specific application.
Computing the desired function SMPC is based on some function which all the parties agree upon. This commonly agreed function can be based upon arithmetic operations as discussed above. The necessary computations required to compute the desired function are performed and final value of the function is computed.
Revealing the Output The output of the previous stage is revealed to all or some of the parties at this stage based on the requirements of the protocol. There can also be additional actions that are taken based on the previous stage’s output in order to meet the requirements of a particular application.
Related Work review
The core of MPC is based on secret sharing. Dividing a secret into multiple shares in order to be able to share it with other parties was introduced by Shamir and Blakley in 1979 [11][16]. Both of these authors worked independent of each other and they used different methods for their sharing schemes. Shamir used polynomial interpolation while Blakley used intersection of hyperplanes. Shamir’s method is more well known and is used in VIFF.
MPC potentially provides solutions to many problems involving trusted third parties. After the introduction of the Millionaire Problem by Yao in 1982, some work has been done to make MPC more secure [3]. This work mainly has focused on how many adversaries a MPC can afford to have while remaining secure. In a (c,n)-threshold scheme where c represents the number of adversaries or corrupted parties and n represents the total parties, a function can be securely computed in the presence of t < n/3 active adversaries and t < n/2 passive adversaries [7][8]. Another protocol by Goldreich et al. presented in 1987 also ensures security of MPC in the presence of t < n/2 adversaries.
There has been a very limited number of MPC based applications in practice despite the fact that this technique potentially provides solutions to many problems. Although there has been work done in the developing MPC based applications, more work needs to be done in order to get the most out of MPC. There have been several frameworks developed in order to facilitate developing MPC based applications. Virtual Ideal Functionality Framework (VIFF) is an example of such a framework (it will be discussed in detail in the next section). Other frameworks include Fairplay and Sharemind
[21]. Fairplay has two versions, i.e. Fairplay for two-party computations and FairplayMP for Multi-party computations (more than two parties) [19][20].
A few MPC based applications were developed using VIFF after the introduction of the framework. The first application is Nordic Sugar, an application for the sugarbeet contracts developed in Denmark [17]. Other applications include Distributed RSA [13], Distributed AES [18], Ranking the Authors and Secure Voting [6].
Virtual Ideal Functionality Framework
Virtual Ideal Functionality Framework (VIFF) provides a Python library allowing multiple players to execute a cryptographic protocol to do secure MPC. It works as an application prgramming interface (API) for MPC and hides the cryptographic and communication details. VIFF handles the network communications, secret sharing, and operations on the shares,thus a developer does not need to be concerned with these details. A developer only needs to know how to use the VIFF library calls. These call will be interpreted by the Python Virtual Machine.
Background
VIFF, originally named PySMPC, is Python library for performing SMPC and was initially developed by Martin Geisler in 2007. PySMPC was renamed VIFF because of difficulties in pronouncing its name. As its name suggests, VIFF is a framework for developing virtual ideal functionalities. A research project named SIMAP (Secure Information Management and Processing) is considered to be the root of VIFF [22].
SIMAP’s main goal was to develop tools for SMPC which can be used by normal programmers to solve real world problems without requiring that the developers be security experts. The sugarbeet contract application was the first MPC based application developed by the SIMAP project [17]. This application is based on a secure double auction which was implemented by the SCET project (Secure Computing Economy and Truct: Successor of the SIMAP project).
Current Features and Security Assumptions
VIFF provides an easy way to implement SMPC based applications by making use of the features provided by VIFF. Its current features as described on the VIFF webpage are discussed in this subsection [15].
The arithmetic operations discussed earlier are performed with shares for Zp or GF28 where Zp and GF are finite fields. All the numbers involved in the SMPC are required to be from these fields in order to ensure perfect security. Secret sharing is based on Shamir’s scheme and the Pseudo Random Sharing Scheme (PRSS) [27]. VIFF consists of a field module for handling the finite fields and separate modules for Shamir and PRSS schemes. VIFF provides overloaded operators for secure addition, subtraction, multiplication, and XORing on the shares as well as comparison of the secret shared inputs with secret shared outputs. VIFF makes use of Twisted for asynchronous and automatic parallel execution [28]. Secure Socket Layer (SSL) is used for secure communication between two communicating parties.
VIFF documentations make it clear that the protocol is only secure if certain security assumptions are fulfilled (just like any other cryptographic system) [15]. These assumptions include that the assumption there must be majority of honest parties. The maximum number of parties that can be corrupted must be less than one third of the total number of parties in case of active adversaries and less than half of the total number of parties in the case of passive adversaries. VIFF protocols rely on assuming a certain degree of computational hardness and it is assumed that the adversary is computationally bounded, i.e., the adversary cannot overcome this computational hardness with its bounded computational power. A passive adversary observes the protocol by monitoring the traffic, but it does not inject any traffic itself.
Table of contents :
1 Introduction
1.1 Context of the Problem
1.2 Motivation for the solution
1.3 Multi-Party Computation as a potential solution
1.4 Goal of the project
1.5 Contributions
1.6 Outline of the report
2 Background and related work
2.1 SecureMulti-Party Computation
2.1.1 Trusted third party and SMPC
2.1.2 Secret Management
2.1.3 Arithmetic on secret shared values
2.1.4 SMPCWork flow
2.1.5 RelatedWork review
2.2 Virtual Ideal Functionality Framework
2.2.1 Background
2.2.2 Current Features and Security Assumptions
2.2.3 VIFF architecture
2.2.4 MPC, VIFF, and Anonymous Authentication
2.3 OAuth Protocol
2.3.1 OAuth Terminology
2.3.2 Work Flow
2.3.3 Prospect of coupling OAuth with MPC based authentication system
3 Anonymous Authentication: A ProposedModel
3.1 Overviewof theModel
3.1.1 Defining the Roles
3.1.2 The big picture
3.2 Operation of the proposed system
3.2.1 The Registration process
3.2.2 The Authentication and Authorization process
3.3 Behavior of the individual entities
3.3.1 Registrar
3.3.2 AnonAuth
3.3.3 CompServer and UnionServer
3.3.4 GWServer
3.3.5 User
4 Security Analysis of the proposed model
4.1 Issues to be addressed
4.2 SecureMulti-party Computation
4.3 Anonymity of the user
4.4 Security of the system
4.5 Areas that need further improvement
5 Development of the System
5.1 SMPC part of the design:
VIFF development
5.2 Skeleton of the System
5.2.1 Registrar
5.2.2 AnonAuth
5.2.3 CompServer and UnionServer
5.2.4 GWServer
5.2.5 User
6 Implementation of a simplified prototype
6.1 Generating the configuration files and starting the entities
6.2 Registration
6.3 Authentication
7 Conclusion and Future Work
7.1 Conclusion
7.2 FutureWork
A Skeleton of the proposed model
A.1 SMPC part of the model
A.1.1 User
A.1.2 Authentication Servers
A.2 Registrar.java
