Rate-1 Trapdoor Functions from the Diffie-Hellman Problem

Döttling, Nico and Garg, Sanjam and Hajiabadi, Mohammad and Liu, Kevin and Malavolta, Giulio
(2019) Rate-1 Trapdoor Functions from the Diffie-Hellman Problem.
In: ASIACRYPT 2019.
Conference: ASIACRYPT International Conference on the Theory and Application of Cryptology and Information Security
(In Press)

[img]
Preview
 Text
r1CDHTDF.pdf
Download (436kB) | Preview

Abstract

Trapdoor functions (TDFs) are one of the fundamental building blocks in cryptography. Studying the underlying assumptions and the efficiency of the resulting instantiations is therefore of both theoretical and practical interest. In this work we improve the input-to-image rate of TDFs based on the Diffie-Hellman problem. Specifically, we present: (a)A rate-1 TDF from the computational Diffie-Hellman (CDH) assumption, improving the result of Garg, Gay, and Hajiabadi [EUROCRYPT 2019], which achieved linear-size outputs but with large constants. Our techniques combine non-binary alphabets and high-rate error-correcting codes over large fields.(b)A rate-1 deterministic public-key encryption satisfying block-source security from the decisional Diffie-Hellman (DDH) assumption. While this question was recently settled by Döttling et al. [CRYPTO 2019], our scheme is conceptually simpler and concretely more efficient. We demonstrate this fact by implementing our construction.

Item Type: Conference or Workshop Item (A Paper) (Paper)
Conference: ASIACRYPT International Conference on the Theory and Application of Cryptology and Information Security
Depositing User: Nico Döttling
Date Deposited: 05 Sep 2019 12:54
Last Modified: 11 May 2021 17:25
Primary Research Area: NRA1: Trustworthy Information Processing
URI: https://publications.cispa.saarland/id/eprint/2968

Actions

Actions (login required)

View Item View Item
CISPA is powered by EPrints 3 which is developed by the School of Electronics and Computer Science at the University of Southampton. More information and software credits.