A like‑ElGamal public‑key cryptosystem based on the Modulo‑1 Factoring
Problem (M1FP) with exact additive homomorphism, written in Go.

The implementation is designed to be used on e-voting systems, so the API contains explicit e-voting references. However it can be used for any other purpose.

The code under this repository is not audited and must not be used for other than research purposes.

Note that the code is licensed under AGPLv3, so any work derived from it must also be published under a GPL compatible license

This implementation follows and extends the scheme from:

Ahmed El‑Yahyaoui, Fouzia Omary,
"A Like ELGAMAL Cryptosystem But Resistant To Post‑Quantum Attacks",
International Journal of Communication Networks and Information Security (IJCNIS), Vol x, No x, April 2022.

Please cite the paper if you use this code in academic work.

This proof-of-concept implementation has been done for the Vocdoni project (for post-quantum encryption research).
So please, cite the project also if you use this work.

• Post‑quantum hope – Traditional ElGamal relies on the Discrete Log problem, broken in polynomial time by Shor's quantum algorithm.
  The M1FP problem is currently outside the reach of every known quantum algorithm, so the scheme is a candidate for quantum‑resistant public‑key encryption.

• Exact additive homomorphism – You can add ciphertexts and, after one decryption, obtain the sum of the underlying plaintexts.
  This is invaluable for e‑voting, private surveys, and any "tally without opening individual ballots" workflow.

• Perfect precision – This implementation uses a novel common domain approach that eliminates precision errors completely, achieving exact arithmetic even for millions of homomorphic additions.

Given an irrational real number x ∈ (0,1)
and another real c = (a·x mod 1) with unknown integer a,
find a.

• "mod 1" keeps only the fractional part, e.g. 0.75 mod 1 = 0.75,
  3.1415 mod 1 = 0.1415.
• Eric Jarpe (2021) proved M1FP is NP‑hard.
• Because x is irrational, the fractional sequence (a·x mod 1) is equidistributed; no efficient lattice attack is known.

P = 256 bits precision, n = 9 decimal digits for voting. The common domain D = 2^P · 5^n eliminates precision loss.

Previous implementations suffered from precision drift when converting between binary (mod 2^P) and decimal (mod 10^n) domains. Floor operations like ⌊R × 10^n / 2^P⌋ introduced tiny errors that accumulated over thousands of homomorphic additions, causing vote counting errors of 5-10 votes in 100k tallies.

We implement all encryption arithmetic in a single high-precision domain D = 2^P · 5^n:

1. Mathematical Foundation
   Since 10^n = 2^n · 5^n, we have:

   D = 2^P · 5^n = 2^P · (10^n / 2^n) = (2^(P-n)) · 10^n
   

   This makes D divisible by both 2^P and 10^n, allowing exact conversions.

2. Message Encoding
   Messages are lifted to the common domain:

   M_encoded = message × (D / 10^n) = message × 2^(P-n)
   

3. Encryption in Common Domain

   C₁ = (r · X) mod D
   C₂ = (M_encoded + r · H) mod D
   

   Where X and H are also lifted to domain D.

4. Exact Decryption

   M' = (C₂ - a·C₁) mod D
   message = M' / 2^(P-n)  [with proper rounding]
   

• Zero precision loss – No floor operations during encryption/addition
• Exact arithmetic – All operations are integer arithmetic mod D
• Perfect scaling – Handles millions of additions without drift
• Simpler code – No complex carry bit logic needed

The homomorphic property works because addition in the common domain preserves the linear structure:

Enc(m₁) + Enc(m₂) = Enc(m₁ + m₂)

Given two ciphertexts E(M₁) = (C₁, C₂) and E(M₂) = (C₁′, C₂′):

1. Simple Addition in Common Domain

   C₁_sum = (C₁ + C₁′) mod D
   C₂_sum = (C₂ + C₂′) mod D
   

2. Why This Works

   C₂_sum = (M₁·2^(P-n) + r₁·H + M₂·2^(P-n) + r₂·H) mod D
          = ((M₁ + M₂)·2^(P-n) + (r₁ + r₂)·H) mod D
   

   This is exactly the encryption of (M₁ + M₂) with randomness (r₁ + r₂).

