Secure Support Vector Machine algorithm. More...

#include <secure_svm.h>

Public Types
enum	KernelTypes { linear, homogeneousPolynomial, inhomogeneousPolynomial, inverseQuadraticRBF }
	Types of implemented kernels.

typedef std::vector < Paillier::Ciphertext >	EncryptedVector
	Define a vector template specialization for vectors of encrypted data.

Public Member Functions
	SecureSvm (const std::string &directoryPath, const std::string &modelFile, const PaillierPublicKey &publicKey, const std::weak_ptr< const Server > &server)
	Constructor. More...

	~SecureSvm ()
	Destructor. More...

const std::string &	GetUnsafeClasses () const
	Returns the unsafe classes of safety block SVMs. More...

Paillier::Ciphertext	Predict (const SecureSvm::EncryptedVector &x, const SecureSvm::EncryptedVector &xx=SecureSvm::nullVector, const SecureSvm::EncryptedVector &xSquared=SecureSvm::nullVector) const
	Computes the prediction for a given set of data. More...

Static Public Member Functions
static KernelTypes	GetKernel (const std::string &input)
	Converts the input string to the proper kernel. More...

Static Public Attributes
static const EncryptedVector	nullVector
	Use this to pass a NULL vector to the Predict method;. More...

Private Types
typedef std::vector< BigInteger >	ModelVector
	Define an std::vector template specialization for rows of model weights.

Private Member Functions
void	preprocessData ()
	Performs scalings and encryptions. More...

Paillier::Ciphertext	linearKernel (const SecureSvm::EncryptedVector &x, const SecureSvm::ModelVector &s) const
	Computes the linear kernel on encrypted data. More...

Paillier::Ciphertext	homogeneousPolynomialKernel (const SecureSvm::EncryptedVector &xx, const SecureSvm::ModelVector &twoGammaSquaredSS) const
	Computes the second degree polynomial kernel on encrypted data. More...

Paillier::Ciphertext	inhomogeneousPolynomialKernel (const SecureSvm::EncryptedVector &x, const SecureSvm::EncryptedVector &xx, const SecureSvm::ModelVector &twoGammaS, const SecureSvm::ModelVector &twoGammaSquaredSS) const
	Computes the second degree polynomial kernel on encrypted data. More...

Paillier::Ciphertext	computeInverseQuadraticRbfKernelDenominator (const SecureSvm::EncryptedVector &x, const SecureSvm::EncryptedVector &xSquared, const SecureSvm::ModelVector &minusTwoS, const SecureSvm::EncryptedVector &encryptedSSquared) const
	Computes the inverse quadratic RBF kernel d values on encrypted data. More...

	SecureSvm (SecureSvm const &)
	Copy constructor - not implemented.

SecureSvm	operator= (SecureSvm const &)
	Copy assignment operator - not implemented.

Private Attributes
Paillier	cryptoProvider
	The crypto provider.

std::weak_ptr< const Server >	server
	A reference to the server - required for interactive protocol requests with the client (secure division)

SecureSvm::KernelTypes	kernel
	The SVM kernel type.

std::string	modelFileName
	The name of the model file.

struct svm_model *	model

BigInteger	featureScalingFactor
	The scaling applied to the test and model vectors $ x_i $ and $ s_i $.

BigInteger	svWeightScaling

unsigned short	minimumAiDecimalDigits
	The minimum number of relevant decimal digits that $ a_i $ should preserve.

unsigned short	inverseQuadraticRbfKernelRelevantDigits
	The number of digits preserved in the inverse quadratic RBF kernel value after performing the division.

BigInteger	inverseQuadraticRbfNumerator
	Scaled 1 - the inverse quadratic RBF kernel numerator.

BigInteger	blindingFactorScaling
	The scaling that needs to be applied to the b parameter in order to compensate for the blinding factor added by the interactive protocol which computes the inverse quadratic RBF kernel.

BigInteger	gammaScaling
	The scaling applied to the SVM gamma parameter.

bool	reversedSign
	During training, libsvm uses an internal flag to denote the sign of the first label it encounters. If it is negative, we have to invert the sign of f.

std::vector< ModelVector >	sMatrix
	Matrix which stores the scaled $ s_i $ SVM model vectors.

