The MPC-DisCSP4 algorithm for DisCSP with privacy guarantees. More...

Inheritance diagram for frodo2.algorithms.mpc_discsp.MPC_DisCSP4< V extends Addable< V > >:

[legend]

Classes
enum	Phase
	A phase of the algorithm. More...
enum	MultiPhase
	The phases in a multiplication operation. More...

Public Member Functions
	MPC_DisCSP4 (DCOPProblemInterface< V, AddableInteger > problem, Element params)
	Constructor.
void	setQueue (Queue queue)
Collection< MessageType >	getMsgTypes ()
void	notifyIn (Message msg)
Public Member Functions inherited from frodo2.communication.IncomingMsgPolicyInterface< T >
default void	notifyIn (Message msg, Object toAgent)
	Notifies the listener of an incoming message.

Protected Member Functions
	MPC_DisCSP4 (DCOPProblemInterface< V, AddableInteger > problem, Element params, AddableInteger plusinf)
	Constructor.
void	terminate ()
	Terminates.
void	nextMultiplication ()
	Moves to the next vector multiplication, if any remains.
void	revealSol ()
	Reveals to each agent all shares of its variables' optimal values.
void	processPending ()
	Processes pending messages.
void	findFirstSolution ()
	Initiates the arithmetic circuit on S that singles out its first 1 entry.
void	init ()
	Parses the problem.
void	recordCandidateSol (AddableInteger publicCost, AddableInteger privateCost, List< BigInteger > sPrimePrime)
	Records a candidate solution.
void	share0 ()
	Creates and sends share of 0.
void	shareVectorOfZeros ()
	Shares a vector full of zeros.

Protected Attributes
Queue	queue
	The queue used to exchange messages.
DCOPProblemInterface< V, AddableInteger >	problem
	The problem.
boolean	started = false
	Whether the algorithm has been started.
ArrayList< String >	agents
	The agents in lexicographic order.
int	nbrAgents
	The number of agents.
int	myAgentID
	This agent's index in the ordered list of agents.
int	nbrSols
	The number of publicly feasible solutions.
final BigInteger	modulo
	Shamir secret shares are modulo this number.
BigInteger[]	Sprime
	The vector S' of Shamir shares of the feasibility of each publicly feasible solution.
final PaillierCryptoScheme	cryptoScheme
	The Paillier crypto scheme.
BigInteger[]	S
	The vector S of Shamir shares of whether each solution is the optimal one.
BigInteger	hi
	When computing the vector S, the previous value of h.
BigInteger	Si
	When computing the vector S, the previous value of Si.
Phase	phase = Phase.SprimePrime
	The current phase.
int	step = 0
	A step of computation.
MultiPhase	multiPhase = MultiPhase.randomize
	The current phase of the current multiplication operation.
boolean	currStep = false
	Boolean used to identify received messages that belong to the next phase and should be postponed.
int	sharesCount = 0
	Counter used to keep track of the number of shares exchanged.
ArrayList< Message >	pendingMsgs = new ArrayList<Message> ()
	Messages received too early to be processed.

Private Member Functions
BigInteger[][]	newVectorOfSharesOf0 ()
void	share (BigInteger nbr)
	Shares a number with all agents.
void	shareVector (List< BigInteger > vector)
	Shares a secret vector with all agents.
BigInteger[]	randPoly (BigInteger at0)
	Creates a random polynomial.
BigInteger	evaluate (BigInteger[] poly, BigInteger x)
	Evaluates a polynomial P at x.

Private Attributes
ArrayList< int[] >	solIndex
	For each entry in the S vector, for each variable, the index of its value in its domain.
int	deg = -1
	The degree of the polynomials in Shamir's secret sharing scheme.
BigInteger[]	agentXvalues
	For each agent, its X value used to evaluate polynomials.
SecureRandom	rand = new SecureRandom ()
	A source of randomness.
TreeMap< Integer, BigInteger[] >	SprimePrime = new TreeMap < Integer, BigInteger[] > ()
	For each agent, its S'' vector.
