Digital Signatures

In chapter 9 we used PRFs for message authentication. If the correct MAC tag $F(\key,\ptxt)$ accompanied a message $\ptxt$, this was “proof” that someone who knows the key has vouched for $\ptxt$. MACs are symmetric-key primitives: The same key is used both to generate and verify a tag.

This chapter introduces digital signatures, the asymmetric-key equivalent of MACs. A private key is used to produce the authentication tag, and a public key is used to verify it.

16.1. Security definitions for digital signatures

In a digital signature scheme, a user first generates a key pair using a key generation algorithm. Only someone who holds the private key can generate authentication tags, now called signatures, of messages. But anyone who holds the public key can verify that the signature is authentic. Thus, verification must happen differently than for MACs. With a MAC (at least MACs as we have defined them), a tag is verified by simply recomputing the “correct” tag and comparing it to the given one. We cannot expect digital signatures to be verified in the same way, since the person performing verification cannot compute correct signatures on their own. Thus, a signature scheme must specify an additional, explicit verification algorithm.

Security: The intuitive guarantee of a signature scheme is that only the private-key holder can produce valid signatures. Even an adversary who is allowed to see many examples of valid signatures, on messages of its choice, and who knows the public key, cannot produce any new examples of valid signatures.

We formalize security in a similar way to MACs (section 9.4). We imagine an attack scenario in which the adversary can request signatures on chosen messages from the victim. Of course these signatures will always be valid. A forgery is any message-signature pair $(\ptxt,S)$ produced by the adversary, which is valid but different than those it received from the victim/library. We say that forgeries should be hard to generate by requiring that the verification algorithm is indistinguishable from an algorithm that simply responds $\myfalse$ to any $(\ptxt,S)$ not generated by the victim. The true verification algorithm differs from this “fake” one only in the case of a forgery, so if they are indistinguishable then it must be hard to produce a forgery.

Another difference with MACs is that we treated MACs and PRFs as synonyms. Thus, every MAC that we have seen has tags that are not only hard to forge but are pseudorandom. But pseudorandom signatures are simply not possible. A valid signature cannot be pseudorandom because it satisfies a very conspicuous property: It causes the $\Verify$ algorithm to output $\mytrue$! A uniformly chosen value would rarely have this property (otherwise, one could easily generate forgeries by sampling signatures uniformly).

Because of this distinction, the security definition for signature schemes does not require signatures to look pseudorandom. Both libraries produce and output truly valid signatures; we do not have a “real” library generating valid signatures and a “random” library generating fake, uniformly chosen ones.

16.2. Signatures from RSA

In RSA-based cryptography, only someone who holds the private key can compute $e$-th roots. On the other hand, anyone with the public key can verify that $X$ is an $e$-th root of $Y$ by checking $X^e = Y$. These properties seem perfectly matched for digital signatures. Can we make a signature scheme in which signatures are $e$-th roots?

16.2.1. Textbook RSA signatures

Textbook RSA is the signature scheme you get by letting the $e$-th root of $\ptxt$ be its signature.

Unfortunately, just like the case of encryption, the textbook RSA approach is insecure.

First, textbook RSA signatures are malleable, thanks to their algebraic structure. Given two textbook RSA signatures $S_1 = (\ptxt_1)^d$ and $S_2 = (\ptxt_2)^d$, it's not hard to see that $S_1 \cdot S_2$ is a valid signature for the message $\ptxt_1 \cdot \ptxt_2$. In a secure signature scheme, it should not be possible to guess a valid signature on $\ptxt_1 \cdot \ptxt_2$ after seeing valid signatures of $\ptxt_1$ and $\ptxt_2$.

Second, we must be more precise when claiming that “it's hard to compute $e$-th roots mod $\nmod$.” In fact, it is easy to find a pair $(S,\ptxt)$ where $S$ is the $e$-th root of $\ptxt$: Simply choose $S$ first, and then set $\ptxt = S^e \pct \nmod$. In the context of textbook RSA signatures, this corresponds to an attack in which the adversary chooses the signature first and then computes the message that matches. Even though the attack results in a signature on a message that the adversary can't control, it's something that should not be possible in a secure digital signature scheme.