std::vector< ModelVector >	twoGammaSMatrix
	Matrix which stores the scaled $ 2 \gamma s_i $ vectors.

std::vector< ModelVector >	minusTwoSMatrix
	Matrix which stores the scaled $ -2 s_i $ vectors.

std::vector< ModelVector >	twoGammaSquaredSSMatrix
	Matrix containing scaled vector product combinations, $ 2 \gamma^2 s_i s_j $, stored as an unraveled upper triangular matrix on each container matrix row.

std::vector< EncryptedVector >	encryptedSSquaredMatrix
	Matrix which stores the encrypted scaled $ [s_i^2] $ SVM model vectors.

std::vector< BigInteger >	aVector
	Vector which stores the scaled $ a_i $ SVM parameters.

Paillier::Ciphertext	encryptedB
	Stores the scaled and encrypted $ b $ SVM parameter (-rho in libsvm)

BigInteger	scaledGamma
	Stores the scaled gamma SVM parameter (1/(number of attributes) by default)

Paillier::Ciphertext	encryptedZero
	Contains [0], used for optimization purposes.

Paillier::Ciphertext	encryptedScaledOne
	[scaled 1], required when computing the inhomogeneous kernel. Precompute it for optimization purposes

std::string	safetyModelFilePrefix
	The prefix of the safety block model files.

std::string	safetyModelUnsafeClasses
	The unsafe classes of the safety block model.

Static Private Attributes
static const std::map < std::string, KernelTypes >	kernelTypesMap
	Map kernel names to the kernelTypes enum. More...

Detailed Description

Secure Support Vector Machine algorithm.

Definition at line 59 of file secure_svm.h.

Constructor & Destructor Documentation

SeComLib::SecureRecommendations::SecureSvm::SecureSvm	(	const std::string &	directoryPath,
		const std::string &	modelFile,
		const PaillierPublicKey &	publicKey,
		const std::weak_ptr< const Server > &	server
	)

Constructor.

Sets configuration parameters.

Sets the path to the configuration file and parses it.

Extracts the unsafe classes in the case of safety model files

Parameters

directoryPath	the absolute path to the model file
modelFile	the model file
publicKey	the client public key
server	a pointer reference to the server instance

Compute the gamma scaling (the linear kernel does not use gamma)

Definition at line 61 of file secure_svm.cpp.

SeComLib::SecureRecommendations::SecureSvm::~SecureSvm ( )

Destructor.

Releases the SVM model data

Definition at line 161 of file secure_svm.cpp.

Member Function Documentation

Paillier::Ciphertext SeComLib::SecureRecommendations::SecureSvm::computeInverseQuadraticRbfKernelDenominator	(	const SecureSvm::EncryptedVector &	x,
		const SecureSvm::EncryptedVector &	xSquared,
		const SecureSvm::ModelVector &	minusTwoS,
		const SecureSvm::EncryptedVector &	encryptedSSquared
	)		const

private

Computes the inverse quadratic RBF kernel d values on encrypted data.

Computes the encrypted denominator of the inverse quadratic RBF kernel.

Inverse quadratic RBF kernel: $ K_i = \frac{1}{r \cdot (1 + \gamma (\sum_{j=1}^f(x_j - s_{i,j})^2))} $

Scaled inverse quadratic RBF kernel: $ K_i^* = \frac{r \cdot sc_{\gamma} \cdot sc_f^2 \cdot sc_r \cdot sc_k}{r \cdot (sc_{\gamma} \cdot sc_f^2 + \gamma \cdot sc_{\gamma} (\sum_{j=1}^f(x_j \cdot sc_f - s_{i,j} \cdot sc_f)^2))} $

Encrypted scaled inverse quadratic RBF kernel: $ [K_i^*] = \left[\frac{r \cdot sc_{\gamma} \cdot sc_f^2 \cdot sc_r \cdot sc_k}{d_i^*}\right] $

Where $ [d_i^*] = \left([sc_{\gamma} \cdot sc_f^2] \cdot \left(\prod_{j=1}^f([x_j^2 \cdot sc_f^2] \cdot [x_j \cdot sc_f]^{-2 \cdot s_{i,j} \cdot sc_f} \cdot [s_{i,j}^2 \cdot sc_f^2])\right)^{\gamma \cdot sc_{\gamma}}\right)^r $ is computed by this function and $ sc_b = sc_r \cdot sc_k $

