A function which is easy to compute but hard to invert (i.e. find preimages for). The existence of one-way functions implies the possibility of many useful cryptographic schemes. No one-way functions have so far been proven to exist, but many likely candidates exist.

learn more… | top users | synonyms

0
votes
2answers
135 views

How to show something is not a one-way function?

Lets say that $f:\{0,1\}^* \to \{0,1\}^*$ is a strong one way function. Let $h(x)=f(x)||x_n$ where $x_n$ is the $n$th bit of $x$. I understand that $h$ will not be a strong one-way function. However, ...
3
votes
2answers
73 views

Probabalistic Polynomial-time Algorithms & One-way functions

I've been reading up on probabilistic polynomial-time algorithms and one-way functions, and I was hoping to get some guidance on the topic. A textbook I'm reading states the following for one of the ...
2
votes
2answers
129 views

Collision free one way function

I was playing with a function that I think is collision free and uninvertible assuming the hardness of integer factorization. I am unfortunately not as skilled at math as I would like to be, and do ...
0
votes
0answers
16 views

XOR of one-way function [migrated]

Considering the top answer to this question here, http://cs.stackexchange.com/a/10418, wouldn't this counter-example imply that we've inverted $f$? Consider the reduction where we take in $f(x_1)$ and ...
5
votes
1answer
64 views

Choice of the one-way function (OWF) for Lamport signatures

I am studying the Lamport signature scheme, and I found that in many sources (eg: Hash-based Digital Signature Schemes) the input and output bitstring of the OWF and the message digest have the same ...
2
votes
1answer
292 views

Periodic One Way Function

Is there any notion of a periodic OWF? I.e. an OWF $f$ that on every input $x$ in its domain it holds that $f(f(f\ldots f(x))\ldots )=x$ when $f$ applied many times, each time on the previous ...
2
votes
1answer
4k views

What is the meaning of “trapdoor” in cryptography?

I do not really understand the meaning of a "trapdoor" in cryptography, so here are my questions: What is the meaning of trapdoor and how can I convert a word or string using a trapdoor in ...
0
votes
1answer
40 views

What Does This Symbol Mean? (Hardcore Predicates for One-Way Functions)

I am studying Pseudorandom Number Generators and when reading the discussion on One-Way Functions and Hardcore Predicates, I came upon this equation. $$b(x,r)=\displaystyle \bigoplus_jx_jr_j$$ I ...
3
votes
3answers
109 views

Fast forwarding hash functions

We know that a good hash function is a one way/trapdoor function. Easy to calculate one way, harder to work out a previous state. I was wondering if anyone knew a good hashing system that allowed ...
5
votes
2answers
400 views

Why do cryptographic hashes need to be fixed length?

Why do cryptographic hashes need to have a fixed length output? I know that the shallow answer is that an output that varies by key size or file size can leak information somehow, leading to ...
0
votes
0answers
27 views

what is the difference between one way function and hard core predicate?

Does anyone know what the difference between a one way function is and a hard core predicate? Are they related to each other or different?
3
votes
1answer
108 views

Can the round function $F$ in a Feistel Network be practically any non-invertible function?

This question might seem silly, but how true is the fact that the round function $F$ does not have to be invertible? I am curious to know this, because non-invertible functions can be very lossy, ...
2
votes
1answer
39 views

Proving the security of a one-way function with partially known input

Let's say we have a construction like in this question: We have a OWF $h(.)$, a secret salt TXT, and a counter starting at 1, and we compute ...
1
vote
1answer
60 views

Inverting One-Way Functions

One of the conditions that a one-way function has to satisfy is the following: $$Pr[A(f(x))\in f^{-1}(f(x))] \leq negl(n)$$ Now, suppose that we have the following function that's not one way: ...
2
votes
1answer
83 views

Are there full cycle cryptographic/one-way hash primitives?

I'm looking for behavior similiar to that of LCGs, (i.e. input and output sizes are same). Full cycle of $2^{32}$ different inputs generates full cycle of $2^{32}$ different outputs, distribution of ...
5
votes
1answer
62 views

Comparing two definitions of one-way function

I'm reading Rafael Pass's lecture notes on one-way function and came across two definitions. The first one is: A function $f$ is one-way if $f$ can be computed in P.P.T. and there exists no ...
6
votes
1answer
218 views

Can I use the ChaCha core as a 256-bit to 256-bit one-way function?

