Selective-node-secure BTE ⇒ Forward-secure PKE (Canetti–Halevi–Katz)

Fully-black-box reduction · standard model · CHK03 · security loss: a factor T, from guessing the challenge period

Statement

A selective-node-secure binary tree encryption (BTE) scheme of depth gives a forward-secure PKE scheme with periods — CHK03. Period is the -th node of the tree in pre-order, a ciphertext for period is a BTE ciphertext for that node, and consists of the keys of that node and of the right siblings of the nodes on its path from the root, so it holds at most BTE keys — CHK03.

Sketch

None of the keys in belongs to a prefix of the node of any period , since the subtrees under those keys contain only periods . The reduction guesses the challenge period , names its node as , and answers the break-in query with keys of non-prefixes of , which it derives by from the keys the BTE game gives it; these are distributed as in the scheme, which also derives every key from the root key by .

Notes

  • An IND-sHIBE-CPA-secure HIBE of depth gives a selective-node-secure BTE scheme of depth when, for every key that can output, is distributed as : the node is the identity for two fixed distinct symbols , the delegated keys of the BTE game are then distributed as independently extracted ones, and the selective HIBE adversary may extract the key of every non-prefix of the target identity — standard. The argument needs the condition: the IND-sHIBE-CPA game gives the adversary only extracted keys, while the BTE game gives keys delegated from the root key — standard.
  • The construction of CHK04 secures any BTE scheme against chosen-ciphertext attacks, which gives chosen-ciphertext forward-secure PKE in the standard model — CHK04.
  • With keys linear in instead, forward-secure PKE follows from CPA-secure PKE alone (CPA-secure PKE ⇔ Forward-secure PKE) — folklore.