A Deterministic Polynomial Public Key Algorithm over a Prime Galois Field GF(p)

DPPK is an Key encapsulation mechanism, a.k.a. - KEM

The ancient Vieta’s formulas reveal the relationships between the coefficients of an nth-degree polynomial and its roots. It has been surprisingly found that there exists a hidden secret for a potential public key exchange: decoupling the product of all roots (or the constant term) from the summations of root products (or coefficients) of a polynomial to establish a keypair.

1. Factorization Dependency: The DPPK algorithm is built on the fact that a polynomial cannot be factorized without its constant term.
2. Keypair Construction: The keypair generator combines a base polynomial, which can be eliminated during decryption, with two solvable polynomials to create two entangled polynomials.
   • Public Key: Formed by the coefficient vectors of the entangled polynomials.
   • Private Key: Composed of the constant terms of the entangled polynomials and the two solvable polynomials.

• By only publishing the coefficients of the polynomials without their constant terms, polynomial factoring techniques for private key extraction are greatly restricted.
• The time complexity for private key extraction from the public key is:
  • Classical Attacks: Super-exponential difficulty $O(p^2)$.
  • Quantum Attacks: Exponential difficulty $O(p)$.
• In comparison, the complexity for the Polynomial Factoring Problem (PFP) is:
  • Classical Attacks: $O(n\sqrt{p})$.
  • Quantum Attacks: $O(\sqrt{p})$, matching the complexity level of Grover’s search algorithm.

• The central idea for keypair construction arises from Vieta’s formulas by decoupling the coefficients of a polynomial into two categories:

  • Private: From its constant term.
  • Public: From the coefficients of the indeterminate $x$.

• DPPK uses two entangled generic polynomials based on a common base polynomial $B_n(x)$ with two solvable polynomials $u(x)$ and $v(x)$:

  • Public Key: All coefficients of the entangled polynomials.
  • Private Key: Their constant terms and the two solvable polynomials.

• Deterministic Time Complexity:
  • Classical Attacks: $O(\sqrt{p})$ (super-exponential difficulty).
  • Quantum Attacks: $O(p)$ (exponential difficulty).

To install DPPK, use:

go get -u github.com/xtaci/dppk

package main

import (
    "github.com/xtaci/dppk"
    "log"
)

func main() {
    // Generate key for Alice
    alice, err := dppk.GenerateKey(10)
    if err != nil {
        log.Fatal(err)
    }

    // Generate key for Bob
    bob, err := dppk.GenerateKey(10)
    if err != nil {
        log.Fatal(err)
    }

    log.Println("Alice's Public Key:", alice.PublicKey)
    log.Println("Bob's Public Key:", bob.PublicKey)
}

package main

import (
    "github.com/xtaci/dppk"
    "log"
    "math/big"
)

func main() {
    // Assume alice and bob have already generated their keys
    alice, _ := dppk.GenerateKey(10)
    bob, _ := dppk.GenerateKey(10)

    // Secret message
    secret := new(big.Int).SetBytes([]byte("hello quantum"))

    // Bob encrypts the message for Alice
    kem, err := bob.Encrypt(&alice.PublicKey, secret)
    if err != nil {
        log.Fatal(err)
    }

    log.Printf("KEM: %+v\n", kem)
}

package main

import (
    "github.com/xtaci/dppk"
    "log"
)

func main() {
    // Assume alice and bob have already generated their keys and bob has encrypted a message
    alice, _ := dppk.GenerateKey(10)
    bob, _ := dppk.GenerateKey(10)
    secret := new(big.Int).SetBytes([]byte("hello quantum"))
    kem, _ := bob.Encrypt(&alice.PublicKey, secret)

    // Alice decrypts the message
    x1, x2, err := alice.Decrypt(kem)
    if err != nil {
        log.Fatal(err)
    }

    log.Println("Decrypted message x1:", x1)
    log.Println("Decrypted message x2:", x2)
}

Contributions are welcome! Please open an issue or submit a pull request for any improvements, bug fixes, or additional features.

This project is licensed under the GPLv3 License. See the LICENSE file for details.

For more detailed information, please refer to the research paper.

Special thanks to the authors of the research paper for their groundbreaking work on DPPK.