Paper 2016/1051

Super-Strong RKA Secure MAC, PKE and SE from Tag-based Hash Proof System

Shuai Han, Shengli Liu, and Lin Lyu

Abstract

$\mathcal{F}$-Related-Key Attacks (RKA) on cryptographic systems consider adversaries who can observe the outcome of a system under not only the original key, say $k$, but also related keys $f(k)$, with $f$ adaptively chosen from $\mathcal{F}$ by the adversary. In this paper, we define new RKA security notions for several cryptographic primitives including message authentication code (MAC), public-key encryption (PKE) and symmetric encryption (SE). This new kind of RKA notions are called _super-strong_ RKA securities, which stipulate minimal restrictions on the adversary's forgery or oracle access, thus turn out to be the strongest ones among existing RKA security requirements. We present paradigms for constructing super-strong RKA secure MAC, PKE and SE from a common ingredient, namely _Tag-based Hash Proof System_ (THPS). We also present constructions for THPS based on the $k$-Linear and the DCR assumptions. When instantiating our paradigms with concrete THPS constructions, we obtain super-strong RKA secure MAC, PKE and SE schemes for the class of restricted affine functions $\mathcal{F}_{\text{raff}}$, of which the class of linear functions $\mathcal{F}_{\text{lin}}$ is a subset. To the best of our knowledge, our MACs, PKEs and SEs are the first ones possessing super-strong RKA securities for a non-claw-free function class $\mathcal{F}_{\text{raff}}$ in the standard model and under standard assumptions. Our constructions are free of pairing and are as efficient as those proposed in previous works. In particular, the keys, tags of MAC and ciphertexts of PKE & SE all consist of only a constant number of group elements.