No Single Optimal CGKA Protocol Exists Sample Clauses

No Single Optimal CGKA Protocol Exists. In Section 5, we present another negative result for CGKA protocols that make black-box use of PKE and OWFs. Naturally, CGKA protocols proceed in an online manner such that users do not know which operations will be executed next. Therefore, users have to make choices when executing operations that may result in unnecessary communication. We leverage this situation to show that there does not exist any single CGKA protocol that makes black-box use of PKE and OWFs and that has optimal communication costs for every sequence that may be executed. More specifically, for every CGKA protocol Π, there exists some distribution of CGKA operations Seq and some other CGKA protocol Πj such that Π has much higher communication costs than Πj when executing Seq. − Our driving example is as follows: suppose again that starting with a CGKA group in arbitrary state, k users are added by user A and remain offline. Next, α users (including user A) execute state refreshes. In this case, some protocols might use a strategy which through these state refreshes creates and communicates extra redundant secrets for the k added users, while others may use a strategy which simply relies on those secrets communicated by user A. For the former strategy, if the k added users afterwards come online and execute their own state refreshes, then the communication of these extra secrets will have been unnecessary, and a protocol which follows the latter strategy will have much lower communication cost. However, for the latter strategy, if one of the α added users, user j, thereafter remains offline while the other α 1 users execute rounds of sequential state refreshes, then we know from what we prove in Section 3 that each of the rounds will have Ω(k) communication cost. On the other hand, a protocol that follows the former strategy can have much lower communication cost if the state refresh ciphertext of user j alone was large (Ω(k)).