Paper 2022/009

Algebraic Reductions of Knowledge

Abhiram Kothapalli, Carnegie Mellon University
Bryan Parno, Carnegie Mellon University

We introduce reductions of knowledge, a generalization of arguments of knowledge, which reduce checking knowledge of a witness in one relation to checking knowledge of a witness in another (simpler) relation. Reductions of knowledge unify a growing class of modern techniques as well as provide a compositional framework to modularly reason about individual steps in complex arguments of knowledge. As a demonstration, we simplify and unify recursive arguments over linear algebraic statements by decomposing them as a sequence of reductions of knowledge. To do so, we develop the tensor reduction of knowledge, which generalizes the central reductive step common to many recursive arguments. Underlying the tensor reduction of knowledge is a new information-theoretic reduction, which, for any modules $U$, $U_1$, and $U_2$ such that $U \cong U_1 \otimes U_2$, reduces the task of evaluating a homomorphism in $U$ to evaluating a homomorphism in $U_1$ and evaluating a homomorphism in $U_2$.

Available format(s)
Publication info
A major revision of an IACR publication in CRYPTO 2023
arguments of knowledgecomposition
Contact author(s)
akothapalli @ cmu edu
parno @ cmu edu
2023-06-15: last of 2 revisions
2022-01-07: received
See all versions
Short URL
Creative Commons Attribution


      author = {Abhiram Kothapalli and Bryan Parno},
      title = {Algebraic Reductions of Knowledge},
      howpublished = {Cryptology ePrint Archive, Paper 2022/009},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.