Paper 2022/009

Algebraic Reductions of Knowledge

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

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$.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A major revision of an IACR publication in CRYPTO 2023
Keywords
arguments of knowledgecomposition
Contact author(s)
akothapalli @ cmu edu
parno @ cmu edu
History
2023-06-15: last of 2 revisions
2022-01-07: received
See all versions
Short URL
https://ia.cr/2022/009
License
Creative Commons Attribution
CC BY

BibTeX

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