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

11
votes
4answers
877 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 ...
9
votes
3answers
254 views

How hard is to invert the function that computes the middle-bits of (x^2)?

I'm designing a function f that should be moderately hard to invert and very fast to evaluate in a modern CPU. The function will be used in a proof-of-work function. I've read that the middle-bits of ...
8
votes
2answers
954 views

What is a hard-core predicate?

I read this article on Wikipedia: Hard-core predicate. Still I don't understand what exactly is a hard-core predicate. Is it possible to put this in simple English terminology, and perhaps with a ...
7
votes
3answers
1k 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 ...
6
votes
3answers
438 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$, ...
5
votes
2answers
302 views

Is there a hash algorithm that is slow to calculate but relatively fast to check?

Or more generally, is there a function or algorithm that is slow to calculate/execute, has a reliable execution time, and has a result that can be tested much more quickly than the calculation took?
5
votes
3answers
325 views

What other one-way functions are used in cryptosystems?

For RSA and El Gamal (and most other public key cryptosystems), one of the key ideas is that factoring and finding discrete logarithms are hard. There are other systems that rely on certain properties ...
5
votes
2answers
281 views

Pen-and-paper one-way function for externally-anonymous survey

When conducting surveys, an Administrator might send an Enumerator to survey a Respondent. For "sensitive" questions (e.g. about embarrassing behavior), the Respondent may be fine with the truth being ...
5
votes
1answer
1k views

Is the AES Key Schedule weak?

After reading this paper entitled Key Recovery Attacks of Practical Complexity on AES Variants With Up To 10 Rounds I was left wondering why the key schedule of AES is invertable. In the paper the ...
5
votes
1answer
51 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 ...
4
votes
5answers
4k views

Are there hash algorithms with variable length output?

I understand that for example MD5 produces a 128 bit hash value from a given text of variable size. My question is if there is a hash-like algorithm that will produce a hash value where one can ...
4
votes
2answers
184 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?
4
votes
1answer
150 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 ...
4
votes
1answer
183 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 ...
4
votes
2answers
71 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 ...
3
votes
1answer
246 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?
3
votes
2answers
370 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 ...
3
votes
2answers
230 views

Quadratic residuosity problem reduction to integer factorization

How can one show how to reduce the quadratic residuosity problem to an integer factorization?
3
votes
2answers
388 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} ...
3
votes
1answer
144 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 ...
3
votes
1answer
146 views

What does it mean to be simultaneously hardcore?

In this paper the term "simultaneously hardcore" is defined as: "We say that a block of bits of $x$ are simultaneously hard-core for a one-way function $f(x)$, if given $f(x)$ they cannot be ...
3
votes
1answer
233 views

Is there a cryptographic hash function that can be performed with pencil and paper?

Imagine I'm signing up for the 99th new web site this month. I somehow take my secret key (which I have written down on a card in my wallet) and the domain name of the site and feed them both into ...
3
votes
1answer
260 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 ...
3
votes
1answer
121 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
5answers
1k views

Using one-way hash functions as the encryption method

Suppose two parties want to communicate securely with each other (Bob and Alice) using a simple messaging system in English. There are approximately 180,000 currently used words in the English ...
2
votes
1answer
3k 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 ...
2
votes
3answers
397 views

Can one build a one-way function from AES?

We change the AES block cipher encryption: we delete the key schedule algorithm the user now provides a string of 1408 bits we divide the string to 11 sub keys, and use them directly in the ...
2
votes
1answer
206 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 ...
2
votes
1answer
365 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
249 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
188 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
2answers
329 views

Are there any bijective one-way functions not based on number-theoretic hardness assumptions?

I'm trying to find a bijective function $y=F(x)$ which should be easy to compute in one direction but hard to compute in the other, where the one-way property is not based on a number theoretic ...
2
votes
1answer
122 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 ...
2
votes
1answer
151 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 ...
2
votes
2answers
60 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 ...
2
votes
1answer
301 views

Is SHA-256 a one way permutation when restricting the domain to {0,1}^256? [duplicate]

Suppose we consider the space of $\lbrace 0,1 \rbrace^{256}$ as the domain and SHA-256 as our hash function. Does SHA-256 become a one way permutation? Has anyone tried to prove this? Or can it be ...
2
votes
0answers
143 views

How can I construct a distinguisher given an inverter?

Let $ PRG: \{ 0, 1\}^n \rightarrow \{ 0, 1\}^{n+s}$ be a pseudo random generator and let $A$ be an inverter that runs in polynomial time, specifically: $\large \mathbb P_{d \leftarrow PRG(U_n)}[ A(d) ...
2
votes
0answers
76 views

partial-domain permutation and strong assumption

Quoting "Verified Security of Redundancy-Free Encryption from Rabin and RSA", Chapter 2 (on page 4): OAEP was proved IND-CCA-secure by Fujisaki et al. [28] under the assumption that the underlying ...
1
vote
1answer
118 views

Pseudo Random Generator (PRG) from Rabin function

I'm trying to make a PRG using the Rabin function. The code (in Java) I wrote to implement the function is: ...
1
vote
1answer
180 views

what is an injective trapdoor function?

The answer to this question at Crypto.SE is clear about what a trapdoor function is, but what makes a trapdoor function "injective"?
1
vote
1answer
105 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 ...
1
vote
1answer
90 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 ...
1
vote
2answers
138 views

One-way function and $EXP$

All examples of one-way functions I have see till now are closely related to the assumption that $NP\neq P $ (or even weaker ones, such as $UP\neq P$), but why not considering the theorem $P\neq EXP$? ...
1
vote
1answer
122 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 ...
1
vote
1answer
99 views

constructing QR-like one way function

I am wondering whether the following form is a one way function with collision resistance: $$ax^2+by^2 \mod p$$ where $a$ and $b$ are given, and $p$ is a prime number. Since the QR (quadratic ...
1
vote
1answer
240 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
3answers
62 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
60 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 ...
0
votes
1answer
181 views

Weak One Way Function

Show The function $mult(a,b)$ is weak one way if the Integer Factorization Assumption is true. I am read the proof of this enunciated but I want know if I understand this in my way. The proof use the ...
0
votes
1answer
26 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 ...