Mathematical Institute of the Serbian Academy of Sciences and Arts
|Title:||A Logic of Interactive Proofs||First page:||89||Last page:||90||Related Publication(s):||Book of Abstracts of the 10th International Conference Logic and Applications, LAP 2021||Conference:||10th International Conference Logic and Applications, LAP 2021, September 20 - 24, 2020, Dubrovnik, Croatia||Issue Date:||Sep-2021||Rank:||M34||URL:||http://imft.ftn.uns.ac.rs/math/cms/uploads/Main/2021_LAP_FORMALS_BoA.pdf||Abstract:||
The introduction of interactive proofs by Goldwasser et al. () poses an inter-
esting question to the already vividly researched area of uncertain reasoning and
justification logic - How can we quantitatively describe an evidence transforma-
tion that gets progressively more meaningful and how can we model agents that
reason based on such transformed evidence?
In this work, we introduce the probabilistic two-agent justification logic IPJ,
a logic in which we can reason about agents that perform interactive proofs.
We present its syntax and semantics and provide a soundness proof. Moreover,
we investigate how our axiomatisation can be extended in order to capture a
weaker notion of the zero-knowledge property of interactive proofs. The foun-
dation of our logic is built on the works of Kokkinis et al. () and Ognjanovi ́c
et al. () who developed a probabilistic justification logic PJ and its extension
CPJL which allows for conditional and non-standard probabilities.
We answer the question above by parametrizing our logic over the set of negligi-
ble functions f (n) = n−kfor all k ∈N. This approach enables us to canonically
construct the set of formulas that are known by the agents to be interactively
provable. By doing so, we closely model the soundness and completeness proper-
ties of interactive proofs which are usually stated by using first-order quantifiers.
Furthermore, we use non-standard probabilities in order to model the limit cases
of the aforementioned properties.
|Keywords:||Interactive Proofs | Justification Logic | Non-standard Probabilities||Publisher:||University Center Dubrovnik, Croatia||Project:||Advanced artificial intelligence techniques for analysis and design of system components based on trustworthy BlockChain technology - AI4TrustBC|
Show full item record
checked on Feb 3, 2023
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.