What are zk-SNARKs? — A Problematic Homomorphism

The post on the Zcash blog gives a little example of a use of a homomorphic hiding. I wanted to recreate this example with the Unpadded RSA homomorphism, but I found that it has a critical flaw. The second property of a homomorphic hiding given on the Zcash blog is not satisfied by Unpadded RSA. The second property states:

that is, E is an injective homomorphism

Without this property there are multiple inputs of the homomorphism that are sent to the same output. With this caveat in mind, let’s explore the rest of the example.

Suppose I have discovered how to factor a “large” number, say 899. I want to prove to you that I have the factors of this number, but I don’t want you know the factors themselves. I could choose a modulus m and an exponent e and use them to create an unpadded-RSA homomorphism that obscures the factors I have found. I give you the encrypted factors. You multiply the encrypted factors together and check them against the the encryption of 899. If they match, you have good evidence that I really do know the factors of 899. (But you don’t know for sure, because of the caveat I mentioned above!)

Here’s how our conversation could go:

You would then compute the encrypted version of 899:

Then you could multiply 128 and 387, taking them mod 503:

They match! If we were using a better encryption scheme, you would be pretty sure that I really did know the factors of 899*. Unfortunately, because the homomorphism is not injective you can’t be sure of that. In fact, I never had the factorization of 899.

Can you see what I did instead? Leave a comment if you figure it out.

*(EDIT: I am not so sure about this statement anymore. I think that it would be very difficult to know for certain if someone knew the factors of some number by checking that the encrypted factors multiply as expected. The person could always trick you by finding the factors of a different number that is in the same equivalence class modulo m. This may be a problem not with the homomorphism used but the protocol. If the “proving” party knows the modulus they can use it to change the desired composite number into another one that is easier to factor.)

Joshua is a mathematician, educator, cryptographer, and developer. He is a developer at @statebox.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store