×

Scalable zero knowledge via cycles of elliptic curves. (English) Zbl 1383.68035

Summary: Non-interactive zero-knowledge proofs of knowledge for general NP statements are a powerful cryptographic primitive, both in theory and in practical applications. Recently, much research has focused on achieving an additional property, succinctness, requiring the proof to be very short and easy to verify. Such proof systems are known as zero-knowledge succinct non-interactive arguments of knowledge (zk-SNARKs), and are desired when communication is expensive, or the verifier is computationally weak. Existing zk-SNARK implementations have severe scalability limitations, in terms of space complexity as a function of the size of the computation being proved (e.g., running time of the NP statement’s decision program). First, the size of the proving key is quasilinear in the upper bound on the computation size. Second, producing a proof requires “writing down” all intermediate values of the entire computation, and then conducting global operations such as FFTs. The bootstrapping technique of N. Bitansky et al. [in: Proceedings of the 45th annual ACM symposium on theory of computing, STOC’13. New York, NY: Association for Computing Machinery (ACM). 111–120 (2013; Zbl 1293.68264)], following P. Valiant [Lect. Notes Comput. Sci. 4948, 1–18 (2008; Zbl 1162.68448)], offers an approach to scalability, by recursively composing proofs: proving statements about acceptance of the proof system’s own verifier (and correctness of the program’s latest step). Alas, recursive composition of known zk-SNARKs has never been realized in practice, due to enormous computational cost. Using new elliptic-curve cryptographic techniques, and methods for exploiting the proof systems’ field structure and nondeterminism, we achieve the first zk-SNARK implementation that practically achieves recursive proof composition. Our zk-SNARK implementation runs random-access machine programs and produces proofs of their correct execution, on today’s hardware, for any program running time. It takes constant time to generate the keys that support all computation sizes. Subsequently, the proving process only incurs a constant multiplicative overhead compared to the original computation’s time, and an essentially-constant additive overhead in memory. Thus, our zk-SNARK implementation is the first to have a well-defined, albeit low, clock rate of “verified instructions per second”.

MSC:

