To me (new), it seems that a lot of cryptography relies on group theory.

Are there any zero knowledge protocols which do not rely on a group?

  • 1
    $\begingroup$ Once you know what a group is, you see them everywhere. If you are familiar with addition of signed integers, you know a group, an infinite one. If you know clock arithmetic (reduced to 12 whole hours and addition), you know a finite one.The concept is a much useful and general one. Don't try to do without it. $\endgroup$
    – fgrieu
    May 18 '20 at 14:43

Are there any zero knowledge protocols which do not rely on a group?

It depends on your definition of "relying on a group". If you mean "doesn't rely on a group-based assumption like DDH, CDH or DLog or variants thereof", then yes. If you mean "doesn't use a group at some point" then no, because such a protocol would be unimplementable because the most basic operations of a processor and the most commonly used ones in cryptography like XOR and addition form groups.

Assuming the former case the detailed answer is that in theory zero-knowledge proofs only rely on the existence of One-Way-Functions - which can be heuristically instantiated e.g. with appropriate modes of AES. If you want to read the details of this, the relevant paper is "Everything Provable is provable in Zero-Knowledge" from CRYPTO '88.

The core idea of this is though that you take a protocol from IP and transform it so that the verifier only sends randomness (Arthur-Merlin-Protocol). Then the prover commits to the correct responses for that specific randomness input (which requires OWFs) and this is iterated until all specified prover messages are through. Then the prover performs an NP zero knowledge proof that if the verifier were to see the openings to the commitments along with the generated randomness, they would accept the interaction. This works using the actual prover responses as witnesses and exploiting the final verification being a deterministic polynomial time function.

The NP-ZK proof itself is a proof that you know a solution to the graph 3-coloring problem (which is NP-complete and thus you can reduce every problem in NP to it). The basic idea is that the prover has a 3-coloring of the graph and for each protocol run picks a new random permutation of the colors and commits to the coloring of all nodes. Then the verifier requests a random edge, the prover opens the commitment for the connected nodes and the commitments and the difference in color is verified. This is iterated until the verifier is satisfied.

  • $\begingroup$ What about hash-based constructions? hash functions don't use a group at some point? $\endgroup$ May 18 '20 at 21:05
  • $\begingroup$ @WeCanBeFriends most hash functions use XOR at some point which is a group operation. $\endgroup$
    – SEJPM
    May 18 '20 at 21:12
  • $\begingroup$ Oh got it, thanks for the answer $\endgroup$ May 18 '20 at 21:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.