paillier

package module
v0.0.0-...-753322e Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Aug 10, 2018 License: MIT Imports: 9 Imported by: 5

README

paillier

Go implementation of the paillier cryptosystem and threshold paillier crytposystem.

travis

introduction

Implementation of the paillier cryptosystem. See http://en.wikipedia.org/wiki/Paillier_cryptosystem for an introduction.

The threshold paillier cryptosystem is a translation of the java version that can be found at http://cs.utdallas.edu/dspl/cgi-bin/pailliertoolbox/ that is an implementation of the algorithm defined in Damgård's paper "A Generalization of Paillier's Public-Key System with Applications to Electronic Voting".

Another important feature of the library is the ease of serilisation of all the structs in JSON and BSON.

Implements the paillier cryptosystem and threshold paillier crytposystem.

caveat

As any cryptographic library, if you use it, you need to trust it. Unfortunatly, this library as not been verified by a third party. There might be some bugs and vulnerabilities. If you find one, please fill a bug.

If you need to encrypt something serious, use the library provided by Go. If you want to have fun, use Paillier!

Documentation

Overview

Implementation of the paillier cryptosystem. See http://en.wikipedia.org/wiki/Paillier_cryptosystem for an introduction.

The threshold paillier cryptosystem is a translation of the java version that can be found at http://cs.utdallas.edu/dspl/cgi-bin/pailliertoolbox/ that is an implementation of the algorithm defined in Damgård's paper "A Generalization of Paillier's Public-Key System with Applications to Electronic Voting".

Another important feature of the library is the ease of serilisation of all the structs in JSON and BSON.

Implements the paillier cryptosystem and threshold paillier crytposystem.

Index

Constants

This section is empty.

Variables

View Source 
var FOUR = big.NewInt(4)
View Source 
var ONE = big.NewInt(1)
View Source 
var TWO = big.NewInt(2)
View Source 
var ZERO = big.NewInt(0)

Functions

func Factorial 

func Factorial(n int) *big.Int

returns n! = n*(n-1)*(n-2)...3*2*1

func GenerateSafePrime 

func GenerateSafePrime(
	bitLen int,
	concurrencyLevel int,
	timeout time.Duration,
	random io.Reader,
) (*big.Int, *big.Int, error)

GenerateSafePrime tries to find a safe prime concurrently. The returned result is a safe prime `p` and prime `q` such that `p=2q+1`. Concurrency level can be controlled with the `concurrencyLevel` parameter. If a safe prime could not be found in the specified `timeout`, the error is returned. Also, if at least one search process failed, error is returned as well.

How fast we generate a prime number is mostly a matter of luck and it depends on how lucky we are with drawing the first bytes. With today's multicore processors, we can execute the process on multiple cores concurrently, accept the first valid result and cancel the rest of work. This way, with the same finding algorithm, we can get the result faster.

Concurrency level should be set depending on what `bitLen` of prime is expected. For example, as of today, on a typical workstation, for 512-bit safe prime, `concurrencyLevel` should be set to `1` as generating the prime of this length is a matter of milliseconds for a single core. For 1024-bit safe prime, `concurrencyLevel` should be usually set to at least `2` and for 2048-bit safe prime, `concurrencyLevel` must be set to at least `4` to get the result in a reasonable time.

This function generates safe primes of at least 6 `bitLen`. For every generated safe prime, the two most significant bits are always set to `1` - we don't want the generated number to be too small.

func GetRandomGeneratorOfTheQuadraticResidue 

func GetRandomGeneratorOfTheQuadraticResidue(n *big.Int, rand io.Reader) (*big.Int, error)

Return a random generator of RQn with high probability. THIS METHOD ONLY WORKS IF N IS THE PRODUCT OF TWO SAFE PRIMES! This heuristic is used threshold signature paper in the Victor Shoup

func GetRandomNumberInMultiplicativeGroup 

func GetRandomNumberInMultiplicativeGroup(n *big.Int, random io.Reader) (*big.Int, error)

Generate a random element in the group of all the elements in Z/nZ that has a multiplicative inverse.

func L 

func L(u, n *big.Int) *big.Int

Types

type Cypher 

type Cypher struct {
	C *big.Int
}

func (*Cypher) String 

func (this *Cypher) String() string

type PartialDecryption 

type PartialDecryption struct {
	Id         int
	Decryption *big.Int
}

type PartialDecryptionZKP 

type PartialDecryptionZKP struct {
	PartialDecryption
	Key *ThresholdPublicKey // the public key used to encrypt
	E   *big.Int            // the challenge
	Z   *big.Int            // the value needed to check to verify the decryption
	C   *big.Int            // the input cypher text
}

A non-interactive ZKP based on the Fiat–Shamir heuristic. This algorithm proves that the decryption server indeed raised secret to his secret exponent (`ThresholdPrivateKey.Share`) by comparison with the public verification key (`ThresholdKey.Vi`). Recall that v_i = v^(delta s_i).

