Paillier

Additively homomorphic public-key encryption over a composite modulus, plus the PSF proof that a Paillier modulus is square-free — the check that keeps a malformed key from breaking protocols above it.

paillier implements Paillier’s 1999 cryptosystem. Its package doc cites the original paper — Public-Key Cryptosystems Based on Composite Degree Residuosity Class — and states that all routines follow the pseudocode of §2.5, Fig. 1. Unlike everything else in this section it is not built on core/curves: plaintexts, ciphertexts, and keys are all *math/big.Int values modulo a composite N = PQ.

It is here rather than under encryption because of what it is used for. Paillier’s value in this module is that a party can compute on data it cannot read, which is the multiplication primitive underpinning several MPC protocols — and the accompanying PsfProof is a zero-knowledge proof about the public key itself.

Additively homomorphic, and only additively

Two operations work on ciphertexts:

That is the whole homomorphic surface, and the boundary is hard:

Note also that both operands must be in range. Add requires c, d ∈ Z_N²; Mul requires a ∈ Z_N and c ∈ Z_N². In particular a must be non-negative and less than N — you cannot pass a negative scalar to subtract. To subtract, add the modular negation new(big.Int).Sub(pk.N, x).

Keys

PublicKey exposes N (the modulus) and N2 (N², cached to avoid recomputation). SecretKey embeds PublicKey and adds:

Both key types implement MarshalJSON/UnmarshalJSON. PublicKeyJson and SecretKeyJson are the exported-but-internal wire shapes. P and Q are not retained on the secret key and are not serialized — only the derived values are, so you cannot recover the factors from a marshalled SecretKey.

Ciphertext is a defined type over *big.Int, so it serializes as an integer with no wrapper.

Encryption

Encrypt returns three values, and the middle one is easy to discard by accident:

func (pk *PublicKey) Encrypt(msg *big.Int) (Ciphertext, *big.Int, error)

The second return is r, the randomness the ciphertext was built with. Internally c = (N+1)^msg · r^N mod N², where r is drawn uniformly from Z_N and rejected if zero.

You need to keep r whenever a later step must prove something about this ciphertext. r and msg together are the witness for essentially every zero-knowledge statement about a Paillier ciphertext (“this encrypts a value in range”, “these two ciphertexts encrypt the same value”, “this encrypts the plaintext behind that commitment”). Without r you cannot produce such a proof and cannot recompute the ciphertext deterministically. If you are only encrypting and never proving, discard it with _.

package main

import (
	"fmt"
	"math/big"

	"github.com/sonr-io/crypto/paillier"
)

func main() {
	// One-time, slow: two 1024-bit safe primes.
	pk, sk, err := paillier.NewKeys()
	if err != nil {
		panic(err)
	}

	a := big.NewInt(1234)
	b := big.NewInt(5678)

	// The second return is the encryption randomness r. Keep it if you will
	// later need to prove a statement about this ciphertext.
	ca, ra, err := pk.Encrypt(a)
	if err != nil {
		panic(err)
	}
	_ = ra

	cb, _, err := pk.Encrypt(b)
	if err != nil {
		panic(err)
	}

	// Add plaintexts by multiplying ciphertexts.
	csum, err := pk.Add(ca, cb)
	if err != nil {
		panic(err)
	}
	sum, err := sk.Decrypt(csum)
	if err != nil {
		panic(err)
	}
	fmt.Println(sum) // 6912

	// Scale a plaintext by a known constant.
	cscaled, err := pk.Mul(big.NewInt(3), ca)
	if err != nil {
		panic(err)
	}
	scaled, err := sk.Decrypt(cscaled)
	if err != nil {
		panic(err)
	}
	fmt.Println(scaled) // 3702

	// A counterparty that only received N can encrypt but not decrypt.
	remote, err := paillier.NewPubkey(pk.N)
	if err != nil {
		panic(err)
	}
	_, _, _ = remote.Encrypt(big.NewInt(1))
}

Plaintexts must satisfy msg ∈ Z_N. Arithmetic wraps modulo N, so a sum of two large plaintexts that exceeds N decrypts to the reduced value, not the integer sum. If you are encoding signed or fixed-point quantities, choose a representation with headroom and check it yourself — the package does not.

The PSF proof: proving a modulus is square-free

A protocol that accepts a Paillier public key from an untrusted party accepts an arbitrary integer N. If N is malformed — not square-free, or sharing a factor with the ambient group order — the homomorphic structure the protocol relies on breaks down, and a malicious key holder can extract information or force a decryption to a value of its choosing. The PSF (Paillier square-free) proof forces N to be well-formed before anything is encrypted under it.

The implementation cites its spec as [spec] §10.2 and fig. 15 (ProvePSF, VerifyPSF), and the source carries explicit notes where it deviates from that pseudocode to fix errors in it — the modulus for the exponentiation in step 5, and the inclusion of N in the challenge commitment.

What it actually asserts

The prover, who knows the factorization, computes M = N⁻¹ mod φ(N) and returns y_i = x_i^M mod N for 13 deterministically derived challenges x_i. The verifier checks y_i^N ≡ x_i mod N for every i.

That check passes for all i only if raising to the N-th power is a bijection on Z_N, which holds exactly when gcd(N, φ(N)) = 1 — that is, when N is square-free. The verifier additionally rejects N if the curve subgroup order q divides N.

Be precise about the limits of this:

• It proves N is square-free.
• It does not prove N is a product of exactly two primes.
• It does not prove the factors are safe primes, or of equal size, or large.
• It does not prove the prover knows the factorization beyond what square-freeness needs.

If your protocol needs a biprime or safe-prime guarantee, PSF alone is insufficient.

PsfProof is []*big.Int, so encoding/json round-trips it directly with no custom codec — psf_test.go marshals and unmarshals it that way.

Parameters

The prover’s and verifier’s parameter structs are deliberately near-identical: the only difference is that the prover holds the *SecretKey while the verifier holds only the *PublicKey. Every other field is a public value both sides must agree on, because all three are hashed into the challenge derivation.

Prove and verify

Grounded in paillier/psf_test.go (TestPsfProofWorks).

package main

import (
	"crypto/elliptic"
	"fmt"
	"math/big"

	"github.com/sonr-io/crypto/core/curves"
	"github.com/sonr-io/crypto/paillier"
)

// Y is an ordinary EC point. In psf_test.go it is built with
// curves.NewScalarBaseMult over the same crypto/elliptic curve.
func bindingPoint(k *big.Int) (*curves.EcPoint, error) {
	return curves.NewScalarBaseMult(elliptic.P256(), k)
}

func provePSF(sk *paillier.SecretKey, pi uint32, y *curves.EcPoint) (paillier.PsfProof, error) {
	return (&paillier.PsfProofParams{
		Curve:     elliptic.P256(),
		SecretKey: sk,
		Pi:        pi, // must be non-zero
		Y:         y,
	}).Prove()
}

func verifyPSF(
	proof paillier.PsfProof,
	pk *paillier.PublicKey,
	pi uint32,
	y *curves.EcPoint,
) error {
	// Do this length check yourself: Verify does not, and indexes 13 elements.
	if len(proof) != paillier.PsfProofLength {
		return fmt.Errorf(
			"malformed psf proof: want %d elements, got %d",
			paillier.PsfProofLength, len(proof),
		)
	}
	return proof.Verify(&paillier.PsfVerifyParams{
		Curve:     elliptic.P256(),
		PublicKey: pk,
		Pi:        pi,
		Y:         y,
	})
}

Wiring it into a key exchange:

Caveats

Related