Skip to content

README.md

Latest commit

 

History

History
142 lines (99 loc) · 6.48 KB

README.md

File metadata and controls

142 lines (99 loc) · 6.48 KB

RootCrypt and the NERP Problem

Marshall Ta
Version 1.0.1 · July 2025

Abstract

This document introduces and outlines RootCrypt, a hybrid post-quantum encryption scheme grounded in a new hardness assumption called NERP
(Nonlinear Entangled Ring Projection). By combining a chaotic, nonlinear ring-based key exchange with AES-256-GCM authenticated encryption,
RootCrypt offers resistance against both classical and quantum adversaries. We contrast NERP with its lattice-based predecessor NELP and highlight
how integer-ring arithmetic, enhanced entropy, and modern AEAD mitigate earlier weaknesses.

Table of Contents

  1. Introduction

As quantum computing advances, widely used public-key primitives such as RSA and ECC face obsolescence. In mid-2025, NIST selected
CRYSTALS-Kyber (Module-LWE) for standardization, owing to its solid proofs and efficient implementation. RootCrypt pursues an alternative:
it embeds secrets into a nonlinear ring map, yielding the NERP challenge. Our goal is to merge cryptographic unpredictability with performance
by leveraging structured integer rings.

  1. From NELP to NERP

The initial RootCrypt design relied on NELP (Nonlinear Entangled Lattice Projection), which used floating-point vectors, fractal mappings,
and Gaussian perturbations. NELP suffered from:

  • Platform-dependent rounding errors and decryption failures
  • Limited seed entropy (64 bits) vulnerable to brute-force
  • No formal reduction to a standard hard problem
  • Lack of side-channel protections

NERP overcomes these by adopting:

  • Fixed-width integer rings (e.g., $\mathbb{Z}_{2^{16}}^n$)
  • Platform-independent modular arithmetic
  • 128-bit seed entropy
  • Deterministic nonlinear mappings
  • Native support for AES-256-GCM

  1. Defining the NERP Problem

Let $f_s: \mathbb{Z}_q^n \to \mathbb{Z}_q^n$ be a nonlinear ring function parameterized by seed $s$. The public key publishes noisy projections:

Let $P_i = f_s(x_i) + \eta_i$ be noisy projections, where $\eta_i$ is small random noise. The challenge is to recover any preimage $x' \approx x_i$ that maps within noise tolerance of $P_i$, without knowledge of $x_i$ or $s$. Security relies on:

  1. Intractability of inverting $f_s$
  2. Indistinguishability of $f_s(x) + \eta$ from random over $\mathbb{Z}_q^n$

These assumptions, while plausible, are not yet reducible to a standard problem like LWE or Ring-LWE.

  1. Hybrid Encryption Design

KEM: NERP-Based Key Encapsulation

  1. KeyGen: Generate $x \in \mathbb{Z}_q^n$, derive $f_s(x)$, publish $P$
  2. Encapsulation: Recipient selects the closest projection to a hashed message vector, deriving $f_s(x)$

DEM: AES-256-GCM

  • Apply HKDF to $f_s(x)$ and a salt to derive a 256-bit key.
  • Encrypt the payload with AES-256-GCM using a 128-bit IV and 16-byte authentication tag.

This composition yields authenticated, quantum-resistant encryption.

  1. Feature Comparison: NELP vs. NERP

Feature NELP (Lattice) NERP (Ring)
Arithmetic Floating-point (double) Integer mod q (int32_t mod q)
Stability Low (rounding errors) High (modular arithmetic)
Noise Gaussian Discrete
Decryption Robustness Fragile inverse map Deterministic
Seed Entropy 64 bits 128 bits
Side-Channel Mitigation Weak Stronger (constant-time friendly)
AE Integration AES-CBC AES-256-GCM
Formal Link None Aligned with Ring-LWE concepts

  1. Comparison with CRYSTALS-Kyber

Feature RootCrypt (NERP) CRYSTALS-Kyber (Kyber-768)
Hardness Basis Heuristic nonlinear map Module-LWE with tight reduction
Public Key Size ~8 KiB (configurable) 1,184 bytes
Ciphertext Size Message + 64 B overhead 1,088 bytes
Provable Security Conjectural IND-CCA2 via FO transform
Performance Moderate (no NTT) Very fast (NTT-accelerated)
Decryption Failure None Negligible (~2⁻¹⁶⁴)
AE Scheme AES-256-GCM Built-in FO transform

  1. Open Questions and Future Work

  • Formal reduction of NERP to Ring-LWE or a related problem
  • Security analysis of fₛ as a one-way function
  • Behavior under chosen-ciphertext attacks (CCA)
  • Acceleration via NTT or polynomial-ring constructions
  • Revised NERP problem allowing for standard asymetric key cryptography (and therefore, E2EE)

  1. Conclusion

RootCrypt and the NERP assumption chart a fresh direction in post-quantum hybrid encryption. By shifting from floating-point lattices to
structured integer rings, boosting entropy, and embracing authenticated encryption, NERP overcomes its predecessor’s shortcomings. NERP’s ring operations are designed for constant-time evaluation, though formal timing leakage analysis remains future work. Though promising, it requires rigorous proofs and extensive cryptanalysis before standardization can proceed.

As both RootCrypt and NERP are yet to be more rigorously studied, this whitepaper doesnt completely exempt either of the two technological advancements from being problem free, and there is a very clear bar to be raised, as I expect within at least the next 20 years to be raised. With all said, RootCrypt and NERP prove to be two very useful innovations within the cybersecurity landscape, and this opens the door for a multitude of other tech and security innovations.