68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
11T71 Algebraic coding theory; cryptography (number-theoretic aspects)
94A60 Cryptography
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Lyubashevsky, V., Micciancio, D., Peikert, C., Rosen, A.: SWIFFT: a modest proposal for FFT hashing. In: Proceedings of the 15th International Workshop on Fast Software Encryption, FSE ’08, pp. 54-72 (2008) · Zbl 1154.68403
[2] Ajtai, M.: Generating hard instances of lattice problems. In: Proceedings of the 28th Annual ACM Symposium on the Theory of Computing, STOC ’96, pp. 99-108 (1996) · Zbl 0921.11071
[3] Atkin, A.O.L., Morain, F.: Elliptic curves and primality proving. Math. Comput. 61, 29-68 (1993) · Zbl 0792.11056 · doi:10.1090/S0025-5718-1993-1199989-X
[4] Angluin, D., Valiant, L.G.: Fast probabilistic algorithms for hamiltonian circuits and matchings. In: Proceedings on 9th Annual ACM Symposium on Theory of Computing, STOC ’77, pp. 30-41 (1977) · Zbl 0437.05040
[5] Boneh, D., Boyen, X.: Secure identity based encryption without random oracles. In: Proceedings of the 24th Annual International Cryptology Conference, CRYPTO ’04, pp. 443-459 (2004) · Zbl 1104.94019
[6] Backes, M., Barbosa, M., Fiore, D., Reischuk, R.M.: ADSNARK: nearly practical and privacy-preserving proofs on authenticated data. In Proceedings of the 36th IEEE Symposium on Security and Privacy, S&P ’15, pp. 271-286 (2015) · Zbl 0963.11068
[7] Bitansky, N., Canetti, R., Chiesa, A., Tromer, E.: From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again. In: Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, ITCS ’12, pp. 326-349 (2012) · Zbl 1347.68129
[8] Bitansky, N., Canetti, R., Chiesa, A., Tromer, E.: Recursive composition and bootstrapping for SNARKs and proof-carrying data. In: Proceedings of the 45th ACM Symposium on the Theory of Computing, STOC ’13, pp. 111-120 (2013) · Zbl 1293.68264
[9] Ben-Sasson, E., Chiesa, A., Genkin, D., Tromer, E., Virza, M.: SNARKs for C: verifying program executions succinctly and in zero knowledge. In Proceedings of the 33rd Annual International Cryptology Conference, CRYPTO ’13, pp. 90-108 (2013) · Zbl 1317.68050
[10] Ben-Sasson, E., Chiesa, A., Genkin, D., Tromer, E., Virza, M.: TinyRAM architecture specification v2.00, 2013. http://scipr-lab.org/tinyram · Zbl 1364.94548
[11] Ben-Sasson, E., Chiesa, A., Garman, C., Green, M., Miers, I., Tromer, E., Virza, M.: Zerocash: decentralized anonymous payments from Bitcoin. In: Proceedings of the 2014 IEEE Symposium on Security and Privacy, SP ’14, pp. 459-474 (2014)
[12] Ben-Sasson, E., Chiesa, A., Genkin, D., Tromer, E.: Fast reductions from RAMs to delegatable succinct constraint satisfaction problems. In: Proceedings of the 4th Innovations in Theoretical Computer Science Conference, ITCS ’13, pp. 401-414 (2013) · Zbl 1361.68088
[13] Ben-Sasson, E., Chiesa, A., Genkin, D., Tromer, E.: On the concrete efficiency of probabilistically-checkable proofs. In: Proceedings of the 45th ACM Symposium on the Theory of Computing, STOC ’13, pp. 585-594 (2013) · Zbl 1293.94054
[14] Bitansky, N., Chiesa, A., Ishai, Y., Ostrovsky, R., Paneth, O.: Succinct non-interactive arguments via linear interactive proofs. In: Proceedings of the 10th Theory of Cryptography Conference, TCC ’13, pp. 315-333 (2013) · Zbl 1316.68056
[15] Bitansky, N., Canetti, R., Paneth, O.: How to construct extractable one-way functions against uniform adversaries. Cryptology ePrint Archive, report 2013/468 (2013)
[16] Bitansky, N., Canetti, R., Paneth, O., Rosen, A.: Indistinguishability obfuscation vs. auxiliary-input extractable functions: One must fall. Cryptology ePrint Archive, report 2013/641 (2013) · Zbl 1366.94540
[17] Ben-Sasson, E., Chiesa, A., Tromer, E., Virza, M.: Succinct non-interactive zero knowledge for a von Neumann architecture. In: Proceedings of the 23rd USENIX Security Symposium, Security ’14, pp. 781-796 (2014). http://eprint.iacr.org/2013/879 · Zbl 1334.68077
[18] Blum, M., De Santis, A., Micali, S., Persiano, G.: Non-interactive zero-knowledge. SIAM J. Comput. 20(6), 1084-1118 (1991) · Zbl 0738.68027 · doi:10.1137/0220068
[19] Blum, M., Evans, W., Gemmell, P., Kannan, S., Naor, M.: Checking the correctness of memories. In: Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, FOCS ’91, pp. 90-99 (1991) · Zbl 1323.68200
[20] Babai, L., Fortnow, L., Levin, L.A., Szegedy, M.: Checking computations in polylogarithmic time. In: Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, STOC ’91, pp. 21-32 (1991) · Zbl 1181.94094
[21] Blum, M., Feldman, P., Micali, S.: Non-interactive zero-knowledge and its applications. In: Proceedings of the 20th Annual ACM Symposium on Theory of Computing, STOC ’88, pp. 103-112 (1988) · Zbl 0919.94011
[22] Braun, B., Feldman, A.J., Ren, Z., Setty, S., Blumberg, A.J., Walfish, M.: Verifying computations with state. In: Proceedings of the 25th ACM Symposium on Operating Systems Principles, SOSP ’13, pp. 341-357 (2013) · Zbl 0957.94025
[23] Ben-Sasson, E., Goldreich, O., Harsha, P., Sudan, M., Vadhan, S.: Short PCPs verifiable in polylogarithmic time. In: Proceedings of the 20th Annual IEEE Conference on Computational Complexity, CCC ’05, pp. 120-134 (2005) · Zbl 0957.94025
[24] Barreto, P.S., Galbraith, S.D., Ó hÉigeartaigh, C., Scott, M.: Efficient pairing computation on supersingular abelian varieties. Des. Codes Cryptogr. 42(3), 239-271 (2007) · Zbl 1142.14307 · doi:10.1007/s10623-006-9033-6
[25] Barreto, P.S.L.M., Kim, H.Y., Lynn, B., Scott, M.: Efficient algorithms for pairing-based cryptosystems. In: Proceedings of the 22Nd Annual International Cryptology Conference, CRYPTO ’02, pp. 354-368 (2002) · Zbl 1026.94520
[26] Brakerski, Z., Langlois, A., Peikert, C., Regev, O., Stehlé, D.: Classical hardness of learning with errors. In: Proceedings of the 45th Annual ACM Symposium on Symposium on Theory of Computing, STOC ’13, pp. 575-584 (2013) · Zbl 1293.68159
[27] Barreto, P.S.L.M., Lynn, B., Scott, M.: Constructing elliptic curves with prescribed embedding degrees. In:Proceedings of the 3rd International Conference on Security in Communication Networks, SCN ’02, pp. 257-267 (2003) · Zbl 1022.94008
[28] Barreto, P.S.L.M., Lynn, B., Scott, M.: Efficient implementation of pairing-based cryptosystems. J. Cryptol. 17(4), 321-334 (2004) · Zbl 1123.94334 · doi:10.1007/s00145-004-0311-z
[29] Benger, N., Scott, M.: Constructing tower extensions of finite fields for implementation of pairing-based cryptography. In: Proceedings of the 3rd International Conference on Arithmetic of Finite Fields, WAIFI ’10, pp. 180-195 (2010) · Zbl 1245.11122
[30] Boneh, D., Segev, G., Waters, B.: Targeted malleability: Homomorphic encryption for restricted computations. In: Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, ITCS ’12, pp. 350-366 (2012) · Zbl 1347.68119
[31] Brezing, F., Weng, A.: Elliptic curves suitable for pairing based cryptography. Des. Codes Cryptpogr. 37(1), 133-141 (2005) · Zbl 1100.14517 · doi:10.1007/s10623-004-3808-4
[32] Cohen, H., Frey, G., Avanzi, R., Doche, C., Lange, T., Nguyen, K., Vercauteren, F.: Handbook of Elliptic and Hyperelliptic Curve Cryptography, 2nd edn. Chapman & Hall/CRC, Boca Raton (2012) · Zbl 1082.94001
[33] Costello, C., Fournet, C., Howell, J., Kohlweiss, M., Kreuter, B., Naehrig, M., Parno, B., Zahur, S.: Geppetto: versatile verifiable computation. In: Proceedings of the 36th IEEE Symposium on Security and Privacy, S&P ’15, pp. 253-270 (2015) · Zbl 0738.68027
[34] Cormode, G., Mitzenmacher, M., Thaler, J.: Practical verified computation with streaming interactive proofs. In: Proceedings of the 4th Symposium on Innovations in Theoretical Computer Science, ITCS ’12, pp. 90-112 (2012) · Zbl 1347.68157
[35] Cocks, C., Pinch, R.G.E.: Identity-based cryptosystems based on the weil pairing. Unpublished manuscript (2001) · Zbl 0979.11057
[36] Cook, S.A., Reckhow, R.A.: Time-bounded random access machines. In: Proceedings of the 4th Annual ACM Symposium on Theory of Computing, STOC ’72, pp. 73-80 (1972) · Zbl 0357.68055
[37] Canetti, R., Riva, B., Rothblum, G.N.: Practical delegation of computation using multiple servers. In: Proceedings of the 18th ACM Conference on Computer and Communications Security, CCS ’11, pp. 445-454 (2011) · Zbl 0382.10001
[38] Chiesa, A., Tromer, E.: Proof-carrying data and hearsay arguments from signature cards. In: Proceedings of the 1st Symposium on Innovations in Computer Science, ICS ’10, pp. 310-331 (2010) · Zbl 0963.11068
[39] Chiesa, A., Tromer, E.: Proof-carrying data: secure computation on untrusted platforms (high-level description). Next Wave Natl. Secur. Agency’s Rev. Emerg. Technol. 19(2), 40-46 (2012)
[40] Chong, S., Tromer, E., Vaughan, J.A.: Enforcing language semantics using proof-carrying data. Cryptology ePrint Archive, Report 2013/513 (2013) · Zbl 0792.11056
[41] Chiesa, A., Tromer, E., Virza, M.: Cluster computing in zero knowledge. In: Proceedings of the 34th Annual International Conference on Theory and Application of Cryptographic Techniques, EUROCRYPT ’15, pp. 371-403 (2015) · Zbl 1371.68257
[42] Dupont, R., Enge, A., Morain, F.: Building curves with arbitrary small MOV degree over finite prime fields. J. Cryptol. 18(2), 79-89 (2005) · Zbl 1084.94014 · doi:10.1007/s00145-004-0219-7
[43] Danezis, G., Fournet, C., Groth, J., Kohlweiss, M.: Square span programs with applications to succinct NIZK arguments. In: Proceedings of the 20th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT ’14, pp. 532-550 (2014) · Zbl 1306.94042
[44] Enge, A., Sutherland, A.V.: Class invariants by the CRT method. In: Proceedings of the 9th International Symposium on Algorithmic Number Theory, ANTS ’10, pp. 142-156 (2010) · Zbl 1260.11083
[45] Frey, G., Müller, M., Rück, H.-G.: The Tate pairing and the discrete logarithm applied to elliptic curve cryptosystems. IEEE Trans. Inf. Theory 45(5), 1717-1719 (2006) · Zbl 0957.94025 · doi:10.1109/18.771254
[46] Frey, G., Rück, H.-G.: A remark concerning m-divisibility and the discrete logarithm in the divisor class group of curves. Math. Comput. 62(206), 865-874 (1994) · Zbl 0813.14045
[47] Fiat, A., Shamir, A.: How to prove yourself: practical solutions to identification and signature problems. In: Proceedings of the 6th Annual International Cryptology Conference, CRYPTO ’87, pp. 186-194 (1987) · Zbl 0636.94012
[48] Freeman, D., Scott, M., Teske, E.: A taxonomy of pairing-friendly elliptic curves. J. Cryptol. 23(2), 224-280 (2010) · Zbl 1181.94094 · doi:10.1007/s00145-009-9048-z
[49] Gennaro, R.: Multi-trapdoor commitments and their applications to proofs of knowledge secure under concurrent man-in-the-middle attacks. In: Proceedings of the 24th Annual International Cryptology Conference, CRYPTO ’04, pp. 220-236 (2004) · Zbl 1104.94050
[50] Goldreich, O., Goldwasser, S., Halevi, S.: Collision-free hashing from lattice problems. Technical report, 1996. ECCC TR95-042 · Zbl 1343.94055
[51] Garg, S., Gentry, C., Halevi, S.: Candidate multilinear maps from ideal lattices. In: Proceedings of the 32nd Annual International Conference on Theory and Application of Cryptographic Techniques, EUROCRYPT ’13, pp. 1-17 (2013) · Zbl 1300.94055
[52] Gennaro, R., Gentry, C., Parno, B., Raykova, M.: Quadratic span programs and succinct NIZKs without PCPs. In: Proceedings of the 32nd Annual International Conference on Theory and Application of Cryptographic Techniques, EUROCRYPT ’13, pp. 626-645 (2013) · Zbl 1300.94056
[53] Galbraith, S.D., Harrison, K., Soldera, D.: Implementing the Tate pairing. In: Proceedings of the 5th International Symposium on Algorithmic Number Theory, ANTS ’02, pp. 324-337 (2002) · Zbl 1058.11072
[54] Gopalan, P., Lovett, S., Shpilka, A.: On the complexity of boolean functions in different characteristics. In: Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC ’09, pp. 173-183 (2009) · Zbl 1213.68309
[55] Groth, J.: Short pairing-based non-interactive zero-knowledge arguments. In: Proceedings of the 16th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT ’10, pp. 321-340 (2010) · Zbl 1253.94049
[56] Granger, R., Smart, N.: On computing products of pairings. Cryptology ePrint Archive, report 2006/172 (2006) · Zbl 1366.94540
[57] Granger, R., Scott, M.: Faster squaring in the cyclotomic subgroup of sixth degree extensions. In: Proceedings of the 13th international conference on Practice and Theory in Public Key Cryptography, PKC’10, pp. 209-223 (2010) · Zbl 1279.94079
[58] Gassend, B., Suh, G.E., Clarke, D.E., van Dijk, M., Devadas, S.: Caches and hash trees for efficient memory integrity verification. In: Proceedings of the 9th International Symposium on High-Performance Computer Architecture, HPCA ’03, pp. 295-306 (2003)
[59] Goh, E.-J., Shacham, H., Modadugu, N., Boneh, D.: SiRiUS: securing remote untrusted storage. In: Proceedings of the Network and Distributed System Security Symposium, NDSS ’03 (2003) · Zbl 0979.11057
[60] Gentry, C., Wichs, D.: Separating succinct non-interactive arguments from all falsifiable assumptions. In: Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, STOC ’11, pp. 99-108 (2011) · Zbl 1288.94063
[61] Hess, F., Smart, N.P., Vercauteren, F.: The Eta pairing revisited. IEEE Trans. Inf. Theory 52(10), 4595-4602 (2006) · Zbl 1189.11057 · doi:10.1109/TIT.2006.881709
[62] Joux, A., Jacques, S.: Lattice reduction: a toolbox for the cryptanalyst. J. Cryptol. 11(3), 161-185 (1998) · Zbl 0919.94011 · doi:10.1007/s001459900042
[63] Kim, T., Kim, S., Cheon, J.H.: On the final exponentiation in Tate pairing computations. IEEE Trans. Inf. Theory 59(6), 4033-4041 (2013) · Zbl 1364.94548 · doi:10.1109/TIT.2013.2240763
[64] Kosba, A.E., Papadopoulos, D., Papamanthou, C., Sayed, M.F., Shi, E., Triandopoulos, N.: TRUESET: faster verifiable set computations. In: Proceedings of the 23rd USENIX Security Symposium, USENIX Security ’14, pp. 765-780 (2014) · Zbl 1016.11021
[65] Kallahalla, M., Riedel, E., Swaminathan, R., Wang, Q., Fu, K.: Plutus: scalable secure file sharing on untrusted storage. In: Proceedings of the 2003 Conference on File and Storage Technologies, FAST ’03 (2003)
[66] Karabina, K., Teske, E.: On prime-order elliptic curves with embedding degrees \[k=\] k= 3, 4, and 6. In: Proceedings of the 8th International Conference on Algorithmic Number Theory, ANTS-VIII ’08, pp. 102-117 (2008) · Zbl 1231.11068
[67] Lipmaa, H.: Progression-free sets and sublinear pairing-based non-interactive zero-knowledge arguments. In: Proceedings of the 9th Theory of Cryptography Conference on Theory of Cryptography, TCC ’12, pp. 169-189 (2012) · Zbl 1303.94090
[68] Lipmaa, H.: Succinct non-interactive zero knowledge arguments from span programs and linear error-correcting codes. In: Proceedings of the 19th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT ’13, pp. 41-60 (2013) · Zbl 1300.94080
[69] Lipmaa, H.: Efficient NIZK arguments via parallel verification of Beneš networks. In: Proceedings of the 9th International Conference on Security and Cryptography for Networks, SCN ’14, pp. 416-434 (2014) · Zbl 1378.94054
[70] Lyubashevsky, V., Micciancio, D.: Generalized compact knapsacks are collision resistant. In: Proceedings of the 33rd International Conference on Automata, Languages and Programming, ICALP ’06, pp. 144-155 (2006) · Zbl 1133.68353
[71] Lauter, K., Montgomery, P.L., Naehrig, M.: An analysis of affine coordinates for pairing computation. In: Proceedings of the 4th International Conference on Pairing-Based Cryptography, Pairing ’10, pp. 1-20 (2010) · Zbl 1287.94079
[72] Lyubashevsky, V., Micciancio, D., Peikert, C., Rosen, A.: SWIFFT: a modest proposal for FFT hashing. In: Proceedings of the 15th International Workshop on Fast Software Encryption, FSE ’08, pp. 54-72 (2008) · Zbl 1154.68403
[73] Lidl, R., Niederreiter, H.: Finite Fields, 2nd edn. Cambridge University Press, Cambridge (1997) · Zbl 1139.11053
[74] Micali, S.: Computationally sound proofs. SIAM J. Comput. 30(4):1253-1298, 2000. Preliminary version appeared in FOCS ’94 · Zbl 1009.68053
[75] Miyaji, A., Nakabayashi, M., Takano, S.: New explicit conditions of elliptic curve traces for FR-reduction. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. 84(5), 1234-1243 (2001) · Zbl 0990.94024
[76] Menezes, A., Okamoto, T., Vanstone, S.: Reducing elliptic curve logarithms to logarithms in a finite field. In: Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, STOC ’91, pp. 80-89 (1991) · Zbl 0801.94011
[77] Mazières, D., Shasha, D.: Don’t trust your file server. In: Proceedings of the 8th Workshop on Hot Topics in Operating Systems, HotOS ’01, pp. 113-118 (2001) · Zbl 1123.94334
[78] Maheshwari, U., Vingralek, R., Shapiro, W.: How to build a trusted database system on untrusted storage. In: Proceedings of the 4th Conference on Symposium on Operating System Design and Implementation, OSDI ’00, pp. 10-10 (2000) · Zbl 0813.14045
[79] Naor, M., Yung, M.: Universal one-way hash functions and their cryptographic applications. In: Proceedings of the 21st Annual ACM Symposium on Theory of Computing, STOC ’89, pp. 33-43 (1989)
[80] Naor, M., Yung, M.: Public-key cryptosystems provably secure against chosen ciphertext attacks. In: Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, STOC ’90, pp. 427-437 (1990)
[81] Odlyzko, A.M.: Discrete logarithms in finite fields and their cryptographic significance. In: Proceedings of the 3rd Annual International Conference on Theory and Application of Cryptographic Techniques, EUROCRYPT ’85, pp. 224-314 (1985) · Zbl 0594.94016
[82] Parno, B., Gentry, C., Howell, J., Raykova, M.: Pinocchio: Nearly practical verifiable computation. In: Proceedings of the 34th IEEE Symposium on Security and Privacy, Oakland ’13, pp. 238-252 (2013) · Zbl 1016.11021
[83] Pohlig, S., Hellman, M.: An improved algorithm for computing logarithms over \[gf(p)\] gf(p) and its cryptographic significance. J. IEEE Trans. Inf. Theory 24(1), 106-110 (1978) · Zbl 0375.68023 · doi:10.1109/TIT.1978.1055817
[84] Pollard, J.M.: Monte Carlo methods for index computation (mod p). Math. Comput. 32(143), 918-924 (1978) · Zbl 0382.10001
[85] Pollard, J.M.: Kangaroos, monopoly and discrete logarithms. J. Cryptol. 13, 437-447 (2000) · Zbl 0979.11057 · doi:10.1007/s001450010010
[86] Peikert, C., Rosen, A.: Efficient collision-resistant hashing from worst-case assumptions on cyclic lattices. In: Proceedings of the 3rd Conference on Theory of Cryptography, TCC ’06, pp. 145-166 (2006) · Zbl 1112.94020
[87] Razborov, A.A.: Lower bounds on the size of bounded depth circuits over a complete basis with logical addition. Math. Notes Acad. Sci. USSR 41(4), 333-338 (1987) · Zbl 0632.94030
[88] Rompel, J.: One-way functions are necessary and sufficient for secure signatures. In: Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, STOC ’90, pp. 387-394 (1990)
[89] Satoh, T., Araki, K.: Fermat quotients and the polynomial time discrete log algorithm for anomalous elliptic curves. Comment. Math. Univ. Sancti Pauli 47(1), 81-92 (1998) · Zbl 1044.11591
[90] Scott, M., Barreto, P.S.: Generating more MNT elliptic curves. Des. Codes Cryptogr. 38(2), 209-217 (2006) · Zbl 1172.14309 · doi:10.1007/s10623-005-0538-1
[91] Scott, M., Benger, N., Charlemagne, M., Dominguez Perez, L.J., Kachisa, E.J.: On the final exponentiation for calculating pairings on ordinary elliptic curves. In: Proceedings of the 3rd International Conference Palo Alto on Pairing-Based Cryptography, Pairing ’09, pp. 78-88 (2009) · Zbl 1248.94093
[92] Setty, S., Braun, B., Vu, V., Blumberg, A.J., Parno, B., Walfish, M.: Resolving the conflict between generality and plausibility in verified computation. In: Proceedings of the 8th EuoroSys Conference, EuroSys ’13, pp. 71-84 (2013)
[93] Setty, S., Blumberg, A.J., Walfish, M.: Toward practical and unconditional verification of remote computations. In: Proceedings of the 13th USENIX Conference on Hot Topics in Operating Systems, HotOS ’11, pp. 29-29 (2011)
[94] Scott, M.: Computing the Tate pairing. In: Proceedings of the The Cryptographers’ Track at the RSA Conference 2005, CT-RSA ’05, pp. 293-304 (2005) · Zbl 1079.94572
[95] Scott, M.: Implementing cryptographic pairings. In: Proceedings of the 1st First International Conference on Pairing-Based Cryptography, Pairing ’07, pp. 177-196 (2007) · Zbl 1148.94432
[96] Semaev, I.A.: Evaluation of discrete logarithms in a group of p-torsion points of an elliptic curve in characteristic p. Math. Comput. 67(221), 353-356 (1998) · Zbl 1016.11021 · doi:10.1090/S0025-5718-98-00887-4
[97] Shanks, D.: Class number, a theory of factorization, and genera. Symp. Pure Math. 20, 415-440 (1971) · Zbl 0223.12006 · doi:10.1090/pspum/020/0316385
[98] Silverman, J.H.: The Arithmetic of Elliptic Curves, 2nd edn. Springer, Berlin (2009) · Zbl 1194.11005 · doi:10.1007/978-0-387-09494-6
[99] Smart, N.P.: The discrete logarithm problem on elliptic curves of trace one. J. Cryptol. 12(3), 193-196 (1999) · Zbl 0963.11068 · doi:10.1007/s001459900052
[100] Setty, S., McPherson, M., Blumberg, A.J., Walfish, M.: Making argument systems for outsourced computation practical (sometimes). In: Proceedings of the 2012 Network and Distributed System Security Symposium, NDSS ’12 (2012) · Zbl 1269.11056
[101] Smolensky, R.: Algebraic methods in the theory of lower bounds for boolean circuit complexity. In: Proceedings of the 19th Annual ACM Symposium on Theory of Computing, STOC ’87, pp. 77-82 (1987)
[102] Solinas, J.A.: Id-based digital signature algorithms. http://cacr.uwaterloo.ca/conferences/2003/ecc2003/solinas.pdf (2003)
[103] Silverman, J.H., Stange, K.E.: Amicable pairs and aliquot cycles for elliptic curves. Exp. Math. 20(3), 329-357 (2011) · Zbl 1269.11056 · doi:10.1080/10586458.2011.565253
[104] Sutherland, A.V.: Computing Hilbert class polynomials with the Chinese remainder theorem. Math. Comput. 80(273), 501-538 (2011) · Zbl 1231.11144 · doi:10.1090/S0025-5718-2010-02373-7
[105] Sutherland, A.V.: Accelerating the CM method. LMS J. Comput. Math. 15, 172-204 (2012) · Zbl 1343.11098 · doi:10.1112/S1461157012001015
[106] Setty, S., Vu, V., Panpalia, N., Braun, B., Blumberg, A.J., Walfish, M.: Taking proof-based verified computation a few steps closer to practicality. In: Proceedings of the 21st USENIX Security Symposium, Security ’12, pp. 253-268 (2012) · Zbl 1016.11021
[107] Thaler, J.: Time-optimal interactive proofs for circuit evaluation. In: Proceedings of the 33rd Annual International Cryptology Conference, CRYPTO ’13, pp. 71-89 (2013) · Zbl 1316.94093
[108] Thaler, J., Roberts, M., Mitzenmacher, M., Pfister, H.: Verifiable computation with massively parallel interactive proofs. CoRR, abs/1202.1350 (2012) · Zbl 1189.11057
[109] Valiant, P.: Incrementally verifiable computation or proofs of knowledge imply time/space efficiency. In: Proceedings of the 5th Theory of Cryptography Conference, TCC ’08, pp. 1-18 (2008) · Zbl 1162.68448
[110] Vercauteren, F.: Optimal pairings. IEEE Trans. Inf. Theory 56(1), 455-461 (2010) · Zbl 1366.94540 · doi:10.1109/TIT.2009.2034881
[111] van Oorschot, P.C., Wiener, M.J.: Parallel collision search with cryptanalytic applications. J. Cryptol. 12(1), 1-28 (1999) · Zbl 0992.94028 · doi:10.1007/PL00003816
[112] Washington, L.C.: Elliptic Curves: Number Theory and Cryptography, 2nd edn. Chapman & Hall/CRC, Boca Raton (2008) · Zbl 1200.11043 · doi:10.1201/9781420071474
[113] Wahby, R.S., Setty, S., Ren, Z., Blumberg, A.J., Walfish, M.: Efficient RAM and control flow in verifiable outsourced computation. In: Proceedings of the 22nd Network and Distributed System Security Symposium, NDSS ’15 (2015)
[114] Zhang, Y., Papamanthou, C., Katz, J.: Alitheia: Towards practical verifiable graph processing. In: Proceedings of the 21st ACM Conference on Computer and Communications Security, CCS ’14, pp. 856-867 (2014)
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.