Tight­ly Se­cu­re Au­then­ti­ca­ted Key Ex­chan­ge

Chris­toph Bader, Den­nis Hof­heinz, Tibor Jager, Eike Kiltz, Yong Li

TCC 2015

Ab­stract

We con­struct the first Au­then­ti­ca­ted Key Ex­chan­ge (AKE) pro­to­col whose se­cu­ri­ty does not de­gra­de with an in­crea­sing num­ber of users or ses­si­ons. Our con­struc­tion is mo­du­lar, and can be in­stan­tia­ted ef­fi­ci­ent­ly from stan­dard as­sump­ti­ons (such as the SXDH or DLIN as­sump­ti­ons in pai­ring-fri­end­ly groups). For in­stan­ce, we pro­vi­de an SXDH-ba­sed pro­to­col whose com­mu­ni­ca­ti­on com­ple­xi­ty is only 14 group ele­ments and 4 ex­po­n­ents (plus some book­ke­eping in­for­ma­ti­on).

Along the way we de­ve­lop new, stron­ger se­cu­ri­ty de­fi­ni­ti­ons for di­gi­tal si­gna­tu­res and key en­cap­su­la­ti­on me­cha­nis­ms. For in­stan­ce, we in­tro­du­ce a se­cu­ri­ty model for di­gi­tal si­gna­tu­res that pro­vi­des exis­ten­ti­al unf­or­ge­abi­li­ty under cho­sen-mes­sa­ge at­tacks in a mul­ti-user set­ting with ad­ap­ti­ve cor­rup­ti­ons of secret keys. We show how to con­struct ef­fi­ci­ent sche­mes that sa­tis­fy the new de­fi­ni­ti­ons with tight se­cu­ri­ty pro­ofs under stan­dard as­sump­ti­ons.

Tags: au­then­ti­ca­ted key ex­chan­ge, di­gi­tal si­gna­tu­re sche­mes, Groth-Sa­hai Pro­ofs, Tight Se­cu­ri­ty Pro­ofs