7 min read
On this page

Advanced Cryptographic Primitives

Functional Encryption (FE)

In functional encryption, a secret key sk_f is associated with a function f. Decrypting ciphertext Enc(m) with sk_f yields f(m) and nothing else about m.

Formal definition: Setup generates master key msk and public parameters. KeyGen(msk, f) produces sk_f. Enc(pk, m) produces ciphertext ct. Dec(sk_f, ct) = f(m).

Security: IND-based -- adversary cannot distinguish encryptions of m_0 and m_1 given function keys for which f(m_0) = f(m_1).

Hierarchy of generality:

  • IBE and ABE are special cases of FE
  • General-purpose FE (for arbitrary circuits) implies indistinguishability obfuscation (iO) (Goldwasser et al.)
  • Known constructions: FE for inner products (from DDH, LWE, pairings -- practical), FE for quadratic functions, general FE from iO or multilinear maps (theoretical)

Inner product FE: Dec(sk_y, Enc(x)) = <x, y>. Useful for weighted sums, linear statistics on encrypted data. Constructions from DDH (Abdalla et al.), LWE (Agrawal et al.), and pairings.

Multi-input FE (MIFE): Multiple ciphertexts from different encryptors; function key decrypts across them. Enables computation on data from multiple sources without a trusted aggregator.

Attribute-Based Encryption (ABE)

Encryption where access is governed by attributes and policies.

Key-Policy ABE (KP-ABE)

Ciphertexts are labeled with attributes. Secret keys are associated with access policies. Decryption succeeds iff the ciphertext's attributes satisfy the key's policy.

Example: Ciphertext tagged with attributes {"Department: Engineering", "Clearance: Secret"}. A key with policy "(Department: Engineering) AND (Clearance: Top Secret OR Clearance: Secret)" can decrypt.

Ciphertext-Policy ABE (CP-ABE)

Dual of KP-ABE: ciphertexts embed the access policy, keys are associated with attribute sets. The encryptor defines who can decrypt. More natural for access control.

Constructions: Based on bilinear pairings (Waters 2011) or lattices (Boneh et al.). The pairing-based schemes support expressive policies (monotone Boolean formulas, linear secret sharing schemes).

Performance: Ciphertext and key sizes grow with the number of attributes/policy complexity. Decryption involves multiple pairing operations. Practical for moderate-size policies.

Multi-Authority ABE

Attributes managed by multiple independent authorities, eliminating single points of trust. Each authority issues keys for its own attribute domain. Decryption combines keys from multiple authorities.

Identity-Based Encryption (IBE)

Public key is an arbitrary identity string (email, name, etc.). A trusted authority (PKG) with master key generates private keys for identities.

Boneh-Franklin IBE

First practical IBE construction (2001), based on bilinear pairings on elliptic curves.

Setup: PKG generates master key s, public parameters (G, G_T, e: G x G -> G_T, P, P_pub = sP, H_1, H_2).

Key extraction: For identity ID, private key d_ID = s * H_1(ID) (point on curve).

Encryption: To encrypt m for identity ID:

  1. Q_ID = H_1(ID)
  2. Choose random r
  3. Ciphertext: C = (rP, m XOR H_2(e(Q_ID, P_pub)^r))

Decryption: Compute e(d_ID, rP) = e(sQ_ID, rP) = e(Q_ID, P_pub)^r, then recover m.

Security: IND-ID-CPA secure under the Bilinear Diffie-Hellman (BDH) assumption in the random oracle model. CCA security via Fujisaki-Okamoto transform.

Key escrow problem: PKG knows all private keys. Mitigated by: threshold PKG (distributed key generation), certificate-based encryption (hybrid with PKI), or certificateless encryption.

Hierarchical IBE (HIBE): Enables delegation of key generation. Root authority delegates to domain authorities, who delegate to users. Constructed from lattices (GPV framework) with shorter parameters.

Broadcast Encryption

Efficiently encrypt to a subset S of n users. Non-members cannot decrypt.

Naor-Naor-Lotspiech (NNL): Tree-based scheme. Each user assigned to a leaf; internal nodes have keys. To revoke r users, transmit O(r log(n/r)) ciphertexts covering all non-revoked subtrees.

Boneh-Gentry-Waters: Constant-size ciphertext regardless of |S| (using bilinear pairings). Public key and user keys are O(n) in size. Ciphertext: O(1), decryption: O(1) pairings.

Traitor tracing: Identify users who leak their decryption keys. Combined with broadcast encryption to create trace-and-revoke systems. The Boneh-Sahai-Waters construction provides fully collusion-resistant traitor tracing.

Proxy Re-Encryption (PRE)

Enables a proxy to transform ciphertexts encrypted under Alice's key into ciphertexts decryptable by Bob, without the proxy learning the plaintext.

