Public-Key Encryption, Local Pseudorandom Generators, and the Low-Degree Method

Andrej Bogdanov, Pravesh K. Kothari, Alon Rosen

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

Abstract

The low-degree method postulates that no efficient algorithm outperforms low-degree polynomials in certain hypothesis-testing tasks. It has been used to understand computational indistinguishability in high-dimensional statistics. We explore the use of the low-degree method in the context of cryptography. To this end, we apply it in the design and analysis of a new public-key encryption scheme whose security is based on Goldreich’s pseudorandom generator. The scheme is a combination of two proposals of Applebaum, Barak, and Wigderson, and inherits desirable features from both.

Original languageEnglish (US)
Title of host publicationTheory of Cryptography - 21st International Conference, TCC 2023, Proceedings
EditorsGuy Rothblum, Hoeteck Wee
PublisherSpringer Science and Business Media Deutschland GmbH
Pages268-285
Number of pages18
ISBN (Print)9783031486142
DOIs
StatePublished - 2023
Externally publishedYes
Event21st International conference on Theory of Cryptography Conference, TCC 2023 - Taipei, Taiwan, Province of China
Duration: Nov 29 2023Dec 2 2023

Publication series

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

Conference

Conference21st International conference on Theory of Cryptography Conference, TCC 2023
Country/TerritoryTaiwan, Province of China
CityTaipei
Period11/29/2312/2/23

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Keywords

  • hypothesis testing
  • local cryptography
  • Public-key encryption

Fingerprint

Dive into the research topics of 'Public-Key Encryption, Local Pseudorandom Generators, and the Low-Degree Method'. Together they form a unique fingerprint.

Cite this