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

Celine Chevalier (1, 2, 3) , Fabien Laguillaumie (4) , Damien Vergnaud (5, 6)

1 UP2 - Université Panthéon-Assas
2 CASCADE - Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities
3 CRED - Centre de Recherche en Economie et Droit
4 ARIC - Arithmetic and Computing
5 IUF - Institut universitaire de France
6 ALMASTY - ALgorithms for coMmunicAtion SecuriTY

We address the problem of speeding up group computations in cryptography using a single untrusted computational resource. We analyze the security of two efficient protocols for securely outsourcing (multi-)exponentiations. We show that the schemes do not achieve the claimed security guarantees and we present practical polynomial-time attacks on the delegation protocols which allow the un-trusted helper to recover part (or the whole) of the device's 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 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 in terms of operations in the underlying group.

Mots clés: Coppersmith methods; Cryptanalysis; Optimality results; Protocols; Secure outsource computation

Domaines: Cryptographie et sécurité [cs.CR]

Celine Chevalier, Fabien Laguillaumie, Damien Vergnaud. Privately Outsourcing Exponentiation to a Single Server: Cryptanalysis and Optimal Constructions. Algorithmica, 2021, 83 (1), pp.72-115. ⟨10.1007/s00453-020-00750-2⟩. ⟨hal-02899803⟩