𝔦-TiRE: Incremental Timed-Release Encryption

or
How to use Timed-Release Encryption on Blockchains?
Leemon Baird Pratyay Mukherjee Rohit Sinha
Swirlds Labs Swirlds Labs Swirlds Labs
leemon@[Link] [Link]@[Link] [Link]@[Link]

ABSTRACT CCS CONCEPTS

Timed-release encryption can encrypt a message to a future time • Security and privacy → Cryptography.
such that it can only be decrypted after that time. Potential appli-
cations include sealed bid auctions, scheduled confidential trans- KEYWORDS
actions, and digital time capsules. To enable such applications as Timed-release Encryption, Blockchain, Identity-based Encryption
decentralized smart contracts, we explore how to use timed-release
ACM Reference Format:
encryption on blockchains. Leemon Baird, Pratyay Mukherjee, and Rohit Sinha. 2022. 𝔦-TiRE: Incre-
Practical constructions in the literature rely on a trusted server mental Timed-Release Encryption or How to use Timed-Release Encryption
(or servers in a threshold setting), which periodically publishes an on Blockchains?. In Proceedings of the 2022 ACM SIGSAC Conference on
epoch-specific decryption key based on a long-term secret. Their Computer and Communications Security (CCS ’22), November 7–11, 2022, Los
main idea is to model time periods or epochs as identities in an Angeles, CA, USA. ACM, New York, NY, USA, 14 pages. [Link]
identity-based encryption scheme. However, these schemes suffer 1145/3548606.3560704
from a fatal flaw: an epoch’s key does not let us decrypt ciphertexts
locked to prior epochs. Paterson and Quaglia [SCN’10] address 1 INTRODUCTION
this concern by having encryption specify a range of epochs when Timed-release encryption [26] can encrypt a message “locked" to a
decryption is allowed. However, we are left with an efficiency con- future time such that a receiver can only decrypt the ciphertext after
cern: in each epoch, the server(s) must publish (via a smart contract that time. It opens the door for several novel applications [31, 32].
transaction) a decryption key of size logarithmic in the lifetime Examples include: 1) sealed-bid auctions; 2) scheduled confidential
(total number of epochs). For instance, on Ethereum, for a modest transactions (e.g. insider trades); 3) digital equivalent of time cap-
lifetime spanning 2 years of 1-minute long epochs, a server must sules1 ; 4) cryptocurrency wallet backups (e.g., escrow or a set of
spend over $6 in gas fees, every minute; this cost multiplies with users assisting with key recovery after a deadline).
the number of servers in a threshold setting. The existing constructions of timed-release encryption can be
We propose a novel timed-release encryption scheme, where a broadly divided into two categories: computational reference clocks
decryption key, while logarithmic in size, allows incremental up- and trusted time servers. Schemes based on computational refer-
dates, wherein a short update key (single group element) is sufficient ence clocks [10, 11, 14, 17, 32] require the recipient to perform an
to compute the successive decryption key; our decryption key lets expensive sequential computation (also called time-lock puzzle) to
the client decrypt ciphertexts locked to any prior epoch. This leads recover the message. This has the benefit of non-interactive decryp-
to significant reduction is gas fees, for instance, only $0.30 in the tion, but is highly inefficient for most applications. The practical
above setting. Moreover, ciphertexts are also compact (logarithmic alternative is to rely on trusted time server(s) [12, 15, 16, 30, 31]
in the total lifetime), and encryption and decryption are on the who holds a master secret key, and periodically releases decryption
order of few milliseconds. Furthermore, we decentralize the trust keys at each time epoch (for example, every minute or even every
among a number of servers, so as to tolerate up to a threshold second).
number of (malicious) corruptions. We begin our work with the following question: how can timed-
Our construction is based on bilinear pairing, and adapts ideas release encryption be used by smart contracts on blockchains? Such a
from Canetti et al.’s binary tree encryption [Eurocypt 2003] and primitive would enable privacy-enhancing alternatives to a large
Naor et al.’s distributed pseudorandom functions [Eurocrypt 1999]. ecosystem of decentralized financial applications, such as auctions
and decentralized exchanges (DEXs) – in particular, sealed bid
auctions and scheduled confidential transactions can rely on the
Permission to make digital or hard copies of all or part of this work for personal or users’ orders being secret (until a deadline) while also binding or
classroom use is granted without fee provided that copies are not made or distributed actionable without requiring any further interaction from the user
for profit or commercial advantage and that copies bear this notice and the full citation
on the first page. Copyrights for components of this work owned by others than ACM (e.g., opening in a commit-reveal scheme, which the user will only
must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, do if the outcome is favorable)2 . We study timed-release encryption
to post on servers or to redistribute to lists, requires prior specific permission and/or a
fee. Request permissions from permissions@[Link]. 1A 19th century application: Mark Twain stipulated that his autobiography not be
CCS ’22, November 7–11, 2022, Los Angeles, CA, USA. published for 100 years after his death [1].
2 In that light, timed-release decryption can be viewed in the same light as threshold
© 2022 Association for Computing Machinery.
ACM ISBN 978-1-4503-9450-5/22/11. . . $15.00 decryption, but with the added crucial property that a single key can be used across
[Link] arbitrary many applications and users.

235
CCS ’22, November 7–11, 2022, Los Angeles, CA, USA. Leemon Baird, Pratyay Mukherjee, and Rohit Sinha

in the following blockchain-based setting: a set of servers, of which can use 𝑛 servers (up to (𝑡 − 1) of them can be malicious), each of
a threshold fraction is assumed to operate correctly, periodically them holding only a share of the master secret key, such that any 𝑡
publish (shares of) the decryption key via transactions to an special (for 1 ≤ 𝑡 ≤ 𝑛) of them can collaborate to generate update keys.
aggregator contract, who then aggregates them for use by other We provide a simple and efficient construction that achieves
smart contracts, such as for sealed-bid auctions3 . chosen-plaintext security using an (asymmetric) bilinear pairing
A long line of constructions [12, 15, 31] operate by deriving an on a Gap Diffie-Hellman group – our security reduces to the de-
independent key for each epoch by essentially making black-box cision Bilinear Diffie-Hellman (DBDH) assumption in the random
use of identity-based encryption (where epochs are mapped to oracle model. Our (𝑡 out of 𝑛) threshold solution is obtained us-
identities). While the keys are sufficiently compact (single group ing the key-homomorphic property of our construction similar to
element), they suffer from a fatal problem: an epoch’s key does not threshold BLS signatures [6] or NPR distributed PRFs [27]. Mali-
let us decrypt ciphertexts locked to prior epochs, which is a common cious security against ≤ 𝑡 corruptions is achieved using techniques
situation given the nature of our applications – a workaround is to similar to DiSE [2]. The overall solution is still quite efficient. We
store historical keys, but that incurs on-chain storage that is linear also show how to obtain CCA-security using a standard (namely
in the lifetime of the system. Fujisaki-Okamoto [19]) transformation. We emphasize that these
Paterson and Quaglia [30] proposed a natural extension, called two augmentations are done independently such that it is possible
time-specific encryption, wherein the encryption procedure can to combine these properties (CCA and threshold-malicious security
lock the ciphertext to a range of time epochs when decryption together) in any desired way.
is allowed, with only logarithmic increase in the ciphertext size Consider a few metrics for our maliciously secure threshold
(and logarithmic size keys) – this allows prior decryption with only scheme (CCA security), for a sample data point: lifetime of 230
logarithmic size on-chain storage. However, an efficiency concern epochs, or roughly 34 years with 1-second epochs. Our key size is
remains. Note that each server must publish the latest decryption logarithmic in the number of epochs; it averages 2.4 KB, depending
key on each epoch, which incurs a smart contract transaction with on the specific epoch. Computing the update key incurs logarithmic
logarithmic size input – the natural design is to use an “incremental" number of group operations on the server (2-4 ms on average).
mode of operation where a server publishes only the delta between The update key is one group element (48 bytes) in each epoch;
two consecutive keys; even then, a server would publish 𝑙𝑜𝑔(𝑇 )/2 in the threshold setting, servers publish one group element each.
new group elements on average in each epoch (where 𝑇 is the total Ciphertexts are also logarithmic in size (0.19-2 KB of ciphertext
number of epochs in the system’s lifetime). expansion) and decryption incurs logarithmic number of group
Input bytes are expensive for on-chain transactions. Consider operations (35-50 ms).
an example deployment on Ethereum; with a lifetime of 𝑇 = 220
epochs (roughly 2 years lifetime spanning 1-minute epochs), 100 1.2 Summary of Our Contribution
servers would spend a total of $614 in gas costs for each epoch.4 − We formalize incremental timed-release encryption, called
For timed-release encryption to be practical on blockchains, in- 𝔦-TiRE, and in particular its incrementality property (and its
cremental updates must be short. That is the objective of this work. extension to the threshold setting).
− We put forward a new efficient construction satisfying our
1.1 Our work incrementality requirement.
We provide a novel solution for timed-release encryption, which − We provide an open-source implementation and evaluation
has an asymptotic and concrete reduction in on-chain costs. In measuring the sizes of keys and ciphertexts, and the running
particular, our scheme has a special incrementality property that time of the various algorithms in our threshold 𝔦-TiRE scheme.
ensures that the server needs to publish exactly one group element
(called the update key) in each epoch, for augmenting the decryp- 2 RELATED WORK
tion key from epoch 𝜏 to 𝜏 + 1; this updated decryption key can be Computational Reference Clocks. Instead of having an absolute
used to decrypt ciphertexts locked to any epoch ≤ 𝜏 + 1. The de- decryption time, schemes based on time-lock puzzles require the re-
cryption key is still logarithmic size, as in [30], so on-chain storage cepient to perform an expensive sequential computation to recover
is logarithmic size. Since update keys, and therefore their smart the message, thus imposing a coarse-grained release time. Rivest et
contract transactions, are now constant size, our total cost for 100 al. [32] provide a construction based on repeated squaring modulo
servers goes down to $30.7 for each epoch, in the example above. a product of two primes. Mahmoody et al. [25] constructs time-lock
We maintain other characteristics from [30]; our ciphertexts are puzzles in the random oracle model. Liu et al. [24] construct time-
logarithmic in size, and encryption and decryption operations are locked encryption using a computational reference clock (based on
also logarithmic time (on the order of few milliseconds). Bitcoin hashchains) and an extractable witness encryption scheme,
While our base scheme has a single trusted key-server, we also which is not practical.
propose how to further decentralize the system by using 𝑡 out of 𝑛
threshold cryptography techniques. In particular, we show how we Trusted Time Servers. Blake and Chan [12] and Cheon et al. [15]
provide schemes that are adaptations of the Boneh-Franklin IBE
3 This model is based on blockchain oracles, who provide off-chain data and services, scheme [5]. An similar technique [28] is adapted by Shutter Net-
by periodically issuing transactions in exchange for a token payment. work to prevent front-running attacks. None of these schemes
4 At the time of writing, as per [36], each byte of a transaction costs 16 gas units; with
an average cost of 200 GWei per gas unit, we incur 0.0000032 ETH or roughly $0.01 at enables compact decryption of prior ciphertexts; in other words, to
$3000 / ETH. So, a single group element of 32 bytes costs roughly $0.30. enable decryption of prior ciphertext one needs to store all keys

236
𝔦-TiRE: Incremental Timed-Release Encryption CCS ’22, November 7–11, 2022, Los Angeles, CA, USA.

