**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Concept# Interactive proof system

Summary

In computational complexity theory, an interactive proof system is an abstract machine that models computation as the exchange of messages between two parties: a prover and a verifier. The parties interact by exchanging messages in order to ascertain whether a given string belongs to a language or not. The prover possesses unlimited computational resources but cannot be trusted, while the verifier has bounded computation power but is assumed to be always honest. Messages are sent between the verifier and prover until the verifier has an answer to the problem and has "convinced" itself that it is correct.
All interactive proof systems have two requirements:

- Completeness: if the statement is true, the honest prover (that is, one following the protocol properly) can convince the honest verifier that it is indeed true.
- Soundness: if the statement is false, no prover, even if it doesn't follow the protocol, can convince the honest verifier that it is true, except with some small proba

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications

Loading

Related people

Loading

Related units

Loading

Related concepts

Loading

Related courses

Loading

Related lectures

Loading

Related publications (9)

Loading

Loading

Loading

Related people (2)

Related concepts (12)

Computational complexity theory

In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each ot

Complexity class

In computational complexity theory, a complexity class is a set of computational problems "of related resource-based complexity". The two most commonly analyzed resources are time and memory.
In ge

Zero-knowledge proof

In cryptography, a zero-knowledge proof or zero-knowledge protocol is a method by which one party (the prover) can prove to another party (the verifier) that a given statement is true, while avoidin

Giuseppe Carleo, Gabriel Maria Pescia

We introduce a family of neural quantum states for the simulation of strongly interacting systems in the presence of spatial periodicity. Our variational state is parametrized in terms of a permutationally invariant part described by the Deep Sets neural-network architecture. The input coordinates to the Deep Sets are periodically transformed such that they are suitable to directly describe periodic bosonic systems. We show example applications to both one- and two-dimensional interacting quantum gases with Gaussian interactions, as well as to He-4 confined in a one-dimensional geometry. For the one-dimensional systems we find very precise estimations of the ground-state energies and the radial distribution functions of the particles. In two dimensions we obtain good estimations of the ground-state energies, comparable to results obtained from more conventional methods.

Related courses (4)

COM-501: Advanced cryptography

This course reviews some failure cases in public-key cryptography. It introduces some cryptanalysis techniques. It also presents fundamentals in cryptography such as interactive proofs. Finally, it presents some techniques to validate the security of cryptographic primitives.

CS-602: Foundation of probabilistic proofs

Probabilistic proof system (eg PCPs and IPs) have had a tremendous impact on the theoretical computer science, and have also found practical uses. They underlie delegation of computation protocols and hardness of approximation. This course covers the foundations of probablistic proof systems.

CS-459: Foundations of probabilistic proofs

Probabilistic proof systems (eg PCPs and IPs) have had a tremendous impact on theoretical computer science,
as well as on real-world secure systems. They underlie delegation of computation protocols and hardness of
approximation. This course covers the foundations of probabilistic proof systems.

, , ,

The communication between an honest prover and an honest verifier can be intercepted by a malicious man-in-the-middle (MiM), without the legitimate interlocutors noticing the intrusion. The attacker can simply relay messages from one party to another, eventually impersonating the prover to the verifier and possibly gaining the privileges of the former. This sort of simple relay attacks are prevalent in wireless communications (e.g., RFID-based protocols) and can affect several infrastructures from contactless payments to remote car-locking systems and access-control verification in high-security areas. As the RFID/NFC technology prevails, a practical and increasingly popular countermeasure to these attacks is given by distance-bounding protocols. Yet, the security of these protocols is still not mature. Importantly, the implications of the return channel (i.e., knowing whether the protocol finished successfully or not) in the security of some distance-bounding protocols have not been fully assessed. In this paper, we demonstrate this by a series of theoretical and practical attacks.

David Jules Froelicher, Jean-Pierre Hubaux, Mickaël Misbach, Jean Louis Raisaro, Juan Ramón Troncoso-Pastoriza

Medical studies are usually time consuming, cumbersome and extremely costly to perform, and for exploratory research, their results are also difficult to predict a priori. This is particularly the case for rare diseases, for which finding enough patients is difficult and usually requires an international-scale research. In this case, the process can be even more difficult due to the heterogeneity of data-protection regulations, making the data sharing process particularly hard. In this short paper, we propose MedCo(2) (pronounced MedCo square), a distributed system that streamlines the process of a medical study by bridging and enabling both data discovery and data analysis among multiple databases, while protecting data confidentiality and patients' privacy. MedCo(2) relies on interactive protocols, homomorphic encryption and differential privacy. It enables the privacy-preserving computations of multiple statistics such as cosine similarity and variance, and the training of machine learning models, on patients that are obliviously selected according to specific criteria among multiple databases.

Related units (1)

Related lectures (6)