Implementation of the public-key DGK Cryptosystem. More...

#include <dgk.h>

Inheritance diagram for SeComLib::Core::Dgk:

Public Member Functions
	Dgk (const bool precomputeDecryptionMap=false)

	Dgk (const DgkPublicKey &publicKey)
	Creates an instance of the class for homomorphic operations and ecryption. More...

	Dgk (const DgkPublicKey &publicKey, const DgkPrivateKey &privateKey, const bool precomputeDecryptionMap=false)
	Creates an instance of the class for homomorphic operations, ecryption and decryption. More...

	~Dgk ()
	Destructor.

virtual bool	GenerateKeys ()
	Generate the public and private keys. More...

virtual BigInteger	DecryptInteger (const Ciphertext &ciphertext) const

virtual Ciphertext	EncryptIntegerNonrandom (const BigInteger &plaintext) const
	Encrypt number without randomization. More...

virtual Randomizer	GetRandomizer () const
	Compute the random factor required for the encryption operation. More...

virtual Ciphertext	RandomizeCiphertext (const Ciphertext &ciphertext) const
	Randomize encrypted number with a self-generated random value. More...

virtual const BigInteger &	GetMessageSpaceUpperBound () const
	Returns the message space upper bound. More...

virtual size_t	GetMessageSpaceSize () const
	Returns the message space bit size. More...

bool	IsEncryptedZero (const Ciphertext &ciphertext) const
	Determines if ciphertext contains an encryption of 0 or not. More...

Public Member Functions inherited from SeComLib::Core::CryptoProvider< DgkPublicKey, DgkPrivateKey, DgkCiphertext, DgkRandomizer >
	CryptoProvider (const unsigned int keyLength)
	Constructor. More...

	CryptoProvider (const DgkPublicKey &publicKey, const unsigned int keyLength)
	Constructor. More...

	CryptoProvider (const DgkPublicKey &publicKey, const DgkPrivateKey &privateKey, const unsigned int keyLength)
	Constructor. More...

virtual	~CryptoProvider ()
	Destructor.

virtual DgkCiphertext	EncryptInteger (const BigInteger &plaintext) const
	Encrypt an integer and apply randomization. More...

const BigInteger &	GetEncryptionModulus () const
	Returns the modulus required for reducing the encryption after randomization. More...

virtual const BigInteger &	GetPositiveNegativeBoundary () const
	Returns the biggest positive number that can be encrypted without overflowing. More...

const DgkPublicKey &	GetPublicKey () const
	Public key getter. More...

const DgkPrivateKey &	GetPrivateKey () const
	Private key getter. More...

Ciphertext	GetEncryptedZero (const bool randomized=true) const
	Returns [0]. More...

Ciphertext	GetEncryptedOne (const bool randomized=true) const
	Returns [1]. More...

Private Types
typedef std::map< const BigInteger, BigInteger >	DecryptionMap
	std::map template specialization

Private Member Functions
virtual void	validateParameters ()
	Validate configuration parameters. More...

virtual void	doPrecomputations ()
	Precompute values for speedups. More...

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

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

Private Attributes
const unsigned int	t
	Parameter \( t \).

const unsigned int	l
	Parameter \( \ell \).

bool	precomputeDecryptionMap
	If true, full decryptions are enabled and the decryption map is (pre)computed.

DecryptionMap	decryptionMap
	Contains all possible values of \( (g^{v_p v_q})^m \pmod n \), where \( m \in \mathbb{Z}_u \), and it is required for decryption.

BigInteger	pTimesPInvModQ
	Contains \( p (p^{-1} \pmod q) \).

BigInteger	qTimesQInvModP
	Contains \( q (q^{-1} \pmod p) \).

Additional Inherited Members
Public Types inherited from SeComLib::Core::CryptoProvider< DgkPublicKey, DgkPrivateKey, DgkCiphertext, DgkRandomizer >
typedef DgkCiphertext	Ciphertext
	Provide public access to the T_Ciphertext type.

