Questions tagged [collision-resistance]

Difficulty of finding two different inputs that hash to the same value

20 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
11
votes
0answers
133 views

Space complexity of quantum collision search?

Is there a known way to reduce the space complexity of quantum collision search (PDF) beyond what is offered by the built-in time-space tradeoff, while keeping the time complexity significantly below ...
3
votes
0answers
39 views

Hash multiset to point on elliptic curve where $A = 0$

I want to hash a multiset to a point on the elliptic curve $y^2 = x^3 + 3$ over a finite field of some 254-bit prime order, where $P = 3 \pmod 4$. Moreover, I want this hash to be incremental, in that ...
3
votes
0answers
60 views

Impossible to construct collision resistant hash function from one way function

[Simon 98] showed that it is impossible to construct collision resistant hash function from one way functions in a black-box way. I read the paper but barely understood it. Is there any source, where ...
2
votes
0answers
48 views

Estimating the Security of SIS-Based Signature, by verifiying a subset of coordinates?

As I understood, the GPV signature scheme works as follows: KeyGen($1^n$) : Generate a Lattice with public $A \in Z_q^{n.m}$ and a secret trapdoor $t$. Sign $m$: compute $\vec y = H(m) \in Z_q^n$ ...
2
votes
0answers
118 views

Does there exist a highly irreversible hash function or a highly irreversible pseudo-random number generator?

In my previous question, I asked about potential symmetric cryptosystems which are designed to be computed by a reversible computer. I am now wondering if there are any cryptographic hash functions ...
2
votes
0answers
153 views

Hash function for sets with efficient membership testing

Is it possible to construct a collision-resistant function that hashes a set of values but also allows membership testing? Essentially, I'm looking for a pair of functions, $\text{H} : \{0,1\}^{**} \...
2
votes
0answers
961 views

Question about modifying the MD5 plain text to cause a collision

I was trying to understand MD5 and got stuck with this question, its from Michael sipser's book on Information security Principles and Practice, 2nd edition The MD5 collision in Problem 25 is said ...
1
vote
1answer
88 views

Birthday attack on hash functions derived from a collision-resistant hash function

$H_1$ is a collision-resistant hash function with an $L$-bit output. 2 hash functions are created based on it as follows: $$H_2((k_1,k_2);m) = (H_1(k_1;m), \space H_1(k_2;m))$$ $$H_3((k_1,k_2);(m_1,...
1
vote
0answers
26 views

Round counts and permutation usage for hashing for a Merkle tree

Are there any current recommendations for performant hashing in a Merkle tree? It appears the hash based signatures in Sphincs use Blake2 everywhere (see Table 1 on page 22 of https://sphincs.cr.yp....
1
vote
0answers
106 views

Show that the CBC-MAC construction applied to a PRP is not collision resistant

I'm trying answer the following question. Yes, it is a homework question, so I'm not asking for the answer directly but would like to get some pointers on how to solve it. So far I have spent several ...
1
vote
0answers
65 views

Extendable hash collision resistance of multiplication

I have a hash function $HashSet(A) = H(a_1) *\cdots * H(a_n)$, where $A = \{a_1,\ldots,a_n\}$ and $H$ is a hash function which generates values of $b$ bits (and $H$ has no collision attack that ...
1
vote
0answers
141 views

How many times does a hash function have to be evaluated?

I have the following homework assignment: $n$ is an even number, $1^n$ and $0^n$ are $n$-bit strings and $x$, $y$ and $z$ are arbitrary strings of length $n$. How many evaluations of hash ...
1
vote
0answers
55 views

When we use a PRF to pad a message, do we need to worry about the PRF's output range and/or probability of collision?

My question is related to: How to contruct a pseudorandom with a specific property Collision in pseudorandom function when two different keys are used Question: When we use a pseudorandom function ...
1
vote
0answers
158 views

TCR hash functions from MD5

I'm reading Collision-Resistant Hashing: Towards Making UOWHFs Practical (pag. 10 and 11) and here say The most direct way to construct a TCR hash function is to key a function like MD5 or SHA-1. ...
1
vote
0answers
43 views

MD Construction Doesn't Propagate TCR

I'm reading a proof of the proposition of CollisionResistant Hashing Towards Making UOWHFs Practical Suppose there exists a compression function $F: \Sigma^k\times\Sigma^{c+m'} \rightarrow \Sigma^...
0
votes
0answers
63 views

collision resistance of a composed hash function

Given a collision-resistant hash function $H(x)$, say SHA256, and I devise another hash function by $H'(x)=\sum^{m}_{1}H(x||i) \mod p$. The summation is defined on finite field of prime order $p$. ...
0
votes
0answers
56 views

Function F is not resistant to collisions

If we have the following block cipher, E(k,m), why is f(x,y) not collision resistant? $$f(x,y) = E(y,x) \oplus y$$
0
votes
0answers
51 views

Collision resistance of a function which chooses the hash from a large table of hashes

Let's say you know a (possibly) large table of ids and some corresponsing hashes $h_{ID_j} = H(ID_j | secret_j)$. The resulting table looks like $$ ID_1 | h_{ID_1} $$ $$ ID_2 | h_{ID_2} $$ $$ ... $$ $...
0
votes
0answers
22 views

Security implications of an extra inner encrypt for a single block Matyas-Meyer-Oseas hash function

Was giving some thought to simple MMO constructions for fast single block hash functions for things like PQ crypto. There's Haraka, but that's not standard and readily available while simple AES is in ...
0
votes
0answers
30 views

When looking for collisions of MD4, how does the 'Multi-step Modification' work in the paper of Wang et. al?

In part 4.2 of this paper, the writers introduced a technique called 'Multi-step Modification', here I got some questions. How does the Multi-step Modification ensure that we will not change any ...