ACE Working Group                                      P.J. Nsiangani Ed.
Internet-Draft                                 draft-nsiangani-phi-ns-00
Intended status: Proposed Standard                       
Expires: June 2026                                      01 December 2025
                                                          
                        Phi-Ns Cryptosystem
                       


Status of this Memo

   This Internet-Draft is submitted in full conformance with the
   provisions of BCP 78 and BCP 79.

   This document is subject to the rights, licenses and restrictions
   contained in BCP 78 and BCP 79, and except as set forth therein,
   the authors retain all their rights.

   This document is provided under the terms of the IETF Trust's Legal
   Provisions Relating to IETF Documents (https://trustee.ietf.org/
   license-info) in effect on the date of publication of this document.
   Please review these documents carefully.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF).  Note that other groups may also distribute
   working documents as Internet-Drafts.  The list of current
   Internet-Drafts is at https://datatracker.ietf.org/drafts/current/.

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time.  It is inappropriate to use Internet-Drafts as reference
   material or to cite them other than as "work in progress".

Copyright Notice

   Copyright (c) 2025 IETF Trust and the persons identified as the
   document authors.  All rights reserved.

   This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF  Documents (https://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License.

Abstract

This document describes Phi-Ns, a new asymmetric cryptographic
primitive based on the structured decomposition of the quadratic gap
between two primes. Phi-Ns defines a public key q and a private key p
such that the difference q^2 - p^2 is expressed as a composite value T.
The value T is then factored into small controlled components noted a,
b, and R, and the final secret structure abR is encoded through a
randomized serialization process.

The security of Phi-Ns does not rely on integer factorization, the
discrete logarithm problem, or elliptic curves. Instead, it depends on
the difficulty of recovering p from q when the attacker has no oracle,
no structural anchor, and no method to determine whether a candidate p
is correct. Because T can be recursively decomposed and reassembled into
multiple unpredictable forms, the resulting search space grows
combinatorially.

Phi-Ns further supports recursive expansion of the internal abR
structure, allowing the construction of high-entropy secret states even
when p and q have relatively small bit lengths. This enables compact



public keys, efficient computation, and strong post-quantum resistance
based on a non-factorization hardness assumption.

This document specifies the algorithmic model of Phi-Ns, its parameter
choices, and the serialization rules used to encode the abR structure.
It also outlines two public-key variants, PK-p and PK-q, which expose
either p or q as the public value depending on deployment constraints.


Status of This Memo

This document is an Internet-Draft and is submitted in full
conformance with the provisions of BCP 78 and BCP 79. Internet-Drafts
are working documents of the Internet Engineering Task Force (IETF).
They represent ongoing work and are not standards. This document is
intended for publication on the Standards Track.

Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or made obsolete by other documents at
any time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as work in progress.

This Internet-Draft will expire six months from the date of
publication unless replaced by a more recent version.

The IETF invites comments and discussion about this document. Please
review the rights, licenses, and restrictions relating to this
document as described in the IETF Trust Legal Provisions:
https://trustee.ietf.org/license-info


Copyright Notice

Copyright (c) 2025 IETF Trust and the persons identified as the
document authors. All rights reserved.

This document is subject to the provisions of BCP 78 and BCP 79.
Please review the information at https://trustee.ietf.org/license-info
to understand your rights and responsibilities.

This document may contain material that is subject to intellectual
property rights, including patent applications or granted patents.
The contributor of this material represents that any such rights
have been disclosed in accordance with Section 6 of BCP 79.

1. Introduction


The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY",
and "OPTIONAL" in this document are to be interpreted as described in
RFC 2119 [RFC2119] and RFC 8174 [RFC8174] when, and only when, they
appear in all capitals, as shown here.

Phi-Ns is an asymmetric cryptographic primitive based on the structured
decomposition of the quadratic gap between two prime numbers. Instead of

deriving its security from integer factorization, discrete logarithms,
or


elliptic curves, Phi-Ns defines a new hardness assumption: recovering
the
secret prime p, or the internal structure abR, from limited public
information when no oracle exists and no method can confirm whether a
candidate p is correct.

Given two primes p and q, Phi-Ns defines the fundamental relation:

    q^2 - p^2 = T

where T is a composite value. The value T is then decomposed into the
structured form abR, where a and b correspond to controlled exponents of
2 and 3 extracted from T, and R is the remaining composite factor. After
this extraction step, the tuple (a, b, R) is serialized through a
randomized encoding process that removes any predictable structure and
achieves a high degree of entropy. Because R can contain multiple
independent factors and the serialization order is randomized, the
number of possible equivalent representations is extremely large.

A critical security property of Phi-Ns is that an attacker cannot
confirm
whether a guessed value p is correct or not. No oracle exists, and no
structural anchor is leaked. A failure or a success is indistinguishable
for all incorrect values. As a result, recovering the correct p requires
exploring a search space with no direction, no gradient, and no method
to
prune incorrect candidates. The attacker must guess p, then guess the
full abR structure, and finally reconstruct the exact serialized form
expected by the system. This produces a combinatorial explosion of
possible candidates, even when p and q have small bit sizes.

Phi-Ns supports two deployment modes:

    * PK-q: the public key is q and the private key contains p and abR.
      In this mode the attacker must recover p from q without knowing
the
      scale of the gap q^2 - p^2, and without knowing whether p lies
near
      or far from q. Because the distribution of prime gaps is irregular
      and unbounded, no attacker can determine the size of the interval
      in which p may reside.

    * PK-p: the public key is p and the private key contains q and abR.
      This mode hides q completely. Since the attacker cannot determine
      the size or direction of the quadratic difference q^2 - p^2, the
      search becomes harder because the attacker does not even know
      whether q is slightly larger than p or extremely distant from p.
      The entropy of the problem grows rapidly when q is chosen far from
      p, and no leakage occurs because the attacker does not know the
      magnitude of T.

The structure of T is not fixed. Phi-Ns allows recursive expansion:
the secret prime p itself may be expressed as:


    p^2 = p2^2 + a2 b2 R2

and this process may be repeated multiple times. Each recursion creates
a


new decomposition, which is also serialized in a randomized way. This
creates a layered secret state with exponentially increasing entropy. In
practice this means that even a 32-bit public parameter can lead to a
secure system if the recursion depth is sufficient. Each decomposition
generates new abR structures, each with its own randomized ordering, and
each requiring full reconstruction by an attacker.

Because no element of abR, and no ordering of abR, is ever exposed, and
because the attacker cannot distinguish invalid candidates from the
correct one, the Phi-Ns search problem has no known reduction to RSA,
DLP, ECC, multivariate systems, or lattice-based constructions. The
security is derived from the impossibility of validating partial guesses
and from the combinatorial explosion of decomposed structures.

This document defines the Phi-Ns primitive, the public key modes PK-p
and
PK-q, the conditions for decomposition of T into abR, the requirements
for randomized serialization, and the general architecture needed for
interoperable implementations. The goal of this specification is to
provide the necessary foundation to support future PKI frameworks,
session protocols, and perpetual key systems that rely on the unique
properties of Phi-Ns.


2. Terminology

This section defines terminology used throughout this document.
All terms are normative for the Phi-Ns cryptographic primitive.

Prime:
    A positive integer greater than 1 whose only divisors are 1 and
itself.

p:
    The private prime in the PK-q mode. In the PK-p mode p is the public
    value. The value p participates in the equation q^2 - p^2 = T.

q:
    The public prime in the PK-q mode. In the PK-p mode q is private.
    The value q participates in the equation q^2 - p^2 = T.

T:
    The quadratic gap defined by T = q^2 - p^2. The value T must be
    strictly positive and composite.

a:
    The maximal exponent of 2 extracted from T. This value is private.

b:
    The maximal exponent of 3 extracted from T. This value is private.

R:

    The remaining composite cofactor of T after removing 2^a and 3^b.
    The value R is private and may contain one or several distinct
    composite or prime factors.

abR:
    The structured decomposition of T into the tuple (a, b, R). This


    tuple represents the complete internal secret state derived from T.

Serialized abR:
    A randomized encoding of the tuple (a, b, R) obtained through a
    permutation and ordered concatenation process. The serialization is
    private and must be reproduced exactly during verification.

Recursive decomposition:
    A process where p itself is replaced by a new p2 such that
    p^2 = p2^2 + a2 b2 R2. The structure abR may therefore contain
    nested decompositions.

PK-q:
    A Phi-Ns mode where q is the public key and p, a, b, R are private.
    The attacker must recover p from q without knowing the magnitude of
    T or the internal decomposition.

PK-p:
    A Phi-Ns mode where p is the public key and q, a, b, R are private.
    The attacker must recover q without knowing the magnitude or even
    the direction of the quadratic gap.

No-oracle condition:
    The attacker receives no feedback when testing a candidate p or q.
    No test can confirm whether a guessed value is correct. All invalid
    candidates appear identical to the correct one.

Serialization space:
    The total number of distinct encodings of the internal structure.
    It includes all permutations of factors inside R, all permutations
    of abR, and all choices of recursive decomposition when enabled.

Entropy amplification:
    The increase in difficulty obtained by applying recursive
    decomposition or by enlarging the number of permutations possible
    during serialization.

Phi-Ns hardness assumption:
    The assumption that recovering p or q from a public parameter,
    together with reconstructing the exact serialized internal structure
    abR, is computationally infeasible both classically and quantumly.

Implementer:
    Any party building, integrating, or deploying Phi-Ns in software,
    hardware, or protocol environments.

Verifier:
    Any party that validates information derived from a Phi-Ns key,
    including correctness of signatures or encrypted structures.



3. Algorithm Overview

Phi-Ns is an asymmetric cryptographic construction based on the
structured decomposition of the quadratic gap between two primes.
Given two primes p and q with q > p, the core identity is:

    q^2 - p^2 = T



The value T is strictly positive and composite. Phi-Ns expands T into
a structured internal secret called abR, defined as:

    T = 2^a * 3^b * R

where:
- a is the maximal power of 2 dividing T.
- b is the maximal power of 3 dividing T.
- R is the remaining composite cofactor, which may include any number
  of prime or composite factors.

None of the values a, b, or R are public. Only one of the two primes
(p or q) is exposed depending on the selected variant. The internal
structure abR is then transformed through a randomized serialization
process that produces a high-entropy private state.

Phi-Ns defines two public-key variants:

PK-q Mode:
    The public key is q. The private key contains p and the serialized
    form of abR. The attacker must recover p from q without oracle
    feedback and without knowing the size or factorization of T.
    Because every incorrect p yields a valid-looking T, there is no
    way for the attacker to detect success.

PK-p Mode:
    The public key is p. The private key contains q and the serialized
    form of abR. The attacker must recover q from p without knowing the
    direction or the magnitude of the gap q^2 - p^2. This removes the
    anchoring property associated with PK-q and increases search
    ambiguity.

In both modes the attacker must also reconstruct the correct abR
decomposition. Even if p were guessed, reconstruction of T would
require:
- determining the correct a and b,
- factoring the remaining R (fully or partially),
- reproducing the exact randomized serialization order applied during
  key generation.

Phi-Ns supports an optional recursive mechanism. A private key holder
may decompose p itself into:

    p^2 = p2^2 + 2^(a2) * 3^(b2) * R2

and repeat the process to obtain arbitrarily deep nested structures.
Each recursion multiplies the number of possible secret states,

producing exponential entropy amplification even when p and q have
modest bit lengths.

Serialization of abR incorporates random permutation of factors,
random placement of a and b, and randomized block grouping. This yields
a very large space of encodings. The verifier cannot derive this
encoding from public data and must rely on the private key.

In all cases Phi-Ns assumes a no-oracle environment: the attacker
obtains no indication whether a candidate p or q is correct, and no


test exists to validate a reconstruction. As a result the search space
contains no gradients, no distinguishing features, and no structural
anchors.

Phi-Ns is not based on integer factorization, discrete logarithms,
elliptic curves, lattices, or multivariate equations. The approach
introduces a new hardness class based on ambiguity of quadratic
inversion combined with non-unique structured decomposition.


4. Detailed Specification

This section defines the Phi-Ns asymmetric primitive using only the
mathematical elements that belong to the specification. No additional
profiles or assumptions are introduced. All size choices for p, q, and
R are controlled by the implementer.

4.1. Core Equation

Phi-Ns is defined by two primes p and q such that:

    T = q^2 - p^2

T MUST be strictly positive and MUST be composite. The implementer
selects the bit lengths of p and q based on the security target.

4.2. Extraction of the abR Structure

The quadratic gap T is decomposed into the triple (a, b, R) through the
following deterministic steps:

    Step 1: Compute T = q^2 - p^2
    Step 2: Extract a such that 2^a divides T but 2^(a+1) does not
    Step 3: Extract b such that 3^b divides (T / 2^a) but 3^(b+1) does
not
    Step 4: Set R = T / (2^a * 3^b)

R MUST NOT be divisible by 2 or 3. R SHOULD be large enough to preserve
entropy but the exact size is left to the implementer.

4.3. Randomized Serialization of abR

To conceal structure, the triple (a, b, R) is transformed into a
serialized encoding called the abR-encoding. The process is:

    - Perform partial factorization of R using small trial division.

    - The resulting values are called atoms. The remaining cofactor,
      if any, is also considered an atom.
    - A seed and a salt are created for this key generation instance.
    - A pseudorandom permutation derived from the seed and the salt
      permutes all atoms.
    - Atoms are grouped into blocks. The number of blocks is derived
      from a pseudorandom function.
    - The final abR-encoding consists of:
         a, b, salt, number_of_blocks, and the permuted list of blocks.

For a given seed the encoding MUST be deterministic. The encoding MUST
hide the internal order and structure of the factors of R.



4.4. Optional Recursive Decomposition

Phi-Ns MAY decompose p itself using the same relation. The recursion is:

    p^2 = p_prime^2 + T_prime

where T_prime is decomposed into a_prime, b_prime, and R_prime. The
process MAY repeat any number of times.

Recursive decomposition increases entropy because each abR triple in the
chain adds uncertainty. The public key does not reveal whether
recursion was used.

4.5. Public Key Exposure Modes (PK-p and PK-q)

Phi-Ns defines two exposure modes:

PK-p mode:
    Public key: p
    Private components: q and the abR-encoding
    The attacker sees p but has no anchor toward q. Since no oracle is
    available, the attacker cannot know whether a guessed p,q pair is
    correct. The search space has no stopping rule.

PK-q mode:
    Public key: q
    Private components: p and the abR-encoding
    The attacker sees q and must guess p. For each candidate p, the
    attacker must test whether q^2 - p^2 yields a T that could match an
    abR encoding. Because the abR structure is randomized and because
    no oracle confirms correctness, there is no way to know when the
    correct p has been found.

4.6. Perpetual PKI Property

Phi-Ns supports perpetual key continuity. The public key (either p or q)
MAY remain constant while the private key is refreshed by re-randomizing
the abR decomposition using new seed and salt values. No reissuance of
certificates is required unless local policy demands it. This property
is derived directly from the fact that the abR encoding carries the
entropy of the secret state, not the size of p or q.

4.7. Minimum and Maximum Sizes


This specification does not enforce a minimum size for p, q, or R.
Implementers are expected to select sizes in accordance with the target
security level. Because entropy is carried primarily by the abR
encoding, even small p and q can be made secure through recursion and
through expansion of the abR structure.

The specification does not restrict the maximum size of any value.

4.8. Parameter Profiles

This specification defines three non normative parameter profiles. They
exist to provide guidance to implementers while preserving full control
over p, q, and R. These profiles are examples only and do not restrict


the algorithm.

Profile S:
    Intended use: embedded systems, IoT, constrained devices
    Typical p size: 64 to 96 bits
    Typical q size: 64 to 96 bits
    Expected R size after decomposition: 150 to 300 bits
    Recursion: optional, typically 1 or 2 levels
    Notes: public key remains small while entropy is carried by the
    abR encoding and optional recursion.

Profile M:
    Intended use: general purpose cryptography
    Typical p size: 128 to 192 bits
    Typical q size: 128 to 192 bits
    Expected R size after decomposition: 300 to 600 bits
    Recursion: optional, typically 1 to 3 levels
    Notes: recommended for most deployments that need long term
    security with compact public keys.

Profile L:
    Intended use: high security, post quantum hardening
    Typical p size: 256 bits or greater
    Typical q size: 256 bits or greater
    Expected R size after decomposition: 512 bits or greater depending
    on the factorization depth and the randomized serialization
    structure.
    Recursion: optional without upper limit
    Notes: for environments requiring maximum entropy. The abR
    serialization and recursive decomposition provide exponential
    growth of the secret search space.

Profile selection does not change the algorithm. All profiles rely on
the same decomposition mechanism, the same abR serialization method,
and the same security model based on the absence of oracle feedback.
Implementers MAY define additional profiles as long as the core
mechanism remains unchanged.

6. Security Considerations

This section describes the security foundations of Phi-Ns, the assumed
attack model, and the cryptanalytic implications of exposing either p or

q as the public key. Security relies on the difficulty of inverting the
structured relation:

    q*q - p*p = 2^a * 3^b * R = T

where T is never published, and the internal structure (a, b, R,
permutation, partition) is committed through SHA-256 without leakage.
The adversary receives only the public key and the commitment.

6.1. Hardness Assumption

The adversary must recover the full private tuple:

    (p or q), a, b, R, factorization of R,
    permutation of atomic factors,
    partition of blocks, and serialized encoding.



The inversion problem is:

    Given PK and commit,
    find all private values such that ENC(abR) matches commit.

This problem is non-linear, combinatorial and recursive. It does not
reduce to integer factorization, discrete logarithm or lattice problems.
Shor's algorithm is ineffective because no usable composite is exposed.
Grover's algorithm yields only quadratic speedup over an already
super-exponential domain.

6.2. No Oracle

Phi-Ns gives no feedback when a candidate reconstruction is incorrect.
The mapping:

    commit = SHA256(ENC(abR))

behaves as a random oracle. Every incorrect guess produces an unrelated
digest. The attacker cannot detect proximity to the correct structure
and
cannot prune the search space. There is no partial verification.

6.3. Growth of the Search Space

To invert Phi-Ns, the adversary must guess simultaneously:

  - the correct prime (p in PKQ, q in PKP),
  - the correct gap T = q*q - p*p,
  - the correct exponents a and b,
  - the correct residual R,
  - the full atomic factorization of R,
  - the permutation of atomic factors,
  - the number of blocks K,
  - the assignment of atoms to blocks,
  - the final serialized bytes of ENC(abR).

Each dimension multiplies the search space. Even modest parameters
produce super-exponential complexity. For example, a 128-bit R with 20

atomic factors yields more than:

    20! * Bell(20)  > 2^200

possible blockings and permutations, excluding the search over p or q.
For realistic security levels, the total inversion space exceeds 2^300.

6.4. Recursive Decomposition

Phi-Ns optionally allows recursive decomposition:

    p*p = p2*p2 + 2^a2 * 3^b2 * R2

and p2 may itself be decomposed again. Each layer introduces new
factors,
new permutations and new partitions. The complexity multiplier per layer
is approximately:



    layer_cost  =  (factor_count)! * Bell(factor_count)

so two layers with 20 factors each yield an inversion space above
2^400. This allows very small public keys (for example, 32 or 64 bits)
to
reach effective security comparable to 128-bit or 256-bit schemes when
recursion is used.

6.5. PKQ vs PKP Exposure

PKQ exposes q. The attacker must find p near q because primes of similar
size have predictable spacing. The search range for p is therefore
bounded.

PKP exposes p. The attacker must guess q without knowing its magnitude.
Since q is derived from a 256-bit PRF, the attacker cannot estimate the
gap:

    delta = q - p

The domain for candidate q is effectively unbounded above p. This makes
PKP strictly harder to invert. PKP enables extremely small public keys
for IoT and embedded deployment.

Numeric illustration (PKP):

    p = 15485863
    q is unknown and could be any prime > p
    For q in [p+1, p+2^128], the adversary must test all primes
    before checking decomposition. This search space is > 2^126.

6.6. Quantum Resistance

Shor's algorithm does not apply because there is no composite number to
factor. Grover's algorithm improves brute-force by a square root, but
the
domain is super-exponential in R and the block structure. For any
deployment profile of at least 128-bit classical security, the quantum-

reduced cost remains far outside practical reach.

6.7. Resistance to Meet-in-the-Middle

Meet-in-the-middle attacks require partial leakage on two halves of a
structure. Phi-Ns reveals none. All private values interact through
ENC(abR), which destroys correlation via permutation and partitioning.
Commitments do not permit partial verification, removing a key pre-
requisite for MITM optimization.

6.8. Side-Channel Considerations

Implementations MUST run constant-time big-integer operations. All
private structures (seed, p, q, a, b, R, blocks) MUST be zeroized after
use. Implementations SHOULD use masked big-integer arithmetic and avoid
secret-dependent branching. The specification itself does not leak
structure.

6.9. PKI Perpetuity and Key Rotation



Phi-Ns supports perpetual public keys. Since only one prime is public,
the private key may be rotated infinitely without modifying the public
key. Rotation replaces the decomposition of T with a new (a, b, R)
structure, a new permutation, and a new block partition. The public
identity remains stable. This property enables long-lived certificates
and lightweight renewal for IoT, automotive, industrial and satellite
environments.

6.10. Summary

Phi-Ns security relies on a new inversion problem combining quadratic
relations and combinatorial decomposition. No known classical or quantum
attack reduces the search below super-exponential cost. The recursive
model allows arbitrarily high entropy from small public keys. The
absence
of oracle feedback and the unpredictability of ENC(abR) define the core
hardness of the primitive.


In designing Phi-Ns, conventional hash standards such as [FIPS180] and
deterministic random bit generators as specified in [NIST90A] are
assumed for commitments and key-derivation functions. The scheme is
positioned in the context of post-quantum cryptography work [NISTPQC]
and existing national guidance such as [ANSSI] and [NCSC]. Earlier
work on one-time signatures [Lamport], hash constructions [SHA256],
and prior descriptions of Phi-Ns [PhiNs] informed aspects of this
design.

7. IANA Considerations

This document does not require any IANA actions.

No new registries are created, no parameters are allocated, and no
existing registries are modified by this specification.

If future versions of Phi-Ns define wire formats, CBOR tags, or protocol

identifiers, those will be registered in separate companion documents.


8. References

8.1. Normative References

[RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
           Requirement Levels", BCP 14, RFC 2119, March 1997.

[RFC8174]  Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 2119
           Key Words", BCP 14, RFC 8174, May 2017.


8.2. Informative References



[NISTPQC]  National Institute of Standards and Technology, "Post-Quantum
           Cryptography Standardization Project", 2016-2025.

[ANSSI]    Agence Nationale de la Securite des Systemes d'Information,
           "RGS v2.0  Rfrentiel Gnral de Scurit", 2020.

[NCSC]     National Cyber Security Centre, "Cryptographic
           Recommendations for TLS, VPNs, and Messaging", 2022.

[Lamport]  Lamport, L., "Constructing Digital Signatures from a One Way
           Function", October 1979.

[SHA256]   Dobbertin, H., Bosselaers, A., and Preneel, B., "The Hash
           Functions MD5, SHA-1 and RIPEMD", 1996.

[PhiNs]    Nsangani, J., "Phi-Ns: Quadratic Structured Decomposition
           for Asymmetric Cryptography", Patent Pending, 2025.


Author's Address

   Parfait Junior Nsiangani (Editor)
   Email: jnsiangani@gmail.com