9.1.2. Computational Analysis
9.1.2. Computational Analysis
It is shown in [CS01] that a hybrid public key encryption scheme of essentially the same form as the Base mode described here is IND-CCA2-secure as long as the underlying KEM and AEAD schemes are IND-CCA2-secure. Moreover, it is shown in [HHK06] that IND-CCA2 security of the KEM and the data encapsulation mechanism are necessary conditions to achieve IND-CCA2 security for hybrid public key encryption. The main difference between the scheme proposed in [CS01] and the Base mode in this document (both named HPKE) is that we interpose some KDF calls between the KEM and the AEAD. Analyzing the HPKE Base mode instantiation in this document therefore requires verifying that the additional KDF calls do not cause the IND-CCA2 property to fail, as well as verifying the additional export key secrecy property.
Analysis of the PSK, Auth, and AuthPSK modes defined in this document additionally requires verifying the sender authentication property. While the PSK mode just adds supplementary keying material to the key schedule, the Auth and AuthPSK modes make use of a non-standard authenticated KEM construction. Generally, the authenticated modes of HPKE can be viewed and analyzed as flavors of signcryption [SigncryptionDZ10].
A preliminary computational analysis of all HPKE modes has been done in [HPKEAnalysis], indicating asymptotic security for the case where the KEM is DHKEM, the AEAD is any IND-CPA-secure and INT-CTXT-secure scheme, and the DH group and KDF satisfy the following conditions:
-
DH group: The gap Diffie-Hellman (GDH) problem is hard in the appropriate subgroup [GAP].
-
Extract() and Expand(): Extract() can be modeled as a random oracle. Expand() can be modeled as a pseudorandom function, wherein the first argument is the key.
In particular, the KDFs and DH groups defined in this document (see Sections 7.2 and 7.1) satisfy these properties when used as specified. The analysis in [HPKEAnalysis] demonstrates that under these constraints, HPKE continues to provide IND-CCA2 security, and provides the additional properties noted above. Also, the analysis confirms the expected properties hold under the different key compromise cases mentioned above. The analysis considers a sender that sends one message using the encryption context, and additionally exports two independent secrets using the secret export interface.
The table below summarizes the main results from [HPKEAnalysis]. N/A means that a property does not apply for the given mode, whereas Y means the given mode satisfies the property.
| Variant | Message Sec. | Export Sec. | Sender Auth. |
|---|---|---|---|
| Base | Y | Y | N/A |
| PSK | Y | Y | Y |
| Auth | Y | Y | Y |
| AuthPSK | Y | Y | Y |
Table 6: HPKE Mode Security Properties
If non-DH-based KEMs are to be used with HPKE, further analysis will be necessary to prove their security. The results from [CS01] provide some indication that any IND-CCA2-secure KEM will suffice here, but are not conclusive given the differences in the schemes.
A detailed computational analysis of HPKE's Auth mode single-shot encryption API has been done in [ABHKLR20]. The paper defines security notions for authenticated KEMs and for authenticated public key encryption, using the outsider and insider security terminology known from signcryption [SigncryptionDZ10]. The analysis proves that DHKEM's AuthEncap()/AuthDecap() interface fulfills these notions for all Diffie-Hellman groups specified in this document. The analysis also provides exact security bounds, under the assumptions that the gap Diffie-Hellman (GDH) problem is hard in the appropriate subgroup [GAP], and that HKDF can be modeled as a random oracle.
Further, [ABHKLR20] proves composition theorems, showing that HPKE's Auth mode fulfills the security notions of authenticated public key encryption for all KDFs and AEAD schemes specified in this document, given any authenticated KEM satisfying the previously defined security notions for authenticated KEMs. The theorems assume that the KEM is perfectly correct; they could easily be adapted to work with KEMs that have a nonzero but negligible probability for decryption failure. The assumptions on the KDF are that Extract() and Expand() can be modeled as pseudorandom functions wherein the first argument is the key, respectively. The assumption for the AEAD is IND-CPA and IND-CTXT security.
In summary, the analysis in [ABHKLR20] proves that the single-shot encryption API of HPKE's Auth mode satisfies the desired message confidentiality and sender authentication properties listed at the beginning of this section; it does not consider multiple messages, nor the secret export API.