Practical and Secure Outsourcing of Discrete Log Group Exponentiation to a Single Malicious Server

Giovanni Di Crescenzo, Matluba Khodjaeva, Delaram Kahrobaei, Vladimir Shpilrain

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Group exponentiation is an important 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 outsourced from a computationally weaker client to a computationally stronger server, possibly implemented in a cloud-based architecture. While preliminary solutions to this problem considered mostly honest servers, or multiple separated servers, some of which honest, solving this problem
in the case of a single (logical), possibly malicious, server, has remained open since a formal cryptographic model was introduced. Several later attempts either failed to achieve privacy or only bounded by a constant the (security) probability that a cheating server convinces a client of an incorrect result.

In this paper we solve this problem for a large class of cyclic groups, thus making our solutions applicable to many cryptosystems in the literature that are based on the hardness of the discrete logarithm problem or on related assumptions.
Our main protocol satisfies natural correctness, security, privacy and efficiency requirements, where the security probability is exponentially small. In our main protocol, with very limited offline computation and server computation, the client can delegate an exponentiation to an exponent of the same length as a group element by performing an exponentiation to an exponent of short length
(i.e., the length of a statistical parameter). We also show an extension protocol that further reduces client computation by a constant factor, while increasing offline computation and server computation by about the same factor.
Original languageEnglish
Title of host publicationPractical and Secure Outsourcing of Discrete Log Group Exponentiation to a Single Malicious Server
PublisherACM
Pages17-28
Number of pages10
ISBN (Print)9781450352048
DOIs
Publication statusPublished - 3 Nov 2017
Event 2017 on Cloud Computing Security Workshop - Texas, United States
Duration: 30 Oct 2017 → …
http://www.wikicfp.com/cfp/servlet/event.showcfp?eventid=66069

Conference

Conference 2017 on Cloud Computing Security Workshop
Abbreviated titleCCSW '17
Country/TerritoryUnited States
Period30/10/17 → …
Internet address

Bibliographical note

© 2017 Association for Computing Machinery. 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