SMC: Secure Multiparty Computation Language

by Silaghi, Marius-Călin

SMC is a declarative programming language for Secure Multiparty Computations. First let us give some definitions.

Definitions
About
Tutorial

Definition
Cryptography is the science of hiding information.

A Cryptographic Protocol is a protocol that has as one of its goals the hiding of information.

A Secure Multiparty Computation is a cryptographic protocol among a set of participants, where some of the inputs needed for the interaction have to be hidden from participants other than the initial owner.

A Declarative Programming Language (as compared with an imperative programming language) is a paradigm within which the programmer describes his problem without needing to know any detail about the algorithms used to solve it. Once the problem is described, an interpreter or a compiler chooses an algorithm (hopefully the best one), and solves it.

Older examples of declarative programming language are PROLOG and Constraint Programming:

In PROLOG the programmer needs to specify his problem in terms of a set of HORN clauses (i.e., first order logic sentences of the form P1/\P2/\...Pn=>C) and a goal (a conjunction of atomic first order logic sentences). However, PROLOG was far from ideal since some knowledge about the underlying algorithm (DFS backward chaining) is needed for writing the description.
Constraint Programming proved to be a better choice. A programmer needs to describe his problem in terms of a set of variables and constraints between them (quite similar to liniar programming), but the constraints can be much more flexible (e.g., for discrete variables the constraint can be specified with any truth table, and for mixed continuous-discrete variables with any symbolic relation). A flexible objective function can be specified as well, and any solution optimizing it acceptable. Still, it was found that important instruction is needed even only for writing such descriptions of problems.

A declarative program looks more like a configuration file or a database, than like an imperative program.

About
Secure Multiparty Computations are non-trivial to design, particularly because not any composition of such protocols remains secure. Given the difficulty of choosing the right algorithms, I considered it important to propose a declarative language based on constraint programming and able to solve most secure multiparty computation problems. The contribution of this language and of the provided interpreter should be considered in the light of the fact that no other support for secure computations was present at the moment when this was written (no imperative languages and even no software libraries).

Note: The first version of our interpretor was made available on-line (and presented at AAMAS in July 2004). A language and a compiler for 2-party secure function evaluation (called FairPlay) was made available and was presented at USENIX (in August 2004), nevertheless FairPlay does not address multiparty computation (i.e., more than 2 participants).

A set of applets that use the engine of this interpreter was written with help from students Vaihav Rajeshirke, Amit Abhyankar, and Julia Hamilton.

Tutorial

The arithmetic circuit syntax
The public program
The secret data
The current constraint solver

To solve a problem, first a description of its public components has to be written in the SMC language, and will be called: the public program. If the description contains declarative sections (based on constraints or first order logic), then the interpreter usees its current constraint solver. The programmer is allowed in SMC to change the current constraint solveror even to write new ones, also by using the SMC language.

The public program and the current constraint solver are distributed among participants. Each participant runs the interpreter with these files on his own machine (considered secure), connected to the Internet. Each participant will also input his own secrets in a separate file called the secret data. The applet interfaces offer graphical (limited) ways to input the secret data. The interpreter assembles a set of algorithms, based on these files. Each participant has a name (n.a., number in the current version). A simple example of how the participant 5 in this computation would launch the interpreter is:

java mcs.apps.SMC -A Version4.smc -P public.smc -S secret.smc -K secret-key-file -i 5

After this is called, the interpreter starts to contact the other participants, (verifies their identity and exchange session keys -- part not yet fully developed in version 1.3). Then each interpreter starts to solve the problem and at the end the solution is printed. The interpreter interprets the public program in file "public.smc" and the secret data in file "secret.smc", by using the constraint solver Version4, for the user with ID 5.

The arithmetic circuit syntax
The programs can contain descriptions of arithmetic circuits. These are described using a functional programming style. Later we may write more friendly preprocessors :):