typedef DgkRandomizer	Randomizer
	Provide public access to the T_Randomizer type.

Protected Types inherited from SeComLib::Core::CryptoProvider< DgkPublicKey, DgkPrivateKey, DgkCiphertext, DgkRandomizer >
typedef RandomizerCache < RandomizerContainer < CryptoProvider< DgkPublicKey, DgkPrivateKey, DgkCiphertext, DgkRandomizer > , RandomizerCacheParameters > >	RandomizerCacheType
	Data type of the randomizer cache.

Protected Attributes inherited from SeComLib::Core::CryptoProvider< DgkPublicKey, DgkPrivateKey, DgkCiphertext, DgkRandomizer >
std::unique_ptr < RandomizerCacheType >	randomizerCache
	Lazy loading randomizer cache.

DgkPublicKey	publicKey
	Public key container.

DgkPrivateKey	privateKey
	Private key container.

unsigned int	keyLength
	The key length in bits.

std::shared_ptr< BigInteger >	encryptionModulus
	The encryption modulus.

BigInteger	positiveNegativeBoundary
	Contains the delimiter between positive and negative values in the message space (usually \( \lfloor messagespace / 2 \rfloor \))

bool	hasPrivateKey
	Boolean flag that enables decryption if the private key is present.

bool	precomputeSpeedupValues
	Boolean flag that indicates wether doPrecomputations() should precompute certain values.

DgkCiphertext	encryptedZero
	Contains [0] used as initializer for homomorphic addition accumulators. Precompute it for optimization purposes.

DgkCiphertext	encryptedOne
	Contains [1].

Detailed Description

Implementation of the public-key DGK Cryptosystem.

Todo:: Disable encryption speedups if we do not have the private key

Definition at line 104 of file dgk.h.

Constructor & Destructor Documentation

SeComLib::Core::Dgk::Dgk ( const bool precomputeDecryptionMap = false )

Default constructor

Todo:: Create a custom exception class for parameter validation.

Sets the specified key size from the configuration file (defaults to 1024).

Sets parameters t (defaults to 160) and l (defaults to 16)

Parameters

precomputeDecryptionMap Populate the decryption map, required to do full decryption (defaults to false)

Definition at line 78 of file dgk.cpp.

SeComLib::Core::Dgk::Dgk ( const DgkPublicKey & publicKey )

Creates an instance of the class for homomorphic operations and ecryption.

Performs required precomputations.

Parameters

publicKey a PublicKey structure

Definition at line 90 of file dgk.cpp.

SeComLib::Core::Dgk::Dgk	(	const DgkPublicKey &	publicKey,
		const DgkPrivateKey &	privateKey,
		const bool	precomputeDecryptionMap = `false`
	)

Creates an instance of the class for homomorphic operations, ecryption and decryption.

Performs required precomputations.

Parameters

publicKey	a DgkPublicKey structure
privateKey	a DgkPrivateKey structure
precomputeDecryptionMap	Populate the decryption map, required to do full decryption (defaults to false)

Definition at line 106 of file dgk.cpp.

Member Function Documentation

BigInteger SeComLib::Core::Dgk::DecryptInteger ( const Ciphertext & ciphertext ) const

virtual

Decrypt number

Todo:: Throw a custom exception!!!

If \( plaintext \geq \lfloor messagespace / 2 \), it is remapped to a negative value.

Parameters

ciphertext the ciphertext integer

Returns: Deciphered plaintext

Exceptions

std::runtime_error	the ciphertext can not be decrypted
std::runtime_error	operation requires the private key
std::runtime_error	operation requires the decryption map

\( m \) is uniquely determined by either \( E_{pk}(m,r)^{v_p} = g^{v_p m} \pmod p \) or \( E_{pk}(m,r)^{v_q} = g^{v_q m} \pmod q \). Since we cannot determine \( m \) directly, we precompute all \( g^{v_p m} \pmod p \) values, we store them in an std::map and we try to find m that matches \( c^{v_p} \pmod p \)

