Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Publication

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

Alessandro Chiesa
2022
Conference Papers

Résumé

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.

Source officielle

Alessandro Chiesa
2022
Conference Papers

Résumé

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.

Source officielle

Concepts associés (32)

Complexité en temps

En algorithmique, la complexité en temps est une mesure du temps utilisé par un algorithme, exprimé comme fonction de la taille de l'entrée. Le temps compte le nombre d'étapes de calcul avant d'arriver à un résultat. Habituellement, le temps correspondant à des entrées de taille n est le temps le plus long parmi les temps d’exécution des entrées de cette taille ; on parle de complexité dans le pire cas. Les études de complexité portent dans la majorité des cas sur le comportement asymptotique, lorsque la taille des entrées tend vers l'infini, et l'on utilise couramment les notations grand O de Landau.

Système de preuve interactive

vignette|504x504px|Un système de preuve interactive est composé de deux machines abstraites : un prouveur et un vérificateur qui s'échangent des messages. En théorie de la complexité des algorithmes, un système de preuve interactive est un protocole formel de démonstration de théorèmes qui fait intervenir deux participants qui échangent des messages. Cela permet de définir des classes de complexité intéressantes, notamment la classe IP qui est le modèle utilisé dans le théorème PCP qui caractérise la classe NP.

Classe de complexité

En informatique théorique, et plus précisément en théorie de la complexité, une classe de complexité est un ensemble de problèmes algorithmiques dont la résolution nécessite la même quantité d'une certaine ressource. Une classe est souvent définie comme l'ensemble de tous les problèmes qui peuvent être résolus sur un modèle de calcul M, utilisant une quantité de ressources du type R, où n, est la taille de l'entrée. Les classes les plus usuelles sont celles définies sur des machines de Turing, avec des contraintes de temps de calcul ou d'espace.

Afficher plus

Publications associées (31)

Afficher plus

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

Graph Chatbot

Ontology-based Knowledge Representation for Traditional Martial Arts

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

Graph generative deep learning models with an application to circuit topologies