New constructions of pseudorandom codes

• URL: http://arxiv.org/abs/2409.07580v1
• Date: Wed, 11 Sep 2024 19:14:39 GMT
• Title: New constructions of pseudorandom codes
• Authors: Surendra Ghentiyala, Venkatesan Guruswami,
• Abstract summary: Pseudorandom error-correcting codes (PRCs) are a new cryptographic primitive with applications in watermarking generative AI models. We show that if both the planted hyperloop assumption introduced in [BKR23] and security of a version of Goldreich's PRG hold, then there exist public-key PRCs for which no efficient adversary can distinguish a number of codewords from random. We show how to construct secret-key PRCs of length $O(n)$ which are $textitunconditionally$ indistinguishable random by $textpoly(
• Score: 23.22566380210149
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Introduced in [CG24], pseudorandom error-correcting codes (PRCs) are a new cryptographic primitive with applications in watermarking generative AI models. These are codes where a collection of polynomially many codewords is computationally indistinguishable from random, except to individuals with the decoding key. In this work, we examine the assumptions under which PRCs with robustness to a constant error rate exist. 1. We show that if both the planted hyperloop assumption introduced in [BKR23] and security of a version of Goldreich's PRG hold, then there exist public-key PRCs for which no efficient adversary can distinguish a polynomial number of codewords from random with better than $o(1)$ advantage. 2. We revisit the construction of [CG24] and show that it can be based on a wider range of assumptions than presented in [CG24]. To do this, we introduce a weakened version of the planted XOR assumption which we call the weak planted XOR assumption and which may be of independent interest. 3. We initiate the study of PRCs which are secure against space-bounded adversaries. We show how to construct secret-key PRCs of length $O(n)$ which are $\textit{unconditionally}$ indistinguishable from random by $\text{poly}(n)$ time, $O(n^{1.5-\varepsilon})$ space adversaries.

Related papers

• Ideal Pseudorandom Codes [8.382679821011134]
  Pseudorandom codes are error-correcting codes with the property that no efficient adversary can distinguish encodings from uniformly random strings. Several constructions of pseudorandom codes have since been proposed, but none of them are robust to error channels that depend on previously seen codewords. We show that any adaptively robust pseudorandom code for single-bit messages can be used to build a CCA-secure pseudorandom code.
  arXiv  Detail & Related papers  (2024-11-08T20:22:14Z)
• Towards Unconditional Uncloneable Encryption [1.18749525824656]
  Uncloneable encryption is a cryptographic primitive which encrypts a classical message into a quantum ciphertext. We show that the adversary's success probability in the related security game converges quadratically as $1/2+1/ (2sqrtK)$, where $K$ represents the number of keys and $1/2$ is trivially achievable.
  arXiv  Detail & Related papers  (2024-10-30T14:40:06Z)
• Crooked indifferentiability of the Feistel Construction [53.572703605492904]
  The Feistel construction is a fundamental technique for building pseudorandom permutations and block ciphers. This paper shows that a simple adaptation of the construction is resistant, even to algorithm substitution attacks.
  arXiv  Detail & Related papers  (2024-04-15T04:29:24Z)
• Pseudorandom Error-Correcting Codes [0.716879432974126]
  We build pseudorandom codes that are robust to cryptographic substitution and deletion errors. We present an undetectable watermarking scheme for outputs of random substitutions and deletions. Our second application is to steganography, where a secret message is hidden in innocent-looking content.
  arXiv  Detail & Related papers  (2024-02-14T18:17:45Z)
• 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)
• Towards Optimal Statistical Watermarking [95.46650092476372]
  We study statistical watermarking by formulating it as a hypothesis testing problem. Key to our formulation is a coupling of the output tokens and the rejection region. We characterize the Uniformly Most Powerful (UMP) watermark in the general hypothesis testing setting.
  arXiv  Detail & Related papers  (2023-12-13T06:57:00Z)
• Signatures From Pseudorandom States via $\bot$-PRFs [0.11650821883155184]
  We introduce new definitions for $bot$-PRG and $bot$-PRF. Our main application is a (quantum) digital signature scheme with classical public keys and signatures.
  arXiv  Detail & Related papers  (2023-11-01T20:54:50Z)
• 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)
• Linear Contextual Bandits with Adversarial Corruptions [91.38793800392108]
  We study the linear contextual bandit problem in the presence of adversarial corruption. We present a variance-aware algorithm that is adaptive to the level of adversarial contamination $C$.
  arXiv  Detail & Related papers  (2021-10-25T02:53:24Z)
• 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)
• Stochastic Linear Bandits Robust to Adversarial Attacks [117.665995707568]
  We provide two variants of a Robust Phased Elimination algorithm, one that knows $C$ and one that does not. We show that both variants attain near-optimal regret in the non-corrupted case $C = 0$, while incurring additional additive terms respectively. In a contextual setting, we show that a simple greedy algorithm is provably robust with a near-optimal additive regret term, despite performing no explicit exploration and not knowing $C$.
  arXiv  Detail & Related papers  (2020-07-07T09:00:57Z)

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.