Banquet: short and fast signatures from AES. (English) Zbl 1479.94291
Garay, Juan A. (ed.), Public-key cryptography – PKC 2021. 24th IACR international conference on practice and theory of public key cryptography, virtual event, May 10–13, 2021. Proceedings. Part I. Cham: Springer. Lect. Notes Comput. Sci. 12710, 266-297 (2021).
Summary: This work introduces Banquet, a digital signature scheme with post-quantum security, constructed using only symmetric-key primitives. The design is based on the MPC-in-head paradigm also used by Picnic and BBQ. Like BBQ, Banquet uses only standardized primitives, namely AES and SHA-3, but signatures are more than 50% shorter, making them competitive with Picnic (which uses a non-standard block cipher to improve performance). The MPC protocol in Banquet uses a new technique to verify correctness of the AES S-box computations, which is efficient because the cost is amortized with a batch verification strategy. Our implementation and benchmarks also show that both signing and verification can be done in under 10ms on a current x64 CPU. We also explore the parameter space to show the range of trade-offs that are possible with the Banquet design, and show that Banquet can nearly match the signature sizes possible with Picnic (albeit with slower, but still practical run times) or have speed within a factor of two of Picnic (at the cost of larger signatures).
For the entire collection see [Zbl 1476.94003].
For the entire collection see [Zbl 1476.94003].
MSC:
| 94A62 | Authentication, digital signatures and secret sharing |
| 94A60 | Cryptography |
| 81P94 | Quantum cryptography (quantum-theoretic aspects) |
References:
| [1] | Albrecht, MR; Rechberger, C.; Schneider, T.; Tiessen, T.; Zohner, M.; Oswald, E.; Fischlin, M., Ciphers for MPC and FHE, Advances in Cryptology - EUROCRYPT 2015, 430-454 (2015), Heidelberg: Springer, Heidelberg · Zbl 1370.94477 · doi:10.1007/978-3-662-46800-5_17 |
| [2] | Ames, S., Hazay, C., Ishai, Y., Venkitasubramaniam, M.: Ligero: lightweight sublinear arguments without a trusted setup. In: ACM CCS 2017, pp. 2087-2104. ACM Press, November 2017 |
| [3] | Baum, C.; Nof, A.; Kiayias, A.; Kohlweiss, M.; Wallden, P.; Zikas, V., Concretely-efficient zero-knowledge arguments for arithmetic circuits and their application to lattice-based cryptography, Public-Key Cryptography - PKC 2020, 495-526 (2020), Cham: Springer, Cham · Zbl 1502.94029 · doi:10.1007/978-3-030-45374-9_17 |
| [4] | Baum, C., de Saint Guilhem, C.D., Kales, D., Orsini, E., Scholl, P., Zaverucha, G.: Banquet: short and fast signatures from AES. Cryptology ePrint Archive, Report 2021/068 (2021). Full version of this paper: https://eprint.iacr.org/2021/068 · Zbl 1479.94291 |
| [5] | Ben-Sasson, E.; Chiesa, A.; Riabzev, M.; Spooner, N.; Virza, M.; Ward, NP; Ishai, Y.; Rijmen, V., Aurora: transparent succinct arguments for R1CS, Advances in Cryptology - EUROCRYPT 2019, 103-128 (2019), Cham: Springer, Cham · Zbl 1470.94079 · doi:10.1007/978-3-030-17653-2_4 |
| [6] | Bernstein, D.J., Hülsing, A., Kölbl, S., Niederhagen, R., Rijneveld, J., Schwabe, P.: The \(SPHINCS^+\) signature framework. In: Cavallaro, L., Kinder, J., Wang, X., Katz, J. (eds.) ACM CCS 2019, pp. 2129-2146. ACM Press, November 2019 |
| [7] | Beullens, W.; Canteaut, A.; Ishai, Y., Sigma protocols for MQ, PKP and SIS, and fishy signature schemes, Advances in Cryptology - EUROCRYPT 2020, 183-211 (2020), Cham: Springer, Cham · Zbl 1479.94295 · doi:10.1007/978-3-030-45727-3_7 |
| [8] | Beullens, W.; Delpech de Saint Guilhem, C.; Ding, J.; Tillich, J-P, LegRoast: efficient post-quantum signatures from the Legendre PRF, Post-Quantum Cryptography, 130-150 (2020), Cham: Springer, Cham · Zbl 1501.94066 · doi:10.1007/978-3-030-44223-1_8 |
| [9] | Bhadauria, R., Fang, Z., Hazay, C., Venkitasubramaniam, M., Xie, T., Zhang, Y.: Ligero++: a new optimized sublinear IOP. In: CCS, pp. 2025-2038. ACM (2020) |
| [10] | Boneh, D.; Boyle, E.; Corrigan-Gibbs, H.; Gilboa, N.; Ishai, Y.; Boldyreva, A.; Micciancio, D., Zero-knowledge proofs on secret-shared data via fully linear PCPs, Advances in Cryptology - CRYPTO 2019, 67-97 (2019), Cham: Springer, Cham · Zbl 1436.94043 · doi:10.1007/978-3-030-26954-8_3 |
| [11] | Boneh, D.; Dagdelen, Ö.; Fischlin, M.; Lehmann, A.; Schaffner, C.; Zhandry, M.; Lee, DH; Wang, X., Random oracles in a quantum world, Advances in Cryptology - ASIACRYPT 2011, 41-69 (2011), Heidelberg: Springer, Heidelberg · Zbl 1227.94033 · doi:10.1007/978-3-642-25385-0_3 |
| [12] | Boyle, E., Gilboa, N., Ishai, Y., Nof, A.: Practical fully secure three-party computation via sublinear distributed zero-knowledge proofs. In: Cavallaro, L., Kinder, J., Wang, X., Katz, J. (eds.) ACM CCS 2019, pp. 869-886. ACM Press, November 2019 |
| [13] | Casanova, A., Faugere, J.C., Macario-Rat, G., Patarin, J., Perret, L., Ryckeghem, J.: GeMSS: a great multivariate short signature. Submission to the NIST’s post-quantum cryptography standardization process (2017) |
| [14] | Chase, M., et al.: Post-quantum zero-knowledge and signatures from symmetric-key primitives. In: Thuraisingham, B.M., Evans, D., Malkin, T., Xu, D. (eds.) ACM CCS 2017, pp. 1825-1842. ACM Press, October-November 2017 |
| [15] | De Feo, L.; Galbraith, SD; Ishai, Y.; Rijmen, V., SeaSign: compact isogeny signatures from class group actions, Advances in Cryptology - EUROCRYPT 2019, 759-789 (2019), Cham: Springer, Cham · Zbl 1509.94155 · doi:10.1007/978-3-030-17659-4_26 |
| [16] | de Saint Guilhem, CD; De Meyer, L.; Orsini, E.; Smart, NP; Paterson, KG; Stebila, D., BBQ: using AES in Picnic signatures, Selected Areas in Cryptography - SAC 2019, 669-692 (2020), Cham: Springer, Cham · Zbl 1457.94204 · doi:10.1007/978-3-030-38471-5_27 |
| [17] | Ding, J.; Schmidt, D.; Ioannidis, J.; Keromytis, A.; Yung, M., Rainbow, a new multivariable polynomial signature scheme, Applied Cryptography and Network Security, 164-175 (2005), Heidelberg: Springer, Heidelberg · Zbl 1126.68393 · doi:10.1007/11496137_12 |
| [18] | Dinur, I.; Liu, Y.; Meier, W.; Wang, Q.; Iwata, T.; Cheon, JH, Optimized interpolation attacks on LowMC, Advances in Cryptology - ASIACRYPT 2015, 535-560 (2015), Heidelberg: Springer, Heidelberg · Zbl 1382.94092 · doi:10.1007/978-3-662-48800-3_22 |
| [19] | Don, J.; Fehr, S.; Majenz, C.; Micciancio, D.; Ristenpart, T., The measure-and-reprogram technique 2.0: multi-round Fiat-Shamir and more, Advances in Cryptology - CRYPTO 2020, 602-631 (2020), Cham: Springer, Cham · Zbl 1504.94134 · doi:10.1007/978-3-030-56877-1_21 |
| [20] | Don, J.; Fehr, S.; Majenz, C.; Schaffner, C.; Boldyreva, A.; Micciancio, D., Security of the Fiat-Shamir transformation in the quantum random-oracle model, Advances in Cryptology - CRYPTO 2019, 356-383 (2019), Cham: Springer, Cham · Zbl 1509.81365 · doi:10.1007/978-3-030-26951-7_13 |
| [21] | Ducas, L.; Kiltz, E.; Lepoint, T.; Lyubashevsky, V.; Schwabe, P.; Seiler, G.; Stehlé, D., CRYSTALS-Dilithium: a lattice-based digital signature scheme, IACR TCHES, 2018, 1, 238-268 (2018) · doi:10.46586/tches.v2018.i1.238-268 |
| [22] | Fiat, A.; Shamir, A.; Odlyzko, AM, How to prove yourself: practical solutions to identification and signature problems, Advances in Cryptology—CRYPTO 1986, 186-194 (1987), Heidelberg: Springer, Heidelberg · Zbl 0636.94012 · doi:10.1007/3-540-47721-7_12 |
| [23] | Fouque, P.A., et al.: Falcon: fast-Fourier lattice-based compact signatures over NTRU. Submission to the NIST’s post-quantum cryptography standardization process (2018) |
| [24] | Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: Ladner, R.E., Dwork, C. (eds.) 40th ACM STOC, pp. 197-206. ACM Press, May 2008 · Zbl 1231.68124 |
| [25] | Giacomelli, I., Madsen, J., Orlandi, C.: ZKBoo: faster zero-knowledge for Boolean circuits. In: Holz, T., Savage, S. (eds.) USENIX Security 2016, pp. 1069-1083. USENIX Association, August 2016 |
| [26] | Goldwasser, S.; Micali, S.; Rivest, RL, A digital signature scheme secure against adaptive chosen-message attacks, SIAM J. Comput., 17, 2, 281-308 (1988) · Zbl 0644.94012 · doi:10.1137/0217017 |
| [27] | Ishai, Y., Kushilevitz, E., Ostrovsky, R., Sahai, A.: Zero-knowledge from secure multiparty computation. In: Johnson, D.S., Feige, U. (eds.) 39th ACM STOC, pp. 21-30. ACM Press, June 2007 · Zbl 1232.68044 |
| [28] | Kales, D.; Ramacher, S.; Rechberger, C.; Walch, R.; Werner, M.; Jarecki, S., Efficient FPGA implementations of LowMC and Picnic, Topics in Cryptology - CT-RSA 2020, 417-441 (2020), Cham: Springer, Cham · doi:10.1007/978-3-030-40186-3_18 |
| [29] | Kales, D.; Zaverucha, G.; Krenn, S.; Shulman, H.; Vaudenay, S., An attack on some signature schemes constructed from five-pass identification schemes, Cryptology and Network Security, 3-22 (2020), Cham: Springer, Cham · Zbl 1520.94078 · doi:10.1007/978-3-030-65411-5_1 |
| [30] | Kales, D.; Zaverucha, G., Improving the performance of the Picnic signature scheme, IACR TCHES, 2020, 4, 154-188 (2020) · doi:10.46586/tches.v2020.i4.154-188 |
| [31] | Katz, J., Kolesnikov, V., Wang, X.: Improved non-interactive zero knowledge with applications to post-quantum signatures. In: Lie, D., Mannan, M., Backes, M., Wang, X. (eds.) ACM CCS 2018, pp. 525-537. ACM Press, October 2018 |
| [32] | Liu, F., Isobe, T., Meier, W.: Cryptanalysis of full LowMC and LowMC-M with algebraic techniques. Cryptology ePrint Archive, Report 2020/1034 (2020) |
| [33] | Lyubashevsky, V.; Pointcheval, D.; Johansson, T., Lattice signatures without trapdoors, Advances in Cryptology - EUROCRYPT 2012, 738-755 (2012), Heidelberg: Springer, Heidelberg · Zbl 1295.94111 · doi:10.1007/978-3-642-29011-4_43 |
| [34] | National Institute of Standards and Technology: Round 3 Submissions for the NIST Post-Quantum Cryptography Project (2020). https://csrc.nist.gov/Projects/post-quantum-cryptography/round-3-submissions. Accessed 11 Nov 2020 |
| [35] | Rechberger, C.; Soleimany, H.; Tiessen, T., Cryptanalysis of low-data instances of full LowMCv2, IACR Trans. Symm. Cryptol., 2018, 3, 163-181 (2018) · doi:10.46586/tosc.v2018.i3.163-181 |
| [36] | Zaverucha, G., et al.: Picnic. Technical report, National Institute of Standards and Technology (2019). https://csrc.nist.gov/projects/post-quantum-cryptography/round-2-submissions |
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.
