The second talk in the 'Public Key Encryption' session of this year's Eurocrypt was given by Dennis Hofheinz, on his paper 'Circular Chosen-Ciphertext Security with Compact Ciphertexts'. The work gives the first KDM-CCA secure scheme with ciphertexts that have O(1) group elements, building on the past work of Boneh et al. who give a KDM-CPA secure scheme. For comparison the other CIRC-CCA secure scheme in the literature has ciphertexts with O(k) group elements. In the KDM-CCA security game, the adversary submits a (length-regular) function to the challenger and receives an encryption of either the function acting upon the secret keys in the system or an encryption of a zero message, and naturally the scheme is secure under this notion if all (efficient) adversaries cannot distinguish between these cases. Note that CIRC-CCA security (called clique security by Boneh et al.) is the scenario where the adversary is restricted to functions that on input take the secret keys in the system and output one of these secret keys. This is a special case of (and implied by) KDM-CCA security.
The KDM-CPA secure scheme of Boneh et al. relies on the possibility of constructing encryptions of secret keys (under their corresponding public keys) publicly, something that will clearly deem it KDM-CCA insecure. Consequently, something else is needed to realise a KDM-CCA scheme from this starting point. The main technical tool used to ramp up to KDM-CCA security is the 'Lossy Algebraic Filter', a family of functions indexed by a public key and a tag. A function LAF from this family takes as input a vector of elements Xi in Zp. For an injective tag, LAF will be injective. If the tag is lossy, then LAF only depends on a linear combination of the input elements. Crucially, different input vectors with the same linear combination (Σi=1n ωi Xi mod p) are mapped to the same value. The coefficients only depend on the public key of the filter, and not on the tag. Three properties are necessary for this definition to acheive its purpose. First of all, lossy and injective tags must be computationally indistinguishable; lossy tags can be generated using a special trapdoor; and finally that new lossy tags cannot be found efficiently without this trapdoor, even given polynomially many lossy tags before. The paper details how to construct LAFs based on the DLIN assumption with a suitable cryptographic pairing, and each tag corresponds to n DLIN-encrypted Waters signatures (if the signatures are valid then the tag is lossy).
The constructed CIRC-CCA secure PKE scheme adds an authentication tag (an encrypted image of the plaintext message under an LAF), and decryption queries are disallowed where the authentication tag is invalid. To prove security, all tags for key-dependent encryptions are made with respect to lossy filter tags, so little information about the secret key is released (information-theoretically speaking). But the fact that adversarial decryption queries must correspond to injective tags, the adversary needs to be able to guess the whole secret key to make any valid decryption query. The resulting scheme is secure under a combination of the DCR, DLIN and DDH assumptions (in appropriate groups).
The KDM-CPA secure scheme of Boneh et al. relies on the possibility of constructing encryptions of secret keys (under their corresponding public keys) publicly, something that will clearly deem it KDM-CCA insecure. Consequently, something else is needed to realise a KDM-CCA scheme from this starting point. The main technical tool used to ramp up to KDM-CCA security is the 'Lossy Algebraic Filter', a family of functions indexed by a public key and a tag. A function LAF from this family takes as input a vector of elements Xi in Zp. For an injective tag, LAF will be injective. If the tag is lossy, then LAF only depends on a linear combination of the input elements. Crucially, different input vectors with the same linear combination (Σi=1n ωi Xi mod p) are mapped to the same value. The coefficients only depend on the public key of the filter, and not on the tag. Three properties are necessary for this definition to acheive its purpose. First of all, lossy and injective tags must be computationally indistinguishable; lossy tags can be generated using a special trapdoor; and finally that new lossy tags cannot be found efficiently without this trapdoor, even given polynomially many lossy tags before. The paper details how to construct LAFs based on the DLIN assumption with a suitable cryptographic pairing, and each tag corresponds to n DLIN-encrypted Waters signatures (if the signatures are valid then the tag is lossy).
The constructed CIRC-CCA secure PKE scheme adds an authentication tag (an encrypted image of the plaintext message under an LAF), and decryption queries are disallowed where the authentication tag is invalid. To prove security, all tags for key-dependent encryptions are made with respect to lossy filter tags, so little information about the secret key is released (information-theoretically speaking). But the fact that adversarial decryption queries must correspond to injective tags, the adversary needs to be able to guess the whole secret key to make any valid decryption query. The resulting scheme is secure under a combination of the DCR, DLIN and DDH assumptions (in appropriate groups).
No comments:
Post a Comment