int[]	permutation
	A random permutation used to shuffle the vectors.
int[]	inversePerm
	The inverse permutation.
BigInteger[][]	vectOfShares
	A vector of shares.
BigInteger[]	shares
	Shares.
BigInteger[]	lagrange
	The coefficients used for Lagrange interpolation.
int	encrSharesCount = 0
	Counter used to keep track of the number of encrypted shares exchanged.
String[]	vars
	The ordered list of variables participating in public constraints.
HashMap< String, BigInteger[] >	solShares
	Shares of the feasible values for my variables.
HashMap< String, V >	solution
	The feasible solution found, if any.
Matrix	reductor
	The matrix used to reduce the degree of a product polynomial.
final AddableInteger	plusinf
	The infinite cost value.

Detailed Description

The MPC-DisCSP4 algorithm for DisCSP with privacy guarantees.

MPC-DisCSP4 is described in the following paper:

Marius-Calin Silaghi. Hiding absence of solution for a distributed constraint satisfaction problem (poster). In Proceedings of the Eighteenth International Florida Artificial Intelligence Research Society Conference (FLAIRS'05), pages 854-855, Clearwater Beach, FL, USA, May 15-17 2005. AAAI Press.

Author: Thomas Leaute

Parameters

<V>	the type used for variable values

Constructor & Destructor Documentation

◆ MPC_DisCSP4() [1/2]

frodo2.algorithms.mpc_discsp.MPC_DisCSP4< V extends Addable< V > >.MPC_DisCSP4	(	DCOPProblemInterface< V, AddableInteger >	problem,
		Element	params )

Constructor.

Parameters

problem	the overall problem
params	the parameters

References problem.

◆ MPC_DisCSP4() [2/2]

frodo2.algorithms.mpc_discsp.MPC_DisCSP4< V extends Addable< V > >.MPC_DisCSP4	(	DCOPProblemInterface< V, AddableInteger >	problem,
		Element	params,
		AddableInteger	plusinf )

protected

Constructor.

Parameters

problem	the overall problem
params	the parameters
plusinf	The infinite cost value

References plusinf, problem, and frodo2.solutionSpaces.ProblemInterface< V extends Addable< V >, U extends Addable >.setUtilClass().

Here is the call graph for this function:

Member Function Documentation

◆ evaluate()

BigInteger frodo2.algorithms.mpc_discsp.MPC_DisCSP4< V extends Addable< V > >.evaluate	(	BigInteger[]	poly,
		BigInteger	x )

private

Evaluates a polynomial P at x.

Parameters

poly	the polynomial P
x	the value

Returns: P(x)

Referenced by newVectorOfSharesOf0(), share(), share0(), and shareVector().

◆ findFirstSolution()

void frodo2.algorithms.mpc_discsp.MPC_DisCSP4< V extends Addable< V > >.findFirstSolution ( )

protected

Initiates the arithmetic circuit on S that singles out its first 1 entry.

References frodo2.algorithms.mpc_discsp.MPC_DisCSP4< V extends Addable< V > >.MultiPhase.randomize, revealSol(), frodo2.algorithms.mpc_discsp.MPC_DisCSP4< V extends Addable< V > >.Phase.S, and share0().

Referenced by nextMultiplication(), and notifyIn().

Here is the call graph for this function:

◆ getMsgTypes()

Collection< MessageType > frodo2.algorithms.mpc_discsp.MPC_DisCSP4< V extends Addable< V > >.getMsgTypes ( )

See also: IncomingMsgPolicyInterface.getMsgTypes()

Implements frodo2.communication.MessageListener< T >.

References frodo2.algorithms.mpc_discsp.EncrSharesMsg.ENCR_SHARES_MSG_TYPE, frodo2.algorithms.mpc_discsp.OneShareMsg.ONE_SHARE_MSG, frodo2.algorithms.mpc_discsp.SharesMsg.SHARES_MSG_TYPE, frodo2.algorithms.mpc_discsp.SolShareMsg.SOL_SHARE_MSG_TYPE, and frodo2.algorithms.AgentInterface< V extends Addable< V > >.START_AGENT.

◆ init()

void frodo2.algorithms.mpc_discsp.MPC_DisCSP4< V extends Addable< V > >.init ( )

protected

Parses the problem.

Referenced by init(), and notifyIn().

Here is the call graph for this function:

◆ newVectorOfSharesOf0()

BigInteger[][] frodo2.algorithms.mpc_discsp.MPC_DisCSP4< V extends Addable< V > >.newVectorOfSharesOf0 ( )

private

Returns: vector of shares of 0

References agentXvalues, evaluate(), share(), and shares.

Referenced by init(), nextMultiplication(), notifyIn(), and shareVectorOfZeros().

Here is the call graph for this function:

◆ nextMultiplication()

void frodo2.algorithms.mpc_discsp.MPC_DisCSP4< V extends Addable< V > >.nextMultiplication ( )

protected

Moves to the next vector multiplication, if any remains.

References frodo2.algorithms.mpc_discsp.PaillierPublicKey.encrypt(), frodo2.algorithms.mpc_discsp.PaillierPublicKey.fakeEncrypt(), findFirstSolution(), newVectorOfSharesOf0(), processPending(), frodo2.algorithms.mpc_discsp.PaillierCryptoScheme.publicKey, frodo2.algorithms.mpc_discsp.MPC_DisCSP4< V extends Addable< V > >.MultiPhase.randomize, frodo2.communication.Queue.sendMessage(), shareVectorOfZeros(), and frodo2.algorithms.mpc_discsp.MPC_DisCSP4< V extends Addable< V > >.Phase.shuffling.

Referenced by notifyIn().

Here is the call graph for this function:

◆ notifyIn()

void frodo2.algorithms.mpc_discsp.MPC_DisCSP4< V extends Addable< V > >.notifyIn ( Message msg )

See also: IncomingMsgPolicyInterface.notifyIn(Message)

Implements frodo2.communication.IncomingMsgPolicyInterface< T >.

Here is the call graph for this function:

◆ processPending()

void frodo2.algorithms.mpc_discsp.MPC_DisCSP4< V extends Addable< V > >.processPending ( )

protected

Processes pending messages.

References frodo2.communication.Queue.sendMessageToSelf().

Referenced by nextMultiplication(), notifyIn(), share(), share0(), shareVector(), and shareVectorOfZeros().

Here is the call graph for this function:

◆ randPoly()

BigInteger[] frodo2.algorithms.mpc_discsp.MPC_DisCSP4< V extends Addable< V > >.randPoly ( BigInteger at0 )

private

Creates a random polynomial.

Parameters

at0	value of the polynomial at 0

Returns: a random polynomial

References deg.

Referenced by share(), and shareVector().

◆ recordCandidateSol()

void frodo2.algorithms.mpc_discsp.MPC_DisCSP4< V extends Addable< V > >.recordCandidateSol	(	AddableInteger	publicCost,
		AddableInteger	privateCost,
		List< BigInteger >	sPrimePrime )

protected

Records a candidate solution.

Parameters

publicCost	the public cost of the candidate solution
privateCost	the private cost of the candidate solution
sPrimePrime	the vector of private costs of candidate solutions

References frodo2.solutionSpaces.AddableInteger.add(), frodo2.solutionSpaces.AddableInteger.equals(), frodo2.solutionSpaces.AddableInteger.intValue(), and frodo2.solutionSpaces.AddableInteger.PlusInfinity.PLUS_INF.

Referenced by init().

Here is the call graph for this function:

◆ revealSol()

void frodo2.algorithms.mpc_discsp.MPC_DisCSP4< V extends Addable< V > >.revealSol ( )

protected

Reveals to each agent all shares of its variables' optimal values.

References frodo2.solutionSpaces.DCOPProblemInterface< V extends Addable< V >, U extends Addable >.getVariables(), frodo2.communication.Queue.sendMessage(), and solShares.

Referenced by findFirstSolution(), and notifyIn().

Here is the call graph for this function:

◆ setQueue()

void frodo2.algorithms.mpc_discsp.MPC_DisCSP4< V extends Addable< V > >.setQueue ( Queue queue )

See also: IncomingMsgPolicyInterface.setQueue(Queue)

Implements frodo2.communication.MessageListener< T >.

References queue.

◆ share()

void frodo2.algorithms.mpc_discsp.MPC_DisCSP4< V extends Addable< V > >.share ( BigInteger nbr )

private

Shares a number with all agents.

Parameters

nbr	the secret number

References evaluate(), nbrAgents, processPending(), randPoly(), frodo2.communication.Queue.sendMessage(), and share().

Referenced by newVectorOfSharesOf0(), notifyIn(), share(), share0(), shareVector(), and shareVectorOfZeros().

Here is the call graph for this function:

◆ share0()

void frodo2.algorithms.mpc_discsp.MPC_DisCSP4< V extends Addable< V > >.share0 ( )

protected

Creates and sends share of 0.

References evaluate(), nbrAgents, processPending(), frodo2.communication.Queue.sendMessage(), and share().

Referenced by findFirstSolution(), and notifyIn().

Here is the call graph for this function:

◆ shareVector()

void frodo2.algorithms.mpc_discsp.MPC_DisCSP4< V extends Addable< V > >.shareVector ( List< BigInteger > vector )

private

Shares a secret vector with all agents.

Parameters

vector the secret vector

References agentXvalues, deg, evaluate(), nbrAgents, nbrSols, processPending(), randPoly(), frodo2.communication.Queue.sendMessage(), and share().

Referenced by init(), and notifyIn().

Here is the call graph for this function:

◆ shareVectorOfZeros()

void frodo2.algorithms.mpc_discsp.MPC_DisCSP4< V extends Addable< V > >.shareVectorOfZeros ( )

protected

Shares a vector full of zeros.

References nbrAgents, newVectorOfSharesOf0(), processPending(), frodo2.communication.Queue.sendMessage(), share(), and shares.

Referenced by nextMultiplication(), and notifyIn().

Here is the call graph for this function:

◆ terminate()

void frodo2.algorithms.mpc_discsp.MPC_DisCSP4< V extends Addable< V > >.terminate ( )

protected

Terminates.

References frodo2.algorithms.AgentInterface< V extends Addable< V > >.AGENT_FINISHED, frodo2.solutionSpaces.DCOPProblemInterface< V extends Addable< V >, U extends Addable >.getVariables(), frodo2.communication.Queue.sendMessage(), frodo2.communication.Queue.sendMessageToSelf(), frodo2.algorithms.AgentInterface< V extends Addable< V > >.STATS_MONITOR, and vars.

Referenced by notifyIn().

Here is the call graph for this function:

Member Data Documentation

◆ agents

ArrayList<String> frodo2.algorithms.mpc_discsp.MPC_DisCSP4< V extends Addable< V > >.agents

protected

The agents in lexicographic order.

◆ agentXvalues

BigInteger [] frodo2.algorithms.mpc_discsp.MPC_DisCSP4< V extends Addable< V > >.agentXvalues

private

For each agent, its X value used to evaluate polynomials.

Referenced by newVectorOfSharesOf0(), and shareVector().

◆ cryptoScheme

final PaillierCryptoScheme frodo2.algorithms.mpc_discsp.MPC_DisCSP4< V extends Addable< V > >.cryptoScheme

protected

The Paillier crypto scheme.

◆ currStep

boolean frodo2.algorithms.mpc_discsp.MPC_DisCSP4< V extends Addable< V > >.currStep = false

protected

Boolean used to identify received messages that belong to the next phase and should be postponed.

◆ deg

int frodo2.algorithms.mpc_discsp.MPC_DisCSP4< V extends Addable< V > >.deg = -1

private

The degree of the polynomials in Shamir's secret sharing scheme.

Referenced by init(), randPoly(), and shareVector().

◆ encrSharesCount

int frodo2.algorithms.mpc_discsp.MPC_DisCSP4< V extends Addable< V > >.encrSharesCount = 0

private

Counter used to keep track of the number of encrypted shares exchanged.

◆ hi

BigInteger frodo2.algorithms.mpc_discsp.MPC_DisCSP4< V extends Addable< V > >.hi

protected

When computing the vector S, the previous value of h.

◆ inversePerm

int [] frodo2.algorithms.mpc_discsp.MPC_DisCSP4< V extends Addable< V > >.inversePerm

private

The inverse permutation.

◆ lagrange

BigInteger [] frodo2.algorithms.mpc_discsp.MPC_DisCSP4< V extends Addable< V > >.lagrange

private

The coefficients used for Lagrange interpolation.

◆ modulo

final BigInteger frodo2.algorithms.mpc_discsp.MPC_DisCSP4< V extends Addable< V > >.modulo

protected

Shamir secret shares are modulo this number.

◆ multiPhase

MultiPhase frodo2.algorithms.mpc_discsp.MPC_DisCSP4< V extends Addable< V > >.multiPhase = MultiPhase.randomize

protected

The current phase of the current multiplication operation.

◆ myAgentID

int frodo2.algorithms.mpc_discsp.MPC_DisCSP4< V extends Addable< V > >.myAgentID

protected

This agent's index in the ordered list of agents.

◆ nbrAgents

int frodo2.algorithms.mpc_discsp.MPC_DisCSP4< V extends Addable< V > >.nbrAgents

protected

The number of agents.

Referenced by init(), share(), share0(), shareVector(), and shareVectorOfZeros().

◆ nbrSols

int frodo2.algorithms.mpc_discsp.MPC_DisCSP4< V extends Addable< V > >.nbrSols

protected

The number of publicly feasible solutions.

Referenced by shareVector().

◆ pendingMsgs

ArrayList<Message> frodo2.algorithms.mpc_discsp.MPC_DisCSP4< V extends Addable< V > >.pendingMsgs = new ArrayList<Message> ()

protected

Messages received too early to be processed.

◆ permutation

int [] frodo2.algorithms.mpc_discsp.MPC_DisCSP4< V extends Addable< V > >.permutation

private

A random permutation used to shuffle the vectors.

◆ phase

Phase frodo2.algorithms.mpc_discsp.MPC_DisCSP4< V extends Addable< V > >.phase = Phase.SprimePrime

protected

The current phase.

◆ plusinf

final AddableInteger frodo2.algorithms.mpc_discsp.MPC_DisCSP4< V extends Addable< V > >.plusinf

private

The infinite cost value.

Referenced by init(), and MPC_DisCSP4().

◆ problem

DCOPProblemInterface<V, AddableInteger> frodo2.algorithms.mpc_discsp.MPC_DisCSP4< V extends Addable< V > >.problem

protected

The problem.

Referenced by MPC_DisCSP4(), and MPC_DisCSP4().

◆ queue

Queue frodo2.algorithms.mpc_discsp.MPC_DisCSP4< V extends Addable< V > >.queue

protected

The queue used to exchange messages.

Referenced by setQueue().

◆ rand

SecureRandom frodo2.algorithms.mpc_discsp.MPC_DisCSP4< V extends Addable< V > >.rand = new SecureRandom ()

private

A source of randomness.

◆ reductor

Matrix frodo2.algorithms.mpc_discsp.MPC_DisCSP4< V extends Addable< V > >.reductor

private

The matrix used to reduce the degree of a product polynomial.

It is V^-1 * P * V, where V is the Vandermonde matrix, and P is a projection.

◆ S

BigInteger [] frodo2.algorithms.mpc_discsp.MPC_DisCSP4< V extends Addable< V > >.S

protected

The vector S of Shamir shares of whether each solution is the optimal one.

◆ shares

BigInteger [] frodo2.algorithms.mpc_discsp.MPC_DisCSP4< V extends Addable< V > >.shares

private

Shares.

Referenced by newVectorOfSharesOf0(), notifyIn(), and shareVectorOfZeros().

◆ sharesCount

int frodo2.algorithms.mpc_discsp.MPC_DisCSP4< V extends Addable< V > >.sharesCount = 0

protected

Counter used to keep track of the number of shares exchanged.

◆ Si

BigInteger frodo2.algorithms.mpc_discsp.MPC_DisCSP4< V extends Addable< V > >.Si

protected

When computing the vector S, the previous value of Si.

◆ solIndex

ArrayList< int[] > frodo2.algorithms.mpc_discsp.MPC_DisCSP4< V extends Addable< V > >.solIndex

private

For each entry in the S vector, for each variable, the index of its value in its domain.

◆ solShares

HashMap< String, BigInteger[] > frodo2.algorithms.mpc_discsp.MPC_DisCSP4< V extends Addable< V > >.solShares

private

Shares of the feasible values for my variables.

Referenced by revealSol().

◆ solution

HashMap<String, V> frodo2.algorithms.mpc_discsp.MPC_DisCSP4< V extends Addable< V > >.solution

private

The feasible solution found, if any.

◆ Sprime

BigInteger [] frodo2.algorithms.mpc_discsp.MPC_DisCSP4< V extends Addable< V > >.Sprime

protected

The vector S' of Shamir shares of the feasibility of each publicly feasible solution.

◆ SprimePrime

TreeMap< Integer, BigInteger[] > frodo2.algorithms.mpc_discsp.MPC_DisCSP4< V extends Addable< V > >.SprimePrime = new TreeMap < Integer, BigInteger[] > ()

private

For each agent, its S'' vector.

These vectors must be multiplied element-wise to obtain S'

◆ started

boolean frodo2.algorithms.mpc_discsp.MPC_DisCSP4< V extends Addable< V > >.started = false

protected

Whether the algorithm has been started.

◆ step

int frodo2.algorithms.mpc_discsp.MPC_DisCSP4< V extends Addable< V > >.step = 0

protected

A step of computation.

◆ vars

String [] frodo2.algorithms.mpc_discsp.MPC_DisCSP4< V extends Addable< V > >.vars

private

The ordered list of variables participating in public constraints.

Referenced by init(), and terminate().

◆ vectOfShares

BigInteger [][] frodo2.algorithms.mpc_discsp.MPC_DisCSP4< V extends Addable< V > >.vectOfShares

private

A vector of shares.

The documentation for this class was generated from the following file:

src/frodo2/algorithms/mpc_discsp/MPC_DisCSP4.java

Classes

Public Member Functions

Protected Member Functions

Protected Attributes

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ MPC_DisCSP4() [1/2]

◆ MPC_DisCSP4() [2/2]

Member Function Documentation

◆ evaluate()

◆ findFirstSolution()

◆ getMsgTypes()

◆ init()

◆ newVectorOfSharesOf0()

◆ nextMultiplication()

◆ notifyIn()

◆ processPending()

◆ randPoly()

◆ recordCandidateSol()

◆ revealSol()

◆ setQueue()

◆ share()

◆ share0()

◆ shareVector()

◆ shareVectorOfZeros()

◆ terminate()

Member Data Documentation

◆ agents

◆ agentXvalues

◆ cryptoScheme

◆ currStep

◆ deg

◆ encrSharesCount

◆ hi

◆ inversePerm

◆ lagrange

◆ modulo

◆ multiPhase

◆ myAgentID

◆ nbrAgents

◆ nbrSols

◆ pendingMsgs

◆ permutation

◆ phase

◆ plusinf

◆ problem

◆ queue

◆ rand

◆ reductor

◆ S

◆ shares

◆ sharesCount

◆ Si

◆ solIndex

◆ solShares

◆ solution

◆ Sprime

◆ SprimePrime

◆ started

◆ step

◆ vars

◆ vectOfShares