+(op1,op2) ---addition (modulus MODULUS defined below, as all subsequent operations)
-(op1,op2) ---subtraction
*(op1,op2) ---multiplication
/(op1,op2) ---division, where operand op2 is public
RANDOM() ---generates a random shared secret, not known by any participant, uniformly distributed between 0 and MODULUS-1 (this is not yet available to users in version 1.3)
FACT(op) ---factorial of a public operand op
INV(op) ---modular inverse of a public operand op
COMB(op1,op2) ---combinatorial divider for C_op1^op2
CONDENSE(array_name,length,permutation) ---remove empty elements of array_name
UNCONDENSE(array_name,length,permutation,result_array,result_length)
SETLOCAL(variable_name,value) ---defines a variable local to the current function
IF(test,non-0-branch,0-branch) ---a conditional branch on a public variable test=0, that executes only the selected branch
--- note that branching on secrets, that evaluates both branches, can be defined as a library function, by placing on a single line: secretIF(secret_test,non_0_branch,0_branch)= *(non_0_branch,test)+*(0_branch,-(1,test)) , where the test is expected be a secret 0 or 1
SUM(index_variable,first,last,series) ---a sum of a series, where first and last are public
PROD(index_variable,first,last,series) ---a product of a series, where first and last are public
PROJ(op1,op2) ---returns the value of the projection of op1-th tuple on variable op2
FOR(index_variable,first,last,array_name1,op1,array_name2,op2,...,array_nameN,opN,result) ---a cycle, where the result of each operation is stored in a corresponding value of an array
SEQUENCE(op1,op2,...op3) ---a sequence of operations, the last one defining the result
SHUFFLE(array_name,length) ---to shuffle an array of secrets
UNSHUFFLE(array_name,length) ---to unshuffle the array
ARRAY(array_name,index_variable,val1,val2,...,valN) ---to create a vector from a set of values, returns the value at position index_variable
array(par1,...parN) ---a function call, or a (multi-dimensional) array element
function(par1,...parN)=expression ---to define a function write from the beginning of the line
function declarations can be continues on other lines, if the continuation does not start from the beginning of the line
comments start with a #

The public program
The public program specifies the knowledge that every participant should know:

Starts with the version of the file: "GENERIC_DISWCSP_V1"
The number n of participants with (PARTICIPANTS n):

the public keys n_i g_i for each participant i (PUBLIC-KEYS n_1 g_1 ... n_n g_n), -- in the next version this will be specified with different files!
their IP and socket addresses -- the applet version fills this online (ADDRESSES ip1 socket_1 ... ipn socket_n)

The secret inputs that each participant is expected to use (INPUTS):

the number of following inputs (for each participant)
a name for each input (can be matrix, vector, or independent value)
a type: T-Table, V-Vector, I-Item in a range
Tables and Vectors are followed by their 2 resp. 1 dimensions
The labels to be displayed with each input (for each dimension)
a type specifier: Boolean or Integer with a specified range (version 1.3 does not yet check these types)
Note: an unlimited number of additional inputs can be provided as direct constraints.

The secret outputs that each participant should obtain (OUTPUTS):

number of outputs (for each participant)
a name for each output
the variable holding the output value

The functions for computing the outputs from inputs -- and from possible declarated constraints (INTERMEDIARY-INPUTS/ INTERMEDIARY-OUTPUTS)
A set of m variables on which the constraints are expressed (VARIABLES m) followed by the number of such variables

the name of each variable and the domain size (the participants can use an unlimited number of secret constraints on these variables).

A set of c0 public constraints on the variables (PUBLIC-CONSTRAINTS c0)

the nb of variables, the variable names, and the relation
These constraints can sensibly speed up the computation.

Descriptions on how to compute c secret constraints from secret inputs (INDUCED-CONSTRAINTS c):

a name (for each secret constraint)
the number of variables involved in this constraint
the names of the involved variables
The arithmetic circuit defining the constraint. Can use a vector introduced with curly braces { }. Can use the functions defined for outputs (INTERMEDIARY-INPUTS)

If the constraints contain objective functions, the bounds are specified here (OPTIMIZE)
While the computation is chosen by the interpreter, the user is allowed to chose his own modulus for the arithmetic function evaluations (MODULUS). The default value is the first prime bigger than T (see below).
The threshold scheme used: (THRESHOLD-SCHEME). We also plan to support declarations of attackers: PASSIVE-ATTACKER vs. ACTIVE-ATTACKER, INFORMATION-THEORTICALLY-SECURE vs. COMPUTATIONALLY-SECURE

Example:

################################
# file "public.smc"
#
# Year 2004
# a meeting-scheduling application
# 3 participants choose from 2 places. If both places could work, the solution is picked randomly
# a file of type:
################################
GENERIC_DISWCSP_V1

# use modulus 13 for arithmetic circuits (the minimum one is chosen automatically)
MODULUS      13

# THRESHOLD-SCHEME n / 2 # default is n/2, in version 1.3 the user is not yet allowed to change it

# number of participants
PARTICIPANTS 3