released so far. The scheme of Rabin and Thorpe [31] requires the al. [4] the decryption key is already 𝑂 (𝑇 ) size – this falls short of
servers to compute a separate public key for each epoch, whose our efficiency requirement (we need 𝑂 (log𝑇 )).
private component is released during that epoch. This requires the
servers to apriori publish a long list of future public keys. Binary Tree Encryption [9]. As we also explain in Section 3, our
techniques build on the binary-tree encryption (BTE) construction
Time-specific Encryption [30]. Perhaps the most relevant to ours proposed by Canetti et al. [9]. However, the main goal of their work
is the work by Paterson and Quaglia [30], who introduced a related was to construct an FSE scheme, which can be thought of as a “dual”
notion called time-specific encryption, where ciphertexts are locked of our goal. Pre-order traversal helped them to achieve it. So using
to a range of timestamps. Certainly, our notion of timed-release a post-order traversal comes as a somewhat natural choice for us.
encryption is a special case of their notion, because one may just But it is not just that. We also have to open up their BTE scheme
fix the upper range to the maximum value of time to obtain a timed- and change the construction to drop the so-called “R” values to
release encryption. We do not focus on achieving time-specific achieve 𝑂 (1)-sized update keys. This does not alter the functionality
encryption. Instead, we focus on achieving the incrementality prop- because we do not really need the key-delegation property (as a
erty which was not considered before. Taking a closer look at their central server holding master-key is issuing the update-keys). So,
work [30], we observe that while it is possible to adapt their scheme in effect, our scheme achieves something which lies somewhere
to our setting, it will still fail to achieve the incrementality. On av- between a HIBE and an IBE (c.f. Remark 1). In fact, we think that it
erage the update keys in the adapted scheme would consist of might be possible just to use pre-order traversal in our scheme with
log(𝑇 )/2 group elements, whereas for our scheme it is always a a reverse interpretation of time like Kasamatsu et al. [23]. However,
single group element (recall that the incrementality requires this to dropping the “R” values seems even more crucial as without that it
be constant size, always). Intuitively, this is due to the fact that they is unclear how to achieve incrementality.
put the path information (root to node) into their keys and use a Additional Relevant Works. Specter et al. [35] add deniability to
minimal set cover for the ciphertexts, whereas our ciphertexts have emails by divulging private signing keys over time from a hierar-
the path information and our decryption keys are corresponding chical identity-based signature scheme, adapted from the Gentry-
to a minimal set cover via a post-order traversal. Since ciphertexts Silverberg scheme [21]. Moreover, their hierarchy mimics that of a
can not be augmented from one another (because they depend on calendar, and they achieve succintness by allowing a child’s key to
independent randomnesses), they are unable to leverage the bene- be derivable from the parent’s key. While there is technical similar-
fit of minimal set cover for incrementality, whereas, our strategy ity, our scheme shows how a binary identity space can enable more
through post-order labeling enables us to leverage this benefit by efficient tree-based encryption with shorter keys. The scheme by
using only a single group element as an update key. Apart from this Ning et al. [29] splits a secret into shares, and requires the share-
crucial difference our scheme also has additional benefits: (i) our ci- holders to release their shares at a future time or get penalized by
phertexts are 2x smaller than theirs as they used IBE in a black-box a smart contract.
manner (both the schemes have log(𝑇 )/2 group elements in their
ciphertexts on average); (ii) our decryption key contains between 1 3 TECHNICAL OVERVIEW
to log(𝑇 ) group elements, whereas theirs is always log(𝑇 ) group
We distinguish between update keys, each of which is released at a
elements, making our keys 2x smaller on average. We note that com-
time epoch, and decryption keys which lets one decrypt all cipher-
bining a generic IBE with post-order traversal (instead of pre-order)
texts encrypted up to a specific time. Looking ahead, a decryption
one would get an incremental scheme that would indeed satisfy
key 𝐾𝜏 for time 𝜏 is constructed from the update key 𝑢𝑘𝜏 for time 𝜏
our definition including efficiency and incrementality. However,
and the decryption key 𝐾𝜏−1 for 𝜏 − 1.
instantiating the IBE even with the most efficient scheme, such as
Boneh-Franklin [5], would incur at least a 2x blow-up in ciphertext
size (as mentioned above in (i)). Our scheme can be alternatively
3.1 Deployment and Operation
thought as an optimized version of such an instantiation, where For clarity, we first describe the system design with a single server,
many ciphertexts would share the same randomness. For more and then discuss the threshold scenario.
details we refer to Section 8. Smart Contract Service. Timed-release encryption is used as a
service to smart contracts provided by a trusted time server, who
Time-Specific Encryption from Forward-secure Encryption [23]. In periodically modifies a smart contract with the decryption key for
a follow up work, Kasamatsu et al. [23] constructed time-specific the latest epoch. In particular, the contract is initialized with the
encryption from any forward-secure encryption (FSE). As a special decryption key for epoch 0. From then on, once every epoch, the
case of time-specific encryption, they also constructed a primitive server issues a transaction containing an update key for the latest
called past time-specific encryption (PTSE) (c.f. Section 4.1 of [23]), epoch. The transaction is destined to a special aggregator contract
which is virtually the same as the notion of timed-release encryp- that uses the update key to compute the latest decryption key – any
tion. The idea to to convert FSE to PTSE relies upon an elegant trick application smart contract (e.g. auction) can read the aggregator’s
of reverse interpretation of time. Nevertheless, the generic construc- most-recent decryption key.
tion relies on the underlying FSE instantiation. When instantiated
with Canetti et al.’s [9] HIBE-based scheme, it yields log(𝑇 )-sized Threshold Setting. To avoid having a single point of failure or
update keys, and thereby does not meet our incrementality require- trust, we show how to extend to a threshold setting that uses a
ment (we need 𝑂 (1)). In another instantiation based on Boneh et collection of servers. A setup phase establishes a lifetime (long-term)

237
 CCS ’22, November 7–11, 2022, Los Angeles, CA, USA. Leemon Baird, Pratyay Mukherjee, and Rohit Sinha

secret key 𝑙𝑠𝑘, and generates a corresponding public key 𝑙𝑝𝑘. Instead − Dec(𝑢𝑘𝜏 , 𝑐) outputs 𝑚 := 𝑣 · 𝑒 (𝑢𝑘𝜏 , 𝑢) −1 where 𝑐 = (𝑢, 𝑣).
of the whole 𝑙𝑠𝑘, the setup phase outputs shares of 𝑙𝑠𝑘 computed Note that these operations correspond closely to the Boneh-
using a 𝑡 out of 𝑛 threshold secret sharing scheme [34];5 here, 𝑛 Franklin IBE construction [5]. A debilitating property of this scheme
denotes the number of servers and 𝑡 is the corruption threshold, as is that the keys {H (𝜏)𝛼 }𝜏 ∈1...𝑇 are unstructured, in that they can-
in 𝑡 shares are required to reconstruct 𝑙𝑠𝑘 and any subset of 𝑡 − 1 not be aggregated or compressed (without 𝛼). In particular, there
shares reveals no information (in the information-theoretic sense) is no way to compactly describe a decryption key at time epoch 𝜏,
about 𝑙𝑠𝑘. Each server 𝑆𝑖 is given a share 𝑙𝑠𝑘𝑖 of the whole secret which would be used to decrypt any ciphertext encrypted to a time
𝑙𝑠𝑘. epoch 𝜏 0 ≤ 𝜏.
Operation. Clients use the public key 𝑙𝑝𝑘 to encrypt messages, at
which point they must also specify a future epoch. During any given
3.3 HIBE-based approach
epoch 𝜏, each server 𝑆𝑖 publishes a partial update key 𝑢𝑘𝜏,𝑖 . Given Our initial observation is that keys must mimic the inherent hi-
any 𝑡 such partial tokens, the aggregator contract can combine erarchy amongst the epochs: key material for a later epoch must
them to attain the whole update key 𝑢𝑘𝜏 ; the 𝑢𝑘𝜏 is then combined subsume that of earlier epochs, while not revealing any bits of infor-
with 𝐾𝜏−1 to compute 𝐾𝜏 . The application contract then uses 𝐾𝜏 to mation about the future epochs. This points us towards hierarchical
decrypt any ciphertext “locked” to epoch 𝜏 or earlier. Note that a identity-based encryption [21, 22] (HIBE).
single instance of timed-release encryption service can support an In addition to the properties of an IBE scheme, HIBE assumes a
arbitrary number of applications. This allows the servers’ cost to partial ordering for the identity-space and derives keys hierarchi-
be amortized; therefore, we must look past simpler schemes that cally. That is, in addition to associating a key with each identity,
scale poorly, such as having the sender secret-share each message given identities 𝑖𝑑  𝑖𝑑 0 , the key for 𝑖𝑑 can be derived from the key
to the servers to be later released to the receiver, for instance. for 𝑖𝑑 0 , via a property called delegation. This property is beneficial
Observe the following key characteristics: for our use case, wherein we can define a partial order amongst
the epochs, and thus avoid using keys of lower-level epochs if a
− The scheme is non-interactive, in that the keys output by
higher-level update key is already available. In particular, we focus
the server do not depend on the message or the ciphertext.
on a particular HIBE construction for a restriced identity space of
Moreover, there is no interaction amongst the servers either.
binary strings, known as Binary Tree Encryption (BTE) [9]. Con-
− The whole 𝑙𝑠𝑘 is never made available to any party.
sider arranging identities or epochs in a binary tree, as illustrated
− Decryption for a ciphertext locked to 𝜏 requires a key for epoch
below for 𝑇 = 15 epochs.
𝜏 0 ≥ 𝜏, which is available when at least 𝑡 servers release their
shares of the update key for epoch 𝜏 0 – this ensures that at
least one honest server must have waited until epoch 𝜏. 15
𝜖
Next we provide technical highlights of our scheme, and defer 1
0
full details to Section 6. First, we describe the prior IBE based con- 7 14
struction, which fails to meet our efficiency requirements. Then,
wee describe our main construction, and later show how to thresh- 00 01 10
oldize it. Finally, we mention how to achieve CCA and malicious 3 6 10 ...
security.
000 001 010 011 100 101
1 2 4 5 8 9
3.2 Prior IBE-based Constructions
Let us briefly examine how prior works [12, 15] essentially adapt
identity-based encryptions (IBE) to the purpose of timed-release Figure 1: Double labeling of tree with epoch id (via post-order tra-
versal) and path id (binary encoding of path from root node)
encryption. The basic idea is to apply the pairing-based IBE scheme
of Boneh and Franklin [5], where each identity is mapped to an
epoch. The scheme makes use of source groups6 G and GT which Each node is given two labels or identities: the epoch id 𝜏 (0 ≤
are both cyclic groups of prime order 𝑞, a bilinear pairing 𝑒 : G × 𝜏 ≤ 𝑇 ), and a path id 𝜔 containing a binary string that denotes the
G → GT , generator 𝑔 ∈ G, and hash function H : {0, 1}∗ → G. path to that node from the root (left child being 0 and right child
The scheme essentially works as follows: being 1) – we find it convenient to present the construction using
the path-based identity, but it is not strictly necessary. The path
− Setup : Sample random 𝛼 ←$ 𝑍𝑞 , and output the lifetime public
identities form a prefix order relation, where 𝜔  𝜔 0 if 𝜔 0 is a prefix
key 𝑙𝑝𝑘 := 𝑔𝛼 , and lifetime secret key 𝑙𝑠𝑘 := 𝛼.
of 𝜔 – we denote the root node (or the least upper bound) by the
− In each epoch, the server outputs update key 𝑢𝑘𝜏 := H (𝜏)𝛼 .
empty string 𝜖. The epoch id is assigned via a post-order traversal
− Enc(𝑚, 𝜏) outputs 𝑐 := (𝑔𝑟 , 𝑚 · 𝑒 (H (𝜏)𝑟 , 𝑙𝑝𝑘)) for 𝑟 ←$ 𝑍𝑞 .
on the binary tree, which gives us a very useful property explained
5 Inthe threshold setting, the setup phase can also be performed using a distributed
later.7
key generation protocol [20], in lieu of assuming a trusted dealer, such that no single Consider a non-leaf node with path id 𝜔 and epoch id 𝜏. Then,
party learns the lifetime secret key, however we do not place any such demands on any of its descendant has an epoch id 𝜏 0 < 𝜏. Furthermore, 𝜔 is a
the setup phase in our definition and it does not matter that much because it is done
only once in the beginning. 7 It is evident later when we present the construction that binary tree structure provides
6 For ease of exposition, we assume the symmetric variant of pairings where both the best space efficiency for our scheme. Furthermore, we also explain why post-order
source groups are same – our implementation uses asymmetric pairings for efficiency. traversal is chosen as opposed to pre-order (as chosen in [9]) or in-order ones.

238
𝔦-TiRE: Incremental Timed-Release Encryption CCS ’22, November 7–11, 2022, Los Angeles, CA, USA.

prefix of 𝜔 0 , which is the path id corresponding to 𝜏 0 . Clearly, a