To be more precise about computing $e$-th roots mod $\nmod$, we should say that “it's hard to compute $e$-th roots mod $\nmod$, of values that you didn't choose.” In textbook RSA signatures, the $\ptxt$ values can be chosen by the adversary, which means they can be chosen with a known $e$-th root. To fix textbook RSA signatures, the signer should not compute the $e$-th root of $\ptxt$ directly, but rather the $e$-th root of something that nobody can directly control.

16.2.2. RSA-PSS

In the RSA-PSS scheme, the signer computes $e$-th roots of a hash of $\ptxt$, the idea being that it should be hard to choose $\ptxt$ that hashes to any favorable value. The signature scheme can be proven secure if the hash function is modeled as a random oracle. The proof is made significantly easier if the signer computes an $e$-th root, not of $\ro(\ptxt)$ but of $\ro(\ptxt \|R)$, where $R$ is chosen uniformly for each signature (and included in the output).

One downside to RSA-PSS is that it requires a hash function that acts like a random oracle, with outputs in $\Z_\nmod$. It's not immediately clear how to instantiate such a hash function in the real world. However, construction 16.2.2 is merely a simplification of the “real” RSA-PSS standard, which uses a more conventional random oracle with outputs in $\bits^\secpar$.

16.2.3. Self-reducibility

In the RSA assumption (definition 15.2.5), one RSA key pair is associated with just a single challenge value $Y$. Finding the $e$-th root of this value $Y$ is hard. On the other hand, the security of RSA-PSS relies on the difficulty of finding the $e$-th root of any one of many random oracle outputs. Hence, one important step in the proof is to bridge this gap between one target for $e$-th roots and many targets.

In this section, we prove that finding the $e$-th root of any one of many uniformly chosen targets is hard. This is a general result, not tied to the use of RSA for signatures. The proof uses the following idea: Given any RSA target value $Y^*$, there is a way to generate many new values $Y_i$ such that:

• Each $Y_i$ is uniformly distributed in $\Z^*_\nmod$, and

• Given the $e$-th root of any of these $Y_i$ values, we can easily compute an $e$-th root of $Y^*$.

Thus, from a single target value $Y^*$ we get many target values $Y_i$ which follow the correct distribution, and whose $e$-th roots are exactly as hard to find as $Y^*$'s. This kind of transformation, from one $Y^*$ to many $Y_i$'s, is called a random self-reduction, and it is a useful concept throughout cryptography.

Let's now see the idea behind this self-reduction, illustrated for a single $Y$ value. Given a target value $Y^*$, how can we choose $Y$ such that an $e$-th root of $Y$ helps us learn the $e$-th root of $Y^*$?

We can now prove the multi-target security of the RSA assumption:

16.2.4. Security proof for RSA-PSS

We now have the tools to prove security of RSA-PSS.

A note on programming: Programming the random oracle is a powerful proof technique, and one of the main features of the random oracle that critics disparage. Indeed, imagine trying to carry out the steps of our security proof where $\ro$ is a public, plain-model hash function like SHA-3. You will get stuck when the proof reaches a hybrid that tries to “choose” $\textsf{SHA3}(\ptxt\|R)$ to have a known $e$-th root. Of course, the library cannot do this, because $\textsf{SHA3}(\ptxt\|R)$ simply is whatever it is, and the library cannot pretend it to be something else.

16.2.5. A rant

If you want to make a cryptographer genuinely angry, casually mention that signing is just encrypting with the private key, or that verifying a signature is just decrypting with the public key.

16.2.6. Looking Ahead

RSA-based signatures have great historical significance, and their security proof demonstrates important new provable security techniques. However, RSA signatures are expensive and large, because RSA requires huge moduli. One might wonder whether, as in the case of key agreement, it is possible to achieve something better by using elliptic curve cryptography, where the underlying values are significantly smaller than RSA group elements. Later in section 19.4 we discuss an alternative approach for signatures—called Schnorr signatures—that can be based on elliptic curves and therefore lead to much smaller signatures. For most applications, Schnorr signatures (and closely related constructions) are a better choice than RSA signatures.

16.3. Common signature idioms

16.3.1. Hash-then-sign

In RSA-PSS, the signer starts by computing a hash of the message being signed. It is important to the security proof that the hash function is a random oracle. But the idea of hashing before signing is a standard general principle. In practice, one can always sign a hash of a long message rather than the message itself.

