Cryptology ePrint Archive: Report 2019/1072

Rate-1 Trapdoor Functions from the Diffie-Hellman Problem

Nico Döttling and Sanjam Garg and Mohammad Hajiabadi and Kevin Liu and Giulio Malavolta

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. Speci cally, we present:

\begin​{enumerate}

\item 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.

\item 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.

\end{enumerate}

Category / Keywords: public-key cryptography / Trapdoor functions, Deterministic encryption, Rate-1 primitives, CDH, DDH

Original Publication (in the same form): IACR-ASIACRYPT-2019

Date: received 20 Sep 2019

Contact author: nico doettling at gmail com,sanjamg@berkeley edu,mdhajiabadi@berkeley edu,solar464@gmail com,malavolta@cs fau de

Available format(s): PDF | BibTeX Citation

Version: 20190923:072650 (All versions of this report)

Short URL: ia.cr/2019/1072


[ Cryptology ePrint archive ]