CISPA
Browse

Rate-1 Trapdoor Functions from the Diffie-Hellman Problem

Download (426.7 kB)
conference contribution
posted on 2023-11-29, 18:11 authored by Nico DöttlingNico Döttling, Sanjam Garg, Mohammad Hajiabadi, Kevin Liu, Giulio Malavolta
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.

History

Preferred Citation

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

Primary Research Area

  • Algorithmic Foundations and Cryptography

Name of Conference

International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT)

Legacy Posted Date

2019-09-05

Open Access Type

  • Unknown

BibTeX

@inproceedings{cispa_all_2968, title = "Rate-1 Trapdoor Functions from the Diffie-Hellman Problem", author = "Döttling, Nico and Garg, Sanjam and Hajiabadi, Mohammad and Liu, Kevin and Malavolta, Giulio", booktitle="{International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT)}", year="2019", }

Usage metrics

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC