International Association for Cryptologic Research

International Association
for Cryptologic Research


Ji Sun Shin


Modeling Insider Attacks on Group Key-Exchange Protocols
Jonathan Katz Ji Sun Shin
Protocols for authenticated key exchange (AKE) allow parties within an insecure network to establish a common session key which can then be used to secure their future communication. It is fair to say that group AKE is currently less well understood than the case of two-party AKE; in particular, attacks by malicious insiders --- a concern specific to the group setting --- have so far been considered only in a relatively ``ad-hoc'' fashion. The main contribution of this work is to address this deficiency by providing a formal, comprehensive model and definition of security for group AKE which automatically encompasses insider attacks. We do so by defining an appropriate ideal functionality for group AKE within the universal composability (UC) framework. As a side benefit, any protocol secure with respect to our definition is secure even when run concurrently with other protocols, and the key generated by any such protocol may be used securely in any subsequent application. In addition to proposing this definition, we show that the resulting notion of security is strictly stronger than the one proposed by Bresson, et al. (termed ``AKE-security''), and that our definition implies all previously-suggested notions of security against insider attacks. We also show a simple technique for converting any AKE-secure protocol into one secure with respect to our definition.
Parallel and Concurrent Security of the HB and HB+ Protocols
Jonathan Katz Ji Sun Shin
At Crypto 2005, Juels and Weis (building on work of Hopper and Blum) proposed and analyzed two shared-key authentication protocols --- HB and HB+ --- whose extremely low computational cost makes them attractive for low-cost devices such as radio-frequency identification (RFID) tags. Security of these protocols is based on the conjectured hardness of the ``learning parity with noise'' (LPN) problem: the HB protocol is proven secure against a passive (eavesdropping) adversary, while the HB+ protocol is proven secure against active attacks. Juels and Weis prove security of these protocols only for the case of sequential executions, and explicitly leave open the question of whether security holds also in the case of parallel or concurrent executions. In addition to guaranteeing security against a stronger class of adversaries, a positive answer to this question would allow the HB+ protocol to be parallelized, thereby reducing its round complexity from super-logarithmic (in the security parameter) to 3. Using a recent result by Regev (STOC 2005) regarding the LPN problem, we answer the aforementioned question in the affirmative and prove security of the HB and HB+ protocols under parallel/concurrent executions. Applying Regev's result also yields what we find to be substantially simpler security proofs for these protocols which are also more complete in that they explicitly address the dependence of the soundness error on the number of iterations.


Jonathan Katz (4)
Adam Smith (1)