I'm looking to implement Lamport signatures as a little fun project, and I need a fast one way function that maps $\{0,1\}^{256} \rightarrow \{0,1\}^{256}$. I was wondering whether I could safely use ...
2
votes
1answer
85 views

Possible to determine equivalence of hash codes from different hashing functions?

Let $H_{1}(x)$, $H_{2}(x)$, ..., $H_{n}(x)$ be a list of $n$ secure one-way hash functions such that for a given input $x$ each $H_{i}(x) \neq H_{j}(x)$ when $i \neq j$. Give one hash function to ...
2
votes
1answer
160 views

Does the key schedule function need to be a one-way function?

For some key schedule $e_n(e_{n-1}(k))$ (where $e_{n-1}(k)$ is the result of the previous round) , does $e$ need to be a one-way function? In the case of DES or Rijndael the key schedule doesn't ...
4
votes
1answer
106 views

Hard-core predicates: should the adversary be given $1^n$?

In most (all?) classical sources such as the book of Goldreich (2001), hard-core predicated are defined thus: A polynomial-time computable predicate $b : \{0,1\}^* \to \{0,1\}$ is a hard-core of a ...
2
votes
0answers
71 views

Worst case one way function

the worst-case one way function is defined as follows $$\forall A \exists x : pr(A(f(x))\in f^{-1}(f(x)))\neq 1$$ can you give any example of such function?
1
vote
1answer
329 views

modular exponentiation as a one-way-hash

As far as I can tell most one-way hashes apply some iterated encryption algorithm to the input data. What would be the issues with a one-way hash based on some fixed large prime p and a generator g ...
0
votes
0answers
79 views

Lightweight hash function

I am researching about lightweight hash functions and I've got two related questions: What is the standard or requirement for a hash function in general to be considered lightweight ? Why can it be ...
0
votes
1answer
71 views

How do we know one-way functions can be iterated?

Suppose we have some one-way function $h$. Without further specification of $h$, how can we be sure that we can define another function $g(n) = h(h(n))$? That is, how do we know the range of $h$ is a ...
4
votes
2answers
106 views

Discrete logarithm over prime modulo: small input, large exponent, larger prime

I am considering using modular exponentiation as a one-way hash function. More specifically, here is the scenario. 1) Input ($m$): the input messages are small (16-bit) 2) Exponent ($e$): the ...
0
votes
3answers
115 views

Is the Salsa20/ChaCha20 keystream generation one-way?

Is it possible to recompute the Salsa20 or ChaCha20 key in a realistic time if the keystream and the nonce are given to an attacker? Or is the keystream generation one-way, like a cryptographic has ...
0
votes
1answer
45 views

Deterministic outputs based on non-connected inputs

I am looking for a one way function that can generate outputs deterministically. However, revealing any of the inputs dont allow the person to generate other inputs. E.g: lets say we have a list of ...
4
votes
1answer
316 views

Composing two one-way functions such that the result is not a one-way function

Is it possible to have two distinct one-way functions (called, say, $h$ and $g$) such that their composition $h \circ g = [\, x \mapsto h(g(x)) \,]$ is not one-way?
5
votes
2answers
242 views

Is $f(x)\oplus x$ a one-way function?

Given that $f$ is a OWF and $|f(x)|=|x|$ for all $x$, is $g(x)=f(x)\oplus x$ necessarily also a OWF?
2
votes
2answers
79 views

One-way function definition

I cannot understand why a one-way function $f$ is defined in this way $\text{Pr}(f(A(f(x))) = f(x)) < \frac{1}{p(n)}$ and not $\text{Pr}(A(f(x)) = x) < \frac{1}{p(n)}$ where $A$ is a ...
7
votes
3answers
2k views

Lamport signature: How many signatures are needed to forge a signature?

Lamport signature: Signing the message Note that now Alice's private key is used and should never be used again. The other 256 random numbers that she did not use for the signature she must never ...
0
votes
1answer
131 views

Davies-Meyer Hash Function

