Succinct Non-interactive Arguments of Knowledge from Supersingular Isogenies

• Paulo L. Barreto University of Washington http://orcid.org/0000-0001-8832-3071
• Marcos A. Simplicio Jr USP https://orcid.org/0000-0001-5227-7165
• Gustavo H. M. Zanon University of Washington

DOI: https://doi.org/10.5753/sbseg.2022.225292

Resumo

A succinct non-interactive argument of knowledge (SNARK) enables a party to convince another of some statement (typically, knowledge of some information) by means of a short argument, while ensuring it is infeasible for an adversary to create a short argument of the opposite statement. We hereby describe a SNARK for CSI-FiSh signatures, whose security stems from hard problems involving supersingular isogenies. Although the scheme looks analogous to a SNARK for conventional Schnorr signatures, it is non-trivial in that, as we also show, a similar SNARK for another isogeny-based signature scheme (SQISign) is not viable. As a bonus, we also discuss how to drastically reduce the memory needed to implement the CSIDH framework required by CSI-FiSh signatures.

Palavras-chave: Cryptography, Succinct non-interactive argument of knowledge (SNARK), CSI-FiSh signatures, supersingular isogenies

Referências

Au, M. H., Susilo, W., and Mu, Y. (2006). Constant-size dynamic k-TAA. In Security and Cryptography for Networks, pages 111–125, Berlin, Heidelberg. Springer. DOI: 10.1007/11832072_8.

Babai, L. (1986). On Lovasz lattice reduction and the nearest lattice point problem. Combinatorica, 6:1–13. DOI:10.1007/BF02579403.

Bertoni, G., Daemen, J., Peeters, M., and Van Assche, G. (2008). On the indifferentiability of the sponge construction. In Advances in Cryptology – EUROCRYPT 2008, pages 181–197, Berlin, Heidelberg. Springer. DOI:10.1007/978-3-540-78967-3_11.

Beullens, W., Kleinjung, T., and Vercauteren, F. (2019). CSI-FiSh: Efficient isogeny based signatures through class group computations. In Advances in Cryptology – ASIACRYPT 2019, pages 227–247, Cham. Springer International Publishing. DOI: 10.1007/978-3-030-34578-5_9.

Camenisch, J. (1998). Group signature schemes and payment systems based on the discrete logarithm problem. PhD thesis, ETH Zurich. DOI:10.3929/ethz-a-001923735.

Camenisch, J. and Lysyanskaya, A. (2004). Signature schemes and anonymous credentials from bilinear maps. In Advances in Cryptology – CRYPTO 2004, pages 56–72, Berlin, Heidelberg. Springer. DOI:10.1007/978-3-540-28628-8_4.

Castryck, W. and Decru, T. (2022). An efficient key recovery attack on SIDH (preliminary version). Cryptology ePrint Archive, Paper 2022/975. https://eprint.iacr.org/2022/975.

Castryck, W., Lange, T., Martindale, C., Panny, L., and Renes, J. (2018). CSIDH: An efficient post-quantum commutative group action. In Advances in Cryptology – ASIACRYPT 2018, pages 395–427, Cham. Springer International Publishing. DOI: 10.1007/978-3-030-03332-3_15.

De Feo, L., Kohel, D., Leroux, A., Petit, C., and Wesolowski, B. (2020). SQISign: Compact post-quantum signatures from quaternions and isogenies. In Advances in Cryptology – ASIACRYPT 2020, pages 64–93, Cham. Springer International Publishing. DOI:10.1007/978-3-030-64837-4_3.

Fiat, A. and Shamir, A. (1987). How to prove yourself: Practical solutions to identification and signature problems. In Advances in Cryptology — CRYPTO’ 86, pages 186–194, Berlin, Heidelberg. Springer. DOI:10.1007/3-540-47721-7_12.

Galindo, D. and Garcia, F. (2009). A Schnorr-like lightweight identity-based signature scheme. In Progress in Cryptology – AFRICACRYPT 2009, pages 135–148, Berlin, Heidelberg. Springer.

Ganesh, C., Nitulescu, A., and Soria-Vazquez, E. (2021). Rinocchio: SNARKs for ring arithmetic. Cryptology ePrint Archive, Paper 2021/322. https://eprint.iacr.org/2021/322.

Groth, J. (2010). Short pairing-based non-interactive zero-knowledge arguments. In Advances in Cryptology - ASIACRYPT 2010, pages 321–340, Berlin, Heidelberg. Springer. DOI:10.1007/978-3-642-17373-8_19.

Montgomery, P. L. (1987). Speeding the Pollard and elliptic curve methods of factorization. Mathematics of computation, 48(177):243–264. DOI:10.1090/S0025-5718-1987-0866113-7.

Ruskey, F. (2003). Combinatorial generation. Draft book. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.93.5967.

Schnorr, C. P. (1990). Efficient identification and signatures for smart cards. In Advances in Cryptology — CRYPTO ’89 Proceedings, pages 239–252, New York, NY. Springer New York. DOI:10.1007/0-387-34805-0_22.