Authors: Lehnherr, David
Ognjanović, Zoran 
Studer. Thomas
Affiliations: Mathematics 
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. ([1]) 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. ([2]) and Ognjanovi ́c
et al. ([3]) 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

Page view(s)

6
checked on Sep 26, 2021

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.