$ r $ is the blinding factor, $ sc_r $ is $ 2^{size(r) + 1} $, $ sc_k $ is set to $ 10^8 $ (in the configuration file) and it allows us to preserve a sufficient number of digits after the division.

The blinding $ r $ is added by the server, before sending $ [d_i^*] $ to the client to evaluate the kernel value, $ [K_i^*] $.

Parameters

x	the encrypted attribute vector
xSquared	the encrypted squared attribute vector
minusTwoS	scaled $ -2 s_i $
encryptedSSquared	$ [s_i^2] $

Returns: The encrypted value of the kernel

Compute [1 + c d], where c is gamma

Definition at line 657 of file secure_svm.cpp.

SecureSvm::KernelTypes SeComLib::SecureRecommendations::SecureSvm::GetKernel ( const std::string & input )

static

Converts the input string to the proper kernel.

Parameters

input a string containing the name of the kernel

Returns: The kernel

Exceptions

std::runtime_error Invalid kernel name received.

Todo:: Throw a custom exception here

Definition at line 170 of file secure_svm.cpp.

const std::string & SeComLib::SecureRecommendations::SecureSvm::GetUnsafeClasses ( ) const

Returns the unsafe classes of safety block SVMs.

Returns: A vector of unsafe classes

Definition at line 185 of file secure_svm.cpp.

Paillier::Ciphertext SeComLib::SecureRecommendations::SecureSvm::homogeneousPolynomialKernel	(	const SecureSvm::EncryptedVector &	xx,
		const SecureSvm::ModelVector &	twoGammaSquaredSS
	)		const

private

Computes the second degree polynomial kernel on encrypted data.

Homogeneous polynomial kernel: $ K_i = (\gamma \sum_{j=1}^f(x_j \cdot s_{i,j}))^2 $ (where $ \gamma = 1 $)

Scaled homogeneous polynomial kernel: $ K_i^* = (\sum_{j=1}^f(x_j \cdot sc_f \cdot s_{i,j} \cdot sc_f))^2 $

Encrypted scaled homogeneous polynomial kernel: $ [K_i^*] = \prod_{j=1}^{f-1} \prod_{k=j+1}^{f}[x_j \cdot x_k \cdot sc_f^2]^{2 \cdot s_{i,j} \cdot s_{i,k} \cdot sc_f^2}) \cdot \prod_{j=1}^f([x^2_j \cdot sc_f^2]^{s^2_{i,j} \cdot sc_f^2}) $ and $ sc_b = sc_f^4 $

Since $ x_i x_j = x_j x_i $ and $ s_i s_j = s_j s_i $, the diagonal elements are taken into account only once!

Parameters

xx	the encrypted attribute vector product combinations, $ x_i x_j $, stored as an unraveled upper triangular matrix
twoGammaSquaredSS	the model weights vector product combinations, $ 2 \gamma^2 s_i s_j $, where $ i \neq j $ and $ \gamma^2 s_i s_j $, where $ i = j $, stored as an unraveled upper triangular matrix

Returns: The encrypted value of the kernel

Initialize the accumulator with [0] for the homomorphic addition to work!

Definition at line 579 of file secure_svm.cpp.

Paillier::Ciphertext SeComLib::SecureRecommendations::SecureSvm::inhomogeneousPolynomialKernel	(	const SecureSvm::EncryptedVector &	x,
		const SecureSvm::EncryptedVector &	xx,
		const SecureSvm::ModelVector &	twoGammaS,
		const SecureSvm::ModelVector &	twoGammaSquaredSS
	)		const

private

Computes the second degree polynomial kernel on encrypted data.

Inhomogeneous polynomial kernel: $ K_i = (\gamma \sum_{j=1}^f(x_j \cdot s_{i,j}) + 1)^2 $

Scaled inhomogeneous polynomial kernel: $ K_i^* = (\gamma \cdot sc_{\gamma} \sum_{j=1}^f(x_j \cdot sc_f \cdot s_{i,j} \cdot sc_f) + sc_{\gamma} \cdot sc_f^2)^2 $

