Big-key cryptography is regular cryptography with huge private keys. The main idea is to make key exfiltration harder. Unlike standard cryptography, which uses (say) 32-byte secret keys, big-key cryptography uses on purpose massive keys (gigabytes) so that an attacker gaining temporary access to your system has a tough time exfiltrating all this. This increases the likelihood you detect the attacker or slow them down.

Big-key public key encryption. Here we design a public-key encryption system with “short” public keys (32 bytes) and very long private keys. The basic idea is to use an identity-based encryption scheme (like Boneh–Franklin) under the hood. The following explanation assumes you have a standard IBE with IBE.Setup(), IBE.Extract(), IBE.Encrypt() and IBE.Decrypt() operations.

Setup phase #

  1. Master Key Generation (Alice)
    • Alice runs IBE.Setup() → generates (MPK, MSK)
    • MPK becomes Alice’s public key (published/distributed to everyone)
    • MSK is kept temporarily for key extraction only
  2. Identity Pre-Agreement (Alice & Bob)
    • They agree on a large set of identities, e.g.:
      • “alice-001”, “alice-002”, …, “alice-100000”
      • Could be: sequential, random strings, UUIDs, etc.
      • Each identity represents one decryption capability
    • Both parties store this list of valid identities
  3. Big Private Key Generation (Alice)
    • For each agreed identity ID_i, Alice runs: SK_i = IBE.Extract(MSK, ID_i)
    • The “big private key” is the collection: BigSK = {SK_001, SK_002, ..., SK_100000}
    • CRITICAL: Alice then securely wipes MSK from memory/storage
    • MSK is never stored long-term, only used during setup

Encryption (Bob → Alice) #

To send message M to Alice:

  1. Bob picks an identity at random from the pre-agreed list
    • E.g., randomly select "alice-047851"

  2. Bob encrypts using IBE: C = IBE.Encrypt(MPK, "alice-047851", M)

  3. Bob sends to Alice: (C, "alice-047851")

    The identity must be included so Alice knows which key component to use

Decryption (Alice) #

When Alice receives (C, ID):

  1. Alice looks up the corresponding private key component from her big key
    • E.g., if ID = "alice-047851", retrieve SK_047851

  2. Alice decrypts using IBE: M = IBE.Decrypt(SK_047851, C)

  3. (Optional) Alice can delete SK_047851 after use for forward secrecy

Drawbacks #

  • It’s not “all or nothing”. An attacker that exfiltrates a portion of the private key gets a non-zero chance of decrypting ciphertexts to Alice (probability proportional to what they managed to exfiltrate).

Prototype implementation #

Can be found here: https://github.com/oreparaz/bigkey-pke

Some notes: