Privately Outsourcing Exponentiation to a Single Server: Cryptanalysis and Optimal Constructions

Celine Chevalier, Fabien Laguillaumie, and Damien Vergnaud

Abstract

We address the problem of speeding up group computations in cryptography using a single untrusted computational resource. We analyze the security of an efficient protocol for securely outsourcing multi-exponentiations proposed at ESORICS 2014. We show that this scheme does not achieve the claimed security guarantees and we present several practical polynomial-time attacks on the delegation protocol which allows the untrusted helper to recover part (or the whole) of the device secret inputs. We then provide simple constructions for outsourcing group exponentiations in different settings (e.g. public/secret, fixed/variable bases and public/secret exponents). Finally, we prove that our attacks on the ESORICS 2014 protocol are unavoidable if one wants to use a single untrusted computational resource and to limit the computational cost of the limited device to a constant number of (generic) group operations. In particular, we show that our constructions are actually optimal.

Available format(s)
Category
Cryptographic protocols
Publication info
Published elsewhere. Algorithmica
Keywords
Secure outsource computationCryptanalysisCoppersmith methodsProtocolsOptimality results
Contact author(s)
celine chevalier @ ens fr
fabien laguillaumie @ ens-lyon fr
damien vergnaud @ ens fr
History
2020-07-16: last of 2 revisions
See all versions
Short URL
https://ia.cr/2016/309

CC BY

BibTeX

@misc{cryptoeprint:2016/309,
author = {Celine Chevalier and Fabien Laguillaumie and Damien Vergnaud},
title = {Privately Outsourcing Exponentiation to a Single Server: Cryptanalysis and Optimal Constructions},
howpublished = {Cryptology ePrint Archive, Paper 2016/309},
year = {2016},
note = {\url{https://eprint.iacr.org/2016/309}},
url = {https://eprint.iacr.org/2016/309}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.