3. Decryption of Sum

   M'_sum = (C₂_sum - a·C₁_sum) mod D
          = (M₁ + M₂)·2^(P-n) mod D
   
   sum = M'_sum / 2^(P-n)  [exact division with rounding]
   

Vote 1: 42    →  M₁ = 42 × 2^(256-9) = 42 × 2^247
Vote 2: 17    →  M₂ = 17 × 2^247

After encryption:
C₁₁ = (r₁ × X) mod D,  C₂₁ = (M₁ + r₁ × H) mod D
C₁₂ = (r₂ × X) mod D,  C₂₂ = (M₂ + r₂ × H) mod D

Homomorphic addition:
C₁_sum = (C₁₁ + C₁₂) mod D
C₂_sum = (C₂₁ + C₂₂) mod D

Decryption:
M'_sum = (C₂_sum - a × C₁_sum) mod D
       = (42 + 17) × 2^247 mod D
       = 59 × 2^247 mod D

Final result: 59 × 2^247 / 2^247 = 59  ✓

• Semantic security – Each ciphertext component looks uniformly random
• Homomorphic privacy – Individual votes remain hidden, only the sum is revealed
• Perfect correctness – Zero precision errors even with millions of additions
• Efficient verification – Results can be independently verified

• Novel assumption – M1FP is much less studied than lattices or codes.
  Treat this as experimental until peer‑review hardens the security.
• Chosen‑ciphertext security – base scheme is IND‑CPA.
  Use a KEM+AEAD wrapper or apply Cramer–Shoup style techniques for IND‑CCA2.
• Decimal encoding overhead – 3× blow‑up. A custom base‑2¹⁶ packing would be denser.
• No signature / key‑exchange yet – only encryption; signatures could reuse the same trapdoor but are future work.

• Each ciphertext reveals only (C₁, C₂) which look uniformly random because r is fresh and the M1FP assumption makes r·H unpredictable.
• Adding ciphertexts preserves the distribution: the sum has the same statistical properties as an honest encryption of the numeric sum.
• Perfect linearity – The common domain approach ensures that Enc(m₁) + Enc(m₂) = Enc(m₁ + m₂) holds exactly, with no approximation errors.
• No extra information is leaked; adversaries cannot learn individual ballots, only the final tally once the holder of a decrypts.

go get github.com/p4u/m1fp-go/m1fp

package main

import (
	"fmt"
	"github.com/p4u/m1fp-go/m1fp"
	"math/big"
)

func main() {
	// --- Key generation ---------------------------------------------------
	pkX := "0.60943791243410037460075933322619" // ln(5) mod 1
	sk, pk, _ := m1fp.KeyGen(256, pkX)

	// --- Encrypt two ballots ---------------------------------------------
	ct1, _ := m1fp.Encrypt(pk, "\x01") // vote = 1
	ct2, _ := m1fp.Encrypt(pk, "\x3F") // vote = 63

	// --- Homomorphic tally -----------------------------------------------
	sum, _ := ct1.Add(ct2, pk.Prec)

	// --- Decrypt final tally ---------------------------------------------
	tally, _ := m1fp.Decrypt(sk, sum)
	fmt.Println("Tally:", tally[0]) // 64 (perfect precision!)
}

// Encrypt a numeric vote (0-64)
ct, _, _ := m1fp.EncryptVote(pk, 42, nil)

// Add votes homomorphically  
tally, _ := ct1.Add(ct2, pk.Prec)

// Decrypt final count
result, _ := m1fp.DecryptVote(sk, tally)
fmt.Println("Total votes:", result) // Exact count

blob, _ := pk.MarshalBinary()
var pk2 m1fp.PublicKey
pk2.UnmarshalBinary(blob)
// pk2 is now identical to pk

r := big.NewInt(1234567)
ct, _ := m1fp.EncryptDeterministic(pk, "Hello", r)