Correcting Subverted Random Oracles
- URL: http://arxiv.org/abs/2404.09442v1
- Date: Mon, 15 Apr 2024 04:01:50 GMT
- Title: Correcting Subverted Random Oracles
- Authors: Alexander Russell, Qiang Tang, Moti Yung, Hong-Sheng Zhou, Jiadong Zhu,
- Abstract summary: 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.
- Score: 55.4766447972367
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The random oracle methodology has proven to be a powerful tool for designing and reasoning about cryptographic schemes. In this paper, we focus on the basic problem of correcting faulty or adversarially corrupted random oracles, so that they can be confidently applied for such cryptographic purposes. 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, even if the adversary is made aware of all randomness used in the transformation. Our results permit future designers of cryptographic primitives in typical kleptographic settings (i.e., those permitting adversaries that subvert or replace basic cryptographic algorithms) to use random oracles as a trusted black box.
Related papers
- Permutation Superposition Oracles for Quantum Query Lower Bounds [14.957648729581502]
We show how to use the resulting oracle simulation to bound the success probability of an algorithm for any predicate on input-output pairs.
We show that the one-round sponge construction is unconditionally preimage resistant in the random permutation model.
arXiv Detail & Related papers (2024-07-12T19:27:13Z) - Fast White-Box Adversarial Streaming Without a Random Oracle [48.45771871410984]
We consider a strong white-box adversarial model, in which the adversary has access to all past random coins and the parameters used by the streaming algorithm.
We focus on the sparse recovery problem and extend our result to other tasks such as distinct element estimation.
We construct a near-optimal solution for the sparse recovery problem in white-box adversarial streams, based on the subexponentially secure Learning with Errors assumption.
arXiv Detail & Related papers (2024-06-10T21:23:19Z) - Simultaneous Haar Indistinguishability with Applications to Unclonable Cryptography [5.360892674012226]
We present a new approach to unclonable encryption via a reduction to a novel question about nonlocal quantum state discrimination.
Our main technical result is showing that the players cannot distinguish between each player receiving independently-chosen Haar random states versus all players receiving the same Haar random state.
We also show other implications to single-decryptor encryption and leakage-resilient secret sharing.
arXiv Detail & Related papers (2024-05-16T17:30:55Z) - 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) - Provably Secure Disambiguating Neural Linguistic Steganography [66.30965740387047]
The segmentation ambiguity problem, which arises when using language models based on subwords, leads to occasional decoding failures.
We propose a novel secure disambiguation method named SyncPool, which effectively addresses the segmentation ambiguity problem.
SyncPool does not change the size of the candidate pool or the distribution of tokens and thus is applicable to provably secure language steganography methods.
arXiv Detail & Related papers (2024-03-26T09:25:57Z) - 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) - Towards an Accurate and Secure Detector against Adversarial
Perturbations [58.02078078305753]
Vulnerability of deep neural networks to adversarial perturbations has been widely perceived in the computer vision community.
Current algorithms typically detect adversarial patterns through discriminative decomposition of natural-artificial data.
We propose an accurate and secure adversarial example detector, relying on a spatial-frequency discriminative decomposition with secret keys.
arXiv Detail & Related papers (2023-05-18T10:18:59Z) - 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) - Tight Bounds for Inverting Permutations via Compressed Oracle Arguments [0.0]
Zhandry studied interactions between quantum query algorithms and the quantum oracle corresponding to random functions.
We introduce a similar interpretation for the case when the oracle corresponds to random permutations instead of random functions.
Because both random functions and random permutations are highly significant in security proofs, we hope that the present framework will find applications in quantum cryptography.
arXiv Detail & Related papers (2021-03-16T11:05:48Z)
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.