API Documentation¶
Paillier¶
Paillier encryption library for partially homomorphic encryption.
-
class
phe.paillier.
EncryptedNumber
(public_key, ciphertext, exponent=0)[source]¶ Bases:
object
Represents the Paillier encryption of a float or int.
Typically, an EncryptedNumber is created by
PaillierPublicKey.encrypt()
. You would only instantiate an EncryptedNumber manually if you are de-serializing a number someone else encrypted.Paillier encryption is only defined for non-negative integers less than
PaillierPublicKey.n
.EncodedNumber
provides an encoding scheme for floating point and signed integers that is compatible with the partially homomorphic properties of the Paillier cryptosystem:- D(E(a) * E(b)) = a + b
- D(E(a)**b) = a * b
where a and b are ints or floats, E represents encoding then encryption, and D represents decryption then decoding.
Parameters: - public_key (PaillierPublicKey) – the
PaillierPublicKey
against which the number was encrypted. - ciphertext (int) – encrypted representation of the encoded number.
- exponent (int) – used by
EncodedNumber
to keep track of fixed precision. Usually negative.
-
public_key
¶ PaillierPublicKey – the
PaillierPublicKey
against which the number was encrypted.
-
exponent
¶ int – used by
EncodedNumber
to keep track of fixed precision. Usually negative.
Raises: TypeError
– if ciphertext is not an int, or if public_key is not aPaillierPublicKey
.-
__radd__
(other)[source]¶ Called when Python evaluates 34 + <EncryptedNumber> Required for builtin sum to work.
-
_add_encoded
(encoded)[source]¶ Returns E(a + b), given self=E(a) and b.
Parameters: encoded (EncodedNumber) – an EncodedNumber
to be added to self.Returns: - E(a + b), calculated by encrypting b and
- taking the product of E(a) and E(b) modulo
n
** 2.
Return type: EncryptedNumber Raises: ValueError
– if scalar is out of range or precision.
-
_add_encrypted
(other)[source]¶ Returns E(a + b) given E(a) and E(b).
Parameters: other (EncryptedNumber) – an EncryptedNumber to add to self. Returns: - E(a + b), calculated by taking the product
- of E(a) and E(b) modulo
n
** 2.
Return type: EncryptedNumber Raises: ValueError
– if numbers were encrypted against different keys.
-
_add_scalar
(scalar)[source]¶ Returns E(a + b), given self=E(a) and b.
Parameters: scalar – an int or float b, to be added to self. Returns: - E(a + b), calculated by encrypting b and
- taking the product of E(a) and E(b) modulo
n
** 2.
Return type: EncryptedNumber Raises: ValueError
– if scalar is out of range or precision.
-
_raw_add
(e_a, e_b)[source]¶ Returns the integer E(a + b) given ints E(a) and E(b).
N.B. this returns an int, not an EncryptedNumber, and ignores
ciphertext
Parameters: - e_a (int) – E(a), first term
- e_b (int) – E(b), second term
Returns: - E(a + b), calculated by taking the product of E(a) and
E(b) modulo
n
** 2.
Return type: int
-
_raw_mul
(plaintext)[source]¶ Returns the integer E(a * plaintext), where E(a) = ciphertext
Parameters: plaintext (int) – number by which to multiply the EncryptedNumber. plaintext is typically an encoding. 0 <= plaintext <
n
Returns: - Encryption of the product of self and the scalar
encoded in plaintext.
Return type: int
Raises: TypeError
– if plaintext is not an int.ValueError
– if plaintext is not between 0 andPaillierPublicKey.n
.
-
ciphertext
(be_secure=True)[source]¶ Return the ciphertext of the EncryptedNumber.
Choosing a random number is slow. Therefore, methods like
__add__()
and__mul__()
take a shortcut and do not follow Paillier encryption fully - every encrypted sum or product should be multiplied by r **n
for random r < n (i.e., the result is obfuscated). Not obfuscating provides a big speed up in, e.g., an encrypted dot product: each of the product terms need not be obfuscated, since only the final sum is shared with others - only this final sum needs to be obfuscated.Not obfuscating is OK for internal use, where you are happy for your own computer to know the scalars you’ve been adding and multiplying to the original ciphertext. But this is not OK if you’re going to be sharing the new ciphertext with anyone else.
So, by default, this method returns an obfuscated ciphertext - obfuscating it if necessary. If instead you set be_secure=False then the ciphertext will be returned, regardless of whether it has already been obfuscated. We thought that this approach, while a little awkward, yields a safe default while preserving the option for high performance.
Parameters: be_secure (bool) – If any untrusted parties will see the returned ciphertext, then this should be True. Returns: - an int, the ciphertext. If be_secure=False then it might be
- possible for attackers to deduce numbers involved in calculating this ciphertext.
-
decrease_exponent_to
(new_exp)[source]¶ Return an EncryptedNumber with same value but lower exponent.
If we multiply the encoded value by
EncodedNumber.BASE
and decrementexponent
, then the decoded value does not change. Thus we can almost arbitrarily ratchet down the exponent of an EncryptedNumber - we only run into trouble when the encoded integer overflows. There may not be a warning if this happens.When adding EncryptedNumber instances, their exponents must match.
This method is also useful for hiding information about the precision of numbers - e.g. a protocol can fix the exponent of all transmitted EncryptedNumber instances to some lower bound(s).
Parameters: new_exp (int) – the desired exponent. Returns: - Instance with the same plaintext and desired
- exponent.
Return type: EncryptedNumber Raises: ValueError
– You tried to increase the exponent.
-
obfuscate
()[source]¶ Disguise ciphertext by multiplying by r ** n with random r.
This operation must be performed for every EncryptedNumber that is sent to an untrusted party, otherwise eavesdroppers might deduce relationships between this and an antecedent EncryptedNumber.
For example:
enc = public_key.encrypt(1337) send_to_nsa(enc) # NSA can't decrypt (we hope!) product = enc * 3.14 send_to_nsa(product) # NSA can deduce 3.14 by bruteforce attack product2 = enc * 2.718 product2.obfuscate() send_to_nsa(product) # NSA can't deduce 2.718 by bruteforce attack
-
class
phe.paillier.
PaillierPrivateKey
(public_key, p, q)[source]¶ Bases:
object
Contains a private key and associated decryption method.
Parameters: - public_key (
PaillierPublicKey
) – The corresponding public key. - p (int) – private secret - see Paillier’s paper.
- q (int) – private secret - see Paillier’s paper.
-
public_key
¶ PaillierPublicKey – The corresponding public key.
-
p
¶ int – private secret - see Paillier’s paper.
-
q
¶ int – private secret - see Paillier’s paper.
-
psquare
¶ int – p^2
-
qsquare
¶ int – q^2
-
p_inverse
¶ int – p^-1 mod q
-
hp
¶ int – h(p) - see Paillier’s paper.
-
hq
¶ int – h(q) - see Paillier’s paper.
-
crt
(mp, mq)[source]¶ The Chinese Remainder Theorem as needed for decryption. Returns the solution modulo n=pq.
Parameters: - mp (int) – the solution modulo p.
- mq (int) – the solution modulo q.
-
decrypt
(encrypted_number)[source]¶ Return the decrypted & decoded plaintext of encrypted_number.
Uses the default
EncodedNumber
, if using an alternative encoding scheme, usedecrypt_encoded()
orraw_decrypt()
instead.Parameters: encrypted_number (EncryptedNumber) – an
EncryptedNumber
with a public key that matches this private key.Returns: - the int or float that EncryptedNumber was holding. N.B. if
the number returned is an integer, it will not be of type float.
Raises: TypeError
– If encrypted_number is not anEncryptedNumber
.ValueError
– If encrypted_number was encrypted against a different key.
-
decrypt_encoded
(encrypted_number, Encoding=None)[source]¶ Return the
EncodedNumber
decrypted from encrypted_number.Parameters: - encrypted_number (EncryptedNumber) – an
EncryptedNumber
with a public key that matches this private key. - Encoding (class) – A class to use instead of
EncodedNumber
, the encoding used for the encrypted_number - used to support alternative encodings.
Returns: The decrypted plaintext.
Return type: EncodedNumber
Raises: TypeError
– If encrypted_number is not anEncryptedNumber
.ValueError
– If encrypted_number was encrypted against a different key.
- encrypted_number (EncryptedNumber) – an
-
static
from_totient
(public_key, totient)[source]¶ given the totient, one can factorize the modulus
The totient is defined as totient = (p - 1) * (q - 1), and the modulus is defined as modulus = p * q
Parameters: - public_key (PaillierPublicKey) – The corresponding public key
- totient (int) – the totient of the modulus
Returns: the
PaillierPrivateKey
that corresponds to the inputsRaises: ValueError
– if the given totient is not the totient of the modulus of the given public key
-
h_function
(x, xsquare)[source]¶ Computes the h-function as defined in Paillier’s paper page 12, ‘Decryption using Chinese-remaindering’.
-
l_function
(x, p)[source]¶ Computes the L function as defined in Paillier’s paper. That is: L(x,p) = (x-1)/p
-
raw_decrypt
(ciphertext)[source]¶ Decrypt raw ciphertext and return raw plaintext.
Parameters: ciphertext (int) – (usually from EncryptedNumber.ciphertext()
) that is to be Paillier decrypted.Returns: Paillier decryption of ciphertext. This is a positive integer < public_key.n
.Return type: int Raises: TypeError
– if ciphertext is not an int.
- public_key (
-
class
phe.paillier.
PaillierPrivateKeyring
(private_keys=None)[source]¶ Bases:
collections.abc.Mapping
Holds several private keys and can decrypt using any of them.
Acts like a dict, supports
del()
, and indexing with [], but adding keys is done usingadd()
.Parameters: private_keys (list of PaillierPrivateKey) – an optional starting list of PaillierPrivateKey
instances.-
add
(private_key)[source]¶ Add a key to the keyring.
Parameters: private_key (PaillierPrivateKey) – a key to add to this keyring.
-
decrypt
(encrypted_number)[source]¶ Return the decrypted & decoded plaintext of encrypted_number.
Parameters: encrypted_number (EncryptedNumber) – encrypted against a known public key, i.e., one for which the private key is on this keyring. Returns: the int or float that encrypted_number was holding. N.B. if the number returned is an integer, it will not be of type float. Raises: KeyError
– If the keyring does not hold the private key that decrypts encrypted_number.
-
-
class
phe.paillier.
PaillierPublicKey
(n)[source]¶ Bases:
object
Contains a public key and associated encryption methods.
Parameters: n (int) – the modulus of the public key - see Paillier’s paper. -
g
¶ int – part of the public key - see Paillier’s paper.
-
n
¶ int – part of the public key - see Paillier’s paper.
-
max_int
¶ int – Maximum int that may safely be stored. This can be increased, if you are happy to redefine “safely” and lower the chance of detecting an integer overflow.
-
encrypt
(value, precision=None, r_value=None)[source]¶ Encode and Paillier encrypt a real number value.
Parameters: - value – an int or float to be encrypted.
If int, it must satisfy abs(value) <
n
/3. If float, it must satisfy abs(value / precision) <<n
/3 (i.e. if a float is near the limit then detectable overflow may still occur) - precision (float) – Passed to
EncodedNumber.encode()
. If value is a float then precision is the maximum absolute error allowed when encoding value. Defaults to encoding value exactly. - r_value (int) – obfuscator for the ciphertext; by default (i.e. if r_value is None), a random value is used.
Returns: An encryption of value.
Return type: Raises: ValueError
– if value is out of range or precision is so high that value is rounded to zero.- value – an int or float to be encrypted.
If int, it must satisfy abs(value) <
-
encrypt_encoded
(encoding, r_value)[source]¶ Paillier encrypt an encoded value.
Parameters: - encoding – The EncodedNumber instance.
- r_value (int) – obfuscator for the ciphertext; by default (i.e. if r_value is None), a random value is used.
Returns: An encryption of value.
Return type:
-
raw_encrypt
(plaintext, r_value=None)[source]¶ Paillier encryption of a positive integer plaintext <
n
.You probably should be using
encrypt()
instead, because it handles positive and negative ints and floats.Parameters: - plaintext (int) – a positive integer <
n
to be Paillier encrypted. Typically this is an encoding of the actual number you want to encrypt. - r_value (int) – obfuscator for the ciphertext; by default (i.e. r_value is None), a random value is used.
Returns: Paillier encryption of plaintext.
Return type: int
Raises: TypeError
– if plaintext is not an int.- plaintext (int) – a positive integer <
-
-
phe.paillier.
generate_paillier_keypair
(private_keyring=None, n_length=2048)[source]¶ Return a new
PaillierPublicKey
andPaillierPrivateKey
.Add the private key to private_keyring if given.
Parameters: - private_keyring (PaillierPrivateKeyring) – a
PaillierPrivateKeyring
on which to store the private key. - n_length – key size in bits.
Returns: The generated
PaillierPublicKey
andPaillierPrivateKey
Return type: tuple
- private_keyring (PaillierPrivateKeyring) – a
Encoding¶
-
class
phe.encoding.
EncodedNumber
(public_key, encoding, exponent)[source]¶ Bases:
object
Represents a float or int encoded for Paillier encryption.
For end users, this class is mainly useful for specifying precision when adding/multiplying an
EncryptedNumber
by a scalar.If you want to manually encode a number for Paillier encryption, then use
encode()
, if de-serializing then use__init__()
.Note
If working with other Paillier libraries you will have to agree on a specific
BASE
andLOG2_BASE
- inheriting from this class and overriding those two attributes will enable this.Notes
Paillier encryption is only defined for non-negative integers less than
PaillierPublicKey.n
. Since we frequently want to use signed integers and/or floating point numbers (luxury!), values should be encoded as a valid integer before encryption.The operations of addition and multiplication [1] must be preserved under this encoding. Namely:
- Decode(Encode(a) + Encode(b)) = a + b
- Decode(Encode(a) * Encode(b)) = a * b
for any real numbers a and b.
Representing signed integers is relatively easy: we exploit the modular arithmetic properties of the Paillier scheme. We choose to represent only integers between +/-
max_int
, where max_int is approximatelyn
/3 (larger integers may be treated as floats). The range of values between max_int and n - max_int is reserved for detecting overflows. This encoding scheme supports properties #1 and #2 above.Representing floating point numbers as integers is a harder task. Here we use a variant of fixed-precision arithmetic. In fixed precision, you encode by multiplying every float by a large number (e.g. 1e6) and rounding the resulting product. You decode by dividing by that number. However, this encoding scheme does not satisfy property #2 above: upon every multiplication, you must divide by the large number. In a Paillier scheme, this is not possible to do without decrypting. For some tasks, this is acceptable or can be worked around, but for other tasks this can’t be worked around.
In our scheme, the “large number” is allowed to vary, and we keep track of it. It is:
One number has many possible encodings; this property can be used to mitigate the leak of information due to the fact that
exponent
is never encrypted.For more details, see
encode()
.Footnotes
[1] Technically, since Paillier encryption only supports multiplication by a scalar, it may be possible to define a secondary encoding scheme Encode’ such that property #2 is relaxed to:
Decode(Encode(a) * Encode’(b)) = a * bWe don’t do this.
Parameters: - public_key (PaillierPublicKey) – public key for which to encode
(this is necessary because
max_int
varies) - encoding (int) – The encoded number to store. Must be positive and
less than
max_int
. - exponent (int) – Together with
BASE
, determines the level of fixed-precision used in encoding the number.
-
public_key
¶ PaillierPublicKey – public key for which to encode (this is necessary because
max_int
varies)
-
encoding
¶ int – The encoded number to store. Must be positive and less than
max_int
.
-
exponent
¶ int – Together with
BASE
, determines the level of fixed-precision used in encoding the number.
-
BASE
= 16¶ Base to use when exponentiating. Larger BASE means that
exponent
leaks less information. If you vary this, you’ll have to manually inform anyone decoding your numbers.
-
FLOAT_MANTISSA_BITS
= 53¶
-
LOG2_BASE
= 4.0¶
-
decode
()[source]¶ Decode plaintext and return the result.
Returns: - the decoded number. N.B. if the number
- returned is an integer, it will not be of type float.
Return type: an int or float Raises: OverflowError
– if overflow is detected in the decrypted number.
-
decrease_exponent_to
(new_exp)[source]¶ Return an EncodedNumber with same value but lower exponent.
If we multiply the encoded value by
BASE
and decrementexponent
, then the decoded value does not change. Thus we can almost arbitrarily ratchet down the exponent of anEncodedNumber
- we only run into trouble when the encoded integer overflows. There may not be a warning if this happens.This is necessary when adding
EncodedNumber
instances, and can also be useful to hide information about the precision of numbers - e.g. a protocol can fix the exponent of all transmittedEncodedNumber
to some lower bound(s).Parameters: new_exp (int) – the desired exponent. Returns: - Instance with the same value and desired
- exponent.
Return type: EncodedNumber Raises: ValueError
– You tried to increase the exponent, which can’t be done without decryption.
-
classmethod
encode
(public_key, scalar, precision=None, max_exponent=None)[source]¶ Return an encoding of an int or float.
This encoding is carefully chosen so that it supports the same operations as the Paillier cryptosystem.
If scalar is a float, first approximate it as an int, int_rep:
for some (typically negative) integer exponent, which can be tuned using precision and max_exponent. Specifically,
exponent
is chosen to be equal to or less than max_exponent, and such that the number precision is not rounded to zero.Having found an integer representation for the float (or having been given an int scalar), we then represent this integer as a non-negative integer <
n
.Paillier homomorphic arithemetic works modulo
n
. We take the convention that a number x < n/3 is positive, and that a number x > 2n/3 is negative. The range n/3 < x < 2n/3 allows for overflow detection.Parameters: - public_key (PaillierPublicKey) – public key for which to encode
(this is necessary because
n
varies). - scalar – an int or float to be encrypted.
If int, it must satisfy abs(value) <
n
/3. If float, it must satisfy abs(value / precision) <<n
/3 (i.e. if a float is near the limit then detectable overflow may still occur) - precision (float) – Choose exponent (i.e. fix the precision) so that this number is distinguishable from zero. If scalar is a float, then this is set so that minimal precision is lost. Lower precision leads to smaller encodings, which might yield faster computation.
- max_exponent (int) – Ensure that the exponent of the returned EncryptedNumber is at most this.
Returns: Encoded form of scalar, ready for encryption against public_key.
Return type: - public_key (PaillierPublicKey) – public key for which to encode
(this is necessary because
Utilities¶
-
phe.util.
extended_euclidean_algorithm
(a, b)[source]¶ Extended Euclidean algorithm
Returns r, s, t such that r = s*a + t*b and r is gcd(a, b)
See <https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm>
-
phe.util.
getprimeover
(N)[source]¶ Return a random N-bit prime number using the System’s best Cryptographic random source.
Use GMP if available, otherwise fallback to PyCrypto
-
phe.util.
improved_i_sqrt
(n)[source]¶ taken from http://stackoverflow.com/questions/15390807/integer-square-root-in-python Thanks, mathmandan
-
phe.util.
invert
(a, b)[source]¶ The multiplicitive inverse of a in the integers modulo b.
Return int: x, where a * x == 1 mod b
-
phe.util.
is_prime
(n, mr_rounds=25)[source]¶ Test whether n is probably prime
See <https://en.wikipedia.org/wiki/Primality_test#Probabilistic_tests>
Parameters: - n (int) – the number to be tested
- mr_rounds (int, optional) – number of Miller-Rabin iterations to run; defaults to 25 iterations, which is what the GMP library uses
Returns: when this function returns False, n is composite (not prime); when it returns True, n is prime with overwhelming probability
Return type: bool
-
phe.util.
miller_rabin
(n, k)[source]¶ Run the Miller-Rabin test on n with at most k iterations
Parameters: - n (int) – number whose primality is to be tested
- k (int) – maximum number of iterations to run
Returns: If n is prime, then True is returned. Otherwise, False is returned, except with probability less than 4**-k.
Return type: bool
See <https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test>