Shortcut: if \( c^{v_p} \pmod p = 1 \), then \( c = \llbracket 0 \rrbracket \)

If \( plaintext < \lfloor messagespace / 2 \rfloor \Rightarrow plaintext \geq 0 \) otherwise if \( plaintext < 0 \Rightarrow plaintext = plaintext - messageSpaceUpperBound \)

Implements SeComLib::Core::CryptoProvider< DgkPublicKey, DgkPrivateKey, DgkCiphertext, DgkRandomizer >.

Definition at line 309 of file dgk.cpp.

void SeComLib::Core::Dgk::doPrecomputations ( )

privatevirtual

Precompute values for speedups.

Precomputes the message space delimiter between positive and negative values.

Precomputes [0] and [1].

Precompute all possible values of \( g^{v_p m} \pmod p \) or \( g^{v_q m} \pmod q \) to speed up decryption, where \( m \in \mathbb{Z}_u \). We choose to compute \( g^{v_p m} \pmod p \)

Speed optimizations for encryption: compute \( p (p^{-1} \pmod q) \) and \( q (q^{-1} \pmod p) \)

Todo:: Catch a custom exception here

Populate the randomizer cache

Implements SeComLib::Core::CryptoProvider< DgkPublicKey, DgkPrivateKey, DgkCiphertext, DgkRandomizer >.

Definition at line 507 of file dgk.cpp.

Dgk::Ciphertext SeComLib::Core::Dgk::EncryptIntegerNonrandom ( const BigInteger & plaintext ) const

virtual

Encrypt number without randomization.

Computes \( c_{nonrand} = g^m \pmod n \)

Parameters

plaintext the plaintext integer

Returns: Encrypted ciphertext

"Standard" version: \( c = g^m h^r \pmod n \)
"Shortcut" version - use the Chinese Remainder Theorem \( \left( x = \sum_{i} a_i \frac{N}{n_i} \left[\left(\frac{N}{n_i}\right)^{-1}\right]_{n_i} \right) \) to speed up computations:
- \( c_{nonrand} = g^m \pmod n = (g^m \bmod p) q (q^{-1}\bmod p) + (g^m \bmod q) p (p^{-1}\bmod q) \pmod n \)
- \( r_h = h^r \pmod {n} = (h^r \bmod p) q (q^{-1}\bmod p) + (h^r \bmod q) p (p^{-1}\bmod q) \pmod n \)

The computation is performed in two steps:

encrypt data (compute \( c_{nonrand} \))
randomize ciphertext (compute \( c_{nonrand} r_h \pmod n \))

If \( plaintext < 0 \), we remap it to the second half of the message space

Todo:: Speedup hint: remove the modulo n reduction, since it's performed later in RandomizeCiphertext...???

Standard version: \( c_{nonrand} = g^m \pmod n \)

Fast version: \( c_{nonrand} = (g^m \bmod p) q (q^{-1}\bmod p) + (g^m \bmod q) p (p^{-1}\bmod q) \pmod n \)

Implements SeComLib::Core::CryptoProvider< DgkPublicKey, DgkPrivateKey, DgkCiphertext, DgkRandomizer >.

Definition at line 356 of file dgk.cpp.

bool SeComLib::Core::Dgk::GenerateKeys ( )

virtual

Generate the public and private keys.

Generates the public and private keys via the generateKeys private method and ensures that they are successfully generated.

Precomputes the decryption map and values required for speeding-up the encryption.

