CODEWITHSUNDEEP
c++algorithmmathhashcryptography
organicoman
organicoman

Reputation: 154

is there a hashing function that satisfies the following

is there a hashing algorithm that satisfies the following?

let "hash_funct" be a hashing function that takes two args, and returns a hash value. so all the following will be true

Hash1 = hash_funct(arg1, arg2) <=> hash_funct(Hash1, arg1) = hash_funct(Hash1, arg2) = Hash1;

Can anyone point me to this Algorithm? or if it doesn't exist, can anyone collaborate with me to invent it?

more explanation:

imagine a set S={A,B,C,D}, and the Hashing function above.

if we can make: Hash1 = hash_funct(A,B,C,D), then we can check if an element X is in the set by checking the hash result of hash_funct(Hash1,X) == Hash1 ? belogns to the set : doesn't belong

with this property we make checking the exisitance of an element in a set O(1) instead of O(NlogN)

Upvotes: 0

Views: 128

Answers (2)

kelalaka
kelalaka

Reputation: 5636

What you are looking for is the Accumulators. Currently, they are very popular with digital coins @youtube

From Wikipedia;

A cryptographic accumulator is a one-way membership function. It answers a query as to whether a potential candidate is a member of a set without revealing the individual members of the set.

For example this paper;

We show how to use the RSA one-way accumulator to realize an efficient and dynamic authenticated dictionary, where untrusted directories provide cryptographically verifiable answers to membership queries on a set maintained by a trusted source

With a Straightforward Accumulator-Based Scheme;

  • Query: When asking for a proof of membership.
  • Verification: check the validity of the answer.
  • Updates: Insertion and deletions

are available.

Upvotes: 2

Sumeet
Sumeet

Reputation: 8292

I suppose Highest common factor(Hcf) will fit right here. Let a and b be two numbers with x as their highest common factor.

hcf(a,b) = x.

This means a = x*m and b = x*n. This clearly means that:

hcf(x,x*m) = hcf(x,x*n) = hcf(x*n,x*m) = x

Upvotes: 2

Related Questions