# n-g for Paillier keys. Real users will want bigger safe values and surely different for participants :)
# you can generate these numbers with the Paillier generator applet at http://cs.fit.edu/~msilaghi/
PUBLIC-KEYS
# n-g for 1st participant
2257    158
# n-g for 2nd participant
2257    158
# n-g for 2nd participant
2257    158

# the IP addresses for participants
ADDRESSES
# IP PORT for 1st participant
127.0.0.1     2001
# IP PORT for 2nd participant
127.0.0.1     2002
# IP PORT for 3rd participant
127.0.0.1     2003

INPUTS
# T-table, V-vector, I-integer, B-boolean 0/1
1                         # inputs for participant 1
ic1    V 2             # a vector with two elements
label c11 c12        # the labels for the elements are shown here
Boolean                 # the type of the inputs is Boolean
1                     # 1 input for the 2nd participant
ic2    V 2         # a vector with two elements
label c21 c22     # the labels for the elements are shown here
Boolean                 # the type of the inputs is Boolean
1                     # 1 input for the 3rd participant
ic3    V 2
label c31 c32
Boolean

INTERMEDIARY-INPUTS 2
r1=*(*(ic1(0),ic2(0)),ic3(0))
r2=*(*(ic1(1),ic2(1)),ic3(1))
# r(x)=ARRAY(r,x,r1,r2) # these can be set in an array
# the elements become r(0) for r1 and r(1) for r2

# CONSTRAINT-PROBLEM
VARIABLES    1 # a single variable
place 2 # it is called "place" and has 2 values

INDUCED-CONSTRAINTS 1
C # name for this constraint
1 # nb of variables involved in this constraint
place
{ r1 r2 } # the constraint is here computed separately for each place

OUTPUTS
1 # 1 input for participant 1
place    place # output the value of variable place with label "place"
1 # 1 input for participant 2
place    place
1 # 1 input for participant 3
place    place
EOF
#

The secret data
Specifies the secret input of the user is specified.

Example:

############################
# file "secret.smc"
#
# Year 2004
# A file of type
############################
GENERIC_DISWCSP_V2
1 # nb of inputs
ic3 # name of the input -- was declared vector of size 2 in the file "public.smc"
1 1 # elements of the vector

The constraint solver version
Specifies the secure distributed constraint solving technique to be used. If constraints are used, the following variables become usable in programs:

CONSTRAINT(i,t) --the satisfaction value for secret constraint i at tuple t
PUBLIC(t) ---the satisfaction of the tuple t by public constraints (implemented since version 1.4)
PUBLICCSP(array, _length) ---create array with all tuples satisfying public constraints, and return its length (not yet implemented in version 1.3)
C ---the number of secret constraints
D ---the maximum domain size
M ---the number of variables
T ---D^M
TuplesNb ---the amount of tuples in the constraints space
_D ---an array with the domain size of each variable
N ---the number of participants
B1 ---the worst bound at optimization
B2 ---the best bound at optimization
SHUFFLE(CSP) ---shuffle the CSP by shuffling its domains
UNSHUFFLE(CSP,array_name) --unshuffle the array of CSP domains

The solver is described by a set of functions whose entry point is the function "main". The chosen assignment to variables are to be saved in the array "_x".

EXAMPLE:

##########################
# file "Version4.smc"
# SMC solver for distributed constraint satisfaction program
# implements the algorithm MPC-DisCSP4
# but uses Generate and Test instead of a powerful backtracker
#
# Year 2004
##########################
p(t)=PROD(i,0,-(C,1),CONSTRAINT(i,t))
makeS=FOR(t,0,-(TuplesNb,1),
    _S, p(t),
    0)
selectS(length)=FOR(j,0,-(length,1),
    _k,IF(j,*(_k(-(j,1)),-(1,_S(-(j,1)))),1),
    _S2,*(_S(j),_k(j)),
    0)
main=SEQUENCE(
    makeS,
    SETLOCAL(length,CONDENSE(_S,TuplesNb,_permutation)),
    SHUFFLE(_S,length),
    selectS(length),
    UNSHUFFLE(_S2,length),
    UNCONDENSE(_S2,length,_permutation,_S,TuplesNb),
    FOR(i,0,-(M,1),
        _x,f(i),
        0))
f(i)=SUM(t,0,-(TuplesNb,1),*(PROJ(t,i),_S(t)))
#

Create Nov. 25, 2004 by Silaghi, Marius-Călin.