\( h \) and \( g \) are computed using algorithms described in the Handbook of Applied Cryptography by Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone (http://cacr.uwaterloo.ca/hac/).

Specifically, we use Algorithm 4.83, Chapter 4: Selecting an element of maximum order in \( \mathbb{Z}_n^* \), where \( n = p q \)

INPUT: two distinct odd primes, \( p \), \( q \), and the factorizations of \( p - 1 \) and \( q - 1 \).

OUTPUT: an element \( \alpha \) of maximum order \( lcm(p - 1; q - 1) \) in \( \mathbb{Z}_n^* \), where \( n = p q \).

Use Algorithm 4.80 with \( G = \mathbb{Z}_p^* \) and \( n = p - 1 \) to find a generator \( a \) of \( \mathbb{Z}_p^* \).
Use Algorithm 4.80 with \( G = \mathbb{Z}_q^* \) and \( n = q - 1 \) to find a generator \( b \) of \( \mathbb{Z}_q^* \).
Use Gauss's algorithm (Algorithm 2.121) to find an integer \( \alpha \), \( 1 \leq \alpha \leq n - 1 \), satisfying \( \alpha \equiv a \pmod p \) and \( \alpha \equiv b \pmod q \).
Return \( \alpha \).

For completeness, here are the two algorithms referenced above in Algorithm 4.83:

Algorithm 4.80, Chapter 4: Finding a generator of a cyclic group

INPUT: a cyclic group \( G \) of order \( n \), and the prime factorization \( n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k} \)

OUTPUT: a generator \( \alpha \) of \( G \)

Choose a random element \( \alpha \) in \( G \)
For \( i \) from \( 1 \) to \( k \) do the following:
1. Compute \( b \gets a^{n/p_i} \) (N.B. \( \pmod n \))
2. If \( b = 1 \) then go to step 1.
Return \( \alpha \).