The Fiat-Shamir is a non-interactive proof of knowledge heuristic. The general algorithm is as follows:

  • Alice wants to prove that she knows x: the discrete logarithm of y = g^x to the base g
  • Alice picks a random r from Z_q and computes t = g^r
  • Alice computes E = H(t, g, y), where H is a cryptographic hash function
  • Alice computes Z = Ex + r. The resulting proof is the pair (t, Z).
  • Anyone can check whether t = g^Z y^E (mod q)

In our case:

Decryption server i wants to prove that he indeed raised the cyphertext to his secret exponent s_i during partial decryption. This is essentialy a protocol for the equality of discrete logs, log_{c^4}(c_i^2) = log_v(v_i).

ZKP construction

  • Pick random r mod n
  • Compute E as: E = HASH(a, b, c^4, c_i^2), where a = (c^4)^r mod n^2 b = V^r mod n^2 c is a cyphertext, V is a generator from ThresholdKey.V c_i is a partial decryption for this server
  • Compute Z as: delta * E * s_i + r, where delta is the factorial of the number of decryption servers s_i is a secret share for this server

ZKP verification

  • Compute the original a from a = a1 * a2 mod n^2 a1 = (c^4)^Z a2 = [ (c_i^2)^E ]^-1 mod n^2
  • Compute the original b from b = b1 * b2 mod n^2 b1 = V^Z b2 = [ v_i^E ] -1 mod n^2
  • Rehash H(a, b, c^4, c_i^2)
  • Compare ZKP hash with the one just computed

func (*PartialDecryptionZKP) Verify 

func (pd *PartialDecryptionZKP) Verify() bool

type PrivateKey 

type PrivateKey struct {
	PublicKey
	Lambda *big.Int
}

func CreatePrivateKey 

func CreatePrivateKey(p, q *big.Int) *PrivateKey

CreatePrivateKey generates a Paillier private key accepting two large prime numbers of equal length or other such that gcd(pq, (p-1)(q-1)) = 1.

Algorithm is based on approach described in [KL 08], construction 11.32, page 414 which is compatible with one described in [DJN 10], section 3.2 except that instead of generating Lambda private key component from LCM of p and q we use Euler's totient function as suggested in [KL 08]. 

[KL 08]:  Jonathan Katz, Yehuda Lindell, (2008)
          Introduction to Modern Cryptography: Principles and Protocols,
          Chapman & Hall/CRC

[DJN 10]: Ivan Damgard, Mads Jurik, Jesper Buus Nielsen, (2010)
          A Generalization of Paillier’s Public-Key System
          with Applications to Electronic Voting
          Aarhus University, Dept. of Computer Science, BRICS

func (*PrivateKey) Decrypt 

func (priv *PrivateKey) Decrypt(cypher *Cypher) (msg *big.Int)

Decodes ciphertext into a plaintext message.

c - cyphertext to decrypt N, lambda - key attributes

D(c) = [ ((c^lambda) mod N^2) - 1) / N ] lambda^-1 mod N

See [KL 08] construction 11.32, page 414.

type PublicKey 

type PublicKey struct {
	N *big.Int
}

func (*PublicKey) Add 

func (pk *PublicKey) Add(cypher ...*Cypher) *Cypher

Add takes an arbitrary number of cyphertexts and returns one that encodes their sum.

It's possible because Paillier is a homomorphic encryption scheme, where the product of two ciphertexts will decrypt to the sum of their corresponding plaintexts:

D( (E(m1) * E(m2) mod n^2) ) = m1 + m2 mod n

func (*PublicKey) Encrypt 

func (pk *PublicKey) Encrypt(m *big.Int, random io.Reader) (*Cypher, error)

Encrypt a plaintext into a cypher one. The plain text must be smaller that N and bigger than or equal zero. random is usually rand.Reader from the package crypto/rand.

m - plaintext to encrypt E(m, r) = [(1 + N) r^N] mod N^2

See [KL 08] construction 11.32, page 414.

Returns an error if an error has be returned by io.Reader.

func (*PublicKey) EncryptWithR 

func (pk *PublicKey) EncryptWithR(m *big.Int, r *big.Int) (*Cypher, error)

EncryptWithR encrypts a plaintext into a cypher one with random `r` specified in the argument. The plain text must be smaller that N and bigger than or equal zero. `r` is the randomness used to encrypt the plaintext. `r` must be a random element from a multiplicative group of integers modulo N.

If you don't need to use the specific `r`, you should use the `Encrypt` function instead.

m - plaintext to encrypt r - randomness used for encryption E(m, r) = [(1 + N) r^N] mod N^2

See [KL 08] construction 11.32, page 414.

func (*PublicKey) GetNSquare 

func (pk *PublicKey) GetNSquare() *big.Int

func (*PublicKey) Mul 

func (pk *PublicKey) Mul(cypher *Cypher, scalar *big.Int) *Cypher

Mul returns a product of `cypher` and `scalar` without decrypting `cypher`.

It's possible because Paillier is a homomorphic encryption scheme, where an encrypted plaintext `m` raised to an integer `k` will decrypt to the product of the plaintext `m` and `k`:

D( E(m)^k mod N^2 ) = km mod N

type ThresholdKeyGenerator 

type ThresholdKeyGenerator struct {
	PublicKeyBitLength             int
	TotalNumberOfDecryptionServers int
	Threshold                      int
	// contains filtered or unexported fields
}

Generates a threshold Paillier key with an algorithm based on [DJN 10], section 5.1, "Key generation".

Bear in mind that the algorithm assumes an existence of a trusted dealer to generate and distribute the keys. 

[DJN 10]: Ivan Damgard, Mads Jurik, Jesper Buus Nielsen, (2010)
          A Generalization of Paillier’s Public-Key System
          with Applications to Electronic Voting
          Aarhus University, Dept. of Computer Science, BRICS

func GetThresholdKeyGenerator 

func GetThresholdKeyGenerator(
	publicKeyBitLength int,
	totalNumberOfDecryptionServers int,
	threshold int,
	random io.Reader,
) (*ThresholdKeyGenerator, error)

GetThresholdKeyGenerator is a preferable way to construct the ThresholdKeyGenerator. Due to the various properties that must be met for the threshold key to be considered valid, the minimum public key `N` bit length is 18 bits and the public key bit length should be an even number. The plaintext space for the key will be `Z_N`.

func (*ThresholdKeyGenerator) Generate 

func (tkg *ThresholdKeyGenerator) Generate() ([]*ThresholdPrivateKey, error)

type ThresholdPrivateKey 

type ThresholdPrivateKey struct {
	ThresholdPublicKey
	Id    int
	Share *big.Int
}

Private key for a threshold Paillier scheme. Holds private information for the given decryption server. `Id` is the unique identifier of a decryption server and `Share` is a secret share generated from hiding polynomial and is used for a partial share decryption.

func (*ThresholdPrivateKey) Decrypt 

func (tpk *ThresholdPrivateKey) Decrypt(c *big.Int) *PartialDecryption

Decrypts the cypher text and returns the partial decryption

func (*ThresholdPrivateKey) DecryptAndProduceZNP 

func (tpk *ThresholdPrivateKey) DecryptAndProduceZNP(c *big.Int, random io.Reader) (*PartialDecryptionZKP, error)

func (*ThresholdPrivateKey) Validate 

func (tpk *ThresholdPrivateKey) Validate(random io.Reader) error

Verifies if the partial decryption key is well formed. If well formed, the method return nil else an explicative error is returned.

type ThresholdPublicKey 

type ThresholdPublicKey struct {
	PublicKey
	TotalNumberOfDecryptionServers int
	Threshold                      int
	V                              *big.Int   // needed for ZKP
	Vi                             []*big.Int // needed for ZKP
}

Public key for a threshold Paillier scheme.

`V` is a generator in the cyclic group of squares Z_n^2 and is used to execute a zero-knowledge proof of a received share decryption.

`Vi` is an array of verification keys for each decryption server `i` used to execute a zero-knowledge proof of a received share decryption.

Key generation, encryption, share decryption and combining for the threshold Paillier scheme has been described in [DJN 10], section 5.1. 

[DJN 10]: Ivan Damgard, Mads Jurik, Jesper Buus Nielsen, (2010)
          A Generalization of Paillier’s Public-Key System
          with Applications to Electronic Voting
          Aarhus University, Dept. of Computer Science, BRICS

func (*ThresholdPublicKey) CombinePartialDecryptions 

func (tk *ThresholdPublicKey) CombinePartialDecryptions(shares []*PartialDecryption) (*big.Int, error)

Combines partial decryptions provided by decryption servers and returns decrypted message. This function does not verify zero knowledge proofs. Returned message can be incorrectly decrypted if an adversary corrupted partial decryption.

func (*ThresholdPublicKey) CombinePartialDecryptionsZKP 

func (tk *ThresholdPublicKey) CombinePartialDecryptionsZKP(shares []*PartialDecryptionZKP) (*big.Int, error)

Combines partial decryptions provided by decryption servers and returns full decrypted message. Function verifies zero knowledge proofs and filters out all shares that failed verification.

func (*ThresholdPublicKey) VerifyDecryption 

func (tk *ThresholdPublicKey) VerifyDecryption(encryptedMessage, decryptedMessage *big.Int, shares []*PartialDecryptionZKP) error

Verifies if the decryption of `encryptedMessage` has been done properly. It verifies all the zero-knoledge proofs, the value of the encrypted and decrypted message. The method returns `nil` if everything is fine. Otherwise, it returns an explicative message.

Source Files

View all Source files

Directories

Path Synopsis

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.