Signing a hash authenticates that the signer vouches for that hash. And if the hash function is collision-resistant, there can be only one known message that produces that hash, so the signature of its hash authenticates that (unique) message. Both the signer and verifier must be able to evaluate this hash function. Thus, one should use a standard collision-resistant hash function with public salt, and not a UHF.

We can formalize the security of signing a hash, with the following construction:

16.3.2. Certificates and chains

When Alice wants to connect to joyofcryptography.com, how does her browser ensure that she is talking to the real joyofcryptography.com and not some impostor website that advocates for ECB mode? Cryptography does not directly involve things like website domain names; instead, it involves public keys and private keys. Users need a way to bridge the gap between cryptographic public keys and human-understandable identities, like domain names. On the internet, this gap is bridged by certificates, a common application of digital signatures. Certificates help answer the question, what is the correct public key for this particular domain name? Later in chapter 18 we discuss how to actually use a public key to cryptographically authenticate a website connection.

There are billions of websites, so web browsers cannot simply ship with a database that maps every domain name to a public keys. Instead, browsers delegate the responsibility to a small number of certificate authorities (CA). The job of a CA is to issue certificates, which are essentially digital signatures on messages of the form “a28f1eb9... is a valid public key for joyofcryptography.com.”

Certificates are issued in the following process:

• A website operator contacts a CA and presents a public key $\pk$. The operator proves that (1) it controls a domain name, usually by adding a special string to its DNS record or to a publicly accessible webpage, and (2) that it controls the public key, usually by signing a challenge message sampled uniformly by the CA.

