Efficient and Secure Delegation of Exponentiation in General Groups to a Single Malicious Server

Research output: Contribution to journalArticlepeer-review

Abstract

Group exponentiation is an important and relatively expensive operation used in many public-key cryptosystems and, more generally, cryptographic protocols. To
expand the applicability of these solutions to computationally weaker devices,
it has been advocated that this operation is delegated from a computationally
weaker client to a computationally stronger server. Solving this problem
in the case of a single, possibly malicious, server, has remained open since the introduction of a formal model.

In previous work we have proposed practical and secure solutions applicable to two classes of specific groups, related to well-known cryptosystems.

In this paper, we investigate this problem in a general class of multiplicative groups, possibly going beyond groups currently subject to quantum cryptanalysis attacks.
Our main results are efficient delegation protocols for exponentiation in
these general groups. The main technique in our results is a reduction of the protocol's security probability (i.e., the probability that a malicious server convinces a client of an incorrect exponentiation output) that is more efficient than by standard parallel repetition. The resulting protocols satisfy natural requirements such as correctness, security, privacy and efficiency, even if the adversary uses the full power of quantum computers. In particular, in our protocols the client performs a number of online group multiplications smaller by 1 to 2 orders of magnitude than in a non-delegated computation.
Original languageEnglish
JournalMathematics in Computer Science
DOIs
Publication statusPublished - 28 Mar 2020

Bibliographical note

This is an author-produced version of the published paper. Uploaded in accordance with the publisher’s self-archiving policy. Further copying may not be permitted; contact the publisher for details.

Cite this