Rate-1 Trapdoor Functions from the Diffie-Hellman Problem

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

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

1 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology – ASIACRYPT 2019 - 25th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings
EditorsSteven D. Galbraith, Shiho Moriai
PublisherSpringer Science and Business Media Deutschland GmbH
Pages585-606
Number of pages22
ISBN (Print)9783030346171
DOIs
StatePublished - 2019
Event25th Annual International Conference on the Theory and Applications of Cryptology and Information Security, ASIACRYPT 2019 - Kobe, Japan
Duration: Dec 8 2019Dec 12 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11923 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference25th Annual International Conference on the Theory and Applications of Cryptology and Information Security, ASIACRYPT 2019
Country/TerritoryJapan
CityKobe
Period12/8/1912/12/19

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Rate-1 Trapdoor Functions from the Diffie-Hellman Problem'. Together they form a unique fingerprint.

Cite this