We investigate the problem of delegating operations in cryptography solutions from client devices that only perform quasilinear-time or lower-order computations (e.g., additions/subtractions, modular reductions with a small modulus, etc.) to a single, possibly malicious, server. All previous work considered clients capable of computing higher-order operations, such as fully homomorphic encryption, group exponentiations or several group multiplications. In this model, we show protocols to delegate the computation of ring multiplications while satisfying desirable result correctness, input privacy and result security requirements. The main technical component, of independent interest, is a family of probabilistic tests that extends a classical test by Pippenger. The asymptotic improvement in our multiplication delegation protocols is also backed up by concrete implementation results, demonstrating that the client's online computation is strictly smaller than non-delegated computation of the same function, for input lengths of interest in cryptography solutions.

When the AAG protocol was first introduced, braid groups were proposed as platform group. However, there are studies that successful attack AAG with braid groups, one main attack method is the length-based attack. Searching for a new platform for AAG, Garber, Kahrobaei, and Lam studied polycyclic groups generated by number field and concluded that they are resistant against the length-based attack. Inspired by this result, we ask whether other type of polycyclic groups can be used as platform for AAG. In this paper, we discuss the use of Heisenberg groups, a type of polycyclic group, as a platform group for AAG by submitting them to one of AAG's major attacks, the length-based attack.

In this paper, we propose a non-commutative key-exchange scheme which generalizes the classical ElGamal Cipher to polycyclic groups. We describe the criteria for groups which would provide good candidates for such cryptosystems, we also examine the complexity of the decision problems related to these key exchange.