4
$\begingroup$

What I am looking for is a function that meets the following criteria:

  • For each possible input (assume integers from [0, 255]), there must be trillions of possible outputs so as to prevent preimage attacks and is hence probabilistic.

  • The function must be a one-way hash, so given an output the input cannot be deduced.

  • The outputs must exhibit additive homomorphism such that some operation on f(a) and f(b) will equal f(a+b).

Is such a scheme possible? I've read many papers that have developed methods close to this, but none that I understand fully meet my criteria.

Paillier exhibits these properties, except it's an encryption scheme as opposed to a hash, meaning it requires public and private keys. In this scheme, there should be no feasible way to "decrypt" an output.

I've found several homomorphic hashing schemes, but each one seems to fall short in some way:

  • LtHash is interesting, but not probabilistic, as an input maps to only one output and a small input set should be easy to preimage.
  • The cryptosystem proposed in this paper seems like it could be a good fit, but I don't entirely understand how the global vs per-publisher hashing would work.
  • This blog post outlines a similar mechanism, but I'm not sure if it's still vulnerable to pre-imaging and always maintains it's homomorphic properties.

I've read through StackExchange, and I've only seen a few posts in the last few years relevant to the question, including this one, but I don't see how Merkle or Hash trees could be used as a solution to these criteria.

The purpose of this function is to obfuscate values in a distributed ledger, while still allowing arithmetic operations to be conducted on them. Paillier would work perfectly if only a public key was distributed, but the potential existence of a private key doesn't work for this scenario, as it would allow one party to read all of the data.

If one of these solutions does, in fact, meet the criteria outlined, a quick explanation as to how would be greatly appreciated. Thanks.

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ Do you consider collision attack? Also, see Are there any practical implementation of a homomorphic hashing or signature scheme? $\endgroup$
    – kelalaka
    Commented Apr 26, 2020 at 15:48
  • $\begingroup$ Yes, this is the post where I found one of the papers I referenced. I couldn't find anything that fit my requirements, and the post is over 7 years old, so there may be a whole new body of research that has emerged since then. $\endgroup$
    – Chandler Freeman
    Commented Apr 26, 2020 at 16:42
  • 1
    $\begingroup$ How about Paillier where no one knows the private key? Or, if you're OK with the idea of something that's 'somewhat partially homomorphic', how about the randomized function ($r$ is the randomizer input) $f(x, r) = g^{x + kr} \bmod p$, where $0 \le x < k$ and $0 \le r \lll q/k$ (for prime $p, q$, $g$ the order of $q$, and $k$ an appropriate integer... $\endgroup$
    – poncho
    Commented Apr 26, 2020 at 19:34
  • 1
    $\begingroup$ "The purpose of this function is to obfuscate values in a distributed ledger" - do you mean that you want it to be feasible for the person who generated $f(x)$ to prove that $x$ is the value (or alternatively that they know $x$ without revealing it)? Again, what is the actual requirement? $\endgroup$
    – poncho
    Commented Apr 29, 2020 at 16:30
  • 1
    $\begingroup$ What's asked is a "function" and "probabilistic". But probabilistic goes against the very definition of a function $f$, which is such that $a=b\implies f(a)=f(b)$. Suggestion: make the thing a true function with an explicit random input $r$, and such that $a=b\implies f(a,r)=f(b,r)$. Then state its desired functionality (what we want it to do) and security properties (what we want an adversary to be unable to do). $\endgroup$
    – fgrieu ♦
    Commented Apr 30, 2020 at 7:08

2 Answers 2

Reset to default
4
$\begingroup$

The outputs must exhibit additive homomorphism such that some operation on $f(a)$ and $f(b)$ will equal $f(a+b)$.

Because $f$ is mandated to be nondeterministic, I assume that the requirement be that $f(a) \odot f(b)$ be some possible output $f(a+b)$ (for some computable operation $\odot$).

If so, there must be some further requirement; here's one $f$ function that meets the above requirements in a spectacularly unuseful way:

$f(x)$ is a nondetermanistic function that ignores the input $x$ and generates a random bit string of length $n$ (for a suitably large value of $n$).

Then:

  • For any input, there are $2^n$ possible outputs; if $n$ is large enough, this easily meets the 'trillions of possible outputs'

  • Examining the output does not allow the input to be deduced - obviously true.

  • There must be an operation on $f(a)$ and $f(b)$ that yields a possible output of $f(a+b)$ - for this, we can pick any arbitrary operation $\odot$ that maps two $n$ bit inputs to an $n$ bit output, and then we have $f(a) \odot f(b)$ is a possible output of $f(a+b)$.

Obviously, this function $f$ is unlikely to solve the specific problem you have in mind - what additional requirements are there?

Improve this answer
$\endgroup$
3
  • $\begingroup$ To specify: f() should exhibit deterministic additive homomorphism, meaning f(a) ⊙ f(b) should always produce a result equivalent to f(a + b). Now, f(a) ⊙ f(b) may produce a different ciphertext than f(a + b), but should represent an equivlant value. $\endgroup$
    – Chandler Freeman
    Commented Apr 26, 2020 at 19:01
  • 2
    $\begingroup$ @ChandlerFreeman: but what does 'equivlant value' mean? Does that mean that $f(x)$ must be an injection (albeit not an easily invertible one)? And, do you want to mention the actual use case (or don't you have one)? $\endgroup$
    – poncho
    Commented Apr 26, 2020 at 19:28
  • $\begingroup$ It looks like that everthing @ChandlerFreeman wants is a database that allows a third party to check blind values from the database $f(a), f(b)$... and do some operations over them. Well... Chandler will need homophorphic encrytpion. With hash and encryption you can do things like "SELECT" in a database... but operations like +... you will need more. Chandler, you can check CyptoDB page: css.csail.mit.edu/cryptdb $\endgroup$
    – Crypto Learner
    Commented Apr 29, 2020 at 19:39
0
$\begingroup$

One solution that meets the requirements outlined above is Pedersen commitments. Pedersen is a homomorphic commitment scheme that is computationally binding.

Improve this answer
$\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.