Oscar Reparaz

A big-key public key encryption scheme

Update: The core idea below already appears in Public-Key Encryption in the Bounded-Retrieval Model, by Joël Alwen, Yevgeniy Dodis, Moni Naor, Gil Segev, Shabsi Walfish, and Daniel Wichs, published in Advances in Cryptology – EUROCRYPT 2010, pp. 113–134 (ePrint preprint, 2009). They take the core idea here and do it properly; the security issue is pretty subtle.

In my version, stealing 1% of the identity keys lets an attacker decrypt about 1% of future messages. More subtly, an attacker could compute on the whole key collection and exfiltrate a short result: ordinary IBE security alone does not rule out a much smaller substitute that still decrypts messages. Erasing MSK does not settle that. Their construction combines several randomly selected key components and proves security against bounded leakage computed before the target ciphertext is known.

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 #

Prototype implementation #

Can be found here: oreparaz/bigkey-pke.

Some notes: