By the same authors

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

Research output: Contribution to journalArticlepeer-review

Published copy (DOI)



Publication details

JournalMathematics in Computer Science
DateAccepted/In press - 15 Dec 2019
DatePublished (current) - 28 Mar 2020
Original languageEnglish


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.

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.

Discover related content

Find related publications, people, projects, datasets and more using interactive charts.

View graph of relations