Skip to main content

Search

Show all results for

Home

Publication

Zero-Knowledge IOPs with Linear-Time Prover and Polylogarithmic-Time Verifier

About
Privacy
Disclaimer

Copyright © 2025 EPFL, all rights reserved

Graph Chatbot

Alessandro Chiesa, Siqi Liu
2022

Abstract

Interactive oracle proofs (IOPs) are a multi-round generalization of probabilistically checkable proofs that play a fundamental role in the construction of efficient cryptographic proofs.

Official source

https://infoscience.epfl.ch/entities/publication/9643ce18-bbd3-4ca7-8be3-0c4bbe24ea1c

About this result

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 concepts (32)

Time complexity

In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, supposing that each elementary operation takes a fixed amount of time to perform. Thus, the amount of time taken and the number of elementary operations performed by the algorithm are taken to be related by a constant factor.

Interactive proof system

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.

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 general, a complexity class is defined in terms of a type of computational problem, a model of computation, and a bounded resource like time or memory. In particular, most complexity classes consist of decision problems that are solvable with a Turing machine, and are differentiated by their time or space (memory) requirements.

Related publications (31)

Ontology-based Knowledge Representation for Traditional Martial Arts

Sarah Irene Brutton Kenderdine, Yumeng Hou

Traditional martial arts are treasures of humanity's knowledge and critical carriers of sociocultural memories throughout history. However, such treasured practices have encountered various challenges in knowledge transmission and now feature many entries ...

2024

A Spectral Ansatz for The Long-Time Homogenization of The Wave Equation

Matthias Ruf, Matthias Benjamin Ruf

Consider the wave equation with heterogeneous coefficients in the homogenization regime. At large times, the wave interacts in a nontrivial way with the heterogeneities, giving rise to effective dispersive effects. The main achievement of the present wor ...

Ecole Polytechnique2024

Graph generative deep learning models with an application to circuit topologies

Modern integrated circuits are tiny yet incredibly complex technological artifacts, composed of millions and billions of individual structures working in unison. Managing their complexity and facilitating their design drove part of the co-evolution of mode ...

EPFL2024