PROFET


Puncturable Encryption – A Fine-Grained Approach to Forward-Secure Encryption and More: Part II

April 16, 2021 | 12 Minute Read

In Part I of this blog series, we discussed why forward security for public-key encryption (PKE) is an important security property, but has limitations concerning synchronization and unprotected ciphertexts within an interval (or, epoch). In this part, we will cover how puncturable encryption (PE) makes the concept of forward security more fine-grained. In particular, we discuss how synchronization can be removed entirely and how ciphertexts within the same epoch for looser synchronization can be protected. Moreover, we reflect on state-of-the-art PE schemes.

Making Forward Security More Fine-Grained

We recall from Part I that if the switches between intervals in forward-secure public-key encryption (PKE) happen too frequently, it requires good synchronization, whereas for longer time intervals, a looser synchronization can be established. The latter is preferred and particularly interesting for many scenarios such as asynchronous messaging or for achieving 0-RTT forward-secure key exchange. It is, however, clear that in case of a looser synchronization, leaking a key might give access to many encrypted messages. Consequently, the achieved forward-security property using plain forward-secure PKE is very coarse-grained, i.e., a synchronized clock has to be maintained and the ciphertexts within the current interval are not protected.

One way to mitigate this problem and make forward-secure PKE more fine-grained is to use puncturable encryption (PE), a cryptographic primitive introduced by Green and Miers [GM15]. The idea here is to provide a forward-security property that allows a secret key to be modified (or, “punctured”) on specific ciphertexts in a way that the resulting secret key will then no longer be useful to decrypt ciphertexts on which the key has been punctured already.

Essentially, the ciphertexts in PE now carry a more general tag instead of the more specific time interval. The secret key can be punctured on that particular tag, thereby removing the ability of the secret key to decrypt such ciphertexts. See that this yields a more fine-grained approach to forward-secure PKE as one can specifically exclude decryption access from keys and removes the all-or-nothing restriction that old-interval ciphertexts cannot be decrypted anymore once the key is updated as in the CHK approach [CHK03]. Furthermore, since puncturing happens on specific tags associated to ciphertexts, when tags are chosen accordingly (as discussed below) no synchronization is needed at all. In Figure 4, we illustrate the high-level idea behind the PE approach, where \((sk,\varepsilon)\) represents the initial unpunctured secret key.

Figure 4: Puncturing the secret key on tags in puncturable encryption.

In the following, we want to discuss the main difference between forward-secure PKE with synchronization (as in [CHK03]) and PE. Forward-secure PKE with synchronization is defined over intervals (or, epochs) and over some time-dependent input, while PE is defined over tags and, hence, over some tag-dependent input. In that sense, PE overcomes the need for synchronization required in forward-secure PKE, but has the limitation that message-suppression attacks (MSA) are possible. Such attacks allow the adversary to refrain the receiver from receiving ciphertexts and, hence, such ciphertexts cannot be used for puncturing the secret key in PE. Clearly, non-punctured ciphertexts can then be decrypted in case of a key leakage. For a a more detailed discussion on MSA, we refer to [BG20].

As a consequence, while forward-secure PKE with synchronization guarantees that old-interval ciphertexts cannot be decrypted anymore, PE ensures that all tag-dependent ciphertexts cannot be decrypted anymore if the secret key was punctured on such a tag already. PE is modular in the sense that if one uses tags from a small tag space, e.g., a tag space consisting of intervals, one obtains forward-secure PKE with synchronization. If tags are chosen uniformly at random from a small tag space, one removes the need for synchronization, but has to deal with collision in the tags and some ciphertexts that might not be decryptable anymore. Moreover, message-suppression attacks are possible. If tags are chosen uniformly at random from a large-enough tag space so that the probability of obtaining collision is negligible, one eliminates synchronization as well, but still one has to deal with message-suppression attacks.

As it turns out, one can use the features of both, forward-secure PKE and PE, in combination. On the higher level, one has the notion of time with the desired property of only a loosely coupled synchronization to defend against message-suppression attacks. Furthermore, within intervals that can be made large enough, e.g., one day, one can puncture ciphertexts on tags to guarantee the forward-security property for already decrypted ciphertexts within that interval. Such combination yields fine-grained forward-secure PKE properties as desired by many applications which we will discuss in Part III. In Figure 5, we depict the discussed properties of forward-secure PKE with synchronization and PE.

Figure 5: Overview of properties for forward-secure PKE with synchronization and PE.

Constructions of Puncturable Encryption for Forward-Secure Public-Key Encryption

In the last years, we have seen quite some works on PE with various flavors starting from the initial work on PE [GM15]. The initial PE work uses non-monotonic attribute-based encryption (ABE), i.e., ABE that supports negations of attributes, to remove the decryption capabilities from secret keys for ciphertexts associated to one or more tags. Essentially, once a ciphertext is received, the secret key is punctured on the ciphertext's tag \(t\) by adding a “NOT \(t\)“-element to the updated secret key. That essentially means that ciphertexts with such a tag \(t\) cannot be decrypted by the updated secret key anymore. The secret key grows with the number of punctures, i.e, tags added, while the public key and ciphertexts enjoy compact sizes. Green and Miers further combined their PE scheme with the CHK-approach to achieve fine-grained forward-secure PKE for the asynchronous-messaging scenario they are targeting. This resulted in a forward-secure PKE scheme with loosely coupled synchronization over intervals while received ciphertexts within the intervals stay protected.

