Paper 2006/472

A Framework for Interactive Argument Systems using Quasigroupic Homorphic Commitment

Luis Teixeira d'Aguiar Norton Brandao

Abstract

Using a model based on \textit{probabilistic functions} (\textit{PF}), it's introduced the concept of \textit{perfect zero knowledge} (\textit{PZK}) \textit{commitment scheme} (\textit{CS}) allowing \textit{quasigroupic} \textit{homomorphic commitment} (\textit{QHC}). Using \textit{QHC} of ${+}_m$ (modular sum in ${\mathbb{Z}}_m$), application is considered in interactive argument systems (\textit{IAS}) for several languages. In four of the examples -- generalized nand ($\text{Lnandalpha}$), string equality ($\left[{=}_{(m,\alpha ,)}\right]$), string inequality ($\left[{\ne }_{(m,\alpha ,)}\right]$) and graph three-colourations ($G3C$) -- complexity improvements are obtained, in comparison to other established results. Motivation then arises to define a general framework for \textit{PZK}-\textit{IAS} for membership in language with committed alphabet (\textit{MLCA}), such that the properties of soundness and \textit{PZK} result from high-level parametrizable aspects. A general simulator is constructed for sequential and (most interestingly) for parallel versions of execution. It therefore becomes easier to conceptualize functionalities of this kind of \textit{IAS} without the consideration of low level aspects of cryptographic primitives. The constructed framework is able to embrace \AcroCS\; allowing \textit{QHC} of functions that are not themselves quasigroupic. Several theoretical considerations are made, namely recognizing a necessary requirements to demand on an eventual \AcroCS \;allowing \textit{QHC} of some complete function in a Boolean sense.