Ideal Pseudorandom Codes

• URL: http://arxiv.org/abs/2411.05947v1
• Date: Fri, 08 Nov 2024 20:22:14 GMT
• Title: Ideal Pseudorandom Codes
• Authors: Omar Alrabiah, Prabhanjan Ananth, Miranda Christ, Yevgeniy Dodis, Sam Gunn,
• Abstract summary: 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.
• Score: 8.382679821011134
• License:
• Abstract: Pseudorandom codes are error-correcting codes with the property that no efficient adversary can distinguish encodings from uniformly random strings. They were recently introduced by Christ and Gunn [CRYPTO 2024] for the purpose of watermarking the outputs of randomized algorithms, such as generative AI models. Several constructions of pseudorandom codes have since been proposed, but none of them are robust to error channels that depend on previously seen codewords. This stronger kind of robustness is referred to as adaptive robustness, and it is important for meaningful applications to watermarking. In this work, we show the following. - Adaptive robustness: We show that the pseudorandom codes of Christ and Gunn are adaptively robust, resolving a conjecture posed by Cohen, Hoover, and Schoenbach [S&P 2025]. - Ideal security: We define an ideal pseudorandom code as one which is indistinguishable from the ideal functionality, capturing both the pseudorandomness and robustness properties in one simple definition. We show that any adaptively robust pseudorandom code for single-bit messages can be bootstrapped to build an ideal pseudorandom code with linear information rate, under no additional assumptions. - CCA security: In the setting where the encoding key is made public, we define a CCA-secure pseudorandom code in analogy with CCA-secure encryption. We show that any adaptively robust public-key pseudorandom code for single-bit messages can be used to build a CCA-secure pseudorandom code with linear information rate, in the random oracle model. These results immediately imply stronger robustness guarantees for generative AI watermarking schemes, such as the practical quality-preserving image watermarks of Gunn, Zhao, and Song (2024).

Related papers

• Efficient Quality Estimation of True Random Bit-streams [5.441027708840589]
  This paper reports the implementation and characterization of an on-line procedure for the detection of anomalies in a true random bit stream. The experimental validation of the approach is performed upon the bit streams generated by a quantum, silicon-based entropy source.
  arXiv  Detail & Related papers  (2024-09-09T12:09:17Z)
• Edit Distance Robust Watermarks for Language Models [29.69428894587431]
  Motivated by the problem of detecting AI-generated text, we consider the problem of watermarking the output of language models with provable guarantees. We aim for watermarks which satisfy: (a) undetectability, a cryptographic notion introduced by Christ, Gunn & Zamir (2024) and (b) robustness to channels which introduce a constant fraction of adversarial insertions, substitutions, and deletions.
  arXiv  Detail & Related papers  (2024-06-04T04:03:17Z)
• Error Correction Capabilities of Non-Linear Cryptographic Hash Functions [56.368766255147555]
  Linear hashes are known to possess error-correcting capabilities. In most applications, non-linear hashes with pseudorandom outputs are utilized instead. We show that non-linear hashes might also exhibit good error-correcting capabilities.
  arXiv  Detail & Related papers  (2024-05-02T17:26:56Z)
• Correcting Subverted Random Oracles [55.4766447972367]
  We prove that a simple construction can transform a "subverted" random oracle which disagrees with the original one at a small fraction of inputs into an object that is indifferentiable from a random function. Our results permit future designers of cryptographic primitives in typical kleptographic settings to use random oracles as a trusted black box.
  arXiv  Detail & Related papers  (2024-04-15T04:01:50Z)
• 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)
• Random Boxes Are Open-world Object Detectors [71.86454597677387]
  We show that classifiers trained with random region proposals achieve state-of-the-art Open-world Object Detection (OWOD) We propose RandBox, a Fast R-CNN based architecture trained on random proposals at each training. RandBox significantly outperforms the previous state-of-the-art in all metrics.
  arXiv  Detail & Related papers  (2023-07-17T05:08:32Z)
• Machine Learning needs Better Randomness Standards: Randomised Smoothing and PRNG-based attacks [14.496582479888765]
  We consider whether attackers can compromise an machine learning system using only the randomness on which they commonly rely. We demonstrate an entirely novel attack, where an attacker backdoors the supplied randomness to falsely certify either an overestimate or an underestimate of robustness for up to 81 times. We advocate updating the NIST guidelines on random number testing to make them more appropriate for safety-critical and security-critical machine-learning applications.
  arXiv  Detail & Related papers  (2023-06-24T19:50:08Z)
• ReCode: Robustness Evaluation of Code Generation Models [90.10436771217243]
  We propose ReCode, a comprehensive robustness evaluation benchmark for code generation models. We customize over 30 transformations specifically for code on docstrings, function and variable names, code syntax, and code format. With human annotators, we verified that over 90% of the perturbed prompts do not alter the semantic meaning of the original prompt.
  arXiv  Detail & Related papers  (2022-12-20T14:11:31Z)
• Testing randomness of series generated in Bell's experiment [62.997667081978825]
  We use a toy fiber optic based setup to generate binary series, and evaluate their level of randomness according to Ville principle. Series are tested with a battery of standard statistical indicators, Hurst, Kolmogorov complexity, minimum entropy, Takensarity dimension of embedding, and Augmented Dickey Fuller and Kwiatkowski Phillips Schmidt Shin to check station exponent. The level of randomness of series obtained by applying Toeplitz extractor to rejected series is found to be indistinguishable from the level of non-rejected raw ones.
  arXiv  Detail & Related papers  (2022-08-31T17:39:29Z)
• Cryptography from Pseudorandom Quantum States [6.164147034988822]
  One-way functions imply the existence of pseudorandom states, but Kretschmer (TQC'20) recently constructed an oracle relative to which there are no one-way functions but pseudorandom states still exist. We study the intriguing possibility of basing interesting cryptographic tasks on pseudorandom states. A consequence of (a) is that pseudorandom states are sufficient to construct maliciously secure multiparty protocols in the dishonest majority setting.
  arXiv  Detail & Related papers  (2021-12-18T22:53:16Z)
• Improved, Deterministic Smoothing for L1 Certified Robustness [119.86676998327864]
  We propose a non-additive and deterministic smoothing method, Deterministic Smoothing with Splitting Noise (DSSN) In contrast to uniform additive smoothing, the SSN certification does not require the random noise components used to be independent. This is the first work to provide deterministic "randomized smoothing" for a norm-based adversarial threat model.
  arXiv  Detail & Related papers  (2021-03-17T21:49: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.