Encrypted scaled inhomogeneous polynomial kernel: $ [K_i^*] = (\prod_{j=1}^{f-1} \prod_{k=j+1}^{f}([x_j \cdot x_k \cdot sc_f^2]^{2 \cdot \gamma^2 \cdot sc_{\gamma}^2 \cdot s_{i,j} \cdot s_{i,k} \cdot sc_f^2})) \cdot (\prod_{j=1}^f([x^2_j \cdot sc_f^2]^{\gamma^2 \cdot sc_{\gamma}^2 \cdot s^2_{i,j} \cdot sc_f^2})) \cdot (\prod_{j=1}^f([x_j \cdot sc_f]^{2 \cdot \gamma \cdot sc_{\gamma}^2 \cdot s_{i,j} \cdot sc_f^3})) \cdot [sc_{\gamma}^2 \cdot sc_f^4] $ and $ sc_b = sc_{\gamma}^2 \cdot sc_f^4 $

Since $ x_i x_j = x_j x_i $ and $ s_i s_j = s_j s_i $, the diagonal elements are taken into account only once!

Parameters

x	the encrypted attribute vector
xx	the encrypted attribute vector product combinations, $ x_i x_j $, stored as an unraveled upper triangular matrix
twoGammaS	scaled $ 2 \gamma s_i $
twoGammaSquaredSS	the model weights vector product combinations, $ 2 \gamma^2 s_i s_j $, where $ i \neq j $ and $ \gamma^2 s_i s_j $, where $ i = j $, stored as an unraveled upper triangular matrix

Returns: The encrypted value of the kernel

Definition at line 630 of file secure_svm.cpp.

Paillier::Ciphertext SeComLib::SecureRecommendations::SecureSvm::linearKernel	(	const SecureSvm::EncryptedVector &	x,
		const SecureSvm::ModelVector &	s
	)		const

private

Computes the linear kernel on encrypted data.

Linear kernel: $ K_i = \sum_{j=1}^f(x_j \cdot s_{i,j}) $

Scaled linear kernel: $ K_i^* = \sum_{j=1}^f(x_j \cdot sc_f \cdot s_{i,j} \cdot sc_f) $

Encrypted scaled linear kernel: $ [K_i^*] = \prod_{j=1}^f([x_j \cdot sc_f]^{s_{i,j} \cdot sc_f}) $$ and $ $ sc_b = sc_f^2 $

Parameters

x	the encrypted attribute vector
s	a model vector

Returns: The encrypted value of the kernel

Initialize the accumulator with [0] for the homomorphic addition to work!!!

Definition at line 550 of file secure_svm.cpp.

Paillier::Ciphertext SeComLib::SecureRecommendations::SecureSvm::Predict	(	const SecureSvm::EncryptedVector &	x,
		const SecureSvm::EncryptedVector &	xx = `SecureSvm::nullVector`,
		const SecureSvm::EncryptedVector &	xSquared = `SecureSvm::nullVector`
	)		const

Computes the prediction for a given set of data.

Evaluates the encrypted prediction function, $ [f(x)] $

$ f(x) = \sum_{i=1}^t (c_i \cdot a_i \cdot K_i) + b $

Scaled prediction function: $ f(x)^* = \sum_{i=1}^t (c_i \cdot a_i^* \cdot sc_a \cdot K_i) + b^* \cdot sc_a \cdot sc_b $

Encrypted scaled prediction function: $ [f(x)^*] = \prod_{i=1}^t ([K_i]^{c_i \cdot a_i^* \cdot sc_a}) \cdot [b^* \cdot sc_a \cdot sc_b] $

Where $ a_i^* = \frac{a_i}{m} $, $ b^* = \frac{b}{m} $ and $ m = min(min(a_i), b) $. Also, $ t $ is the number of SV.

If the sign of the labels produced by libsvm is reversed, then the signs of $ a_i $ and $ b $ are reversed during preprocessing. See preprocessData() for details.

Parameters

x	the encrypted attribute vector
xx	the encrypted attribute vector product combinations, $ x_i x_j $, stored as an unraveled upper triangular matrix (defaults to SecureSvm::nullVector)
xSquared	the encrypted squared attribute vector (defaults to SecureSvm::nullVector)

Returns: The encrypted value of the kernel

Exceptions

std::runtime_error Invalid kernel type.

Initialize the accumulator with [0] for the homomorphic addition to work!!!

