Paper 2018/014

Ubiquitous Weak-key Classes of BRW-polynomial Function

Kaiyan Zheng, Peng Wang, and Dingfeng Ye


BRW-polynomial function is suggested as a preferred alternative of polynomial function, owing to its high efficiency and seemingly non-existent weak keys. In this paper we investigate the weak-key issue of BRW-polynomial function as well as BRW-instantiated cryptographic schemes. Though, in BRW-polynomial evaluation, the relationship between coefficients and input blocks is indistinct, we give out a recursive algorithm to compute another $(2^{v+1}-1)$-block message, for any given $(2^{v+1}-1)$-block message, such that their output-differential through BRW-polynomial evaluation, equals any given $s$-degree polynomial, where $v\ge\lfloor\log_2(s+1)\rfloor$. With such algorithm, we illustrate that any non-empty key subset is a weak-key class in BRW-polynomial function. Moreover any key subset of BRW-polynomial function, consisting of at least $2$ keys, is a weak-key class in BRW-instantiated cryptographic schemes like the Wegman-Carter scheme, the UHF-then-PRF scheme, DCT, etc. Especially in the AE scheme DCT, its confidentiality, as well as its integrity, collapses totally, when using weak keys of BRW-polynomial function, which are ubiquitous.

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. MINOR revision.Africacrypt 2018
weak keypolynomial evaluation hashBRW-polynomial
Contact author(s)
zhengkaiyan @ iie ac cn
wp @ is ac cn
2018-03-18: revised
2018-01-04: received
See all versions
Short URL
Creative Commons Attribution


      author = {Kaiyan Zheng and Peng Wang and Dingfeng Ye},
      title = {Ubiquitous Weak-key Classes of BRW-polynomial Function},
      howpublished = {Cryptology ePrint Archive, Paper 2018/014},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.