Black-Box Compact Key Exchange Lower Bound Sample Clauses

Black-Box Compact Key Exchange Lower Bound. In order to prove the CGKA lower bounds discussed above, we need a lower bound on the underlying CKE primitive. Therefore, in Section 4, we prove a black-box separation showing that all CKE protocols that make black-box use of public-key encryption (PKE) require the ciphertext sent from the special user to the n users to have size Ω(n), irrespective of the sizes of the public keys that the n users have sent to the special user. Our impossibility holds even if the scheme comes with a CRS, of arbitrary size. Ruling out schemes that allow for a CRS will help us with our CGKA lower bounds. Intuitively, since the n public keys are generated independently from each other, our result implies that there is no non-trivial “compression” operation that the special user can do to save over the trivial protocol: choosing a key and separately encrypting the key to each user independently. Relations to broadcast encryption. We note that the notion of CKE is incomparable to that of broadcast encryption, at least in an ostensible sense. Recall that a broadcast encryption scheme is a type of attribute-based encryption that allows for broadcasting a message to a subset of users, in a way that the resulting ciphertext is compact. One crucial difference between broadcast encryption and CKE is that under CKE, users have independent secret keys, while under broadcast encryption, user secret keys are correlated, all obtained via a master secret key. Relations to other black-box impossibility results. The work of Boneh et al. [15] shows that identity-based encryption (IBE) is black-box impossible from trapdoor permutations (TDPs). A striking similarity between IBE and CKE is that both deal with some form of compactness: that of public parameters (PP) for IBE and of ciphertexts in CKE. The techniques of [15] crucially rely on the number of identities being much larger than the number of queries required to generate a public parameter. In our setting, this is no longer the case: the number of queries made by the encryption algorithm to generate a compact ciphertext may be much larger than n, and hence the techniques of [15] do not work in our setting. In addition, we allow the CRS to grow with the number of identities. Extensions and limitations of our impossibility results. We believe that out impossibility should extend quite naturally to separate CKE from trapdoor permutations (TDPs), though we have not worked out the details. Our impossibility results have no bearing on the base...