Compute $ (1 + c d) $ for the inverse quadratic RBF kernel and use an interactive protocol to produce the actual kernel values

Todo:: Throw a custom error here

Compute $ \prod_i{([K(s_i, x)]^{a_i})} $

The inverse quadratic RBF kernel requires an interactive protocol to compute the kernel values

Interact with the client to compute $ [K] = [1 / denominator] $

Definition at line 208 of file secure_svm.cpp.

void SeComLib::SecureRecommendations::SecureSvm::preprocessData ( )

private

Performs scalings and encryptions.

Preprocess the SVM model parameters and vectors required for computing f

Exceptions

std::runtime_error Computed scaling is too large.

If the training file has a negative value as the first label, then we need to invert the sign of the a and b model parameters. Details here: http://www.csie.ntu.edu.tw/~cjlin/libsvm/faq.html#f430

Scale the gamma parameter

Determine the amount of scaling which needs to be applied to $ a_i $

Since $ f(x) = \sum_i{a_i K(s_i, x)} + b $ and we are only interested in the sign of $ f $, we can divide both $ a_i $ and $ b $ by $ \min(|a_i|, |b|) $ such that the smallest value becomes 1

Scale the $ a_i $ parameters

We need to check if the sign of the prediction needs to be inverted.

Scale and encrypt the $ b $ parameter

Todo:: Throw a custom error here

Precompute the scaled model vector factors

Temporary vector containing scaled model weights

Temporary vector containing scaled $ 2 \gamma * s_i $

Temporary vector containing scaled $ -2 s_i $

Polynomial kernel => need to compute the weight combinations, $ s_i s_j $, of the model, stored as an unraveled upper triangular matrix. We also multiply them by two (when $ i \neq j $), because $ s_i s_j = s_j s_i $ (see the polynomial kernels implementation for details). We also multiply the products by $ \gamma^2 $.

Inverse quadratic RBF kernel => need to compute $ [s_i^2] $

W A R N I N G!!! DO NOT multiply the diagonal with 2! (see the polynomial kernels implementation for details)

Compute the $ 2 \gamma * s_i $ factor for inhomogeneous polynomial, SCALED ACCORDINGLY (see the inhomogeneous polynomial kernel implementation for details on the required scaling)

Compute the $ s_i^2 $ factors

Compute the $ -2 s_i $ factors

Compute [scaled 1] for the inhomogeneous polynomial kernel

Compute [scaled 1] for the inverse quadratic RBF kernel denominator

Scale the divisor of the interactive division protocol for the inverse quadratic RBF kernel

Precompute [0] for optimization purposes

Definition at line 287 of file secure_svm.cpp.

Member Data Documentation

const std::map< std::string, SecureSvm::KernelTypes > SeComLib::SecureRecommendations::SecureSvm::kernelTypesMap

staticprivate

Initial value:

= boost::assign::map_list_of("linear", SecureSvm::linear)
                                                                                                                ("homogeneous_poly", SecureSvm::homogeneousPolynomial)
                                                                                                                ("inhomogeneous_poly", SecureSvm::inhomogeneousPolynomial)
                                                                                                                ("rbf", SecureSvm::inverseQuadraticRBF)

Map kernel names to the kernelTypes enum.

Initialize the kernel types map

Definition at line 93 of file secure_svm.h.

struct svm_model* SeComLib::SecureRecommendations::SecureSvm::model

private

Contains the trained SVM model. Set this to NULL if the class is constructed with the default constructor

Todo:: Make this a local variable and wrap it in a std::unique_ptr

Definition at line 106 of file secure_svm.h.

const SecureSvm::EncryptedVector SeComLib::SecureRecommendations::SecureSvm::nullVector

static

Use this to pass a NULL vector to the Predict method;.

Initialize the nullVector instance

Definition at line 65 of file secure_svm.h.

BigInteger SeComLib::SecureRecommendations::SecureSvm::svWeightScaling

private

The scaling applied to the SVM parameters, $ a_i $ and $ b $ (b is -rho in libsvm) We want all $ a_i $ to be > minimumAiValue

Definition at line 113 of file secure_svm.h.

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

Public Types

Public Member Functions

Static Public Member Functions

Static Public Attributes

Private Types

Private Member Functions

Private Attributes

Static Private Attributes

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation