dpaillier

README

TNO MPC Lab - Distributed Paillier

The TNO MPC lab consists of generic software components, procedures, and functionalities developed and maintained on a regular basis to facilitate and aid in the development of MPC solutions. The lab is a cross-project initiative allowing us to integrate and reuse previously developed MPC functionalities to boost the development of new protocols and solutions.

The package dpaillier is part of the TNO Go Toolbox.

Limitations in (end-)use: the content of this repository may solely be used for applications that comply with international export control laws.

Distributed key generation and decryption for the Paillier cryptosystem

This package provides an implementation of a distributed key generation algorithm for the Paillier cryptosystem. It can be used to share a private key among multiple parties, so that a ciphertext can only be decrypted if they work together.

Usage

This key generation algorithm is meant to be used by a set of parties communicating over a network. Therefore, it is expressed as a number of stages, and to get from one stage to the next, the parties have to exchange a message with one another.

To start, agree externally on values for the parameters in KeyGenerationParameters. These can be validated using their Validate method to make sure they are suitable. Note that each participant should be assigned a distinct ParticipantIndex.

The parties can use a validated instance of the key generation parameters to start their protocol using NewKeyGenerationProtocol. This results in a state struct and a set of messages to send to the other parties, or a possible error. The state struct should be saved until all messages have been exchanged, after which each party calls the Advance method on the struct, supplying it with the messages received from the other parties. This results in a new state struct and new outgoing messages.

The distributed Paillier key generation protocol is probabilistic, and has a high chance of failure. Implementations should check for errors and restart the protcol if they occur.

The Advance method on KeyGenerationStage6 results in a PrivateKeyShare if successful. The private key share contains a regular paillier.PublicKey, for which we refer to that package's documentation. To decrypt a ciphertext, owners of the private key shares should call their PartiallyDecrypt method on the ciphertext. This results in a set of partial decryptions. Anyone with a private key share can call its Decrypt method on this set to recover the plaintext.

We refer to Godoc (or the code comments) for detailed documentation.

Documentation

Index

• Variables
• func NewKeyGenerationProtocol(params KeyGenerationParameters) (*KeyGenerationStage1, []*KeyGenerationMessage1, error)
• type KeyGenerationMessage1
• type KeyGenerationMessage2
• type KeyGenerationMessage3
• type KeyGenerationMessage4
• type KeyGenerationMessage5
• type KeyGenerationMessage6
• type KeyGenerationParameters
  • func (params *KeyGenerationParameters) MarshalJSON() ([]byte, error)
  • func (p *KeyGenerationParameters) Validate() error
• type KeyGenerationStage1
  • func (kgs *KeyGenerationStage1) Advance(messages []*KeyGenerationMessage1) (*KeyGenerationStage2, []*KeyGenerationMessage2, error)
• type KeyGenerationStage2
  • func (kgs *KeyGenerationStage2) Advance(messages []*KeyGenerationMessage2) (*KeyGenerationStage3, []*KeyGenerationMessage3, error)
• type KeyGenerationStage3
  • func (kgs *KeyGenerationStage3) Advance(messages []*KeyGenerationMessage3) (*KeyGenerationStage4, []*KeyGenerationMessage4, error)
• type KeyGenerationStage4
  • func (kgs *KeyGenerationStage4) Advance(messages []*KeyGenerationMessage4) (*KeyGenerationStage5, []*KeyGenerationMessage5, error)
• type KeyGenerationStage5
  • func (kgs *KeyGenerationStage5) Advance(messages []*KeyGenerationMessage5) (*KeyGenerationStage6, []*KeyGenerationMessage6, error)
• type KeyGenerationStage6
  • func (kgs *KeyGenerationStage6) Advance(messages []*KeyGenerationMessage6) (*PrivateKeyShare, error)
• type PartialDecryption
• type PrivateKeyShare
  • func (sk *PrivateKeyShare) Decrypt(partials []*PartialDecryption) *big.Int
  • func (sk *PrivateKeyShare) PartiallyDecrypt(ct *big.Int) *PartialDecryption

Variables

var ErrorBiprimalityTestFailed = errors.New("Probabilistic generation of bi-prime N failed. Restart the key generation protocol.")

var SMALL_PRIMES = [...]int64{}/* 10000 elements not displayed */

Functions

func NewKeyGenerationProtocol

func NewKeyGenerationProtocol(params KeyGenerationParameters) (*KeyGenerationStage1, []*KeyGenerationMessage1, error)

Starts a new key generation protocol. This step generates random numbers pi and qi and secret shares these among the participants.

Types

type KeyGenerationMessage1

type KeyGenerationMessage1 struct {
	From, To       int
	ShareOfTermOfP secret.Share
	ShareOfTermOfQ secret.Share
	ShareOfZero    secret.Share
}

type KeyGenerationMessage2

type KeyGenerationMessage2 struct {
	From, To int
	ShareOfN secret.Share
}

type KeyGenerationMessage3

type KeyGenerationMessage3 struct {
	From, To     int
	N            *big.Int
	TestElements []*big.Int
}

type KeyGenerationMessage4

type KeyGenerationMessage4 struct {
	From, To      int
	TestResponses []*big.Int
}

type KeyGenerationMessage5

type KeyGenerationMessage5 struct {
	From, To                       int
	ShareOfTermOfL, ShareOfTermOfB secret.Share
}

type KeyGenerationMessage6

type KeyGenerationMessage6 struct {
	From, To     int
	ShareOfTheta secret.Share
}

type KeyGenerationParameters

type KeyGenerationParameters struct {
	// The number of total participants n in the protocol
	NumberOfParticipants int
	// The index of this participant (0 <= ParticipantIndex < NumberOfParticipants)
	ParticipantIndex int

	// The bit size kappa of the Paillier modulus N
	PaillierBitSize int

	// The degree t of the secret sharing polynomial
	// 2t + 1 participants are necessary
	SecretSharingDegree int
	// The statistical security parameter sigma of secret sharing over the integers
	SecretSharingStatisticalSecurity int
	// The secret sharing modulus prime P of bit size at least 2(kappa + log_2 n)
	SecretSharingModulus *big.Int

	// Number of times b to perform the biprimality check of N
	BiprimalityCheckTimes int
	// Number of parallel goroutines to use during the biprimality test
	NumProcessors int
}

func (*KeyGenerationParameters) MarshalJSON

func (params *KeyGenerationParameters) MarshalJSON() ([]byte, error)

MarshalJSON returns a json representation of the key generation parameters. This is needed because otherwise the contained big.Int marshals as a float64, which loses precision.

func (*KeyGenerationParameters) Validate

func (p *KeyGenerationParameters) Validate() error

Validate validates the given parameters. If an impossible situation is specified, an error is returned. Otherwise, any missing optional parameters are automatically added. The following parameters are optional:

If SecretSharingDegree is omitted, the highest possible value for the given NumberOfParticipants is used.

If SecretSharingStatisticalSecurity is omitted, it is set to 20.

If SecretSharingModulus is omitted, a suitable one is randomly chosen.

If BiprimalityCheckTimes is omitted, it is set to 100.

type KeyGenerationStage1

type KeyGenerationStage1 struct {
	Parameters       *KeyGenerationParameters
	TermOfP, TermOfQ *big.Int
	MessageToSelf    *KeyGenerationMessage1
}

func (*KeyGenerationStage1) Advance

func (kgs *KeyGenerationStage1) Advance(messages []*KeyGenerationMessage1) (*KeyGenerationStage2, []*KeyGenerationMessage2, error)

type KeyGenerationStage2

type KeyGenerationStage2 struct {
	Parameters       *KeyGenerationParameters
	TermOfP, TermOfQ *big.Int
	ShareOfN         secret.Share
}

func (*KeyGenerationStage2) Advance

func (kgs *KeyGenerationStage2) Advance(messages []*KeyGenerationMessage2) (*KeyGenerationStage3, []*KeyGenerationMessage3, error)

type KeyGenerationStage3

type KeyGenerationStage3 struct {
	Parameters       *KeyGenerationParameters
	TermOfP, TermOfQ *big.Int
	N                *big.Int
	TestElements     []*big.Int
}

func (*KeyGenerationStage3) Advance

func (kgs *KeyGenerationStage3) Advance(messages []*KeyGenerationMessage3) (*KeyGenerationStage4, []*KeyGenerationMessage4, error)

type KeyGenerationStage4

type KeyGenerationStage4 struct {
	Parameters    *KeyGenerationParameters
	N             *big.Int
	TermOfLambda  *big.Int
	TestResponses []*big.Int
}

func (*KeyGenerationStage4) Advance

func (kgs *KeyGenerationStage4) Advance(messages []*KeyGenerationMessage4) (*KeyGenerationStage5, []*KeyGenerationMessage5, error)

type KeyGenerationStage5

type KeyGenerationStage5 struct {
	Parameters       *KeyGenerationParameters
	N                *big.Int
	TermOfL, TermOfB *big.Int
	MessageToSelf    *KeyGenerationMessage5
}

func (*KeyGenerationStage5) Advance

func (kgs *KeyGenerationStage5) Advance(messages []*KeyGenerationMessage5) (*KeyGenerationStage6, []*KeyGenerationMessage6, error)

type KeyGenerationStage6

type KeyGenerationStage6 struct {
	Parameters    *KeyGenerationParameters
	N             *big.Int
	I             int
	Hi            *big.Int
	MessageToSelf *KeyGenerationMessage6
}

func (*KeyGenerationStage6) Advance

func (kgs *KeyGenerationStage6) Advance(messages []*KeyGenerationMessage6) (*PrivateKeyShare, error)

type PartialDecryption

type PartialDecryption struct {
	I  int
	Ci *big.Int
}

PartialDecryption is a partial decryption of a ciphertext generated by one share of a Paillier private key.

type PrivateKeyShare

type PrivateKeyShare struct {
	paillier.PublicKey

	ParticipantIndex int
	Hi               *big.Int // h(i)
	FactorialOfNPart *big.Int // \nu = n!
	ThetaInv         *big.Int // Cached value for faster decryption
}

PrivateKeyShare is a share of a Paillier private key. It can be used in cooperation with owners of the other private key shares to decrypt messages encrypted with the enclosed public key.

func (*PrivateKeyShare) Decrypt

func (sk *PrivateKeyShare) Decrypt(partials []*PartialDecryption) *big.Int

Decrypt combines a full set of partial decryptions of a ciphertext and recovers the corresponding plaintext. Any of the private key shares can be used to combine the set of partial decryptions. The result is unspecified if an incomplete set of partial decryptions is supplied, but the set need not be ordered.

func (*PrivateKeyShare) PartiallyDecrypt

func (sk *PrivateKeyShare) PartiallyDecrypt(ct *big.Int) *PartialDecryption

PartiallyDecrypt generates a partial decryption of the ciphertext ct. By using this method for all shares of the private key on a given ciphertext and using Decrypt on the set of partial decryptions, the plaintext can be recovered.