  In this paper we present a new primitive for a key exchange protocol based on
multivariate non-commutative polynomial rings, analogous to the classic
Diffie-Hellman method. Our technique extends the proposed scheme of Boucher et
al. from 2010. Their method was broken by Dubois and Kammerer in 2011, who
exploited the Euclidean domain structure of the chosen ring. However, our
proposal is immune against such attacks, without losing the advantages of
non-commutative polynomial rings as outlined by Boucher et al. Moreover, our
extension is not restricted to any particular ring, but is designed to allow
users to readily choose from a large class of rings when applying the protocol.
Our primitive can also be applied to other cryptographic paradigms. In
particular, we develop a three-pass protocol, a public key cryptosystem, a
digital signature scheme and a zero-knowledge proof protocol.