15𝜖
HIBE key (we refer to such keys as update keys) for a node labeled 𝜔 𝑆𝜖 =𝐻 (𝜖) 𝛼
can be used to derive a key corresponding to node 𝜔 0 . This satisfies
𝑆 0 =𝐻 (𝜖) 𝛼 𝐻 (0) 𝛼
our requirement because any such epoch 𝜏 0 is smaller than 𝜏. So, it 70 ...
is sufficient to include a single update key for 𝜏 to enable decryption
corresponding to any 𝜏 0 which is the epoch id of a descendant — this 𝑆 01 =𝐻 (𝜖) 𝛼 𝐻 (0) 𝛼 𝐻 (01) 𝛼
enables the desired compression. Note that, the set of descendants, ... 601
however, do not exhaust all prior epochs, and therefore we need
to include more update keys into a decryption key to enable the 𝑆 01 =𝐻 (𝜖) 𝛼 𝐻 (0) 𝛼 𝐻 (01) 𝛼 𝐻 (011) 𝛼
time hierarchy we want. However, the tree-structure guarantees ... 5011
that any decryption key does not contain more than log(𝑇 ) update
keys. Figure 2: update keys for our doubly-labeled tree
For instance, we can publish the HIBE key for node 000 in epoch
1, 000 and 001 in epoch 2, 00 in epoch 3, nodes 00 and 010 in epoch 4,
and so on. In particular, for a node with path id 𝜔, a decryption key
consists of 𝑤 update keys, where 𝑤 denotes the hamming weight of Lifetime Keys : 𝑙𝑠𝑘 = 𝛼, 𝑙𝑝𝑘 = 𝑔𝛼 where 𝛼 ←$ 𝑍𝑞
bit-string 𝜔. Therefore, in the worst case a decryption key consists
of log(𝑇 ) + 1 update keys.8 Instantiating with a scheme such as Key for path id 𝜔 generated with 𝑙𝑠𝑘 :
BTE, that uses 𝑂 (log(𝑇 )) group elements for one update key, we |𝜔 |
Ö
obtain a scheme where a decryption key requires 𝑂 (log2 (𝑇 )) group 𝑆𝜔 = H (𝜖)𝛼 · H (𝜔 | 𝑗 )𝛼
elements in total. 𝑗=1
While investigating this, we find that the delegation property – Encryption of 𝑀 :
using an id key to derive keys for lower-level identities – of HIBE is
𝐶 = (𝑔𝛾 , H (𝜔 | 1 )𝛾 , H (𝜔 | 2 )𝛾 . . . , H (𝜔)𝛾 , 𝑀 · 𝑑)
not strictly required for our setting (also see Remark 1). In particular,
in contrast to the HIBE requirements, our key-generation procedure where 𝑑 = 𝑒 (𝑙𝑝𝑘, H (𝜖))𝛾 = 𝑒 (𝑔, H (𝜖))𝛼𝛾
always has access to the lifetime secret-key 𝑙𝑠𝑘 (which actually Decryption of 𝐶 with 𝑆𝜔 :
makes it similar to IBE). Our key contribution is to construct a new Parse 𝐶 as (𝑈 0, 𝑈 1, . . . , 𝑈𝑡 , 𝑉 )
encryption scheme that supports a hierarchical decryption, in that
𝑒 (𝑈 0, 𝑆𝜔 )
any decryption key for time 𝜏 can be used to decrypt a ciphertext Output 𝑀 = 𝑉 · 𝑑 −1 where 𝑑 = Î
|𝜔 |
corresponding to time 𝜏 0 ≤ 𝜏, but does not support key-delegation 𝑖=1 𝑒 (𝑙𝑝𝑘, 𝑈𝑖 )
such as deriving a decryption key exactly for epoch 𝜏 0 . Sacrificing
the delegation property enables us to have constant size update
The bilinearity property of pairings implies that:
keys, which are sufficient to “increment” the time bound key from
one epoch to the next one. A new trick we use for this purpose is 𝑒 (𝑈 0, 𝑆𝜔 )
𝑑= Î
|𝜔 |
𝑖=1 𝑒 (𝑔 , 𝑈𝑖 )
a post-order labeling of the tree (hence calling it a doubly-labeled 𝛼
tree). Î |𝜔 |
Next we provide an overview of our core 𝔦-TiRE construction. 𝑒 (𝑔𝛾 , H (𝜖)𝛼 · 𝑗=1 H (𝜔 | 𝑗 )𝛼 )
= Î |𝜔 |
𝑖=1 𝑒 (𝑔 , H (𝜔 |𝑖 ) )
𝛼 𝛾

|𝜔 |
3.4 Our 𝔦-TiRE scheme
Î
𝑒 (𝑔, H (𝜖))𝛼𝛾 · 𝑖=1 𝑒 (𝑔, H (𝜔 |𝑖 ))𝛼𝛾
= Î |𝜔 |
We now present the core aspects of our scheme below (within the
𝑖=1 𝑒 (𝑔, H (𝜔 |𝑖 ))
𝛼𝛾
box), and give the full details in Sec. 6. We note that our construction
= 𝑒 (𝑔, H (𝜖))𝛼𝛾
is inspired by the BTE construction of Canetti et al. [9]. In what
follows, we use path id and epoch id of a node interchangably — as
discussed in Sec. 6, this is enabled by an efficient bijective mapping For instance, say that we wish to encrypt for 𝜔 = 01, and decrypt
between these two labels. In the description in the following box, first using 𝑆 01 and later using 𝑆 0 (note that for 01, the decryption
we shall use 𝜔 |𝑖 to denote the first 𝑖 bits of 𝜔, |𝜔 | to denote the key consists of two update keys). Encryption of message 𝑀 for
bit-length of 𝜔, and 𝑆𝜔 to denote the id key for node with path id 𝜔 = 01 produces the ciphertext:
𝜔.
(𝑈 0 = 𝑔𝛾 , 𝑈 1 = H (0)𝛾 , 𝑈 2 = H (01)𝛾 ,
The update keys for our example are shown here in red.
𝑉 = 𝑀 · 𝑒 (𝑔𝛼 , H (𝜖))𝛾 )
Observe that the 𝑒 (𝑔𝛼 , H (𝜖))𝛾 term acts as a random mask based
on the client’s chosen randomness 𝛾. Given id key 𝑆 01 = H (𝜖)𝛼 ·
H (0)𝛼 · H (01)𝛼 , we decrypt the above ciphertext as follows:
𝑒 (𝑔𝛼 , 𝑈 1 ) · 𝑒 (𝑔𝛼 , 𝑈 2 )
𝑉 · 𝑑 −1 = 𝑉 · =𝑀
8 Note that this happens for nodes with path id 111 . . . 1. 𝑒 (𝑈 0, 𝑆 01 )

239
CCS ’22, November 7–11, 2022, Los Angeles, CA, USA. Leemon Baird, Pratyay Mukherjee, and Rohit Sinha

More importantly, due to hierarchical structure, we can also decrypt a right child which is a leaf, and a left child which branches out
the same ciphertext using id key 𝑆 0 = H (𝜖)𝛼 · H (0)𝛼 : further.
𝑒 (𝑔𝛼 , 𝑈 1 ) Such a tree (for 𝑇 = 15) is illustrated to our left. It is easy to
𝑉 · 𝑑 −1 = 𝑉 · see that such a structure indeed supports decryption keys of 𝑂 (1)
𝑒 (𝑈 0, 𝑆 0 )
sizes, in that all non-leaf nodes with epoch id 𝜏 0 < 𝜏 are contained
𝑒 (𝑔𝛼 , H (0)𝛾 )
= 𝑀 · 𝑒 (𝑔𝛼 , H (𝜖))𝛾 · within the sub-tree rooted at 𝜏. That would mean that an decryption
𝑒 (𝑔 , H (𝜖)𝛼 ) · 𝑒 (𝑔𝛾 , H (0)𝛼 )
𝛾
key could contain as few as two id-keys (two group elements).
=𝑀 However, this leads to a blow up in the ciphertext size, rendering
We emphasize that 𝑆𝜔 0 for any prefix 𝜔 0 of 𝜔 is sufficient to it to contain 𝑂 (𝑇 ) many group elements — intuitively, this occurs
decrypt a ciphertext locked to 𝜔. The intuition behind this scheme because each ciphertext for a node with path id 𝜔 must contain
is that the ciphertext for 𝜔 contains an element corresponding to Ω(|𝜔 |) group elements when using the above encryption technique
each prefix of 𝜔, and hence, can be thought of as encrypting to each with hierarchical decryption. In an unbalanced tree, a path id 𝜔
prefix of 𝜔 (or an epoch corresponding to each node from the root can have up to 𝑇 bits. Thus, such alternatives fail to achieve our
to the node for 𝜔). Therefore, when given a key corresponding to a efficiency requirements.
node for any prefix 𝜔 0  𝜔, we can ignore the remaining elements
of the ciphertext (i.e., beyond 𝑈 |𝜔 0 | = H (𝜔 | |𝜔 0 | )𝛾 ) and decrypt as
if the ciphertext was instead locked to id 𝜔 0 .
3.4.2 Thresholdizing
Remark 1 (Comparison with HIBE and IBE). Delegation means and CCA security.
that anyone with a key for id 𝜔 can derive a key for id 𝜔 0 . This is 15 Since our update
useful in the original motivation for HIBE, where a separate party can keys consist of a
assume full ability to derive keys in an identity subspace (e.g. a team single 𝑆 value, com-
within a larger organization) with respect to the assigned hierarchical 13 14 puted by exponen-
structure. However, in 𝔦-TiRE, all update keys are issued by the same tiating the lifetime
server, and access to the lifetime secret 𝑙𝑠𝑘 gives the server ability ... 12 secret key 𝑙𝑠𝑘 = 𝛼
to compute the key for any epoch/id — this is rather similar to IBE. on a known group
Therefore, in our case, it suffices to enforce the hierarchy efficiently element, it is sim-
without providing the ability to delegate. 3 ple to compute that
when the lifetime
Given the above scheme, it is straightforward to construct a
secret key is dis-
𝔦-TiRE scheme: for any epoch 𝜏, the decryption key consists of 1 2
tributed in a man-
𝑂 (log(𝑇 )) 𝑆 values, such that their subtrees cover all epochs be-
ner such that there
tween 1 and 𝜏. For instance, in our running example with𝑇 = 15, the Figure 3: Unbalanced id are 𝑛 servers hold-
key for epoch 4 is 𝐾4 = {𝑆 00, 𝑆 010 }, epoch 5 is 𝐾5 = {𝑆 00, 𝑆 010, 𝑆 011 }, tree ing a (𝑡, 𝑛)-threshold
and so on. The final epoch 15 is 𝐾15 = {𝑆𝜖 = H (𝜖)𝛼 }, which simply
secret sharing of
allows decryption of all ciphertexts encrypted with the 𝑙𝑝𝑘. Since
each 𝑆 value is a single group element, our update keys have 𝑂 (1) 𝑙𝑠𝑘. Basically, instead of computing values like H (𝑣)𝑙𝑠𝑘 (for some
size and the decryption keys have 𝑂 (log(𝑇 )) size (as opposed to value 𝑣) the 𝑖-th server now computes H (𝑣)𝑙𝑠𝑘𝑖 . The client, on
𝑂 (log2 (𝑇 )) in HIBE). We stress that hierarchical decryption is the receiving any 𝑡 such values, can combine them using Lagrange
key enabler here, as it allows us to prune 𝑆 values of children once reconstruction in the exponent to get the full update key. This
a parent node’s key can be emitted. step is similar to the threshold computation of PRF as proposed
in [2, 27], and it lets us handle up to 𝑡 − 1 server compromises.
Incremental Updates. When releasing keys sequentially in the In Section 6.2 we show the extension to the threshold setting. In
order of epochs, the post-order traversal ensures the following fact. fact, we consider security against malicious adversaries who can
The set of 𝑆 values for any decryption key 𝐾𝜏+1 includes all but one corrupt up to 𝑡 − 1 parties. In this setting it is crucial that a client
of the 𝑆 values from 𝐾𝜏 ; therefore, the server must release only one can verify the responses from each server and thus protect against
𝑆 value (one group element) as the update key in each epoch when malicious corruption – this is enabled by efficient non-interactive
computing keys incrementally. zero-knowledge proofs. In Section 6.3, we outline how to use a
3.4.1 Drawbacks of Unbalanced Trees. We have a hierarchical struc- variant of the Fujisaki-Okamoto [19] transformation (also used
ture of a balanced binary tree similar to BTE [9]. As explained above, in BTE [9]) to obtain CCA-security. Importantly, these two aug-
the standard IBE gives a linear structure which fails to achieve our mentations can be made independently of each other and hence
efficiency requirement of compact time-bound keys. Therefore, a one can easily combine them to obtain a CCA-secure construction
tree-like structure seems inevitable in order for an aggregate key (c.f. Corollary 1) which supports threshold key-generation and is
to cover a large number of epochs. However, as we have seen, an resilient against malicious attacks.
update key for epoch 𝜏 does not cover all keys corresponding to
epochs < 𝜏 — this leads to an decryption key size of 𝑂 (log(𝑇 )).
One might wonder whether this blow up can be avoided by instead
employing an unbalanced tree: each node in the tree would have 4 DEFINITIONS

240
𝔦-TiRE: Incremental Timed-Release Encryption CCS ’22, November 7–11, 2022, Los Angeles, CA, USA.

