The twelfth edition of the Theory of Cryptography Conference (TCC) was held in the beautiful city of Warsaw this week amidst uncertainty over the future (placement in the cryptographic calendar) of the event. The next edition will be held in Tel Aviv in January 2016 ahead of a planned shift to the latter end of the calendar year. This blog post lives in the present, and will take a closer look at 'Constructing and Understanding Chosen Ciphertext Security via Puncturable Key Encapsulation Mechanisms' [link] by Takahiro Matsuda and Goichiro Hanaoka, part of the broad-reaching session titled 'Encryption and Key Exchange'. Enhancing our understanding of a concept as fundamental as chosen ciphertext security can only be a good thing, particularly when much of the remainder of the TCC program was so heavily focused on obfuscation.
Sending messages via public-key encryption is expensive and slow, so we want to achieve the speed benefits of symmetric-key primitives (such as blockciphers) without having to exchange symmetric keys between all communicating parties. A natural approach for sending long messages is to construct a ciphertext of two components: an encryption of a (randomly chosen) symmetric key under the recipient's public key, and an encryption of the message under the symmetric key. The process of creating this first ciphertext component is known as a Key Encapsulation Mechanism, and is reversed by the recipient performing 'decapsulation' using their secret key. This two-tier framework is known as hybrid encryption, the component that encrypts the plaintext is called a Data Encapsulation Mechanism (DEM), and if we combine a CCA-secure KEM with a CCA-secure DEM then we get a CCA-secure public-key encryption scheme.
Many constructions of Chosen-Ciphertext Attack (CCA)-secure PKE (/KEMs) are inspired by the Dolev/Dwork/Naor framework, (incl. Lossy Trapdoor Functions by Peikert and Waters, Correlated-Input secure TDFs by Rosen and Segev among others), so the paper attempts to generalise this style of technique. Taking some inspiration from recent work on puncturable PRFs and puncturable tag-based encryption, the authors give a definition of puncturable KEMs which comprise the classical key generation, encapsulation and decapsulation algorithms plus three additional algorithms: $\hat{sk_{c^*}}\gets\mathsf{Punc}(sk,c^*)$ that punctures $sk$ by a ciphertext $c^*$; punctured decapsulation $K/\bot\gets\mathsf{PDecap}(\hat{sk_{c^*}},c)$ and a predicate $0/1\gets\mathsf{F}(c,c')$ that decides whether ciphertexts $c$ and $c'$ are 'close to' each other.
The punctured secret key $\hat{sk_{c^*}}$ can be used by $\mathsf{PDecap}$ to decapsulate all ciphertexts that are 'far from' $c^*$, yet is useless for ciphertexts 'close to' $c^*$ (including $c^*$ itself). This means that a 'normal' secret key $sk$ defines a map whose domain is entire ciphertext space, whereas a punctured secret key $\hat{sk_{c^*}}$ only defines a map whose domain has a hole punctured by $c^*$. If ciphertexts are in this 'hole' punctured by $c^*$ then they will not decrypt. The authors describe how many existing CCA-secure KEMs fit the puncturable KEM framwork, and show that the following ingredients yield a CCA-secure KEM:
Sending messages via public-key encryption is expensive and slow, so we want to achieve the speed benefits of symmetric-key primitives (such as blockciphers) without having to exchange symmetric keys between all communicating parties. A natural approach for sending long messages is to construct a ciphertext of two components: an encryption of a (randomly chosen) symmetric key under the recipient's public key, and an encryption of the message under the symmetric key. The process of creating this first ciphertext component is known as a Key Encapsulation Mechanism, and is reversed by the recipient performing 'decapsulation' using their secret key. This two-tier framework is known as hybrid encryption, the component that encrypts the plaintext is called a Data Encapsulation Mechanism (DEM), and if we combine a CCA-secure KEM with a CCA-secure DEM then we get a CCA-secure public-key encryption scheme.
Many constructions of Chosen-Ciphertext Attack (CCA)-secure PKE (/KEMs) are inspired by the Dolev/Dwork/Naor framework, (incl. Lossy Trapdoor Functions by Peikert and Waters, Correlated-Input secure TDFs by Rosen and Segev among others), so the paper attempts to generalise this style of technique. Taking some inspiration from recent work on puncturable PRFs and puncturable tag-based encryption, the authors give a definition of puncturable KEMs which comprise the classical key generation, encapsulation and decapsulation algorithms plus three additional algorithms: $\hat{sk_{c^*}}\gets\mathsf{Punc}(sk,c^*)$ that punctures $sk$ by a ciphertext $c^*$; punctured decapsulation $K/\bot\gets\mathsf{PDecap}(\hat{sk_{c^*}},c)$ and a predicate $0/1\gets\mathsf{F}(c,c')$ that decides whether ciphertexts $c$ and $c'$ are 'close to' each other.
The punctured secret key $\hat{sk_{c^*}}$ can be used by $\mathsf{PDecap}$ to decapsulate all ciphertexts that are 'far from' $c^*$, yet is useless for ciphertexts 'close to' $c^*$ (including $c^*$ itself). This means that a 'normal' secret key $sk$ defines a map whose domain is entire ciphertext space, whereas a punctured secret key $\hat{sk_{c^*}}$ only defines a map whose domain has a hole punctured by $c^*$. If ciphertexts are in this 'hole' punctured by $c^*$ then they will not decrypt. The authors describe how many existing CCA-secure KEMs fit the puncturable KEM framwork, and show that the following ingredients yield a CCA-secure KEM:
- Decapsulation soundness (the only valid ciphertext that is 'close' to $c$ is $c$ itself),
- Punctured decapsulation soundness (punctured decapsulation works as well as the 'normal' decapsulation algorithm for all ciphertexts 'far' from $c$),
- Extended CPA (eCPA) security (CPA security still holds even in the presence of a punctured secret key corresponding to the challenge ciphertext)
No comments:
Post a Comment