• If the CA is satisfied, it will generate a certificate signed under its (the CA's) public key.

This process is frequently automated, and some larger website hosting companies are also CAs themselves, making the process easier.

Later, when a browser connects to the website:

• The webserver presents its public key $\pk$, and its certificate.

• The browser verifies that the certificate lists $\pk$ and the expected domain name, and that it is signed by a known CA. Each browser ships with a small collection of known CA public keys; at the time of writing, my browser recognizes 74 CAs.

• Assuming all of these checks pass, the browser attempts to authenticate the server as the holder of the private key corresponding to $\pk$. Authentication happens using the techniques described in chapter 18.

Signature/Certificate Chains: A certificate is just a signature vouching for someone else's public key. That someone else could be a website, but it could also be another CA. In practice, root CAs sign the public keys of other CAs, called intermediate CAs, who then sign public keys of websites. This arrangement helps relieve load on the root CAs.

For example, the certificate for joyofcryptography.com is signed by Cloudflare's CA, whose CA certificate is signed by Baltimore CyberTrust, a root CA whose public key is in your browser's trust store. When your browser connects to joyofcryptography.com, the server presents its public key along with this certificate chain. Your browser validates the entire chain from root to website.

Trusting CAs: Any certificate authority that your browser trusts can issue a certificate for any domain name. Thus, CAs have the power to completely and silently impersonate any website on the internet. The decision to include a CA in a browser's trusted list is therefore not taken lightly, and geopolitical forces are often at play. (The EU recently proposed controversial legislation that would force browsers to trust CAs operated by EU governments.)

A rogue CA who issues improper certificates can have a disastrous impact on the internet. While rogue certificates cannot be completely eliminated, modern web browsers include some features to detect them. For example, a website operator can instruct browsers to accept certificates only from specific CAs, using a special DNS record called certificate authority authorization (CAA). In a project called certificate transparency, CAs are required to publicly announce all certificates they issue; some browsers periodically check certificates they have received against this public list. A domain name owner can also check the list for unexpected certificates for their domain. If a website presents a certificate that is not in this public list, the offending CA's reputation can be damaged.

Exercises

1. Let $\Sigma$ be a digital signature scheme, and define the new scheme $\Sigma'$ as follows:

   $\Sigma'.\KeyGen = \Sigma.\KeyGen$

   $\Sigma'.\Sign(\sk,\ptxt)$:

   $S := \Sigma.\Sign(\sk,\ptxt)$

   return $S \| M$

   $\Sigma'.\Verify(\pk,M,S)$:

   parse $S' \| M' := S$

   if $M' \ne M$: return $\myfalse$ ($\star$)

   return $\Sigma.\Verify(\pk,M,S')$

   1. Prove that $\Sigma'$ is secure, if $\Sigma$ is. This example shows that digital signatures do not need to hide the message, since signatures in $\Sigma'$ include the message in the clear.

   2. Show that if the line marked $\star$ is removed, then the resulting scheme is not secure.

2. Let $\Sigma$ be a digital signature scheme, and define the new scheme $\Sigma'$ as follows:

   $\begin{aligned} \Sigma'.\KeyGen &= \Sigma.\KeyGen \\ \Sigma'.\M &= \Sigma.\M = \bits^n \end{aligned}$

   $\Sigma'.\Sign(\sk,\ptxt)$:

   $V \gets \bits^n$

   $S_1 := \Sigma.\Sign(\sk,V)$

   $S_2 := \Sigma.\Sign(\sk,V \oplus \ptxt)$

   return $(V,S_1,S_2)$

   $\Sigma'.\Verify\bigl(\pk,\ptxt,(V,S_1,S_2)\bigr)$:

   return $\Sigma.\Verify(\pk,V,S_1)$ and $\Sigma.\Verify(\pk,V\oplus \ptxt,S_2)$

   Show that $\Sigma'$ is not a secure digital signature scheme.

3. In this exercise, $\ro$ is a random oracle with input and output length $\secpar$. We use the following shorthand notation:

   $\ro^{(i)}(X) = \underbrace{\ro(\ro(\cdots\ro}_{i \text{ times}}(X)\cdots).$

   Consider the following signature scheme:

   $\begin{aligned} \M &= \{0, \ldots, 127\} \end{aligned}$

   $\KeyGen(\,)$:

   $\sk_1 \gets \bits^\secpar$

   $\sk_2 \gets \bits^\secpar$

   $\pk_1 := \ro^{(127)}(\sk_1)$

   $\pk_2 := \ro^{(127)}(\sk_2)$

   return $\bigl( (\pk_1,\pk_2), (\sk_1,\sk_2) \bigr)$

   $\Sign\bigl( (\sk_1,\sk_2), \ptxt \bigr)$:

   // $\ptxt \in \{0, \ldots, 127\}$

   $S_1 := \ro^{(\ptxt)}(\sk_1)$

   $S_2 := \ro^{(127-\ptxt)}(\sk_2)$

   return $(S_1, S_2)$

   $\Verify\bigl( (\pk_1, \pk_2), \ptxt, (S_1, S_2) \bigr)$:

   $X_1 := \ro^{(127-\ptxt)}(S_1)$

   $X_2 := \ro^{(\ptxt)}(S_2)$

   return $[X_1 == \pk_1$ and $X_2 == \pk_2]$

   1. Show that the scheme satisfies correctness.

   2. $\star$ Consider a variant of the security definition for digital signatures, in which the adversary can receive only one signature (e.g., $\sigsign$ returns an error if called more than once). Prove that the scheme is secure with respect to this modified definition.

   3. Show that the scheme is not secure with respect to the standard definition for digital signatures.

4. In section 15.3 we proved that RSA-KEM is a secure one-message KEM. Then we used the general result that a secure one-message KEM is a secure many-message KEM. But the latter proof involves a sequence of $q$ hybrids, where $q$ is the number of ciphertexts encrypted by the adversary. Each hybrid adds a negligible loss to the proof's concrete security. Overall, these two proofs show that breaking security of RSA-KEM is at most $q$ times easier than breaking the RSA assumption.

   Give a direct proof that RSA-KEM is a secure many-message KEM (in the random oracle model), where the sequence of hybrids applies the RSA assumption only once. Thus, in terms of concrete security, breaking security of RSA-KEM is no easier than breaking the RSA assumption.

5. Show a random self-reduction for the discrete logarithm problem. Let $\G$ be a cyclic group with order $n$ and generator $g$.

   Given any $X^* \in \G$, show how to generate a new value $X \in \G$ such that:

   • $X$ is uniformly distributed in $\G$.

   • Given the discrete logarithm of $X$, there is an efficient way to compute the discrete logarithm of $X^*$.

6. h This exercise develops a random self-reduction for the DDH problem. Let $\G$ be a cyclic group with order $n$ and generator $g$. Consider the following algorithm:

   $\textsf{SelfReduce}(A^*,B^*,C^*)$:

   $r \gets \Z_\nmod$

   $s \gets \Z_\nmod$

   $t \gets \Z_\nmod$

   $A := (A^*)^t \cdot g^r$

   $B := B^* \cdot g^s$

   $C := (A^*)^{st} (B^*)^r (C^*)^t \cdot g^{rs}$

   return $(A,B,C)$

   We will say that $(A,B,C)$ are a Diffie-Hellman triple if $A = g^a$, $B= g^b$, and $C=g^{ab}$. The DDH assumption says that it is hard to distinguish the uniform distribution over Diffie-Hellman triples from the uniform distribution over all triples in $\G^3$.

   1. Show that if $(A^*,B^*,C^*)$ is a Diffie-Hellman triple, then the output of $\textsf{SelfReduce}(A^*,B^*,C^*)$ is uniformly distributed over Diffie-Hellman triples. Make no assumptions about the distribution on $(A^*, B^*, C^*)$. The output of $\textsf{SelfReduce}$ is induced by its random choices, not a distribution over its inputs.

   2. Show that if $(A^*,B^*,C^*)$ is not a Diffie-Hellman triple, then the output of $\textsf{SelfReduce}(A^*,B^*,C^*)$ is uniformly distributed over $\G^3$.

   3. The DDH assumption (definition 13.2.3) generates only a single triple in its lifetime. Prove that if the DDH assumption is true, then the following two libraries (which generate many independent triples) are indistinguishable:

      $\lib{ddh-real*}^\G$

      $\subname{ddh.get}^*(\,)$:

      $a \gets \Z_\nmod$

      $b \gets \Z_\nmod$

      return $(g^a, g^b, g^{ab})$

      $\indist$

      $\lib{ddh-rand*}$

      $\subname{ddh.get}^*(\,)$:

      $a \gets \Z_\nmod$

      $b \gets \Z_\nmod$

      $c \gets \Z_\nmod$

      return $(g^a, g^b, g^c)$

      Your proof should invoke the standard DDH assumption only once!

   For part (a), reason about all cyclic group elements in terms of their discrete logs. For part (b), a non-Diffie-Hellman triple has the form $(g^a, g^b, g^{ab+d})$ where $d\ne 0$.

7. Below is a variant of RSA-PSS which does not use a random oracle. Assume that the RSA modulus has $k$ bits, message $\ptxt$ has $k - \secpar$ bits, and $\ptxt \| R$ is interpreted as a $k$-bit integer in the usual way.

   $\KeyGen = \RSA.\KeyGen$

   $\Sign( \sk=(\nmod,d), \ptxt )$:

   $R \gets \bits^\secpar$

   $S := (\ptxt \| R)^d \pct \nmod$

   return $(R,S)$

   $\Verify( \pk=(\nmod,e), \ptxt, (R,S) )$:

   if $S^e \equiv_\nmod (\ptxt \| R)$:

   return $\mytrue$

   else: return $\myfalse$

   Show that the scheme is not secure.

8. h Exponentiation mod $\nmod$ can be sped up using the CRT method (section 15.4), if the factorization of $\nmod$ is known. In RSA-PSS signatures, it is the signer who knows this factorization. Using the CRT optimization, the signer will compute $\ro(M\|R)^d$ mod $\pmod$, then mod $\qmod$, and finally reconstruct the result $S$ mod $\pmod\qmod$.

   Suppose a victim has signed a known message $M$ in this way, resulting in signature $(R,S)$. However, their CPU experienced a glitch while computing $\ro(M\|R)^d$ mod $\pmod$, resulting in an incorrect result. The CPU correctly computed $\ro(M\|R)^d$ mod $\qmod$ and the CRT reconstruction (on the wrong values). As a result, the final result $(R,S)$ does not verify as a valid signature.

   Show how an adversary who knows $M$, $(R,S)$, and the public key can factor $\nmod$.

   $S$ satisfies:

   $\begin{aligned} S^e \not\equiv_\pmod \ro(M\|R); \\ S^e \equiv_\qmod \ro(M\|R).\end{aligned}$

9. $\star$ Usually it is not advisable to use the same key for different purposes. Despite that, it is safe to use RSA-KEM and RSA-PSS with the same RSA keypair; prove that the following two libraries are indistinguishable. RSA-KEM requires a random oracle with output $\bits^\secpar$, while RSA-PSS requires one with output $\Z_\nmod$. The following libraries implement two independent random oracles, with different ranges.

   $(\nmod,e,d) := \RSA.\KeyGen()$

   $\subname{pk}(\,)$:

   return $(\nmod,e)$

   $\subname{enc}(\,)$:

   // $\Encaps(\pk)$:

   $R \gets \Z_\nmod$

   $\ctxt := R^e \pct \nmod$

   $\ptxt := \ro_2(R)$

   return $(\ctxt, \ptxt)$

   $\subname{dec}(\ctxt)$:

   // $\Decaps(\sk, \ctxt)$:

   return $\ro_2(\ctxt^d \pct \nmod)$

   $\subname{sign}(\ptxt)$:

   // $\Sign(\sk,\ptxt)$:

   $R \gets \bits^\secpar$

   $S := \ro_1(\ptxt\|R)^d \pct \nmod$

   return $(R,S)$

   $\subname{ver}(\ptxt,(R,S))$:

   // $\Verify(\pk,\ptxt, (R,S))$:

   $Y := \ro_1(\ptxt\|R)$

   return $Y == S^e \pct \nmod$

   $\ro_1(A)$:

   if $\rotable_1[A]$ undefined:

   $\rotable_1[A] \gets \Z_\nmod$

   return $\rotable_1[A]$

   $\ro_2(A)$:

   if $\rotable_2[A]$ undefined:

   $\rotable_2[A] \gets \bits^\secpar$

   return $\rotable_2[A]$

   $\indist$

   $(\nmod,e,d) := \RSA.\KeyGen()$

   $\subname{pk}(\,)$:

   return $(\nmod,e)$

   $\subname{enc}(\,)$:

   $\ctxt \gets \Z_\nmod$

   $\ptxt \gets \bits^\secpar$

   $\mathcal{D}[\ctxt] := \ptxt$

   return $(\ctxt, \ptxt)$

   $\subname{dec}(\ctxt)$:

   if $\mathcal{D}[\ctxt]$ defined: return $\mathcal{D}[\ctxt]$

   // $\Decaps(\sk, \ctxt)$:

   return $\ro_2(\ctxt^d \pct \nmod)$

   $\subname{sign}(\ptxt)$:

   // $\Sign(\sk,\ptxt)$:

   $R \gets \bits^\secpar$

   $S := \ro_1(\ptxt\|R)^d \pct \nmod$

   $\mathcal{S} := \mathcal{S} \cup \{ (\ptxt,R,S) \}$

   return $(R,S)$

   $\subname{ver}(\ptxt,(R,S))$:

   if $(\ptxt,R,S) \in \mathcal{S}$: return $\mytrue$

   return $\myfalse$

   $\ro_1(A)$:

   if $\rotable_1[A]$ undefined:

   $\rotable_1[A] \gets \Z_\nmod$

   return $\rotable_1[A]$

   $\ro_2(A)$:

   if $\rotable_2[A]$ undefined:

   $\rotable_2[A] \gets \bits^\secpar$

   return $\rotable_2[A]$

10. Prove that if $H$ is a secure (salted) CRHF and $\Sigma$ is a secure signature scheme, then the following scheme is also a secure signature scheme:

    $\KeyGen(\,)$:

    $(\pk,\sk) := \Sigma.\KeyGen()$

    $T \gets \bits^\secpar$

    $V := H(T,\pk)$

    $\pk' := (V,T)$

    $\sk' := (\sk,\pk,T)$

    return $(\pk',\sk')$

    $\Sign\bigl((\sk,\pk,T),\ptxt\bigr)$:

    $S := \Sigma.\Sign(\sk,\ptxt)$

    return $(S,\pk)$

    $\Verify\bigl( (V,T), \ptxt, (S,\pk) \bigr)$:

    return $V == H(T,\pk)$ and $\Sigma.\Verify(\pk,\ptxt,S)$

    So if a signature scheme has very large public keys, they can be shrunk at the expense of making signatures longer.

11. Suppose $\Sigma_{\text{pke}}$ is a PKE scheme and $\Sigma_{\text{sig}}$ is a signature scheme, and consider the following new PKE scheme:

    $\KeyGen = \Sigma_{\text{pke}}.\KeyGen$

    $\Enc(\pk,\ptxt)$:

    $\ctxt := \Sigma_{\text{pke}}.\Enc(\pk,\ptxt)$

    $(\pk',\sk') := \Sigma_{\text{sig}}.\KeyGen()$

    $S := \Sigma.\Sign(\sk', \ctxt)$

    return $(\ctxt, \pk', S)$

    $\Dec\bigl(\sk,(\ctxt,\pk',S)\bigr)$:

    if $\Sigma_{\text{sig}}.\Verify(\pk', \ctxt, S)$:

    return $\Sigma_{\text{pke}}.\Dec(\sk,\ctxt)$

    else: return $\myerr$

    Show that this scheme is not CCA-secure, even if $\Sigma_{\text{pke}}$ is CPA-secure and $\Sigma_{\text{sig}}$ is a secure digital signature scheme.

12. This exercise explores whether we can convert a CPA-secure PKE into a CCA-secure one, by incorporating signatures similar to how MACs promote CPA security to CCA security for SKE.

    1. Let $\Sigma_{\text{cpa}}$ be a CPA-secure PKE with $\Sigma_{\text{cpa}}.\M = \bits^n$. Prove that the following scheme is correct and is also CPA-secure:

       $\begin{aligned} \KeyGen &= \Sigma_{\text{cpa}}.\KeyGen \\ \M &= \Sigma_{\text{cpa}}.\M = \bits^n \\ \C &= \Sigma_{\text{cpa}}.\C \times \bits^n \times \bits^n \end{aligned}$

       $\Enc(\pk,\ptxt)$:

       $\ctxt := \Sigma_{\text{cpa}}.\Enc(\pk,\ptxt)$

       return $(\ctxt, \bit1^n, \bit0^n)$

       $\Dec\bigl(\sk,(\ctxt,R,S)\bigr)$:

       $\ptxt := \Sigma_{\text{cpa}}.\Dec(\sk,\ctxt)$

       // $\&$ denotes bitwise-and

       return $(\ptxt \mathbin{\&} R) \oplus S$

    2. Now consider the following natural approach to authenticate ciphertexts using a signature: Encrypt the plaintext along with a verification key, and then sign the resulting ciphertext. More formally, let $\Sigma_{\text{pke}}$ be a PKE scheme and $\Sigma_{\text{sig}}$ be a signature scheme, and define the following PKE:

       $\KeyGen = \Sigma_{\text{pke}}.\KeyGen$

       $\Enc(\pk,\ptxt)$:

       $(\pk',\sk') := \Sigma_{\text{sig}}.\KeyGen()$

       $\ctxt := \Sigma_{\text{pke}}.\Enc(\pk,\ptxt \| \hl{\pk'})$

       $S := \Sigma.\Sign(\sk', \ctxt)$

       return $(\ctxt, S)$

       $\Dec\bigl(\sk,(\ctxt,\pk',S)\bigr)$:

       $\ptxt \| \pk' := \Sigma_{\text{pke}}.\Dec(\sk,\ctxt)$

       if $\Sigma_{\text{sig}}.\Verify(\pk', \ctxt, S)$:

       return $\ptxt$

       else: return $\myerr$

       Show that the resulting scheme is not CCA-secure, when $\Sigma_{\text{pke}}$ is the CPA-secure scheme from part (a), and $\Sigma_{\text{sig}}$ is a secure digital signature scheme. Thus, this recipe does not suffice to upgrade an arbitrary CPA-secure PKE into a CCA-secure.

13. Let $\Sigma$ be a signature scheme and define the new scheme $\Sigma^*$ below, which produces a signature chain:

    $\KeyGen = \Sigma.\KeyGen$

    $\Sign(\sk,\ptxt)$:

    $(\pk',\sk') := \Sigma.\KeyGen()$

    $S_1 := \Sigma.\Sign(\sk, \hl{\pk'})$

    $S_2 := \Sigma.\Sign(\hl{\sk'}, \ptxt)$

    return $(\pk', S_1, S_2)$

    $\Verify\bigl(\pk,\ptxt,(\pk',S_1,S_2)\bigr)$:

    if $\Sigma.\Verify(\pk, \pk', S_1)$

    and $\Sigma.\Verify(\pk',\ptxt,S_2)$:

    return $\mytrue$

    else: return $\myfalse$

    Prove that $\Sigma^*$ is a secure digital signature scheme, if $\Sigma$ is.