**Ubiquitous Weak-key Classes of BRW-polynomial Function**

*Kaiyan Zheng and Peng Wang and Dingfeng Ye*

**Abstract: **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.

**Category / Keywords: **secret-key cryptography / weak key, polynomial evaluation hash, BRW-polynomial

**Original Publication**** (with minor differences): **Africacrypt 2018

**Date: **received 3 Jan 2018, last revised 17 Mar 2018

**Contact author: **zhengkaiyan at iie ac cn; wp@is ac cn

**Available format(s): **PDF | BibTeX Citation

**Version: **20180318:034915 (All versions of this report)

**Short URL: **ia.cr/2018/014

[ Cryptology ePrint archive ]