Cryptography | Computational complexity theory

Proof of knowledge

In cryptography, a proof of knowledge is an interactive proof in which the prover succeeds in 'convincing' a verifier that the prover knows something. What it means for a machine to 'know something' is defined in terms of computation. A machine 'knows something', if this something can be computed, given the machine as an input. As the program of the prover does not necessarily spit out the knowledge itself (as is the case for zero-knowledge proofs) a machine with a different program, called the knowledge extractor is introduced to capture this idea. We are mostly interested in what can be proven by polynomial time bounded machines. In this case the set of knowledge elements is limited to a set of witnesses of some language in NP. Let be a statement of language in NP, and the set of witnesses for x that should be accepted in the proof. This allows us to define the following relation: . A proof of knowledge for relation with knowledge error is a twoparty protocol with a prover and a verifier with the following two properties: 1. * Completeness: If , then the prover who knows witness for succeeds in convincing the verifier of his knowledge. More formally: , i.e. given the interaction between the prover P and the verifier V, the probability that the verifier is convinced is 1. 2. * Validity: Validity requires that the success probability of a knowledge extractor in extracting the witness, given oracle access to a possibly malicious prover , must be at least as high as the success probability of the prover in convincing the verifier. This property guarantees that no prover that doesn't know the witness can succeed in convincing the verifier. (Wikipedia).

Video thumbnail

How many subsets in a set? (1 of 2: Induction proof)

More resources available at www.misterwootube.com

From playlist The Nature of Proof

Video thumbnail

What is Knowledge?

In this lecture, Dr Arif Ahmed (University of Cambridge) thinks about the concept of knowledge and the analysis of a particular category of knowledge called ‘propositional knowledge’ (also known as ‘knowledge that’). In particular, we focus on: (i) the distinction between different kinds o

From playlist Philosophy

Video thumbnail

Geometry: Ch 5 - Proofs in Geometry (5 of 58) How to Proof Proofs

Visit http://ilectureonline.com for more math and science lectures! In this video I will explain what is and how to proof proofs in geometry. Next video in this series can be seen at: https://youtu.be/xuWliQ6CHpw

From playlist GEOMETRY 5 - PROOFS IN GEOMETRY

Video thumbnail

Learning to write an algebraic proof

👉 Learn how to write an algebraic proof. Algebraic proofs are used to help students understand how to write formal proofs where we have a statement and a reason. In the case of an algebraic proof the statement will be the operations used to solve an algebraic equation and the reason will

From playlist Parallel Lines and a Transversal

Video thumbnail

Proofs by contradiction -- Proofs

This lecture is on Introduction to Higher Mathematics (Proofs). For more see http://calculus123.com.

From playlist Proofs

Video thumbnail

Proof by Induction

Ben discusses proof by induction and goes over two examples.

From playlist Basics: Proofs

Video thumbnail

Efficient Zero Knowledge Proofs - A Modular Approach (Lecture 1) by Yuval Ishai

DISCUSSION MEETING : FOUNDATIONAL ASPECTS OF BLOCKCHAIN TECHNOLOGY ORGANIZERS : Pandu Rangan Chandrasekaran DATE : 15 to 17 January 2020 VENUE : Madhava Lecture Hall, ICTS, Bangalore Blockchain technology is among one of the most influential disruptive technologies of the current decade.

From playlist Foundational Aspects of Blockchain Technology 2020

Video thumbnail

Zero Knowledge Proofs - Seminar 4 - Non-interactive Zero Knowledge

This seminar series is about the mathematical foundations of cryptography. In this series Eleanor McMurtry is explaining Zero Knowledge Proofs (ZKPs). This seminar continues the development of non-interactive Zero Knowledge protocols, closing in on systems that can be used in practice. Yo

From playlist Metauni

Video thumbnail

Zero Knowledge Proofs - Seminar 1 - Introduction

This seminar series is about the mathematical foundations of cryptography. In this series Eleanor McMurtry is explaining Zero Knowledge Proofs (ZKPs), a fascinating set of techniques that allow one participant to prove they know something *without revealing the thing*. You can join this s

From playlist Metauni

Video thumbnail

MPC in the Head With Applications to Blockchain (Lecture 1) by Carmit Hazay

DISCUSSION MEETING : FOUNDATIONAL ASPECTS OF BLOCKCHAIN TECHNOLOGY ORGANIZERS : Pandu Rangan Chandrasekaran DATE : 15 to 17 January 2020 VENUE : Madhava Lecture Hall, ICTS, Bangalore Blockchain technology is among one of the most influential disruptive technologies of the current decade.

From playlist Foundational Aspects of Blockchain Technology 2020

Video thumbnail

zkSNARKs -- Recent progress and applications to blockchain protocols by Chaya Ganesh

DISCUSSION MEETING : FOUNDATIONAL ASPECTS OF BLOCKCHAIN TECHNOLOGY ORGANIZERS : Pandu Rangan Chandrasekaran DATE : 15 to 17 January 2020 VENUE : Madhava Lecture Hall, ICTS, Bangalore Blockchain technology is among one of the most influential disruptive technologies of the current decade.

From playlist Foundational Aspects of Blockchain Technology 2020

Video thumbnail

Luca De Feo, Proving knowledge of isogenies, quaternions and signatures

VaNTAGe Seminar, November 15, 2022 License: CC-BY-NC-SA Links to some of the papers and cites mentioned in the talk: Couveignes (2006): https://eprint.iacr.org/2006/291 Fiat-Shamir (1986): https://doi.org/10.1007/3-540-47721-7_12 De Feo-Jao-Plût (2011): https://eprint.iacr.org/2011/506 B

From playlist New developments in isogeny-based cryptography

Video thumbnail

Zero Knowledge Proofs - Seminar 5 - NP languages have zero knowledge proofs

This seminar series is about the mathematical foundations of cryptography. In this series Eleanor McMurtry is explaining Zero Knowledge Proofs (ZKPs). This seminar covers the 1991 proof by Goldreich-Micali-Widgerson that every NP language has a zero knowledge proof. You can join this semi

From playlist Metauni

Video thumbnail

Introduction to Proof by Counter Example

This video provides an introduction to the proof method of proof by counter example. mathispower4u.com

From playlist Symbolic Logic and Proofs (Discrete Math)

Related pages

Digital credential | Interactive proof system | Schnorr signature | Turing machine | Group signature | Abstract machine | Discrete logarithm | Zero-knowledge proof | Formal language | Cyclic group | Relation (mathematics) | Cryptography | NP (complexity)