Authenticated Key Exchange Protocols Based on Factoring Assumption

摘要

This paper investigates authenticated key exchange protocols over signed quadratic residues group QR_N~+, which is originally used for encryption schemes. The key technical tool developed by Hofheinz et al. is that in group QR_N~+ the strong Diffie-Hellman (SDH) problem is implied by the factoring assumption. To apply group QR_N~+, to authenticated key exchange protocols in the enhanced Canetti-Krawczyk (eCK) model, we extend Hofheinz et al.'s technique and introduce a new proof approach called k-th power. The k-th power proof approach is almost generic, i.e., applying it to many, if not all, existing authenticated Diffie-Hellman key exchange protocols in eCK model under gap assumption immediately produces protocols in eCK model under factoring assumption if they work over QR_N~+,. As one application of k-th power approach, we show that FS protocol, in which k is a constant, is provably secure in eCK model under factoring assumption if it works over QR_N~+. Our technique also applies to other protocols, e.g., UP,HMQV and its variants, in which A: is a non-constant, but at the cost of degrading a factor in the reduction.