Snarky signatures: minimal signatures of knowledge from simulation-extractable snarks. (English) Zbl 1410.94077
Katz, Jonathan (ed.) et al., Advances in cryptology – CRYPTO 2017. 37th annual international cryptology conference, Santa Barbara, CA, USA, August 20–24, 2017. Proceedings. Part II. Cham: Springer. Lect. Notes Comput. Sci. 10402, 581-612 (2017).
Summary: We construct a pairing based simulation-extractable SNARK (SE-SNARK) that consists of only 3 group elements and has highly efficient verification. By formally linking SE-SNARKs to signatures of knowledge, we then obtain a succinct signature of knowledge consisting of only 3 group elements.SE-SNARKs enable a prover to give a proof that they know a witness to an instance in a manner which is: (1) succinct – proofs are short and verifier computation is small; (2) zero-knowledge – proofs do not reveal the witness; (3) simulation-extractable – it is only possible to prove instances to which you know a witness, even when you have already seen a number of simulated proofs.{
}We also prove that any pairing based signature of knowledge or SE-NIZK argument must have at least 3 group elements and 2 verification equations. Since our constructions match these lower bounds, we have the smallest size signature of knowledge and the smallest size SE-SNARK possible.
For the entire collection see [Zbl 1369.94004].
For the entire collection see [Zbl 1369.94004].
MSC:
| 94A60 | Cryptography |
References:
| [1] | Abe, M.; Fehr, S.; Vadhan, SP, Perfect NIZK with adaptive soundness, Theory of Cryptography, 118-136, 2007, Heidelberg: Springer, Heidelberg · Zbl 1129.94008 · doi:10.1007/978-3-540-70936-7_7 |
| [2] | Bdmp, MB; De Santis, A.; Micali, S.; Persiano, G., Non-interactive zero-knowledge proof systems, SIAM J. Comput., 20, 6, 1084-1118, 1991 · Zbl 0738.68027 · doi:10.1137/0220068 |
| [3] | Bellare, M.; Fuchsbauer, G.; Krawczyk, H., Policy-based signatures, Public-Key Cryptography - PKC 2014, 520-537, 2014, Heidelberg: Springer, Heidelberg · Zbl 1335.94031 · doi:10.1007/978-3-642-54631-0_30 |
| [4] | Ben-Sasson, E.; Chiesa, A.; Tromer, E.; Virza, M.; Garay, JA; Gennaro, R., Scalable zero knowledge via cycles of elliptic curves, Advances in Cryptology - CRYPTO 2014, 276-294, 2014, Heidelberg: Springer, Heidelberg · Zbl 1334.68077 · doi:10.1007/978-3-662-44381-1_16 |
| [5] | Benhamouda, F.; Camenisch, J.; Krenn, S.; Lyubashevsky, V.; Neven, G.; Sarkar, P.; Iwata, T., Better zero-knowledge proofs for lattice encryption and their application to group signatures, Advances in Cryptology - ASIACRYPT 2014, 551-572, 2014, Heidelberg: Springer, Heidelberg · Zbl 1306.94026 |
| [6] | Bernhard, D.; Fuchsbauer, G.; Ghadafi, E.; Jacobson, M.; Locasto, M.; Mohassel, P.; Safavi-Naini, R., Efficient signatures of knowledge and DAA in the standard model, Applied Cryptography and Network Security, 518-533, 2013, Heidelberg: Springer, Heidelberg · Zbl 1416.94042 · doi:10.1007/978-3-642-38980-1_33 |
| [7] | Bernhard, D.; Fuchsbauer, G.; Ghadafi, E.; Smart, NP; Warinschi, B., Anonymous attestation with user-controlled linkability, Int. J. Inf. Secur., 12, 3, 219-249, 2013 · doi:10.1007/s10207-013-0191-z |
| [8] | Bitansky, N., Canetti, R., Chiesa, A., Tromer, E.: Recursive composition and bootstrapping for snarks and proof-carrying data. In: Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, pp. 111-120. ACM (2013) · Zbl 1293.68264 |
| [9] | Bitansky, N., Canetti, R., Paneth, O., Rosen, A.: Indistinguishability obfuscation vs. auxiliary-input extractable functions: One must fall. IACR Cryptology ePrint Archive, 2013:641 (2013) |
| [10] | Bitansky, N.; Canetti, R.; Paneth, O.; Rosen, A., On the existence of extractable one-way functions, SIAM J. Comput., 45, 5, 1910-1952, 2016 · Zbl 1353.94039 · doi:10.1137/140975048 |
| [11] | Bitansky, N.; Chiesa, A.; Ishai, Y.; Paneth, O.; Ostrovsky, R.; Sahai, A., Succinct non-interactive arguments via linear interactive proofs, Theory of Cryptography, 315-333, 2013, Heidelberg: Springer, Heidelberg · Zbl 1316.68056 · doi:10.1007/978-3-642-36594-2_18 |
| [12] | Blum, M., Feldman, P., Micali, S.: Non-interactive zero-knowledge and its applications. In: Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, pp. 103-112. ACM (1988) |
| [13] | Boneh, D.; Boyen, X.; Goh, E-J; Cramer, R., Hierarchical identity based encryption with constant size ciphertext, Advances in Cryptology - EUROCRYPT 2005, 440-456, 2005, Heidelberg: Springer, Heidelberg · Zbl 1137.94340 · doi:10.1007/11426639_26 |
| [14] | Boyle, E.; Pass, R.; Iwata, T.; Cheon, JH, Limits of extractability assumptions with distributional auxiliary input, Advances in Cryptology - ASIACRYPT 2015, 236-261, 2015, Heidelberg: Springer, Heidelberg · Zbl 1375.94106 · doi:10.1007/978-3-662-48800-3_10 |
| [15] | Brickell, E.; Chen, L.; Li, J.; Lipp, P.; Sadeghi, A-R; Koch, K-M, A new direct anonymous attestation scheme from bilinear maps, Trusted Computing - Challenges and Applications, 166-178, 2008, Heidelberg: Springer, Heidelberg · doi:10.1007/978-3-540-68979-9_13 |
| [16] | Camenisch, J.; Stadler, M.; Kaliski, BS, Efficient group signature schemes for large groups, Advances in Cryptology — CRYPTO ’97, 410-424, 1997, Heidelberg: Springer, Heidelberg · Zbl 0882.94018 · doi:10.1007/BFb0052252 |
| [17] | Chase, M.; Lysyanskaya, A.; Dwork, C., On signatures of knowledge, Advances in Cryptology - CRYPTO 2006, 78-96, 2006, Heidelberg: Springer, Heidelberg · Zbl 1129.94043 · doi:10.1007/11818175_5 |
| [18] | Damgård, I.; Rueppel, RA, Non-interactive circuit based proofs and non-interactive perfect zero-knowledge with preprocessing, Advances in Cryptology — EUROCRYPT’ 92, 341-355, 1993, Heidelberg: Springer, Heidelberg · Zbl 0801.68050 · doi:10.1007/3-540-47555-9_28 |
| [19] | Danezis, G.; Fournet, C.; Groth, J.; Kohlweiss, M.; Sarkar, P.; Iwata, T., Square span programs with applications to succinct NIZK arguments, Advances in Cryptology - ASIACRYPT 2014, 532-550, 2014, Heidelberg: Springer, Heidelberg · Zbl 1306.94042 |
| [20] | Santis, A.; Crescenzo, G.; Persiano, G.; Montanari, U.; Rolim, JDP; Welzl, E., Necessary and sufficient assumptions for non-interactive zero-knowledge proofs of knowledge for All NP relations, Automata, Languages and Programming, 451-462, 2000, Heidelberg: Springer, Heidelberg · Zbl 0973.94526 · doi:10.1007/3-540-45022-X_38 |
| [21] | De Santis, A., Persiano, G.: Zero-knowledge proofs of knowledge without interaction. In: 33rd Annual Symposium on Foundations of Computer Science, 1992, Proceedings, pp. 427-436. IEEE (1992) · Zbl 0942.68606 |
| [22] | Derler, D., Slamanig, D.: Fully-anonymous short dynamic group signatures without encryption. IACR Cryptology ePrint Archive 2016:154 (2016) |
| [23] | Escala, A.; Herold, G.; Kiltz, E.; Rafols, C.; Villar, J., An algebraic framework for diffie-hellman assumptions, J. Cryptol., 30, 1, 242-288, 2017 · Zbl 1370.94510 · doi:10.1007/s00145-015-9220-6 |
| [24] | Faust, S.; Kohlweiss, M.; Marson, GA; Venturi, D.; Galbraith, S.; Nandi, M., On the non-malleability of the fiat-shamir transform, Progress in Cryptology - INDOCRYPT 2012, 60-79, 2012, Heidelberg: Springer, Heidelberg · Zbl 1295.94063 · doi:10.1007/978-3-642-34931-7_5 |
| [25] | Feige, U.; Lapidot, D.; Shamir, A., Multiple noninteractive zero knowledge proofs under general assumptions, SIAM J. Comput., 29, 1, 1-28, 1999 · Zbl 1018.94015 · doi:10.1137/S0097539792230010 |
| [26] | Feng, D-G; Xu, J.; Chen, X-F, An efficient direct anonymous attestation scheme with forward security, WSEAS Trans. Commun., 8, 10, 1076-1085, 2009 |
| [27] | Fischlin, M.; Onete, C.; Lopez, J.; Tsudik, G., Relaxed security notions for signatures of knowledge, Applied Cryptography and Network Security, 309-326, 2011, Heidelberg: Springer, Heidelberg · doi:10.1007/978-3-642-21554-4_18 |
| [28] | Galbraith, SD; Paterson, KG; Smart, NP, Pairings for cryptographers, Discrete Appl. Math., 156, 16, 3113-3121, 2008 · Zbl 1156.94347 · doi:10.1016/j.dam.2007.12.010 |
| [29] | Ge, H.; Tate, SR; Okamoto, T.; Wang, X., A direct anonymous attestation scheme for embedded devices, Public Key Cryptography - PKC 2007, 16-30, 2007, Heidelberg: Springer, Heidelberg · Zbl 1127.94025 · doi:10.1007/978-3-540-71677-8_2 |
| [30] | Gennaro, R.; Gentry, C.; Parno, B.; Raykova, M.; Johansson, T.; Nguyen, PQ, Quadratic span programs and succinct NIZKs without PCPs, Advances in Cryptology - EUROCRYPT 2013, 626-645, 2013, Heidelberg: Springer, Heidelberg · Zbl 1300.94056 · doi:10.1007/978-3-642-38348-9_37 |
| [31] | Gentry, C.; Groth, J.; Ishai, Y.; Peikert, C.; Sahai, A.; Smith, AD, Using fully homomorphic hybrid encryption to minimize non-interative zero-knowledge proofs, J. Cryptol., 28, 4, 820-843, 2015 · Zbl 1332.94066 · doi:10.1007/s00145-014-9184-y |
| [32] | Gentry, C., Wichs, D.: Separating succinct non-interactive arguments from all falsifiable assumptions. In: Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing, pp. 99-108. ACM (2011) · Zbl 1288.94063 |
| [33] | Ghadafi, E., Groth, J.: Towards a classification of non-interactive computational assumptions in cyclic groups. Cryptology ePrint Archive, Report 2017/343 (2017) |
| [34] | Groth, J.; Lai, X.; Chen, K., Simulation-sound NIZK proofs for a practical language and constant size group signatures, Advances in Cryptology - ASIACRYPT 2006, 444-459, 2006, Heidelberg: Springer, Heidelberg · Zbl 1172.94615 · doi:10.1007/11935230_29 |
| [35] | Groth, J.; Abe, M., Short non-interactive zero-knowledge proofs, Advances in Cryptology - ASIACRYPT 2010, 341-358, 2010, Heidelberg: Springer, Heidelberg · Zbl 1253.94050 · doi:10.1007/978-3-642-17373-8_20 |
| [36] | Groth, J.; Fischlin, M.; Coron, J-S, On the size of pairing-based non-interactive arguments, Advances in Cryptology - EUROCRYPT 2016, 305-326, 2016, Heidelberg: Springer, Heidelberg · Zbl 1369.94539 · doi:10.1007/978-3-662-49896-5_11 |
| [37] | Groth, J.; Ostrovsky, R., Cryptography in the multi-string model, J. Cryptol., 27, 3, 506-543, 2014 · Zbl 1302.94050 · doi:10.1007/s00145-013-9152-y |
| [38] | Groth, J.; Ostrovsky, R.; Sahai, A., New techniques for noninteractive zero-knowledge, J. ACM (JACM), 59, 3, 11, 2012 · Zbl 1281.68102 · doi:10.1145/2220357.2220358 |
| [39] | Groth, J.; Sahai, A., Efficient noninteractive proof systems for bilinear groups, SIAM J. Comput., 41, 5, 1193-1232, 2012 · Zbl 1259.94048 · doi:10.1137/080725386 |
| [40] | Kilian, J.; Coppersmith, D., Improved efficient arguments, Advances in Cryptology — CRYPT0’ 95, 311-324, 1995, Heidelberg: Springer, Heidelberg · doi:10.1007/3-540-44750-4_25 |
| [41] | Kilian, J.; Petrank, E., An efficient noninteractive zero-knowledge proof system for np with general assumptions, J. Cryptol., 11, 1, 1-27, 1998 · Zbl 1019.94014 · doi:10.1007/s001459900032 |
| [42] | Maurer, U.; Wolf, S.; Nyberg, K., Lower bounds on generic algorithms in groups, Advances in Cryptology — EUROCRYPT’98, 72-84, 1998, Heidelberg: Springer, Heidelberg · Zbl 0919.94027 · doi:10.1007/BFb0054118 |
| [43] | Micali, S., Computationally sound proofs, SIAM J. Comput., 30, 4, 1253-1298, 2000 · Zbl 1009.68053 · doi:10.1137/S0097539795284959 |
| [44] | Miers, I., Garman, C., Green, M., Rubin, A.D.: Zerocoin: anonymous distributed e-cash from bitcoin. In: 2013 IEEE Symposium on Security and Privacy (SP), pp. 397-411. IEEE (2013) |
| [45] | Nechaev, VI, Complexity of a determinate algorithm for the discrete logarithm, Math. Notes, 55, 2, 165-172, 1994 · Zbl 0831.11065 · doi:10.1007/BF02113297 |
| [46] | Peikert, C.; Vaikuntanathan, V.; Waters, B.; Wagner, D., A framework for efficient and composable oblivious transfer, Advances in Cryptology - CRYPTO 2008, 554-571, 2008, Heidelberg: Springer, Heidelberg · Zbl 1183.94046 · doi:10.1007/978-3-540-85174-5_31 |
| [47] | Sahai, A.: Non-malleable non-interactive zero knowledge and adaptive chosen-ciphertext security. In: 40th Annual Symposium on Foundations of Computer Science, 1999, pp. 543-553. IEEE (1999) |
| [48] | Sasson, E.B., Chiesa, A., Garman, C., Green, M., Miers, I., Tromer, E., Virza, M.: Zerocash: decentralized anonymous payments from bitcoin. In: 2014 IEEE Symposium on Security and Privacy (SP), pp. 459-474. IEEE (2014) |
| [49] | Schnorr, C-P, Efficient signature generation by smart cards, J. Cryptol., 4, 3, 161-174, 1991 · Zbl 0743.68058 · doi:10.1007/BF00196725 |
| [50] | Shoup, V.; Fumy, W., Lower bounds for discrete logarithms and related problems, Advances in Cryptology — EUROCRYPT ’97, 256-266, 1997, Heidelberg: Springer, Heidelberg · doi:10.1007/3-540-69053-0_18 |
| [51] | Valiant, P.; Canetti, R., Incrementally verifiable computation or proofs of knowledge imply time/space efficiency, Theory of Cryptography, 1-18, 2008, Heidelberg: Springer, Heidelberg · Zbl 1162.68448 · doi:10.1007/978-3-540-78524-8_1 |
| [52] | Yang, B.; Yang, K.; Qin, Y.; Zhang, Z.; Feng, D.; Conti, M.; Schunter, M.; Askoxylakis, I., DAA-TZ: an efficient DAA scheme for mobile devices using ARM TrustZone, Trust and Trustworthy Computing, 209-227, 2015, Cham: Springer, Cham · doi:10.1007/978-3-319-22846-4_13 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
