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.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
related-key attackhash proof systemmessage authentication codepublic-key encryptionsymmetric encryption
Contact author(s)
dalen17 @ sjtu edu cn
History
2016-11-15: received
Short URL
https://ia.cr/2016/1051
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/1051,
      author = {Shuai Han and Shengli Liu and Lin Lyu},
      title = {Super-Strong RKA Secure MAC, PKE and SE from Tag-based Hash Proof System},
      howpublished = {Cryptology ePrint Archive, Paper 2016/1051},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/1051}},
      url = {https://eprint.iacr.org/2016/1051}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.