4.1 Incremental Timed-Release Encryption bit 𝑏 and sends A the encryption of 𝑚𝑏 locked to the epoch 𝜏 ★
(𝔦-TiRE) (selected by A earlier). After receiving the challenge ciphertext,
A submits another set of decryption and key generation queries,
Definition 1 (𝔦-TiRE). An incremental timed-release encryption
under the constraint that A is not requesting the decryption of the
(𝔦-TiRE) scheme is a tuple of algorithms (Setup, UKGen,DKGen,
challenge ciphertext nor is requesting a key for any epoch ≥ 𝜏 ★.
Enc, Dec) with the following syntax:
Finally, A outputs the guess bit 𝑏 0 and wins if 𝑏 0 = 𝑏.
− Setup(1𝜅 ,𝑇 ) → (𝑝𝑝, 𝑙𝑝𝑘, 𝑙𝑠𝑘) : On input the security parame-
ter 1𝜅 and the lifetime duration 𝑇 (in the number of epochs), Definition 2 (IND-TR-CPA/CCA). A 𝔦-TiRE := (Setup, UKGen,
Setup generates public parameters 𝑝𝑝 (to be used by all algo- UKCombine, Enc, Dec) scheme satisfies indistinguishability under
rithms that follow), a lifetime public key 𝑙𝑝𝑘, a lifetime secret chosen ciphertext attack if for all PPT adversaries A, there exists a
key 𝑙𝑠𝑘. negligible function negl such that the advantage of A is given by
− UKGen(𝑙𝑠𝑘, 𝜏) → 𝑢𝑘𝜏 : On input a lifetime secret key 𝑙𝑠𝑘 and  
Pr CCA𝔦-TiRE,A (1𝜅 , 0) = 1 −
an epoch 𝜏 ∈ {1, . . . ,𝑇 }, this algorithm outputs an update key  
𝑢𝑘𝜏 specific to the epoch 𝜏. Pr CCA𝔦-TiRE,A (1𝜅 , 1) = 1 ≤ negl(𝜅),
− DKGen(𝐾𝜏−1, 𝑢𝑘𝜏 ) → 𝐾𝜏 : On input a decryption key for
in a security game CCA which is defined below.
the (previous) epoch 𝜏 − 1 (𝜏 ∈ 1, . . . ,𝑇 ) and update key for
CCA𝔦-TiRE,A (1𝜅 , 𝑏):
(current) epoch 𝜏, this algorithms output the decryption key
𝐾𝜏 for the (current) epoch 𝜏. − Selection. A (1𝜅 ,𝑇 ) outputs an epoch 0 ≤ 𝜏 ★ ≤ 𝑇 .
− Enc(𝑙𝑝𝑘, 𝑚, 𝜏) → 𝑐 : encrypts a message 𝑚 “locked to” epoch − Initialization. Initialize 𝜏𝑚𝑎𝑥 := 0. Run Setup(1𝜅 ,𝑇 ) to get
𝜏, using the lifetime public key 𝑙𝑝𝑘, and outputs a ciphertext 𝑐. (𝑝𝑝, 𝑙𝑝𝑘, 𝑙𝑠𝑘, 𝐾0 ). Give (𝑝𝑝, 𝑙𝑝𝑘) to A.
− Dec(𝑙𝑝𝑘, 𝐾, 𝑐) → 𝑚/⊥ : deterministically decrypts the cipher- − Phase 1. A adaptively issues a polynomial number of queries,
text 𝑐 using a decryption key 𝐾, returning ⊥ on failure. each of one of two types:
Then, the following condition holds for any 𝜅,𝑇 ∈ N. Let (𝑝𝑝, 𝑙𝑝𝑘, 𝑙𝑠𝑘) − Pre-challenge decryption. In response to A’s decryption
← Setup(1𝜅 ,𝑇 ); then, for any message 𝑚, any two epochs 𝜏, 𝜏 0 ∈ query (Decrypt, 𝜏, 𝑐), C responds by generating the up-
[𝑇 ] for which 𝜏 ≤ 𝜏 0 , it satisfies: date key 𝐾𝜏 (by running UKGen many times as needed),
and using it to decrypt 𝑐.
− Pre-challenge key derivation. In response to A’s key deriva-
(i) correctness, that is there exists a negligible function negl(·) for
tion query (Derive, 𝜏), run UKGen with 𝑙𝑠𝑘 and 𝜏 and
which the following probability is at least 1 − negl(𝜅):
return the output to A. Update 𝜏𝑚𝑎𝑥 := 𝑚𝑎𝑥 (𝜏𝑚𝑎𝑥 , 𝜏).
h − Challenge. A outputs (Challenge, 𝑚 0, 𝑚 1 ) where |𝑚 0 | = |𝑚 1 |.
Pr 𝑚 ← Dec(𝑙𝑝𝑘, 𝐾𝜏 0 , 𝑐) |
Give 𝑐 ★ ← Enc(𝑝𝑝, 𝑚𝑏 , 𝜏 ★) to A. Output 1 if 𝜏𝑚𝑎𝑥 ≥ 𝜏 ★.
(𝑝𝑝, 𝑙𝑝𝑘, 𝑙𝑠𝑘, 𝐾0 ) ← Setup(1𝜅 ,𝑇 ); − Phase 2. A adaptively issues a polynomial number of queries,
𝑐 ← Enc(𝑙𝑝𝑘, 𝑚, 𝜏); each of one of two types:
− Post-challenge decryption. Repeat phase 1 but with the
𝑢𝑘 1 ← UKGen(𝑙𝑠𝑘, 1); 𝐾1 ← DKGen(𝐾0, 𝑢𝑘 1 );
following caveat. Only process A’s decryption query
.. (Decrypt, 𝜏, 𝑐) if 𝑐 ≠ 𝑐 ★, else return ⊥ to A.
. − Post-challenge key derivation. Repeat phase 1 but with the
i
𝑢𝑘𝜏 0 ← UKGen(𝑙𝑠𝑘, 𝜏 0 ); 𝐾𝜏 0 ← DKGen(𝐾𝜏 0 −1, 𝑢𝑘𝜏 0 ) following caveat: respond to A’s key derivation query
(Derive, 𝜏) only if 𝜏 < 𝜏 ★else return ⊥ to A.
where the probability is over the random coin tosses of the − Guess. Finally, A returns a guess 𝑏 0 . Output 𝑏 0 .
parties involved in Setup, UKGen, DKGen and Enc; When the attacker is prohibited from invoking the decryption or-
(ii) efficiency, that is both |𝐾𝜏 | and |𝑐 | are proportional to 𝑂 (log(𝑇 )). acle, the above definition achieves a weaker guarantee called in-
(iii) incrementality, that is |𝑢𝑘𝜏 | is of size 𝑂 (1). distinguishability under chosen plaintext attack or IND-TR-CPA.
We define a security game (IND-TR-CCA) for achieving cho- However, even in IND-TR-CPA, the adversary is given access to the
sen ciphertext security against a “selective" 𝔦-TiRE attacker who key-derivation oracle. The corresponding experiment is denoted
commits to the epoch to be attacked in advance (before the setup by CPA𝔦-TiRE,A .
phase). For that reason, we call this attack a selective-epoch attack.
Our definition is inspired by the security definitions for binary tree 4.2 Threshold 𝔦-TiRE
encrypion [9]. In a threshold 𝔦-TiRE scheme there are 𝑛 parties, each of which
First, the attacker A submits her target epoch 𝜏 ★. As is common holds a share of the lifetime secret key. Therefore, the algorithm
in CCA games, we allow A to perform a set of queries both before to generate the (partial) update keys is now run by a single party
and after sending the challenge plaintexts. To avoid trivial wins, using her share of the secret-key instead of the whole secret key.
the game checks whether A issued a key generation query for any Additionally, there’s a (public) combine algorithm which combines
epoch on or after 𝜏 ★, whose result can be used to decrypt for epoch the partial update keys to construct the entire update key. Apart
𝜏 ★. The challenger C responds to a polynomial number of decryp- from these changes, the syntax remains the same. We consider a 𝑡
tion and key generation queries by A, after which A submits a out of 𝑛 threshold setting where any 𝑡 (≤ 𝑛) partial update keys can
challenge pair of equal-length messages 𝑚 0 , 𝑚 1 ; C selects a random be combined to construct the entire update key, but no 𝑡 0 < 𝑡 partial

241
CCS ’22, November 7–11, 2022, Los Angeles, CA, USA. Leemon Baird, Pratyay Mukherjee, and Rohit Sinha

keys suffice. We provide the syntax below, and omit the formal − Guess. Finally, A returns a guess 𝑏 0 . Output 𝑏 0 .
correctness definition, which can be adjusted straightforwardly.
Remark 2 (Adaptive security). The definition achieves a stronger
The efficiency and incrementality conditions remain exactly the
adaptive security if the “selection” phase takes place after ’corruption”
same. For reader’s convenience we highlight the major changes in
but before the challenge phase. Our construction can be generically
syntax in 𝑏𝑙𝑢𝑒.
transformed to satisfy adaptive security by using complexity leverag-
A threshold incremental timed-release encryption (𝔦-TiRE) scheme
ing, that is by assuming sub-exponential security of the underlying
is a tuple of algorithms (Setup, PartUKGen, Combine, DKGen, Enc,
assumption.
Dec) where the syntax for algorithms DKGen, Enc, Dec remain un-
altered from the previous (non-threshold) definition. So we only 5 NOTATIONS AND PRIMITIVES
provide the syntax for the other algorithms below.
Notation. The set of all binary strings of length ℓ is denoted as
− Setup(1𝜅 ,𝑇 , 𝑛, 𝑡) → (𝑝𝑝, 𝑙𝑝𝑘, (𝑙𝑠𝑘 1, . . . 𝑙𝑠𝑘𝑛 )) : On input the
{0, 1}ℓ . Sometimes we denote 1ℓ or 0ℓ to denote strings of 1 and 0
security parameter 1𝜅 and the lifetime duration 𝑇 (in the num-
resp. repeated ℓ times. The output 𝑦 of a probabilistic algorithm 𝐴
ber of epochs), Setup generates public parameters 𝑝𝑝 (to be
on input 𝑥 is denoted by 𝑦 ← 𝐴(𝑥). For deterministic algorithms
used by all algorithms that follow), a life-time public key 𝑙𝑝𝑘,
sometimes we use 𝑦 := 𝐴(𝑥). Moreover, occasionally we need to
𝑛 shares of lifetime secret key (𝑙𝑠𝑘 1, . . . 𝑙𝑠𝑘𝑛 ). .
explicitly specify the randomness 𝑟 of a probabilistic algorithm,
− PartUKGen(𝑙𝑠𝑘 𝑗 , 𝜏) → 𝑢𝑘𝜏,𝑗 : On input a share of lifetime se-
which is denoted by 𝑦 := 𝐴(𝑥; 𝑟 ). For any bitstring 𝑤, we write 𝑤 |𝑖
cret key 𝑙𝑠𝑘 𝑗 and an epoch 𝜏 ∈ {1, . . . ,𝑇 }, this algorithm out-
to denote the first 𝑖 bits of 𝑤. We denote the empty string by 𝜖.
puts a partial update key 𝑢𝑘𝜏,𝑗 specific to the epoch 𝜏 and party
𝑗. 5.1 Bilinear Pairings
− UKCombine(𝑢𝑘𝜏,1, . . . , 𝑢𝑘𝜏,𝑡 ) → 𝑢𝑘𝜏 combines 𝑡 partial up-
date keys into a whole update key. Certain elliptic curves have an additional structure, called a bilinear
pairing. We use the following definitions from [7].
In the threshold setting the security definition also changes
accordingly. In particular, in a 𝑡 out of 𝑛 setting, the adversary, in Definition 3. Let G0 , G1 , G𝑇 be three cyclic groups of prime
addition to making CPA/CCA queries as elaborated in Definition 2, order 𝑞 where 𝑔0 ∈ G0 and 𝑔1 ∈ G1 are generators. A pairing is an
may also maliciously corrupt up to 𝑡 − 1 parties in the security efficiently computable function 𝑒 : G0 × G1 → G𝑇 satisfying the
game. We describe the changed security game below (with the following properties:
major changes highlighted in 𝑏𝑙𝑢𝑒 as well). − bilinear:
IND-ThTR-CCATh-𝔦-TiRE,A (1𝜅 , 𝑏): ∀𝑢, 𝑢 0 ∈ G0 . ∀𝑣 ∈ G1 . 𝑒 (𝑢 · 𝑢 0, 𝑣) = 𝑒 (𝑢, 𝑣) · 𝑒 (𝑢 0, 𝑣)
− Selection. A (1𝜅 ,𝑇 , 𝑛, 𝑡) 𝜏★
outputs an epoch 0 ≤ ≤ 𝑇. ∀𝑢 ∈ G0 . ∀𝑣, 𝑣 0 ∈ G1 . 𝑒 (𝑢, 𝑣 · 𝑣 0 ) = 𝑒 (𝑢, 𝑣) · 𝑒 (𝑢, 𝑣 0 )
− Initialization. Initialize 𝜏𝑚𝑎𝑥 := 0. Run Setup(1𝜅 ,𝑇 , 𝑛, 𝑡) to get
(𝑝𝑝, 𝑙𝑝𝑘, (𝑙𝑠𝑘 1, . . . , 𝑙𝑠𝑘𝑛 )). Give (𝑝𝑝, 𝑙𝑝𝑘) to A. − non-degenerate: 𝑔𝑇 =: 𝑒 (𝑔0, 𝑔1 ) is a generator of G𝑇 .
− Corruption. A outputs a set of corrupt party’s identities 𝐶 ⊆ Bilinearity implies the following property:
[𝑛] such that |𝐶 | < 𝑡. Give 𝑙𝑠𝑘𝑖 to A for all 𝑖 ∈ 𝐶. 𝑒 (𝑔𝛼0 , 𝑔1 ) = 𝑒 (𝑔0, 𝑔1 )𝛼 ·𝛽 = 𝑒 (𝑔0 , 𝑔𝛼1 )
𝛽 𝛽
− Phase 1. A adaptively issues a polynomial number of queries,
each of one of two types: The decision-BDH assumption states that given random ele-
ments 𝑔𝛼0 , 𝑔0 ∈ G0 and 𝑔𝛼1 ,𝑔1 ∈ G0 , the value 𝑒 (𝑔0, 𝑔1 )𝛼 ·𝛽 ·𝛾 ∈ G𝑇
𝛽 𝛾
− Pre-challenge decryption. In response to A’s decryption
query (Decrypt, 𝜏, 𝑐), C responds by generating the up- is indistinguishable from a random element in G𝑇 .
date key 𝐾𝜏 (by running UKGen and UKCombine many
Definition 4. Attack Game for Decision bilinear Diffie -
times in sequence as needed), and using it to decrypt 𝑐.
Hellman (DBDH) assumption: let 𝑒 : G0 × G1 → G𝑇 be a bilinear
− Pre-challenge key derivation. In response to A’s key deriva-
pairing where G0 , G1 , G𝑇 are cyclic groups of prime order 𝑞 with
tion query (Derive, 𝜏, 𝑗) where 𝑗 ∈ [𝑛]\𝐶, run PartUKGen
generators 𝑔0 ∈ G0 and 𝑔1 ∈ G1 . For a given adversary A, we define
with 𝑙𝑠𝑘 𝑗 and 𝜏 and return the output to A. Update 𝜏𝑚𝑎𝑥 :=
two experiments.
𝑚𝑎𝑥 (𝜏𝑚𝑎𝑥 , 𝜏) only if (Derive, 𝜏, 𝑗) is asked for at least
Experiment 𝑏 ∈ {0, 1}:
𝑡 − |𝐶 | different 𝑗 values — the challenger can track by
The challenger computes
storing the queries in a list 𝐿𝜏 for each 𝜏.
− Challenge. A outputs (Challenge, 𝑚 0, 𝑚 1 ) where |𝑚 0 | = |𝑚 1 |. − 𝛼, 𝛽, 𝛾, 𝛿 ← Z𝑞 .
𝛽 𝛾
Give 𝑐 ★ ← Enc(𝑝𝑝, 𝑚𝑏 , 𝜏 ★) to A. Output 1 if 𝜏𝑚𝑎𝑥 ≥ 𝜏 ★. − 𝑢 0 ← 𝑔𝛼0 , 𝑢 1 ← 𝑔𝛼1 , 𝑣 0 ← 𝑔0 , and 𝑤 1 ← 𝑔1
− Phase 2. A adaptively issues a polynomial number of queries, − 𝑧 (0) ← 𝑒 (𝑔0, 𝑔1 )𝛼 ·𝛽 ·𝛾 ∈ G𝑇 , 𝑧 (1) ← 𝑒 (𝑔0, 𝑔1 )𝛿 ∈ G𝑇
each of one of two types: The adversary is given (𝑢 0, 𝑢 1, 𝑣 0, 𝑤 1, 𝑧 (𝑏) ) outputs a bit 𝑏ˆ ∈ {0, 1}.
− Post-challenge decryption. Repeat phase 1 but with the Let 𝑊𝑏 be the event that A outputs 1 in experiment 𝑏. We define A’s
following caveat. Only process A’s decryption query advantage in solving the DBDH problem as:
(Decrypt, 𝜏, 𝑐) if 𝑐 ≠ 𝑐 ★, else return ⊥ to A.
− Post-challenge key derivation. Repeat phase 1 but with the
following caveat: respond to A’s key derivation query DBDHadv[A, e] =| 𝑃𝑟 [𝑊0 ] − 𝑃𝑟 [𝑊1 ] |
(Derive, 𝜏, 𝑗) only if either 𝜏 < 𝜏 ★or 𝐿𝜏 has < 𝑡 − |𝐶 | − 1 Definitions of additional primitives are provided in the full ver-
distinct 𝑗 values,else return ⊥ to A. sion [3].

242
𝔦-TiRE: Incremental Timed-Release Encryption CCS ’22, November 7–11, 2022, Los Angeles, CA, USA.

6 OUR CONSTRUCTIONS 6.1 CPA-secure 𝔦-TiRE

Our 𝔦-TiRE constructions, though inspired by the so-called Binary- Our construction follows the basic description from Sec. 3, and
tree encryption [9], are much simpler and more efficient. Our base it is provided in Fig. 4.9 While it works for both symmetric and
𝔦-TiRE construction (Fig. 4) satisfies CPA-security. In Sec. 6.2 we asymmetric pairings, the latter provides smaller sized groups G0
show how to augment this construction to a 𝑡 out of 𝑛 threshold (for the same level of security) (requiring fewer bits for encoding),
setting, secure against malicious corruption of up to 𝑡 − 1 par- and also more efficient group and pairing operations. Moreover, we
ties. Finally, we show how to achieve CCA-security in Sec. 6.3 by designed our construction so that the elements of the aggregated
a variant of Fujisaki-Okamoto transformation [19] analogous to key (i.e., the 𝑆 values) are elements of the smaller group G0 , while
Canetti et al. [9]. Since these two augmentations are orthogonal, the public key is an element of G1 . The ciphertext consists of |𝜔 |
it is possible to combine them easily to obtain a threshold 𝔦-TiRE elements of G0 (where 𝜔 = 𝑀 −1 (𝜏)), one element from G1 , and
construction satisfying CCA security against malicious corruption one element from target group GT ; since a majority of elements
(c.f. Corollary 1). of the ciphertext come from G0 , we get a further reduction in our
ciphertext size as well. The following theorem formally captures
this (a proof sketch is provided in the full version [3].
Doubly-labeled tree. We use a binary-tree in our construction
analogous to BTE [9]. Each node of the tree is labeled with a binary
Theorem 1. Under the decisional BDH assumption (DBDH in
bit-string as follows: let the depth of the tree be 𝑑; then the root is
Def. 4), there exists an 𝔦-TiRE scheme that satisfies IND-TR-CPA se-
labeled with the empty string 𝜖, its left child is labeled 0 and the right
curity as per Def. 2 in the random oracle model.
child is labeled 1; then the entire tree is labeled recursively such
that for each node with label 𝜔 ∈ {0, 1}∗ , its left child is labeled by
𝜔0 and right child by 𝜔1. Clearly, any node at level 𝛿 ∈ {1, . . . , 𝑑 } is 6.2 Threshold 𝔦-TiRE
labeled with a binary string of length 𝛿, which is equal to the length Our threshold mechanism is a straightforward adaptation of dis-
of the path from the root to this node. These labels of the nodes tributed psuedo-random function [27] for multiplicative prime-
are called primary labels. We refer to a node by its primary label. order groups. We first recall their mechanism. The PRF functional-
Additionally, each node is labeled with an integer (referred to as ity being computed collectively can be written as 𝑓𝛼 (𝑥) = H (𝑥)𝛼 ,
secondary labels), which is assigned through a post-order traversal where H : {0, 1}∗ → 𝐺 is a hash function (modeled as a random
on the tree. Recall that a post-ordered traversal assigns integer labels oracle) and the secret key is 𝛼 ∈ Z𝑝 . To distribute the evaluation
in an increasing sequence (that is 1, 2, . . .) in order left-right-root of 𝑓 , the secret key 𝛼 must be secret shared between the parties.
recursively. So, we can define a bijective mapping 𝑀 : {0, 1}∗ → N In the setup phase, a trusted party samples a master key 𝛼 ←$ Z𝑝
which maps the primary labels to the secondary labels. The inverse and uses Shamir’s secret sharing scheme [34] with a threshold 𝑡
mapping from the secondary to primary labels is denoted by 𝑀 −1 : to create 𝑛 shares 𝛼 1, . . . , 𝛼𝑛 of 𝛼. Share 𝛼𝑖 is given privately to the
N → {0, 1}∗ . This notation extends to tuples as (𝜏1, . . . , 𝜏ℓ ) := server 𝑖. We know that for any set of 𝑡 parties {𝑖 1, ..., 𝑖𝑡 } ⊆ [𝑛],
𝑀 (𝜔 1, . . . 𝜔 ℓ ). An example is given in Fig. 1. For the lack of a better there exists integers (i.e. Lagrange coefficients) 𝜆𝑖 1 , . . . , 𝜆𝑖𝑡 ∈ Z𝑝
name we shall refer to this structure by doubly-labeled tree.
Í
such that 𝑗 ∈ {𝑖 1 ,...,𝑖𝑡 } 𝛼 𝑗 𝜆 𝑗 = 𝛼. Therefore, it holds that

Í
Left-extended Family. For any node 𝜔 in the tree we define its 𝑓𝑠 (𝑥) = H (𝑥)𝛼 = H (𝑥) 𝑗 ∈{𝑖 1 ,...,𝑖𝑡 } 𝜆𝑗 𝛼 𝑗
left-extended (similarly right-extended family) family (denoted as Ö
𝜆𝑗
LEF(𝜔)) as the set which contains node 𝜔 plus all nodes that are left = H (𝑥)𝛼 𝑗
children of any node in the path from root to 𝜔, but do not belong to 𝑗 ∈ {𝑖 1 ,...,𝑖𝑡 }
the path themselves. For example, let 𝜔 = 0100, then the path from
root to 𝜔 is the ordered set (𝜖, 0, 01, 010, 0100). Among them, only which can be computed in a distributed manner, by having each
the node 0 has a left child, namely 00, which does not belong to the server 𝑖 produce 𝐻 (𝑥)𝛼 𝑗 . Coming back to our construction, we can
path. So LEF(0100) consists of nodes {00, 0100}. Similarly for 111, write 𝑆𝜔 as a combination of values produced by the above DPRF
we have LEF(111) = {0, 10, 110, 111}, because every intermediate 𝑓 , as follows:
node of the path (𝜖, 1, 11) has a left child that does not belong to
the path. It is worth noting that the size of LEF(𝜔) is equal to the |𝜔 |
Ö |𝜔 |
Ö
hamming weight of 𝜔 plus one. Equivalently LEF(𝜏) can be defined 𝑆𝜔 = H (𝜖)𝛼 · H (𝜔 | 𝑗 )𝛼 = 𝑓𝛼 (𝜖) · 𝑓𝛼 (𝜔 | 𝑗 )
as the same as LEF(𝜔) when 𝜏 = 𝑀 (𝜔). 𝑗=1 𝑗=1

Reconstruction from partial keys leverages the natural homomor-

Remark 3 (An important property). A very important property
phism. Consider any set of 𝑡 servers {𝑖 1, ..., 𝑖𝑡 } ⊆ [𝑛], who publish
is that for any 𝜏 ∈ {1, . . . ,𝑇 } if 𝜔 := 𝑀 −1 (𝜏) and 𝜔 0 := 𝑀 −1 (𝜏 + 1),
then the set difference LEF(𝜔 0 ) \ LEF(𝜔) = {𝜔 0 }. In other words all
but exactly one element, namely 𝜔 0 , of the set LEF(𝜔 0 ) is contained
in the set LEF(𝜔). This follows from the labeling through post-order 9 Fornotational convenience we assume that the UKCombine algorithm works with
traversal. Looking ahead, this fact ensures that the incrementality responses from the first 𝑡 servers, as opposed to any 𝑡 servers. The generalization is
property holds in our constructions. straightforward.

243
CCS ’22, November 7–11, 2022, Los Angeles, CA, USA. Leemon Baird, Pratyay Mukherjee, and Rohit Sinha

{𝑆𝜔,1, . . . , 𝑆𝜔,𝑡 } respectively. Then, we get: respect to these commitments, in lieu of simply proving correctness
𝜆𝑗 with respect to the public key 𝑙𝑝𝑘 – since the adversary is allowed
Ö Ö |𝜔 |
Ö
𝜆 to corrupt parties after obtaining the public parameters output by
­H (𝜖)𝛼 𝑗 · H (𝜔 |𝑘 )𝛼 𝑗 ®
𝑗
=
© ª
𝑆𝜔,𝑗
Setup, we make use of trapdoor commitments to let the simulator
𝑗 ∈ {𝑖 1 ,...,𝑖𝑡 } 𝑗 ∈ {𝑖 1 ,...,𝑖𝑡 } « 𝑘=1 ¬ open the commitments to different values using a trapdoor. Correct-
|𝜔 |
Ö © Ö ness follows from the extractability property of the NIZK scheme
= ­H (𝜖)𝛼 𝑗 𝜆 𝑗 · H (𝜔 |𝑘 )𝛼 𝑗 𝜆 𝑗 ®
ª
and the binding property of the commitment scheme.
𝑗 ∈ {𝑖 1 ,...,𝑖𝑡 } « 𝑘=1 ¬ Algorithms for our threshold 𝔦-TiRE scheme are described in
|𝜔
Ö© Ö| Figure 5 (formalized below in Theorem 2, a proof sketch is given
= H (𝜖)𝛼 · H (𝜔 |𝑘 )𝛼 𝑗 𝜆 𝑗 ®
ª
­ in the full version [3]), where the major changes from the previous
𝑘=1 « 𝑗 ∈ {𝑖 1 ,...,𝑖𝑡 } ¬ construction are highlighted in blue. The algorithms DKGen, Enc
|𝜔 |
Ö and Dec algorithms remain the same, so we omit mentioning them.
= H (𝜖)𝛼 · H (𝜔 |𝑘 )𝛼 = 𝑆𝜔 We need some additional ingredients:
𝑘=1 − A trapdoor commitment scheme (Setupcom, Commit).
− Another hash function H 0 : {0, 1}∗ → {0, 1}poly(𝜅) modeled
Ingredients as a random oracle (within the NIZK).
0 0
* Let G0 , G1 , and GT be multiplicative cyclic groups of prime order − A SS-NIZK := (Prove H , Verify H ).
𝑞 such that there exists a bilinear pairing 𝑒: G0 × G1 → GT that is
efficiently computable and non-degenerate. Let 𝑔0 ∈ G0 and 𝑔1 ∈ G1 Theorem 2. Under the decisional BDH assumption (DBDH in
be generators of the respective groups. Def. 4), there exists a threshold 𝔦-TiRE scheme that satisfies IND-TR-CPA
* Hash function H : {0, 1}∗ → G0 modeled as a random oracle security against malicious adversary in the random oracle model.
* A doubly-labeled tree Γ of depth 𝑑 such that 𝑇 = 2𝑑 − 1
CPA-secure 𝔦-TiRE Fig. 5 also defines our concrete instantiation of the trapdoor com-
− Setup(1𝜅 ,𝑇 ) → (𝑝𝑝, 𝑙𝑝𝑘, 𝑙𝑠𝑘) : mitment and NIZK proofs. We use Pedersen commitments (using
Choose uniform random 𝛼←$ 𝑍𝑞 . Then, set 𝑝𝑝 := independent generators 𝑔, ℎ ∈ G0 , whose discrete log is the trap-
(G0 , G1 , GT , 𝑒, 𝑞, H, Γ); 𝑙𝑠𝑘 := 𝛼; ; 𝑙𝑝𝑘 := 𝑔𝛼1 . door), and Schnorr-style proofs (more generally, sigma protocols
− UKGen(𝑙𝑠𝑘, 𝜏) → 𝑢𝑘𝜏 : made non-interactive using the Fiat-Shamir transformation in the
Parse 𝛼 := 𝑙𝑠𝑘. 𝜔 := 𝑀 −1 (𝜏).Then, compute: random oracle model. The Setup phase outputs a commitment 𝛾𝑖
 LetÎ 𝛼
• 𝑆𝜏 := H (𝜖) 𝑘=1 ℓ
H (𝜔 |𝑘 ) , where ℓ = |𝜔 | to each share 𝛼𝑖 using randomness 𝜌𝑖 .
Output 𝑢𝑘𝜏 := (𝜏, 𝑆𝜏 ).
Concretely, server 𝑖 proves the following statement for 𝜔:
− DKGen(𝐾𝜏 −1 , 𝑢𝑘𝜏 ) → 𝐾𝜏 : |𝜔 | 𝛼𝑖
Ö
• If 𝜏 = 1, then 𝐾1 := 𝑢𝑘 1 . 𝛼𝑖 𝜌𝑖
∃𝛼𝑖 , 𝜌𝑖 .𝛾𝑖 := 𝑔 ·ℎ ∧ 𝑆𝜔,𝑖 = ­H (𝜖) H (𝜔 | 𝑗 ) ®
© ª
• Otherwise, let (𝜏1 , 𝜏2 , . . . , 𝜏ℓ ) := 𝑀 (LEF(𝜏 − 1) ∩ LEF(𝜏)).
𝑗=1
Output 𝐾𝜏 := {𝑢𝑘𝜏1 , . . . 𝑢𝑘𝜏ℓ , 𝑢𝑘𝜏 }, « ¬
where {𝑢𝑘𝜏1 , . . . 𝑢𝑘𝜏ℓ } ⊆ 𝐾𝜏 −1 . We emphasize that our proof contains 3 field elements of 𝑍𝑞 (where
− Enc(𝑙𝑝𝑘, 𝑚, 𝜏) → 𝑐 : 𝑞 is the order of group G0 ), and its size is independent of the bit-
Let 𝜔 = 𝑀 −1 (𝜏). Sample uniform random 𝑟 ←$ 𝑍𝑞 and then com- length of 𝜔. The reason is that even though 𝑆𝜔,𝑖 is a product of |𝜔 |
pute: Î |𝜔 |
• 𝑐 1 := (𝜏, 𝑔𝑟1 , H (𝜔 | 1 ) 𝑟 , H (𝜔 | 2 ) 𝑟 , . . . , H (𝜔) 𝑟 );
terms, it can be written as 𝑥 𝛼𝑖 , where 𝑥 = H (𝜖) 𝑗=1 H (𝜔 | 𝑗 ) is one
• 𝑐 2 := 𝑚 · 𝑒 ( H (𝜖) 𝑟 , 𝑙𝑝𝑘); group element. Therefore, decryption keys are of size Θ(𝑙𝑜𝑔(𝑇 ))
Output 𝑐 = (𝑐 1 , 𝑐 2 ) even in the verifiable construction.
− Dec(𝑙𝑝𝑘, 𝐾, 𝑐) =: 𝑚/⊥ :
Parse 𝑐 as (𝑐 1 , 𝑐 2 ) and then: 6.3 CCA-security
• parse 𝑐 1 := (𝜏 0, 𝑅, ℎ 1 , . . . , ℎ ℓ );
Our CPA-secure construction achieves IND-TR-CCA-security by
• parse ( (𝜏1 , 𝑆 1 ), . . . , (𝜏𝜂+1 , 𝑆𝜂+1 )) := 𝐾.
• if 𝜏 0 > 𝜏𝜂+1 then output ⊥, else go to the next step;
using a variant of Fujisaki-Okamoto [19] transformation, similar to
• identify the unique (𝜏𝑖 , 𝑆𝑖 ) such that either 𝜏𝑖 = 𝜏 0 or 𝜔𝑖 := the BTE construction of Canetti et al. [9]. It is formalized below in
𝑀 −1 (𝜏𝑖 ) is a prefix of 𝜔 0 := 𝑀 −1 (𝜏 0 ); Theorem 3, a proof is sketched in the full version [3]. Remarkably
• set 𝑑 := 𝑒 (𝑆𝑖 , 𝑅) · ( 𝑖=1
Îℓ𝑖
𝑒 (ℎ𝑖 , 𝑙𝑝𝑘)) −1 where ℓ𝑖 := |𝜔𝑖 |; the only changes we need to make are in the Enc and Dec algo-
Output 𝑚 := 𝑐 2 · 𝑑 −1 rithms. Therefore, one can easily deploy these changes together
with the augmentation needed for threshold setting as discussed in
Figure 4: Our CPA-secure 𝔦-TiRE construction the previous subsection, thereby achieving a threshold construction
satisfying security against malicious corruption and IND-TR-CCA
Furthermore, in this setting to protect against malicious attacker security. To that end, we will need more ingredients:
each party needs to publish a NIZK proof (specifically, Schnorr’s − A symmetric-key encryption scheme ([Link], [Link]) that takes
proof [13, 33] via the Fiat-Shamir transform [18]) to prove the key’s {0, 1}𝜅 bit key.
validity. For provable security, we use trapdoor commitments to − Two hash functions H1 : GT → {0, 1}𝜅 and H2 : GT × {0, 1}∗ ×
commit to secret key shares of parties and generate NIZKs with {0, 1}∗ → 𝑍𝑞 modeled as random oracles.

244
𝔦-TiRE: Incremental Timed-Release Encryption CCS ’22, November 7–11, 2022, Los Angeles, CA, USA.

Threshold 𝔦-TiRE Combining Theorem 2 with the above theorem we get the fol-
− Setup(1𝜅 ,𝑇 , 𝑛, 𝑡 ) → (𝑝𝑝, 𝑙𝑝𝑘, (𝑙𝑠𝑘 1 , . . . , 𝑙𝑠𝑘𝑛 )) : Choose uniform lowing corollary immediately.
random 𝛼←$ 𝑍𝑞 . Let 𝑙𝑠𝑘 := 𝛼, 𝑙𝑝𝑘 := 𝑔𝛼 and run (𝛼 1 , . . . , 𝛼𝑛 ) := Corollary 1. Under the decisional BDH assumption (DBDH in
SSS𝑛,𝑡,𝑞 (𝛼). Run Setupcom (1𝜅 ) to get 𝑝𝑝 com . Sample uniform ran-
Def. 4), there exists a threshold 𝔦-TiRE scheme that satisfies IND-TR-CCA
dom 𝜌𝑖 and compute 𝛾𝑖 := Commit(𝑝𝑝 com , 𝛼𝑖 ; 𝜌𝑖 ). Then set: 𝑝𝑝 :=
(G0 , G1 , GT , 𝑒, 𝑞, H, Γ, , 𝑝𝑝 com , 𝛾 1 , . . . , 𝛾𝑛 ) and 𝑙𝑠𝑘𝑖 := (𝛼𝑖 , 𝜌𝑖 ).
security against malicious adversary in the random oracle model.
− PartUKGen(𝑙𝑠𝑘 𝑗 , 𝜏) → 𝑢𝑘𝜏,𝑗 : Parse 𝛼 𝑗 := 𝑙𝑠𝑘 𝑗 . Let 𝜔 := 𝑀 −1 (𝜏)
and ℓ = |𝜔 |, then
7 IMPLEMENTATION AND EVALUATION
• Compute 𝑤0 := H (𝜖), for 𝑘 ∈ {1, . . . , ℓ } 𝑤𝑘 := H (𝜔 |𝑘 ). We measure several attributes of our threshold 𝔦-TiRE scheme, in-
Îℓ
• Compute 𝑆𝜏,𝑗 := ( 𝑘=0 𝑤𝑘 ) 𝛼 𝑗 . cluding the size of decryption keys, size of ciphertexts, and the
H 0
• Run Prove for the language {∃ 𝛼, 𝜌 s.t. 𝑆𝜏,𝑗 = running time of the individual algorithms. We implemented it in
Îℓ
( 𝑘=0 𝑤𝑘 ) 𝛼 ∧ 𝛾 = Commit(𝑝𝑝 com , 𝛼; 𝜌) } with statement Go, using the BLS12-381 curve [8], and released it open source at
(𝑆𝜏,𝑗 , 𝑤0 , 𝑤1 , . . . , 𝑤ℓ , 𝛾 𝑗 ) and witness (𝛼 𝑗 , 𝜌 𝑗 ) to obtain a [Link] Benchmarks were run on a Mac-
proof 𝜋 𝑗 book Pro with a 2.6 GHz Intel Core i7 CPU and 16 GB RAM.
Output 𝑢𝑘𝜏,𝑗 := (𝜏, 𝑆𝜏,𝑗 , 𝜋 𝑗 ).
− UKCombine(𝑢𝑘𝜏,1 , . . . , 𝑢𝑘𝜏,𝑡 ) =: 𝑢𝑘𝜏 /⊥ : Parse each 𝑢𝑘𝜏,𝑗 := 7.1 Update Key Size
(𝜏, 𝑆𝜏,𝑗 , 𝜋 𝑗 ), then compute 𝑤0 := H (𝜖), for 𝑘 ∈ {1, . . . , ℓ } and
𝑤𝑘 := H (𝜔 |𝑘 ) where 𝜔 = 𝑀 −1 (𝜏). Then, first check whether Due to incremental updates, a server only publishes an update key
proof 𝜋 𝑗 verifies with respect to the statements (𝑆𝜏,𝑗 , 𝜏, 𝛾 𝑗 ), if not comprising 1 group element from G0 , which is of length 48 bytes,
then output ⊥, otherwise use Lagrange coefficients 𝜆 𝑗 ∈ 𝑍𝑞 to when serialized in binary form. Contrast this with [30], where
𝜆
compute 𝑆𝜏 := 𝑗 ∈ [𝑡 ] 𝑆𝜏,𝑗𝑗 . Output 𝑢𝑘𝜏 := (𝜏, 𝑆𝜏 ).
Î update keys are of 𝑙𝑜𝑔(𝑇 ) size: 0.48 KB, 0.72 KB, 0.96 KB, and 1.44
KB for 𝑇 = 210, 215, 220, 230 , respectively.
Concrete instantiation
− Setupcom (1𝜅 ): Sample generator ℎ ←$ G0 , and output 𝑝𝑝 com =:
7.2 Decryption Key Size
(𝑔0 , ℎ).
− Commit(𝑝𝑝 com = (𝑔, ℎ), 𝛼; 𝜌): output 𝑔𝛼 · ℎ 𝜌 We measure the size of the decryption key (produced by DKGen) as
0
− ProveH ( {∃ 𝛼, 𝜌. 𝑆 = ( 𝑘=0
Îℓ𝑖 a function of the lifetime 𝑇 . This metric is indicative of the on-chain
𝑤𝑘 ) 𝛼 ∧𝛾 = 𝑔𝛼 · ℎ 𝜌 } with statement
(𝑆, 𝑤0 , 𝑤1 , . . . , 𝑤ℓ𝑖 , 𝛾 ) and witness (𝛼, 𝜌): storage required by the smart contract to maintain the decryption
𝑤𝑘 . Sample 𝑣, 𝑣0 ←$ 𝑍𝑝 and set 𝑡 := 𝑤 𝑣 , 𝑡 0 :=
Îℓ𝑖
Let 𝑤 = 𝑘=0 key.
0
𝑔 · ℎ . Compute 𝑐 := H 0 (𝑔, ℎ, 𝑆, 𝑤0 , 𝑤1 , . . . , 𝑤ℓ𝑖 , 𝛾, 𝑡, 𝑡 0 ). Let 𝑢 :=
𝑣 𝑣 Recall that the size of the key 𝐾𝜏 for epoch 𝜏 < 𝑇 depends on
𝑣 − 𝑐 · 𝑠 and 𝑢 0 := 𝑣0 − 𝑐 · 𝑟 . Output proof 𝜋 = (𝑐, 𝑢, 𝑢 0 ). the number of tree nodes required to cover the range of epochs
− Verify(𝜋 = (𝑐, 𝑢, 𝑢 0 )) for statement (𝑆, 𝑤0 , 𝑤1 , . . . , 𝑤ℓ𝑖 , 𝛾 ): from 1 to 𝜏. For that reason, we get a range of key sizes within a
0
Compute 𝑡 := 𝑤𝑢 · 𝑆 𝑐 , 𝑡𝑖0 := 𝑔𝑢 · ℎ𝑢 · 𝛾 𝑐 and output 1 iff 𝑐 = lifetime 𝑇 . We expect 𝑙𝑜𝑔(𝑇 ) number of nodes in the worst case,
0 0
H (𝑔, ℎ, 𝑆, 𝑤0 , 𝑤1 , . . . , 𝑤ℓ𝑖 , 𝛾, 𝑡, 𝑡 ). and each node has an associated 𝑆 value in 𝐾𝜏 – each 𝑆 value is
an element of G0 of length 48 bytes. So, we collect key sizes for
Figure 5: Changes for the Threshold 𝔦-TiRE construction the entire range of epochs in a lifetime, and report the max and
the average statistics (which unsurprisingly ends up being half of
the max size). We also report the key size for both maliciously-
secure and semi-honest settings, with the distinction being that
We describe the changed Enc 0 and Dec 0 algorithms below. Those the maliciously-secure scheme has a NIZK proof (containing 3 field
are generic extensions of the algorithms Enc and Dec respectively elements of 32 bytes each) alongside each 𝑆 value.
from the base construction. The results are in Table 1. Our keys grow logarithmically in 𝑇 ,
1. Enc 0 (𝑙𝑝𝑘, 𝑚, 𝜏) → 𝑐: Let 𝜔 := 𝑀 −1 (𝜏). Then: and it is under 2 KB in the semi-honest and 5 KB in the malicious
− Sample uniform random 𝑠 ←$ GT . setting for a lifetime of 230 epochs. On average, our keys are half
− Compute 𝑐 1 ← Enc(𝑙𝑝𝑘, 𝑠, 𝜏; H2 (𝑠, 𝜔, 𝑚)). the size of those in [30] (denoted TSE in Table 1, though no imple-
− Compute 𝑐 2 ← [Link](H1 (𝑠), 𝑚) where H1 (𝑠) is used as the mentation is reported in their work), as their keys are always of
key. size 𝑙𝑜𝑔(𝑇 ). Had we used an IBE-based scheme, such as [12, 15],
− Set 𝑐 := (𝜏, 𝑐 1, 𝑐 2 ). decryption keys would have grown linearly with the number of
2. Dec 0 (𝑙𝑝𝑘, 𝐾, 𝑐) → 𝑚/⊥: Parse (𝜏, 𝑐 2, 𝑐 2 ) := 𝑐 and let 𝜔 := 𝑀 −1 (𝜏) epochs 𝑇 , and they end up being prohibitively large (in the order
then: of gigabytes) for even modest sized lifetimes.
− Compute 𝑠 := Dec(𝑐 1 ).
− Use H1 (𝑠) as the key to decrypt 𝑚 := [Link](H1 (𝑠), 𝑐 2 ).
7.3 Ciphertext Size
− Then, re-encrypt with H2 (𝑠, 𝜔, 𝑚) to check whether 𝑐 1 = We report the ciphertext size, which can be treated as the overhead
Enc(𝑙𝑝𝑘, 𝑠, 𝜏; H2 (𝑠, 𝜔, 𝑚)). If the check succeeds then output from ciphertext expansion when encrypting a binary string in our
𝑚 otherwise output ⊥. CCA construction (see Sec. 6.3).
Similar to the case with key size, different epochs produce cipher-
Theorem 3. Under the decisional BDH assumption (DBDH in texts of varying size, depending on the position of the node in the
Def. 4), there exists an 𝔦-TiRE scheme that satisfies IND-TR-CCA tree – recall that for path-based identity 𝜔 of the node labelled 𝜏, a
security as per Def. 2 in the random oracle model. ciphertext locked to epoch 𝜏 will have |𝜔 | group elements from G0

245
CCS ’22, November 7–11, 2022, Los Angeles, CA, USA. Leemon Baird, Pratyay Mukherjee, and Rohit Sinha

Semi-Honest Malicious
epochs stat
𝔦 -TiRE 𝔦 -TiRE 15
TSE TSE
14
max 0.480 0.480 1.6 - 13

Running Time (millisec)

210 avg 0.240 0.480 0.8 - 12
11
max 0.720 0.720 2.4 - 10
215 avg 0.360 0.720 1.2 - 9
8
max 0.960 0.960 3.2 - 7
220 avg 0.480 0.960 1.6 - 6
5
max 1.440 1.440 4.8 -
4
230 avg 0.720 1.440 2.4 - 3
Table 1: Key size (in KBs) 2^10 2^15 2^20 2^30
Number of epochs in lifetime

(a) Running Time of Enc

Semi-Honest
9 Malicious 56
8 51
46

Running Time (millisec)

7 41
Latency (millisec)

6 36
5 31
26
4 21
3 16
11
2
6
1 1
2^10 2^15 2^20 2^30
0 Number of epochs in lifetime
2^10 2^15 2^20 2^30
Number of epochs in lifetime
(b) Running Time of Dec
Figure 6: Running Time of UKGen
Figure 7: Distribution of Running Time of Enc and Dec oper-
ations
(48 bytes each), one element from G1 (96 bytes), and one element
from G𝑇 (384 bytes). Table 2 reports the min, max, and average
statistics over the ciphertext sizes across the lifetime, for various
values of 𝑇 . One can observe that ciphertexts grow logarithmically in a key nor compute its child in future). Consider Fig. 1; in epoch
in the lifetime 𝑇 . 4 for instance, we remove 𝑆 000 and 𝑆 001 from the cache, and add
𝑆 01 and 𝑆 010 . We still compute Θ(𝑙𝑜𝑔(𝑇 )) new 𝑆 values in the worst
epochs 210 215 220 230 case (e.g. in epoch 8, where fresh 𝑆 values must be computed along
min 0.576 0.576 0.576 0.576 the entire path from the root). However, observe that intermediate
max 1.088 1.408 1.728 2.368 nodes never compute fresh 𝑆 values, since a leaf node would have
avg 1.025 1.344 1.664 2.304 already computed the necessary 𝑆 values. In general, we find a
Table 2: Ciphertext Expansion (in KBs) significant drop in the required computation across a large fraction
of the nodes. Note that the cache never exceeds the tree’s height,
so it is at most 64 * d𝑙𝑜𝑔(𝑇 )e bytes (2 KB for 230 epochs).

Running Time of Key Generation. Fig. 6 shows the distribution of

7.4 Running Time running times. Most UKGen evaluations terminate under 1 ms due
We report the running times of the UKGen algorithm run by the to caching, but we can observe the Θ(𝑙𝑜𝑔(𝑇 )) worst case running
server, and the Enc and Dec algorithms run by the client (using a time in the outliers. The quantiles grow with 𝑇 in the malicious
whole aggregate key). execution as the NIZK proofs do not benefit from caching in the
same manner as the 𝑆 values.
7.4.1 Key Generation.
7.4.2 Running Time of Encryption and Decryption. Like other met-
Caching Optimization. We implement an obvious caching opti-
rics, the running time for each Enc and Dec operation depends
mization when running UKGen for consecutive epochs. For any
on the depth of the node – ciphertext includes a group element
node with id 𝜔, 𝑆𝜔 is defined recursively as 𝑆𝜔 0 · H (𝜔)𝛼 (where 𝜔 0
for each node along the path from the root node – so we plot the
denotes the parent of 𝜔). So, if we have cached the 𝑆 value of any
distribution attained from 106 trials, with each trial operating over
parent node, we can avoid recomputing several group operations.
a random epoch. The results are shown in Fig. 7.
To that end, we maintain a cache comprising 𝑆 values for each node
along the path from the root node to 𝜔, and remove 𝑆 values of
nodes that are no longer needed (because we will never output it 8 A GENERIC SCHEME USING ANY IBE

246
𝔦-TiRE: Incremental Timed-Release Encryption CCS ’22, November 7–11, 2022, Los Angeles, CA, USA.

In this section we describe an alternative scheme that satisfies our − Otherwise output ⊥.
definition (Def 1). The scheme is based generically on any IBE The security of this scheme mostly follows from the security of the
scheme. We start by defining an IBE scheme. An IBE scheme is underlying IBE scheme. Correctness follows from the post-order
a tuple of algorithms ([Link], [Link], [Link], [Link]) structure of the doubly-labeled keys. Instantiating the above with
with the following syntax: Boneh-Franklin [5] we get a scheme which satisfies the efficiency
− [Link](1𝜅 ) → (𝑝𝑝, 𝑚𝑝𝑘, 𝑚𝑠𝑘) : This algorithm outputs a and incrementality requirements, albeit with ciphertexts that are
public parameter 𝑝𝑝 (to be inputted into all algorithms that at least twice as large as our scheme. For completeness we put the
follow), a master public key 𝑚𝑝𝑘 and a master secret-key 𝑚𝑠𝑘. Boneh-Franklin scheme in the full version [3].
− [Link](𝑚𝑠𝑘, 𝑖𝑑) → 𝑑𝑘𝑖𝑑 : This algorithm generates a In this framework, our scheme can also be viewed as an optimized
decryption key 𝑑𝑘𝑖𝑑 for an identity 𝑖𝑑 using the master secret- version of this scheme, in that the randomness of a number of
key 𝑚𝑠𝑘. ciphertexts are reused for different identities and the message is
− [Link](𝑚𝑝𝑘, 𝑚, 𝑖𝑑) → 𝑐𝑖𝑑 : This algorithm encrypts a mes- “masked” with a fixed identity. Nevertheless, structuring identity
sage 𝑚 with respect to an identity 𝑖𝑑 using the master public through a post-order traversal ensures that the final scheme is
key 𝑚𝑝𝑘 to produce a ciphertext 𝑐𝑖𝑑 . somewhat between a full HIBE and a plain IBE. Also note that, this
− [Link](𝑚𝑝𝑘, 𝑐𝑖𝑑 , 𝑑𝑘𝑖𝑑 ) =: 𝑚 : This algorithm deterministi- scheme can be easily thresholdized in a same way as our scheme.
cally decrypts the ciphertext 𝑐𝑖𝑑 with a decryption key 𝑑𝑘𝑖𝑑
both corresponding to the same identity 𝑖𝑑, and returns a 9 CONCLUSION
message 𝑚. We put forward a new timed-release encryption scheme with a
The corresponding 𝔦-TiRE scheme would basically use the same crucial incrementality property – this enables applications such as
doubly-leveled tree, and associates each node with secondary label performing sealed bid auction over blockchains. Both the decryp-
𝜏 (which denotes the time) with identity 𝑖𝑑 := 𝜏. However, each tion key and the ciphertext size of our scheme are proportional to
ciphertext at primary label 𝜔 = 𝑀 −1 (𝜏) consists of |𝜔 | = log(𝑇 ) log(𝑇 ), where 𝑇 is the lifetime of the system. Moreover, we show
many IBE ciphertexts 𝑐𝜖 , 𝑐 𝜔 | 1 , . . . , of the message, where 𝑐𝜖 is the how to strengthen our scheme to a threshold setting, which is
IBE ciphertext encrypted with respect to the identity 𝑀 (𝜖) at the secure against malicious adversary and also provides CCA-security.
root of the tree , 𝑐 𝜔 | 1 is with respect to the identity 𝑀 (𝜔 | 1 ) and
so on. The decryption keys are constructed in a way which is
very similar to our scheme (Figure 4); that is each decryption key
𝐾𝜏 consists of all IBE decryption keys (in our scheme these are
replaced by update keys) corresponding to all nodes in LEF(𝜏). This
ensures that for any ciphertext corresponding to a specific 𝜏 and
any decryption key corresponding to 𝜏 0 ≥ 𝜏, there is at least one
IBE decryption key which can decrypt an IBE ciphertext included
in the final ciphertext – this enables the decryption. We formally
describe the scheme below:
− Setup(1𝜅 ,𝑇 ) → (𝑝𝑝, 𝑙𝑝𝑘, 𝑙𝑠𝑘) :
− Run [Link](1𝜅 ) → (𝑝𝑝, 𝑚𝑝𝑘, 𝑚𝑠𝑘).
− Output (𝑝𝑝, 𝑙𝑝𝑘 := 𝑚𝑝𝑘, 𝑙𝑠𝑘 :=𝑚𝑠𝑘).
− UKGen(𝑙𝑠𝑘, 𝜏) → 𝑢𝑘𝜏 :
− Parse 𝑚𝑠𝑘 := 𝑙𝑠𝑘.
− Run 𝑑𝑘𝜏 ← [Link](𝑚𝑠𝑘, 𝜏).
− Output 𝑢𝑘𝜏 := (𝜏, 𝑑𝑘𝜏 ).
− DKGen(𝐾𝜏−1, 𝑢𝑘𝜏 ) → 𝐾𝜏 :
− − If 𝜏 = 1, then 𝐾1 := 𝑢𝑘 1 .
− Otherwise, let (𝜏1, 𝜏2, . . . , 𝜏ℓ ) := 𝑀 (LEF(𝜏 − 1) ∩ LEF(𝜏)).
Output 𝐾𝜏 := {𝑢𝑘𝜏1 , . . . 𝑢𝑘𝜏ℓ , 𝑢𝑘𝜏 },
where {𝑢𝑘𝜏1 , . . . 𝑢𝑘𝜏ℓ } ⊆ 𝐾𝜏−1 .
− Enc(𝑙𝑝𝑘, 𝑚, 𝜏) → 𝑐 :
− Let 𝜔 := 𝑀 −1 (𝜏); 𝑚𝑝𝑘 := 𝑙𝑝𝑘.
− Let ℓ = |𝜔 | and for all 𝑖 ∈ [ℓ], 𝜏𝑖 := 𝑀 (𝜔 |𝑖 ).
− Output 𝑐 := (𝑐𝜏1 , . . . , 𝑐𝜏ℓ ) where ℓ := |𝜔 | and for each
𝑖 ∈ [ℓ], 𝑐𝜏𝑖 ← [Link](𝑚𝑝𝑘, 𝜏𝑖 )).
− Dec(𝑙𝑝𝑘, 𝐾, 𝑐) → 𝑚/⊥ :
− Let 𝑚𝑝𝑘 := 𝑙𝑝𝑘; (𝑑𝑘𝜏1 , . . . 𝑑𝑘𝜏ℓ ) := 𝐾.
− (𝑐𝜏10 , . . . , 𝑐𝜏 0 ) := 𝑐.
𝜆
− If there exists a pair (𝑑𝑘𝜏𝑖 , 𝑐𝜏 0𝑗 ) for which 𝜏𝑖 = 𝜏 𝑗0 , then
output 𝑚 := [Link](𝑚𝑝𝑘, 𝑐𝜏𝑖 , 𝑑𝑘𝜏 0𝑗 )

247
CCS ’22, November 7–11, 2022, Los Angeles, CA, USA. Leemon Baird, Pratyay Mukherjee, and Rohit Sinha

REFERENCES [Link]
[1] [n.d.]. Now Released (Fall 2010): Autobiography of Mark Twain, Volume 1. [18] Amos Fiat and Adi Shamir. 1987. How to Prove Yourself: Practical Solutions
[Link] to Identification and Signature Problems. In CRYPTO’86 (LNCS, Vol. 263), An-
[2] Shashank Agrawal, Payman Mohassel, Pratyay Mukherjee, and Peter Rindal. drew M. Odlyzko (Ed.). Springer, Heidelberg, 186–194. [Link]
2018. DiSE: Distributed Symmetric-key Encryption. In ACM CCS 2018, David Lie, 3-540-47721-7_12
Mohammad Mannan, Michael Backes, and XiaoFeng Wang (Eds.). ACM Press, [19] Eiichiro Fujisaki and Tatsuaki Okamoto. 1999. Secure Integration of Asym-
1993–2010. [Link] metric and Symmetric Encryption Schemes. In CRYPTO’99 (LNCS, Vol. 1666),
[3] Leemon Baird, Pratyay Mukherjee, and Rohit Sinha. 2021. i-TiRE: Incremen- Michael J. Wiener (Ed.). Springer, Heidelberg, 537–554. [Link]
tal Timed-Release Encryption or How to use Timed-Release Encryption on 3-540-48405-1_34
Blockchains? Cryptology ePrint Archive, Paper 2021/800. [Link] [20] Rosario Gennaro, Stanislaw Jarecki, Hugo Krawczyk, and Tal Rabin. 2007. Secure
1145/3548606.3560704 [Link] Distributed Key Generation for Discrete-Log Based Cryptosystems. Journal of
[4] Dan Boneh, Xavier Boyen, and Eu-Jin Goh. 2005. Hierarchical Identity Based Cryptology 20, 1 (Jan. 2007), 51–83. [Link]
Encryption with Constant Size Ciphertext. In EUROCRYPT 2005 (LNCS, Vol. 3494), [21] Craig Gentry and Alice Silverberg. 2002. Hierarchical ID-Based Cryptography.
Ronald Cramer (Ed.). Springer, Heidelberg, 440–456. [Link] In ASIACRYPT 2002 (LNCS, Vol. 2501), Yuliang Zheng (Ed.). Springer, Heidelberg,
11426639_26 548–566. [Link]
[5] Dan Boneh and Matthew K. Franklin. 2001. Identity-Based Encryption from [22] Jeremy Horwitz and Ben Lynn. 2002. Toward Hierarchical Identity-Based En-
the Weil Pairing. In CRYPTO 2001 (LNCS, Vol. 2139), Joe Kilian (Ed.). Springer, cryption. In EUROCRYPT 2002 (LNCS, Vol. 2332), Lars R. Knudsen (Ed.). Springer,
Heidelberg, 213–229. [Link] Heidelberg, 466–481. [Link]
[6] Dan Boneh, Ben Lynn, and Hovav Shacham. 2001. Short Signatures from the [23] Kohei Kasamatsu, Takahiro Matsuda, Keita Emura, Nuttapong Attrapadung,
Weil Pairing. In ASIACRYPT 2001 (LNCS, Vol. 2248), Colin Boyd (Ed.). Springer, Goichiro Hanaoka, and Hideki Imai. 2016. Time-specific encryption from forward-
Heidelberg, 514–532. [Link] secure encryption: generic and direct constructions. Int. J. Inf. Sec. 15, 5 (2016),
549–571. [Link]
[7] Dan Boneh and Victor Shoup. 2020. A Graduate Course in Applied Cryptography.
[24] Jia Liu, Tibor Jager, Saqib A. Kakvi, and Bogdan Warinschi. 2018. How to Build
Manuscript. [Link]
Time-Lock Encryption. Des. Codes Cryptography 86, 11 (Nov. 2018), 2549–2586.
[8] Sean Bowe. 2017. BLS12-381: New zk-SNARK elliptic curve construction. https:
[Link]
//[Link]/blog/new-snark-curve/.
[25] Mohammad Mahmoody, Tal Moran, and Salil P. Vadhan. 2011. Time-Lock Puzzles
[9] Ran Canetti, Shai Halevi, and Jonathan Katz. 2003. A Forward-Secure Public-
in the Random Oracle Model. In CRYPTO 2011 (LNCS, Vol. 6841), Phillip Rogaway
Key Encryption Scheme. In EUROCRYPT 2003 (LNCS, Vol. 2656), Eli Biham (Ed.).
(Ed.). Springer, Heidelberg, 39–50. [Link]
Springer, Heidelberg, 255–271. [Link]
[26] T.C. May. 2021. Timed-release crypto. [Link]
[10] Julien Cathalo, Benoît Libert, and Jean-Jacques Quisquater. 2005. Efficient and
[Link].
Non-interactive Timed-Release Encryption. In ICICS 05 (LNCS, Vol. 3783), Sihan
[27] Moni Naor, Benny Pinkas, and Omer Reingold. 1999. Distributed Pseudo-random
Qing, Wenbo Mao, Javier López, and Guilin Wang (Eds.). Springer, Heidelberg,
Functions and KDCs. In EUROCRYPT’99 (LNCS, Vol. 1592), Jacques Stern (Ed.).
291–303.
Springer, Heidelberg, 327–346. [Link]
[11] Konstantinos Chalkias, Dimitrios Hristu-Varsakelis, and George Stephanides.
[28] Shutter Network. 2021. Shutter – In-Depth Explanation of
2007. Improved Anonymous Timed-Release Encryption. In ESORICS 2007 (LNCS,
How We Prevent Front Running. [Link]
Vol. 4734), Joachim Biskup and Javier López (Eds.). Springer, Heidelberg, 311–326.
shutter-in-depth-explanation-of-how-we-prevent-frontrunning/.
[Link]
[29] Jianting Ning, Hung Dang, Ruomu Hou, and Ee-Chien Chang. 2018. Keeping
[12] Aldar C. F. Chan and Ian F. Blake. 2005. Scalable, Server-Passive, User-Anonymous
Time-Release Secrets through Smart Contracts. Cryptology ePrint Archive,
Timed Release Cryptography. In Proceedings of the 25th IEEE International Con-
Report 2018/1166. [Link]
ference on Distributed Computing Systems (ICDCS ’05). IEEE Computer Society,
[30] Kenneth G. Paterson and Elizabeth A. Quaglia. 2010. Time-Specific Encryption.
USA, 504–513. [Link]
In SCN 10 (LNCS, Vol. 6280), Juan A. Garay and Roberto De Prisco (Eds.). Springer,
[13] David Chaum and Hans Van Antwerpen. 1990. Undeniable Signatures. In
Heidelberg, 1–16. [Link]
CRYPTO’89 (LNCS, Vol. 435), Gilles Brassard (Ed.). Springer, Heidelberg, 212–
[31] Michael O Rabin and Christopher Thorpe. 2006. Time-lapse cryptography. (2006).
216. [Link]
[32] Ronald L. Rivest, Adi Shamir, and David A. Wagner. 1996. Time-lock puzzles and
[14] Jung Hee Cheon, Nicholas Hopper, Yongdae Kim, and Ivan Osipkov. 2006. Timed-
timed-release crypto. Technical Report.
Release and Key-Insulated Public Key Encryption. In FC 2006 (LNCS, Vol. 4107),
[33] Claus-Peter Schnorr. 1990. Efficient Identification and Signatures for Smart
Giovanni Di Crescenzo and Avi Rubin (Eds.). Springer, Heidelberg, 191–205.
Cards. In CRYPTO’89 (LNCS, Vol. 435), Gilles Brassard (Ed.). Springer, Heidelberg,
[15] Jung Hee Cheon, Nicholas Hopper, Yongdae Kim, and Ivan Osipkov. 2008. Prov-
239–252. [Link]
ably Secure Timed-Release Public Key Encryption. ACM Trans. Inf. Syst. Secur.
[34] Adi Shamir. 1979. How to Share a Secret. Communications of the Association for
11, 2, Article 4 (May 2008), 44 pages. [Link]
Computing Machinery 22, 11 (Nov. 1979), 612–613.
[16] Gwangbae Choi and Serge Vaudenay. 2019. Timed-Release Encryption With
[35] Michael Specter, Sunoo Park, and Matthew Green. 2021. KeyForge: Mitigating
Master Time Bound Key (Extended). J. Wirel. Mob. Networks Ubiquitous Comput.
Email Breaches with Forward-Forgeable Signatures.
Dependable Appl. 10, 4 (2019), 88–108. [Link]
[36] Gavin Wood et al. 2014. Ethereum: A secure decentralised generalised transaction
31.088
ledger. Ethereum project yellow paper 151, 2014 (2014), 1–32.
[17] Giovanni Di Crescenzo, Rafail Ostrovsky, and Sivaramakrishnan Rajagopalan.
1999. Conditional Oblivious Transfer and Timed-Release Encryption. In EU-
ROCRYPT’99 (LNCS, Vol. 1592), Jacques Stern (Ed.). Springer, Heidelberg, 74–89.

248