So the Davies-Meyer Hash Function is: Hi = Hi−1 ⊕ exi (Hi−1) Say I pick H0 = 1110 0011 And the message x1 = "5" or "0000 0101" Is this the correct way to compute H1? H1 = 1110 0011 ⊕ (0000 0101 ⊕ ...
3
votes
2answers
430 views

Proving that a function is not invert-able (one way function)

I am having problems with proving if the one-way function (http://crypto.stackexchange.com/tags/one-way-function/info) is hard to invert or not. $2^\sqrt {m} $ one-way function $ f: \{0, 1\}^{2m} ...
11
votes
4answers
1k views

Are there cryptographic hash functions that can be computed using only paper and pen without leaking any information about the plaintext?

I am looking for a cryptographic hash function that can be computed by a human using only paper and pen without ever leaking any information about the plaintext on the paper. The cryptographic hash ...
0
votes
1answer
99 views

A one way Function provably reversible at N applications with the same seed?

I'm looking for a function that is generally one way from some secret $F(s, A) \rightarrow Y$, where $A$ is known, $Y$ is produced (also known), and $s$ is kept secret. But whose repeated application ...
1
vote
1answer
114 views

Question about second preimage resistance of hash function combiner

Let $\Pi=(Gen_1,H_1)$ and $\Pi=(Gen_2,H_2)$ be two hash functions. Define $(Gen, H)$ so that $Gen$ runs $Gen_1$ and $Gen_2$ obtaining $s_1$ and $s_2$ respectively. Then let ...
2
votes
1answer
439 views

Hash collision resistance requirements for Lamport signatures

According to the original paper, Lamport one-time signature scheme uses two one-way functions: $F$ and $G$. The former one, $F$, is used to create a public key by hashing elements of the private key ...
2
votes
1answer
169 views

One Way function and Merkle Damgård

Is it possible keep the "one wayness property" of certain one way function in Merkle-Damgård construction? I'm asking this question because according to Collision-Resistant hashing: Towards making ...
3
votes
1answer
125 views

Why is Lamport-Diffie secure?

Why is Lamport-Diffie secure? I note that there is a demonstration based on onewayness (in the book postquantum cryptography). But a one way function is not sufficient to ensure that it can not infer ...
2
votes
1answer
295 views

Help in understanding exactly how lattices used as one way functions for hashing

I am doing a cryptography course via long distance and we have been given an assignment which is based on lattice-based cryptography. I have spent the majority of the past week sifting through papers ...
0
votes
2answers
74 views

Building cryptographic primitives using additive maps?

Suppose we have a one-way function F(x) that exhibits the property F(a + b) = F(a) + F(b). Such a function could be used as a cryptographic primitive, no?
1
vote
1answer
97 views

Definition of one-way functions: randomly-chosen point vs every point

Notation: $\Sigma^k$ is the set of $k$-strings on the alphabet $\Sigma$; $\Sigma^\ast$ is the set of all finite dimensional strings on the alphabet $\Sigma$. In the context of computer-science a ...
4
votes
1answer
489 views

Disadvantages of one-way accumulators?

One-way accumulators are built upon a (quasi)-commutative one-way function. With quasi-commutativity, I refer to the following property: For $f : X \times Y \to X$, it is true that $f(f(x, y_1), y_2) ...
2
votes
2answers
230 views

One-way function and uninvertible function [closed]

How can I prove the following: If $f$ is a one-way function, then it is an uninvertible function?
2
votes
1answer
264 views

Proving that a function is not a OWF (One-way-function)

I was trying to prove that a given function is not a one way function and I was not sure how to do it because maybe I had unclear what a one way function was (OWF). The definition that I have for a ...
5
votes
1answer
296 views

One-way permutation over a small interval?

I am wondering what concrete computable functions we know that are a permutation over an integer interval of parameterizable size $s$, for relatively small $s$ starting circa $2^{64}$, to perhaps ...
4
votes
1answer
155 views

Reason for difference in assumptions for practical private-key and public-key crypto

Theoretical cryptography tells us that everything in the world of private-key cryptography (CCA-secure symmetric encryption, message authentication codes, etc.) can be built from one-way functions and ...
3
votes
2answers
529 views

unique one-way hash

For a 10-digits numeric domain (swedish social security numbers), is there a hash function with the following properties? no two numbers result in the same hash it is not possible to deduce the ...
4
votes
1answer
195 views

Keyed digest function with odds of collision below the birthday bound?

I wonder if it is possible to devise a function $F(K,S,R_S)\mapsto D$ where: $K$ is some key (I have freedom on $K$, it could even be generated by a trusted party); $S$ is in $\{0,1\}^s$, say ...
6
votes
3answers
478 views

Slow one-way pseudo-random permutation?

I'm looking for a slow one-way pseudo-random permutation; or in other words a block cipher $E_K: P\in\{0,1\}^b\mapsto C\in\{0,1\}^b$ with moderate block size $b\approx 64$ bits, wide key $K$, ...