3
$\begingroup$

This is not a formal but intuitive concept of one-wayness. The intuition is that if you have a combinatorial object that requires $n$ bits to describe. A one way operation introduces noise in random bit locations such that $\epsilon n$ bits are modified. Then only exponential time algorithm can invert the function. Are there any known candidate one way function around (similar) idea.

$\endgroup$
4
  • $\begingroup$ Look at "One-way Functions are Essential for Complexity Based Cryptography" by Impagliazzo and Luby, 1989, DOI: 10.1109/SFCS.1989.63483. There is a definition of one-way function. $\endgroup$ Commented Aug 9, 2022 at 20:04
  • $\begingroup$ I am aware of the standard definition of one way functions. My question is about alternate notions. $\endgroup$ Commented Aug 9, 2022 at 20:15
  • $\begingroup$ I think you may want to read this as well. Note that it solves this for exponential time using RSA at the bottom. Now for security... $\endgroup$
    – Maarten Bodewes
    Commented Aug 9, 2022 at 22:39
  • $\begingroup$ There is some contradiction within your question. Information theoretic security is complete and thus >>>>>> exponentially breakable security. In effect it's perfect. That's why one time pads are used. As described by Daniel below... $\endgroup$
    – Paul Uszak
    Commented Jan 7, 2023 at 13:44

2 Answers 2

3
$\begingroup$

There are multiple notions of one-way functions which do provide information-theoretic security guarantees. I will cover three things that come to mind, but there are others.

(1) The first example that comes to mind is bounded-storage cryptography: a branch of cryptography that operates on the assumption that the adversary storage (as opposed to runtime) is limited. In this setting, you can actually get cryptographic primitives without relying on any computational assumptions.

Here is a simple example: assume an $m\times n$ matrix H is streamed row-by-row (let me call $H_i$ the $i$-th row) together with $\langle H_i,x\rangle$, where $x$ is a secret size-$n$ vector (everything is over some finite field). Then by a celebrated result of Ran Raz, if your memory is bounded by $n^2/20$, it is information-theoretically impossible to recover $x$ unless you get $m > 2^{\Omega(n)}$ samples.

This result has been used to design unconditional private-key encryption schemes in the bounded-storage model (this is in Ran Raz’s paper) as well as other primitives such as key exchange, oblivious transfer, and commitments (see here).

(2) A second thing that comes to mind, which might be slightly closer in spirit to what you had in mind, is cryptography over noisy channels. Here, we also don’t make any cryptographic assumptions: rather, we make the physical assumptions that parties communicate over channels that randomly flip the bits transmitted, with some probability. This model was introduced by Crepeau and Kilian here, and has inspired many works afterwards. The paper establishes that oblivious transfer (a fundamental cryptographic task) can be realized unconditionally over noisy channels. Here again, everything is purely information-theoretic.

(3) Eventually, information-theoretic one-way functions also exist in the fine-grained model, where the adversary is assumed to be in a low complexity class. Typically, if the parties are modeled as constant-depth Boolean circuits (in $\mathsf{AC}^0$), there are one-way functions computable in this class, which are unconditionally secure against all adversaries in this class (see here). A standard example is parity: sampling $(x, \mathsf{parity}(x))$ where the distribution of $x$ is uniform over $\{0,1\}^n$ can be done efficiently in $\mathsf{AC}^0$, but given $x$, distinguishing $\mathsf{parity}(x)$ from random is impossible for $\mathsf{AC}^0$ circuits (it’s a classical result of Razborov).

Granted, this might be a bit more distant from what you had in mind, since a bound on the adversary power is assumed, but it is information-theoretic in the sense of not requiring any cryptographic assumption.

$\endgroup$
1
  • $\begingroup$ Upvoted for the inclusion of a primitive in the bounded storage model. I hope to see more of this on this forum :) $\endgroup$ Commented Jan 7, 2023 at 18:34
1
$\begingroup$

I'm not sure if this answers your question, but when talking about information theoretically secure hashing/MAC, people often mean the Carter-Wegman construction of applying a one-time pad to a universal hash function.

The one-time pad be the same size as the hash function and have full entropy (thus needing $n$-bits to describe) and the output will then have the same property. However, the Carter-Wegman MAC can only be evaluated/validated (with non-negligible probability) by someone in possession of the one time pad.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.