Unidirectional PRE: Re-encryption key rk_{A->B} allows transformation A -> B but not B -> A. Alice generates rk_{A->B} from her secret key and Bob's public key.

Construction (BBS, based on ElGamal):

  • Alice encrypts: (c_1, c_2) = (g^r, m * pk_A^r)
  • Re-encryption key: rk = pk_B^{1/sk_A} (requires Alice's secret key)
  • Re-encrypt: (c_1, c_2 * e(c_1, rk)) transforms to a ciphertext Bob can decrypt

Properties: Collusion resistance (proxy + Bob should not learn sk_A), non-interactivity (Bob need not participate in re-key generation), single-hop vs multi-hop (can re-encryption be applied repeatedly).

Applications: Encrypted email forwarding, cloud storage access delegation, DRM, encrypted file sharing systems.

Searchable Encryption

Enables search over encrypted data without decryption.

Symmetric Searchable Encryption (SSE)

Client encrypts documents and keyword indices. Server stores encrypted data. Client generates search tokens for keywords; server identifies matching documents without learning keywords or contents.

Approaches:

  • Inverted index: Encrypt a mapping from keywords to document identifiers. Search token reveals the keyword's entry but nothing else.
  • Forward privacy: New documents cannot be linked to previous searches for the same keyword.
  • Backward privacy: Deleted documents do not appear in future search results.

Leakage profiles: SSE inevitably leaks some information (access pattern, search pattern, volume). Formal leakage functions quantify what the server learns. ORAM-based approaches reduce leakage but with significant performance overhead.

Public-Key Searchable Encryption (PEKS)

Based on IBE (Boneh-Di Crescenzo-Ostrovsky-Persiano). Anyone can encrypt searchable ciphertexts; only the key holder can generate search tokens. Enables keyword search on public-key encrypted email.

Structured Encryption

Generalization of SSE to arbitrary data structures (graphs, matrices). Encrypt a data structure while supporting specific query types (range queries, graph traversals) with controlled leakage.

AEAD (Authenticated Encryption with Associated Data)

Provides both confidentiality and integrity in a single primitive.

Security notion: INT-CTXT (ciphertext integrity) + IND-CPA = IND-CCA. AEAD achieves this natively.

Constructions:

  • AES-GCM: AES in Counter mode (CTR) for encryption + GHASH (polynomial MAC over GF(2^128)) for authentication. Hardware-accelerated (AES-NI + CLMUL). Nonce-misuse is catastrophic (reusing nonce leaks XOR of plaintexts and breaks authentication).
  • ChaCha20-Poly1305: ChaCha20 stream cipher + Poly1305 MAC. Software-efficient (no hardware AES needed), used in TLS 1.3, WireGuard. Same nonce-misuse vulnerability.
  • AES-GCM-SIV: Nonce-misuse resistant. Derives a synthetic IV from nonce and message. Nonce reuse only leaks equality of plaintexts, not contents.
  • AEGIS: AES-based AEAD with state-of-the-art performance (faster than AES-GCM on hardware with AES-NI). Uses AES round functions as the state update, achieving very high throughput.

Associated data: Authenticated but not encrypted (e.g., packet headers, metadata). The tag covers both ciphertext and associated data.

Key commitment: Standard AEAD schemes are not key-committing -- the same ciphertext may decrypt validly under different keys to different plaintexts. Key-committing AEAD adds a binding property, important for applications like encrypted backups and abuse reporting.

Deniable Encryption

Encryption where the sender and/or receiver can produce fake randomness that makes a ciphertext appear to encrypt a different message.

Sender deniable: Given ciphertext c = Enc(m, r), sender can produce fake randomness r' such that c = Enc(m', r') for any chosen m'. Indistinguishable from genuine encryption.

Receiver deniable: Receiver can produce a fake secret key sk' that decrypts c to m' instead of m.

Bidirectional deniability: Both sender and receiver can deny.

Constructions:

  • Canetti-Dwork-Naor-Ostrovsky: First sender-deniable scheme. Uses a translucent set (large public key, O(n) ciphertext expansion).
  • Sahai-Waters: Bidirectional deniability from indistinguishability obfuscation (iO). Theoretical but establishes feasibility.
  • Practical approaches: Deniable file systems (hidden volumes in VeraCrypt), steganographic encryption, plausible deniability in messaging (OTR's deniability property).

Applications: Protecting against coercion (forced disclosure of keys), plausible deniability for journalists/activists, legal protections.

Limitations: Offline deniability (producing fake randomness after the fact) is easier than online deniability (generating deniable ciphertexts in real time). Most practical messaging protocols achieve a weaker form of deniability through ephemeral keys and lack of non-repudiation, rather than full cryptographic deniability.