I spent some time reading the Jager paper so I share my intuitive understanding of the time-lock encryption using the witness encryption here. Witness encryption is just a building block in the paper but I think putting it into the context helps the understanding.
The paper presents a way to encrypt a message "to the future", i.e., in a way it can be decrypted only after a certain amount of time passes. It is not feasible to decrypt the ciphertext before the deadline. The reference clock is instantiated as a Bitcoin blockchain as a new block is added (roughly) every 10 minutes. The deadline is thus specified in the length of the blockchain X, from some starting block $\beta$ (can be the block $B_0$, i.e., genesis block or a random, already-generated block).
After the blockchain reaches the length X, the blockchain is a witness $w$ of the length X. Thus the length $X$ and witness $w$ belong to the NP-relation $R$, i.e., $(1^X, w) \in R_{\beta, \delta}$, where $\beta$ is the starting block and $\delta$ is a mining difficulty (specifies the zero-hash prefix, regularly adapted by BTC network so one block is found each 10 minutes, depends on the BTC network hash-rate/computational power).
NP-relation
The $R_{\beta, \delta}$ is said to be NP as there exists a polynomial-time algorithm $A_{R_{\beta, \delta}}$ that can verify that $(1^X, w)$ belong to the $R_{\beta, \delta}$.
The algorithm in fact already exists in the BTC software as it verifies that the block hash-chain matches the given difficulty and that the blockchain is valid (in BTC sense).
It is also computationally expensive to find a $w^\prime$, such that $w^\prime$ is a valid witness, i.e., $(1^X, w^\prime) \in R_{\beta, \delta}$, because the attacker would have to solve BTC puzzles with given difficulty over $X$ times. This equals generating an alternative blockchain and it should not be possible to do it faster than BTC network. The hardness of generating another witness backs the security of the scheme.
Reductions
One can convert the NP algorithm checking the witness $w$ validity to a Boolean formula in Conjunctive-Normal-Form (CNF) $C$, such that $C(x, w_1) = 1 \iff A_{R_{\beta, \delta}}(x,w) = 1$. The witness $w_1$ is a formula assignment which satisfies the formula $C$. The $w_1$ can be computed from the blockchain witness $w$ by a polynomial reduction. Reduction that converts $A_{R_{\beta, \delta}}$ to $C$ also defines reduction from $w$ to $w_1$. Note it still holds that finding another $w_1$ satisfying the formula $C$ is a hard problem (CNF-SAT).
In the high level the reduction flow is the following: $A_{R_{\beta, \delta}}$ $\rightarrow$ CNF-SAT $\rightarrow$ 3-CNF-SAT $\rightarrow$ Subset-sum problem. The reductions also specify witness reductions $w \rightarrow w_1 \rightarrow w_2 \rightarrow w_3$ (subset-sum witness).
Note that BTC time relation $R_{\beta, \delta}$ is just an example of NP relation that is used for witness encryption. We could use another NP relation and choose the associated decision algorithm to build witness encryption such that any witness in the NP relation decrypts the ciphertexts in the system. NP relations could also be traveling salesman problem, integer factorization problem, shortest vector problem, etc...
Subset-sum problem
The Subset-sum problem is another hard problem which is core of the witness encryption used in the paper. Once we fix $A_{R_{\beta, \delta}}$ (system setup, done once), we can create an instance of the Subset-sum problem with given $\mathbf{s}$, i.e., a target sum-vector with $d$ elements and the $\Delta = \{(\mathbf{v}_i : l_i)\}_{i \in I}$, a multi-set of d-sized vectors $\mathbf{v}_i$ of positive integers with $l_i$ occurrences in the multi-set $\Delta$ such that $(l_i+1) \mathbf{v}_i \nleq \mathbf{s}$ and $\mathbf{v}_i$ are pairwise-distinct. The question is to find a witness $w_3=\{(b_i)\}_{i \in I}$ such that $\sum_{i \in I} b_i \mathbf{v}_i = \mathbf{s}$, with $b_i$ positive integers and $b_i \leq l_i$.
Encryption
Encrypting is easy, we don't need a witness $w_3$ to encrypt the message $m$ (we cannot know it ahead in the BTC example). Choose a random vector $\alpha = (\alpha_1, \dots, \alpha_d)$.
The ciphertext $c := (\text{subset-sum-params}, \{ g_{\mathbf{v}_i}^{\alpha^{\mathbf{v}_i}}\}, m \cdot g_\mathbf{s}^{\alpha^\mathbf{s}})$, where $g_\mathbf{u}$ is a generator of the group $\mathbb{G}_\mathbf{u}$ specified by the subset-sum problem instance and the multilinear-pairing function (below). The $g_\mathbf{s}^{\alpha^\mathbf{s}}$ is then the encryption key $K$.
In order to decrypt the $c$ to obtain message $m$ an user has to find a witness $w_3$ which helps him to reconstruct the key $K$ by solving the subset-sum problem ($w_3$ is a solution), from the elements $\{ g_{\mathbf{v}_i}^{\alpha^{\mathbf{v}_i}}\}$.
Note that information on the blockchain relation $R$ is encoded in the subset-problem instance (and thus also in the $\mathbf{s}$). Also, note that any witness $w_3^\prime$ that satisfies the subset-sum problem, i.e., $(1^x, w_3^\prime) \in R$, can be used to construct a decryption key $K$. There can be many witnesses and in the BTC example, it is any valid blockchain of the length $X$.
Decryption
A multilinear $s$-mapping $e_{\mathbf{u},\mathbf{v}}(g_\mathbf{u}^a, g_\mathbf{v}^b)=g^{ab}_{\mathbf{u}+\mathbf{v}}$ is used to compute the decryption key from the witness $w_3$, where $e_{\mathbf{u},\mathbf{v}}$ maps $\mathbb{G}_\mathbf{u} \times \mathbb{G}_\mathbf{v}$ into $\mathbb{G}_{\mathbf{u}+\mathbf{v}}$, with $\mathbf{u}+\mathbf{v} \leq \mathbf{s}$.
Let have $w_3 = (b_1, \dots, b_{|I|})$, then the decryption key
$K := e(\underbrace{g_{\mathbf{v}_1}^{\alpha^\mathbf{v}_1}, \dots, g_{\mathbf{v}_1}^{\alpha^\mathbf{v}_1}}_{b_1}, \underbrace{g_{\mathbf{v}_2}^{\alpha^\mathbf{v}_2}, \dots, g_{\mathbf{v}_2}^{\alpha^\mathbf{v}_2}}_{b_2}, \dots, \underbrace{g_{\mathbf{v}_{|I|}}^{\alpha^\mathbf{v}_{|I|}}, \dots, g_{\mathbf{v}_{|I|}}^{\alpha^\mathbf{v}_{|I|}}}_{b_{|I|}})$.
If $\sum_{i \in I}b_i\mathbf{v}_i = \mathbf{s}$ then $K = g_{\sum_{i \in I}b_i\mathbf{v}_i}^{\alpha^{\sum_{i \in I}b_i\mathbf{v}_i}} = g_\mathbf{s}^{\alpha^\mathbf{s}}$ from
the subset-sum problem definition and multilinearity of the $e$.
Closing remarks
Simplifications
In order to make this as short as possible (I may failed here, heh), I made a few simplifications, e.g., I am not going too deep into SNARK application to reduce the multilinearity. I also do not specify how is the multilinear map instantiated and computed, it is enough to consider it as a blackbox in this context (open problem, some approximations exist).
Also note that this scheme is far from practical. In the basic setting (without SNARK), we would have to check SHA-256 hash of the Bitcoin blocks in the boolean-circuit / CNF-SAT which would require transforming SHA-256 verification into the form it was not designed to be fast. This could yield a formula with millions of elements (just internal compression function takes thousands of gates in the arithmetic circuits). Usage of SNARKs helps with this obstacle, but still expressing SNARK verifier in CNF results in huge formulas.
Please take this with a grain of salt and correct me if I am wrong somewhere.
Length encoding / X parameter
In this simplification, it is not obvious how the blockchain length $x$ is encoded in the subset-sum problem. From the definitions the witness encryption $c := \text{WE.Enc}(1^X, m)$, i.e., the ciphertext $c$ is tied to the length $x$. If $c$ would not be tied to the $x$ then an attacker could wait 1 block and present $(1^1, w_3^\prime) \in R_{\beta,\delta}$ and $w_3^\prime$ could be thus used to construct the key $K$. It is not clear how is the length embedded in the Construction 1 in the section 6.1, as it defines $\text{WE.Enc}(1^\lambda, x, m)$, where $x$ is an instance of the subset-sum problem here, $\lambda$ if often a security parameter. So it seems that subset-sum problem has to define the length $x$.
The length encoding lies (as I understood it) in the SNARK trick.
The paper uses SNARKs (zero-knowledge proof system) to reduce multilinear complexity in a quite tricky way. They do not directly use the relation $R_{\beta,\delta}$ (as the complexity is related to the formula size and witness size), but they use SNARKs to prove&verify that $(1^x,w) \in R_{\beta,\delta}$.
SNARKs overview
Time-lock Encryption TL.Enc$(1^\lambda, \tau, m)$, where $\tau$ is a time parameter:
run SNARK generator to get $(ek, vk) \leftarrow \text{SNARK.Gen}(1^\lambda, 1^\tau)$ (i.e., proving key $ek$ and verificatin key $vk$).
Let $x^*(w) = \text{SNARK.Verify}(vk, 1^\tau, w)$ (i.e., SNARK verifier function, precomputed with $vk, 1^\tau$) and define a relation $R^* = \{(x^*, w^*) : x^*(w^*) = 1\}$. Compute $ct \leftarrow \text{WE.Enc}(1^\lambda, x^*, m)$ for the relation $R*$.
Output $c := (\tau, ek, ct)$.
Time-Lock Decryption TL.Dec$(w,c)$, where $c = (\tau, ek, ct)$:
- Run the SNARK prover to get $\pi \leftarrow \text{SNARK.Prove}(ek, 1^\tau, w)$
- Let $w^* = \pi$. Compute and output WE.Dec$(w^*, ct)$.
The witness encryption WE encrypts with an instance/statement $x^*$, which is the verification procedure of a SNARK proof. The proof $\pi$ is a tuple of group elements of a fixed size. Thus the computing time of the $x^*$ is also constant.
Witness $w^*$ is then a SNARK proof that $(1^\tau, w) \in R_{\beta, \delta}$.
The blockchain length $\tau$ is encoded in the SNARK.Verify procedure $x^*$, which is used as a statement for the relation $R^*$ in the witness encryption.
As I understood it, the SNARK Proof verify procedure $x^*$ is reduced to the subset-sum problem. The SNARK generated by the encrypting party incorporates the instance/statement $1^\tau$ for the $R$ relation to the system, thus the length $x$ is fixed per $R^*$.