In 2017, the initial work on PE was extended for the use in 0-RTT forward-secret key-exchange with replay protection [GHJL17], a combination of properties unknown to be achievable at that time. Essentially, the authors showed how to construct fine-grained forward-secure PKE from any (selectively secure) HIBE. While their scheme now only required HIBEs and not the stronger form of ABE anymore, puncturing the secret keys is a very costly operation which could take seconds to minutes for appropriate tag spaces and reasonable implementations. The secret key now grows linearly in the number of punctures while the public key and ciphertexts are compact. As with the initial work on PE, this resulted in forward-secure PKE scheme with a loosely coupled synchronization over intervals while received ciphertexts within the intervals stay protected.

A short time later, Bloom-Filter Encryption (BFE) was defined in [DJSS18] (and additional instantiations are given in [DGJSS21]), where a large tag space of a PE scheme is shrinked to be polynomial in the security parameter using a Bloom Filter, a probabilistic data structure for approximate set-membership tests. Puncturing secret keys now became very efficient and only consists of deleting parts of the secret key indexed by bits resulting from including the tag into the Bloom Filter. The secret-key sizes increase, though, and scale in the security parameter and the number of maximum punctures. Yet, the public key and the ciphertexts are of compact sizes. Essentially, the mapping to the Bloom Filter results in a non-negligible decryption error which is the trade-off for efficient secret-key puncturings. We discuss the application of BFE for 0-RTT forward-secret key-exchange in Part III.

Inspired by BFE as an efficient PE primitive, the work in [CRSS20] recently showed how to obtain BFE generically from any identity-based encryption (IBE) scheme with non-negligible correctness error. This yielded a first step towards a post-quantum BFE instantiation. Another work [SDLP20] provides a post-quantum secure PE, based on a primitive called delegetable fully-key homomorphic encryption. It however cannot be considered puncture-efficient. Furthermore, in [SSSLG20], an approach to generically construct PE based on a variant of an identity-based revocation scheme was provided. It allows various instantiations in bilinear groups providing different trade-offs in sizes of keys and ciphertexts. At this point it becomes clear that there are various approaches to construct PE providing different trade-offs between sizes and efficiency. The choice of the most suitable one then heavily depends on the targeted application. In Figure 6, we give a comparison of state-of-the-art PE schemes.

Figure 6: Comparison of state-of-the-art PE schemes.

Variants of Puncturable Encryption

We now focus on PE schemes with enhanced puncturing features beyond the simple secret-key manipulation. The first line of works is fully PE (FuPE) [DKLRSS18] and forward-secure puncturable IBE (fs-PIBE) [WCWHM19]. Within FuPE, ciphertexts are associated to separate tag spaces, i.e., to tags from a so-called positive and negative tag space, while decryption keys can be first associated to several negative tags and a final positive tag. In fs-PIBE on the other hand, ciphertexts are also associated to a positive and a negative tag while decryption keys can be first associated to one positive tag and afterwards to several negative tags. Here, negative tags are as in conventional PE, i.e., a secret key punctured on such a tag cannot decrypt a ciphertext carrying this tag, while a secret key punctured on a positive tag requires this tag to be present in the ciphertext to be able to decrypt. FuPE realized the first forward-secret proxy re-encryption (PRE) scheme while fs-PIBE has been shown to have applications to Cloud-hosted e-mail systems.

The recent work in [DRSS21] enhanced those capabilities even further. In particular, their work allows to first associate the secret key with several negative tags, then with a positive tag, and afterwards with several further negative tags again, which yields new applications areas not yet covered by existing approaches such as an enhanced version of Cloudflare's Geo Key Manager, forward-secure IBE and signatures. [DRSS21] also provides an abstraction via so-called allow-list/deny-list encryption that helps to classify PE schemes with such different types of puncturing functionality.

Another recent work [SS21] extends the functionality of puncturing from secret keys only to also allow puncturing of ciphertexts via the notion of ciphertext-puncturable encryption (CPE). A CPE scheme can abstractly be viewed as a PE scheme with an additional algorithm to puncture ciphertexts. However, there are some significant differences compared to conventional PE. Ciphertext puncturing is no fully public and stand-alone operation, but requires so-called puncturing tokens to keep ciphertexts and public keys in synchronization. Overall, CPE gives rise to the first no-directional updatable encryption (UE) scheme.

In the next blog post (Part III), we discuss applications of puncturable encryption and an implementation. If you have any comments, suggestions or questions, please feel free to contact us (@CStriecks, @sebastinas_, @drl3c7er).

References

me
me
me
me

Based on long haul and project pages. Powered by Jekyll.