Algorithm 2.121, Chapter 2 (Gauss's algorithm): The solution \( x \) to the simultaneous congruences in the Chinese Remainder Theorem (Fact 2.120) may be computed as \( \sum_{i = 1}^{k}{a_i N_i M_i \pmod n} \), where \( N_i = n / n_i \) and \( M_i = N_i^{-1} \pmod {n_i} \). These computations can be performed in \( O((\lg n)^2) \) bit operations.

Fact 2.120, Chapter 2: (Chinese remainder theorem, CRT) If the integers \( n_1 \), \( n_2 \), ..., \( n_k \) are pairwise relatively prime, then the system of simultaneous congruences

\( x \equiv a_1 \pmod {n_1} \)

\( x \equiv a_2 \pmod {n_2} \)

\( \vdots \)

\( x \equiv a_k \pmod {n_k} \)

has a unique solution modulo \( n = n_1 n_2 \cdots n_k \).

Returns: Always true, for now.

Exceptions

std::runtime_error parameter errors.

Generate \( u \) as the smallest prime having more than \( \ell + 2 \) bits.

Generate \( v_p \) and \( v_q \), two t bit primes.

We need to prevent \( v_p \) and \( v_q \) from dividing both p - 1 and q - 1, so we ensure that \( v_p \neq v_q \). Otherwise, one could compute \( a = (n - 1) / u^j \), where \( u^j \) is the maximal power of \( u \) that divides \( n - 1\), and, thus, it can be determined which numbers have order \( a \) in \( H \).

Generate \( p = 2 p_r v_p u + 1 \) and \( q = 2 q_r v_q u + 1 \), where \( p_r \) and \( q_r \) are prime numbers. We impose \( p - 1 = 2 p_r v_p u \) and \( q - 1 = 2 q_r v_q u \) because, in order to generate \( h \) and \( g \), we need to have the factorization of \( p - 1 \) and \( q - 1 \). The factor 2 is required because the product of three odd primes is odd, and, thus, by adding one, we get an even number larger than 2 (which can't be prime) \( p \) and \( q \) must have \( k/2 \) bits length.

Todo:: Throw a custom exception here!

Todo:: Throw a custom exception here!

Compute \( n = p q \)

Compute \( h \) and \( g \): We compute \( h_r \) and \( g_r \) of order \( LCM(p - 1, q - 1) = (p - 1)(q - 1) / GCD(p - 1, q - 1) = 2 u p_r v_p q_r v_q \) in \( \mathbb{Z}_n^* \) with Algorithm 4.83

Since \( h \) must have order \( v_p v_q \) in \( \mathbb{Z}_n^* \), compute \( h = h_r^{2 u p_r q_r} \pmod n \)

Since \( g \) must have order \( u v_p v_q \) in \( \mathbb{Z}_n^* \), compute \( g = g_r^{2 p_r q_r} \pmod n \)

Implements SeComLib::Core::CryptoProvider< DgkPublicKey, DgkPrivateKey, DgkCiphertext, DgkRandomizer >.

Definition at line 161 of file dgk.cpp.

size_t SeComLib::Core::Dgk::GetMessageSpaceSize ( ) const

virtual

Returns the message space bit size.

Returns: The message space bit size.

Implements SeComLib::Core::CryptoProvider< DgkPublicKey, DgkPrivateKey, DgkCiphertext, DgkRandomizer >.

Definition at line 451 of file dgk.cpp.

const BigInteger & SeComLib::Core::Dgk::GetMessageSpaceUpperBound ( ) const

virtual

Returns the message space upper bound.

Returns: \( u \)

Implements SeComLib::Core::CryptoProvider< DgkPublicKey, DgkPrivateKey, DgkCiphertext, DgkRandomizer >.

Definition at line 444 of file dgk.cpp.

Dgk::Randomizer SeComLib::Core::Dgk::GetRandomizer ( ) const

virtual

Compute the random factor required for the encryption operation.

Selects random \( r \in \mathbb{Z}_{v_p v_q} \) and computes \( h^r \pmod n \)

Speedup hint: remove the modulo n reduction?

Returns: the random factor

The public key does not allow us to compute \( v_p * v_q \), so we choose a random number of size \( 2 t \)

"Standard" version: \( h^r \pmod n \)

"Shortcut" version: \( h^r \pmod {n} = (h^r \bmod p) q (q^{-1}\bmod p) + (h^r \bmod q) p (p^{-1}\bmod q) \pmod n \)

Implements SeComLib::Core::CryptoProvider< DgkPublicKey, DgkPrivateKey, DgkCiphertext, DgkRandomizer >.

Definition at line 402 of file dgk.cpp.

bool SeComLib::Core::Dgk::IsEncryptedZero ( const Ciphertext & ciphertext ) const

Determines if ciphertext contains an encryption of 0 or not.

If and only if \( m = 0 \), then both \( c^{v_p} \pmod p = 1 \) and \( c^{v_q} \pmod q = 1 \). It suffices to test only \( c^{v_p} \pmod p \).

This is faster than the actual decryption, since the table lookup is not required.

Parameters

ciphertext a DGK ciphertext

Returns: True if ciphertext = [0] and fase otherwise

Definition at line 463 of file dgk.cpp.

Dgk::Ciphertext SeComLib::Core::Dgk::RandomizeCiphertext ( const Ciphertext & ciphertext ) const

virtual

Randomize encrypted number with a self-generated random value.

Computes \( c = c h^r \pmod n \)

Parameters

ciphertext the ciphertext integer

Returns: The randomized ciphertext

Implements SeComLib::Core::CryptoProvider< DgkPublicKey, DgkPrivateKey, DgkCiphertext, DgkRandomizer >.

Definition at line 437 of file dgk.cpp.

void SeComLib::Core::Dgk::validateParameters ( )

privatevirtual

Validate configuration parameters.

Exceptions

std::runtime_error the configuration parameters are invalid

Todo:: Throw custom parameter exceptions below!!!

Implements SeComLib::Core::CryptoProvider< DgkPublicKey, DgkPrivateKey, DgkCiphertext, DgkRandomizer >.

Definition at line 476 of file dgk.cpp.

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

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation