Public Key Encryption from High-Corruption Constraint Satisfaction Problems

• URL: http://arxiv.org/abs/2604.10479v1
• Date: Sun, 12 Apr 2026 06:19:54 GMT
• Title: Public Key Encryption from High-Corruption Constraint Satisfaction Problems
• Abstract summary: We give a public key encryption scheme with plausible quasi-exponential security based on the conjectured intractability of two constraint satisfaction problems (CSPs)<n>Our public key encryption scheme is the first to leverage high corruption CSPs while simultaneously achieving a plausible security level far above quasi-polynomial.
• Score: 6.201763450086127
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We give a public key encryption scheme with plausible quasi-exponential security based on the conjectured intractability of two constraint satisfaction problems (CSPs), both of which are instantiated with a corruption rate of $1 - o(1)$. First, we conjecture the hardness of a new large alphabet random predicate CSP (LARP-CSP) defined over an arbitrary but strongly expanding factor graph, where the vast majority of predicate outputs are replaced with random outputs. Second, we conjecture the hardness of the standard $k$XOR problem defined over a random factor graph, again where the vast majority of parity computations are replaced with random bits. In support of our hardness conjecture for LARP-CSPs, we give a variety of lower bounds, ruling out many natural attacks including all known attacks that exploit non-random factor graphs. Our public key encryption scheme is the first to leverage high corruption CSPs while simultaneously achieving a plausible security level far above quasi-polynomial. At the heart of our work is a new method for planting cryptographic trapdoors based on the label extended factor graph for a CSP. Along the way to achieving our result, we give the first uniform construction of an error-correcting code that has an expanding, low density generator matrix while simultaneously allowing for efficient decoding from a $1 - o(1)$ fraction of corruptions.

Related papers

• Towards Worst-case Hardness for Low-Noise LPN [6.6603865098703805]
  Existing worst-case-to-average-case reductions for [BLVW19, YZ21] rely on statistical smoothing of linear codes.<n>We show that any efficient solver can be transformed into a pair of efficient algorithms.
  arXiv  Detail & Related papers  (2026-06-04T08:11:23Z)
• Post-Quantum Cryptography: An Analysis of Code-Based and Lattice-Based Cryptosystems [55.49917140500002]
  Quantum computers will be able to break modern cryptographic systems using Shor's Algorithm.<n>We first examine the McEliece cryptosystem, a code-based scheme believed to be secure against quantum attacks.<n>We then explore NTRU, a lattice-based system grounded in the difficulty of solving the Shortest Vector Problem.
  arXiv  Detail & Related papers  (2025-05-06T03:42:38Z)
• On the Independence Assumption in Quasi-Cyclic Code-Based Cryptography [3.298620737848292]
  Most efficient proposals rely on the presumed hardness of decoding structured codes.<n> HQC is based on quasi-cyclic codes, which are codes generated by matrices consisting of two cyclic blocks.<n>We discuss implications of our result for potential worst-case to average-case reductions for quasi-cyclic codes.
  arXiv  Detail & Related papers  (2025-01-05T18:43:08Z)
• New constructions of pseudorandom codes [23.22566380210149]
  Pseudorandom error-correcting codes (PRCs) are a new cryptographic primitive with applications in watermarking generative AI models.<n>In this work, we examine the assumptions under which PRCs with robustness to a constant error rate exist.<n>We show how to construct secret-key PRCs of length $O(n)$ which are $textitunconditionally$ indistinguishable from random by $textpoly(n)$ time, $O(n1.5-varepsilon) space.
  arXiv  Detail & Related papers  (2024-09-11T19:14:39Z)
• Implementation of Entropically Secure Encryption: Securing Personal Health Data [0.704590071265998]
  Entropically Secure Encryption (ESE) offers unconditional security with shorter keys to the One-Time Pad. We present the first implementation of ESE for bulk encryption.
  arXiv  Detail & Related papers  (2024-04-04T12:07:33Z)
• Lossy Cryptography from Code-Based Assumptions [7.880958076366762]
  A proliferation of advanced cryptographic primitives imply hard problems in the complexity class $SZK$. This poses a barrier for building advanced primitives from code-based assumptions. We propose a new code-based assumption: Dense-Sparse, that falls in the complexity class $BPPSZK$ and is conjectured to be secure against subexponential time adversaries.
  arXiv  Detail & Related papers  (2024-02-06T02:17:08Z)
• Publicly-Verifiable Deletion via Target-Collapsing Functions [81.13800728941818]
  We show that targetcollapsing enables publiclyverifiable deletion (PVD) We build on this framework to obtain a variety of primitives supporting publiclyverifiable deletion from weak cryptographic assumptions.
  arXiv  Detail & Related papers  (2023-03-15T15:00:20Z)
• Revocable Cryptography from Learning with Errors [61.470151825577034]
  We build on the no-cloning principle of quantum mechanics and design cryptographic schemes with key-revocation capabilities. We consider schemes where secret keys are represented as quantum states with the guarantee that, once the secret key is successfully revoked from a user, they no longer have the ability to perform the same functionality as before.
  arXiv  Detail & Related papers  (2023-02-28T18:58:11Z)
• A Robust Phased Elimination Algorithm for Corruption-Tolerant Gaussian Process Bandits [118.22458816174144]
  We propose a novel robust elimination-type algorithm that runs in epochs, combines exploration with infrequent switching to select a small subset of actions, and plays each action for multiple time instants. Our algorithm, GP Robust Phased Elimination (RGP-PE), successfully balances robustness to corruptions with exploration and exploitation. We perform the first empirical study of robustness in the corrupted GP bandit setting, and show that our algorithm is robust against a variety of adversarial attacks.
  arXiv  Detail & Related papers  (2022-02-03T21:19:36Z)
• Probabilistic Sequential Shrinking: A Best Arm Identification Algorithm for Stochastic Bandits with Corruptions [91.8283876874947]
  We consider a best arm identification (BAI) problem for Sequential bandits with adversarial corruptions in the fixed-budget setting of T steps. We design a novel randomized algorithm, Probabilistic Shrinking($u$) (PSS($u$)), which is agnostic to the amount of corruptions. We show that when the CPS is sufficiently large, no algorithm can achieve a BAI probability tending to $1$ as $Trightarrow infty$.
  arXiv  Detail & Related papers  (2020-10-15T17:34:26Z)
• Quantum copy-protection of compute-and-compare programs in the quantum random oracle model [48.94443749859216]
  We introduce a quantum copy-protection scheme for a class of evasive functions known as " compute-and-compare programs" We prove that our scheme achieves non-trivial security against fully malicious adversaries in the quantum random oracle model (QROM) As a complementary result, we show that the same scheme fulfils a weaker notion of software protection, called "secure software leasing"
  arXiv  Detail & Related papers  (2020-09-29T08:41:53Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.