On the (In)security of SNARKs in the Presence of Oracles

Dario Fiore 1 Anca Nitulescu 2, 3
3 CASCADE - Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities
DI-ENS - Département d'informatique de l'École normale supérieure, CNRS - Centre National de la Recherche Scientifique : UMR 8548, Inria de Paris
Abstract : In this work we study the feasibility of knowledge extraction for succinct non-interactive arguments of knowledge (SNARKs) in a scenario that, to the best of our knowledge, has not been analyzed before. While prior work focuses on the case of adversarial provers that may receive (statically generated) auxiliary information, here we consider the scenario where adversarial provers are given access to an oracle. For this setting we study if and under what assumptions such provers can admit an extractor. Our contribution is mainly threefold. First, we formalize the question of extraction in the presence of oracles by proposing a suitable proof of knowledge definition for this setting. We call SNARKs satisfying this definition O-SNARKs. Second, we show how to use O-SNARKs to obtain formal and intuitive security proofs for three applications (ho-momorphic signatures, succinct functional signatures, and SNARKs on authenticated data) where we recognize an issue while doing the proof under the standard proof of knowledge definition of SNARKs. Third, we study whether O-SNARKs exist, providing both negative and positive results. On the negative side, we show that, assuming one way functions, there do not exist O-SNARKs in the standard model for every signing oracle family (and thus for general oracle families as well). On the positive side, we show that when considering signature schemes with appropriate restrictions on the message length O-SNARKs for the corresponding signing oracles exist, based on classical SNARKs and assuming extraction with respect to specific distributions of auxiliary input. This article is based on an earlier article which appears in the proceedings of TCC 2016-B, c IACR 2016.
Type de document :
Communication dans un congrès
TCC 2016-B - Fourteenth IACR Theory of Cryptography Conference , Oct 2016, Beijing, China. 2016, Theory of Cryptography 14th International Conference, TCC 2016-B, Beijing, China, November 1-3, 2016, Proceedings
Liste complète des métadonnées

Littérature citée [38 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01378013
Contributeur : Anca Nitulescu <>
Soumis le : samedi 8 octobre 2016 - 15:22:14
Dernière modification le : jeudi 26 avril 2018 - 10:29:08
Document(s) archivé(s) le : lundi 9 janvier 2017 - 12:15:18

Fichier

112.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01378013, version 1

Collections

Citation

Dario Fiore, Anca Nitulescu. On the (In)security of SNARKs in the Presence of Oracles. TCC 2016-B - Fourteenth IACR Theory of Cryptography Conference , Oct 2016, Beijing, China. 2016, Theory of Cryptography 14th International Conference, TCC 2016-B, Beijing, China, November 1-3, 2016, Proceedings. 〈hal-01378013〉

Partager

Métriques

Consultations de la notice

220

Téléchargements de fichiers

103