How Does A Posteriori Openable Encryption Work?

TL;DR

A posteriori openable public key encryption lets a sender create a constant-size interval key after messages have been sent, allowing a proxy to decrypt one selected interval while protecting messages outside it. The presented construction strengthens prior work with CCA security, standard-model proofs, generic cryptographic tools, and only one public key encryption operation per message.

Transcript

Hello, everybody. I am Xavier Butel. I am associate professor at INSA Centre Val de Loire in France, and I'm going to present you my work entitled CCA Secure A Posteriori Openable Encryption in the Standard Model. So let me first introduce the motivation of the primitive, so the motivation of a posteriori openable public key encryption. We consider... Read More

Key Insights

• A posteriori openable public key encryption is a selective-disclosure mechanism that lets a sender choose an interval only after sending encrypted messages, then authorize a proxy to decrypt that interval without revealing messages outside its boundaries.
• The construction supports an unbounded number of messages and an unbounded interval size, while its interval key, sender secret key, and ciphertexts remain independent of both the total ciphertext count and the selected interval length.
• The scheme has a single-interval limitation: the sender can produce only one interval key for one interval, although the chosen interval can be extended. An adaptation can support disjoint intervals, but ciphertext size then grows linearly with the number of intervals.
• The naive alternative assigns a symmetric key to every encrypted message and forms an interval key by concatenating all keys within the selected range. Consequently, the resulting interval key has the same linear size as the interval it opens.
• Delegatable pseudorandom functions provide another alternative that supports keys for disjoint intervals, but the total ciphertext count must be bounded before encryption begins, and neither interval-key size nor interval decryption time remains constant.
• IND-CCA security addresses an adversary formed by the interval opener colluding with dishonest receivers. The adversary attempts to identify the message in a challenge ciphertext but cannot obtain an interval key covering that challenge.
• IND-CSCA security treats an interval of successive ciphertexts as the challenge and models colluding dishonest receivers without the opener. Its non-malleability goal requires interval decryption to reject altered, added, removed, or reordered ciphertexts.
• The double-chain decryption mechanism splits every message into red and blue shares. Forward-linked red ciphertexts and backward-linked blue ciphertexts let an interval key expose both shares only within the selected interval, leaving outside messages with one unavailable share.

Questions & Answers

Q: What is a posteriori openable public key encryption?

A posteriori openable public key encryption lets a sender encrypt a sequence of messages and later choose an interval to disclose. The sender extracts a special interval key after the messages have already been sent. A proxy using that key can decrypt all messages within the chosen interval but cannot recover messages outside the interval.

Q: Why is selective interval opening useful for encrypted messaging?

Selective interval opening lets a user provide evidence about communications from a relevant period without exposing every stored conversation. In the example, Alice wants to demonstrate to a legal authority that she did not cooperate with an accused contact. Plaintext storage would reveal unrelated messages, while ordinary public key encryption would prevent the authority from examining the relevant ciphertexts.

Q: What efficiency requirements does the encryption scheme satisfy?

The scheme allows an unbounded number of encrypted messages and an interval whose length is also unbounded. Its interval key, sender secret key, and ciphertexts do not depend on either the total number of ciphertexts or the interval size. These objects are constant in size and must also be generated in constant time.

Q: What limitation applies to the interval keys?

The construction can produce only one interval key for one interval, although the selected interval may be extended later. It cannot directly issue two interval keys for two disjoint intervals. The scheme can be adapted to support that behavior, but the ciphertext size then increases linearly with the number of intervals that must be supported.

Q: How do naive and pseudorandom-function alternatives compare?

A naive construction creates a separate symmetric decryption key for every message and concatenates the relevant keys to open an interval, so the interval key grows exactly with the interval length. A delegatable pseudorandom function can reduce the key size to logarithmic in a predetermined message bound and support disjoint intervals, but it loses constant key size and decryption time.

Q: What does the IND-CCA security property protect?

IND-CCA extends conventional chosen-ciphertext security to the setting with standard receiver decryption and interval opening. Its adversary represents collusion between the interval opener and dishonest receivers and tries to determine which message appears in a challenge ciphertext. The adversary is not permitted to obtain an interval key for an interval containing that challenge.

Q: What does IND-CSCA security protect against?

IND-CSCA covers chosen-set-of-ciphertexts attacks involving colluding dishonest receivers without the opener. Its challenge is an interval of successive ciphertexts rather than one ciphertext, and the adversary receives standard and interval-opening decryption oracles. The intended non-malleability property makes decryption fail when ciphertexts in an interval are altered, inserted, removed, or reordered.

Q: How does the double-chain decryption mechanism open an interval?

Each message is divided into a red share and a blue share. Every red ciphertext contains a key for opening the next red ciphertext, while every blue ciphertext contains a key for opening the previous blue ciphertext. Giving the opener boundary keys reveals both shares inside the interval, but only one share for each outside message, preventing its reconstruction.

Summary & Key Takeaways

• A posteriori openable public key encryption addresses selective disclosure after communication. A sender encrypts successive messages normally, then later derives an interval key for a chosen period. A proxy can use that key to recover every message inside the interval, while messages before and after the selected interval remain protected from disclosure.

• The construction supports unbounded message sequences and intervals while keeping ciphertexts, secret keys, and interval keys constant in size and generation time. Its principal limitation is that only one interval key for one interval can be produced, although that interval may later be extended. Supporting multiple disjoint intervals requires larger ciphertexts.

• The proposed scheme introduces IND-CCA, IND-CSCA, and integrity requirements for its two decryption paths. It relies on public key encryption, secret key encryption, a pseudorandom function, and message authentication codes. A double-chain mechanism distributes message shares so that only messages inside the authorized interval can be reconstructed.