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

• (Quantum) Indifferentiability and Pre-Computation [50.06591179629447]
  Indifferentiability is a cryptographic paradigm for analyzing the security of ideal objects. Despite its strength, indifferentiability is not known to offer security against pre-processing attacks. We propose a strengthening of indifferentiability which is not only composable but also takes arbitrary pre-computation into account.
  arXiv  Detail & Related papers  (2024-10-22T00:41:47Z)
• Learning Randomized Algorithms with Transformers [8.556706939126146]
  In this paper, we enhance deep neural networks, in particular transformer models, with randomization. We demonstrate for the first time that randomized algorithms can be instilled in transformers through learning, in a purely data- and objective-driven manner.
  arXiv  Detail & Related papers  (2024-08-20T13:13:36Z)
• 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)
• 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)
• 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)

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.