Full description of the algorithm

Below is a complete description of the QuarkDash Crypto library's operating algorithm. This algorithm provides production ready and fast quantum-resistant hybrid encryption protocol

General architecture

QuarkDash is a hybrid post-quantum protocol combining:

• Asymmetric key exchange based on Ring-LWE (resistant to quantum attacks);
• Symmetric encryption with a choice of stream ciphers (ChaCha20 or Gimli);
• Quantum-resistant KDF based on SHAKE256;
• Message authentication via SHAKE256-MAC;
• Protection against replay attacks using timestamps and sequence numbers;

---

Algorithm Description

Full QuarkDash comparison with popular encryption algorithms can be found here

1. Long-Term Key Generation (Ring-LWE)

Ring parameters:

• Dimension N = 256
• Modulus Q = 7681 (a prime number suitable for NTT)
• Primitive root ω = 5685 (of order N) (Changed in v.1.2.1, previous is 7)
• For Q = 12289 is ω = 8340

Key pair generation process:

• A polynomial a(x) with uniform coefficients from ``Z_Q` is randomly selected.
• A secret polynomial s(x) with small coefficients from {-1, 0, 1} is randomly selected.
• An error polynomial e(x) with small coefficients from {-1, 0, 1} is randomly selected.
• Calculate b(x) = a(x) ⊗ s(x) + e(x) (multiplication in the ring Z_Q[x]/(x^N+1)):
• • NTT is implemented with the bit-reversible Cooley-Tukey algorithm.
• • To protect against side-channel attacks, blinding, doubleCheck, and input polynomial validation are enabled (all protections are active by default).
• Public key = (a, b) (serialized into bytes, ~2KB).
• Private key = s(x) (~1KB).

Mathematically:
b = a ⊗ s + e (multiplication via NTT, addition coefficient-wise Q).

2. Session Establishment (KEM – Key Encapsulation Mechanism)

Initiator (for example Client):

• Obtains Recipient's public key (a, b).
• Generates random small polynomials s' and e'.
• Computes u = a ⊗ s' + e' (this is the ciphertext).
• Computes w = b ⊗ s' (the approximate shared secret).
• Uses single-bit cross-rounding to generate a 32-byte hint. The hint allows the recipient to correct possible decoding errors.
• Generates the final ciphertext: u (512 B) + hint (32 B) = 544 B.
• Sends cifertext to Recipient.

Recipient (for example Server):

• Receives u and hint.
• Applies rounding and recovers the shared secret using the hint (function rec), correcting for errors.
• As a result, both parties receive the same sharedSecret (256 bits).

Why does the secret match?
w' = u ⊗ s = (a⊗s' + e') ⊗ s = a⊗s'⊗s + e'⊗s
w = b ⊗ s' = (a⊗s + e) ⊗ s' = a⊗s⊗s' + e⊗s'

The difference w - w' = e⊗s' - e'⊗s is a small error that does not affect rounding.

Important: Version 1.2.1 fixes NTT roots and introduces a hint, improving security and error tolerance. The old ciphertext format (512 B without a hint) is no longer supported.

3. Session Key Derivation (KDF)

• SHAKE256 (an implementation of Keccak-f with 50×32-bit state) is used
• Input: sharedSecret (256 bits), deterministic salt (32 bytes), "session-key" label.
• Expansion process (HKDF-like): PRK = SHAKE256(salt || sharedSecret), T(0) = SHAKE256(PRK || info || 0x01), T(i) = SHAKE256(PRK || T(i-1) || info || i)
• Output: 64 bytes of key material.
• Divided into:
• • sessionKey (32 bytes) – for encryption.
• • macKey (32 bytes) – for authentication.

4. Cipher Initialization

• A per-message nonce is generated for each message (enabled by default): a 12-byte header containing a timestamp (8 bytes) and a sequence number (4 bytes). This prevents gamma reuse.
• The encryption algorithm is selected: ChaCha20 or Gimli. Both are implemented with optimized Keystream classes that support lazy evaluation, caching, and random access.
• A cipher instance is created with session key.

5. Message Encryption (AEAD – Authenticated Encryption)

• Input: plaintext P (Uint8Array).
• Formation of metadata (12 bytes):
• • Bytes 0-7: current timestamp (uint64, little-endian).
• • Bytes 8-11: sequence number (uint32, little-endian, incrementing).
• Encryption: -- C = cipher.encrypt(P) (stream cipher: XOR with gamma, with cache and lazy compute).
• MAC Calculation:
• • Input for MAC: metadata || C.
• • Key: macKey.
• • Algorithm: MAC = SHAKE256(macKey || data, 32).
• Formation of final message:
• • E = metadata || C || MAC.

6. Message Decryption

• Input: encrypted message E.
• Parsing:
• • metadata = E[0:12]
• • C = E[12:-32]
• • MAC = E[-32:]
• MAC Check:
• • Calculate expectedMAC similarly and compare using constant-time.
• Timestamp Check:
• • Extract the timestamp from the metadata and compare it with the current time. The acceptable deviation is 5 minutes.
• Sequence Number Check:
• • Extract the seq and verify that it has not been repeated (store it in a window of the last 1000 packets).
• Decryption:
• • P = cipher.decrypt(C).
• • Return P.

---

Key rotation

• Secure session key rotation without disconnecting is supported.
• The rekey() method generates a new sessionKey and macKey based on the old key, salt, and counters.
• First, the token is encrypted with the old key (encrypt), then the new key is derived (derive). This ensures that the other party can decrypt the token using the old keys and then switch to the new ones (synchronization).
• The rotation policy can be set by the number of bytes, the number of messages, or a time interval.

---

Syntetic Tests

The data below are approximate values ​​from synthetic tests of the algorithm.

QuarkDash Crypto Results:

• Encryption speed: ~2.5 GB/s;
• Decryption speed: ~2.5 GB/s;
• Session creation speed: ~2-3 ms;
• Public key size: ~2KB;
• Private key size: ~1KB;
• Overhead: 44 bytes;
• The Difficulty of Quantum Hacking: 2^256