Introducing two ROS attack variants: breaking one-more unforgeability of BZ blind signatures

• Bruno M. F. Ricardo USP
• Lucas C. Cardoso USP
• Leonardo Kimura USP
• Marcos A. Simplicio Junior USP
• Paulo L. Barreto University of Washington

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

Abstract

In 2023, Barreto and Zanon proposed a three-round Schnorr-like blind signature scheme, leveraging zero-knowledge proofs to produce one-time signatures as an intermediate step of the protocol. The resulting scheme, called BZ, is proven secure in the discrete-logarithm setting under the one-more discrete logarithm assumption with (allegedly) resistance to the Random inhomogeneities in a Overdetermined Solvable system of linear equations modulo a prime number p attack, commonly referred to as ROS attack. The authors argue that the scheme is resistant against a ROS-based attack by building an adversary whose success depends on extracting the discrete logarithm of the intermediate signing key. In this paper, however, we describe a distinct ROS attack on the BZ scheme, in which a probabilistic polynomial-time attacker can bypass the zero-knowledge proof step to break the one-more unforgeability of the scheme. We also built a BZ variant that, by using one secure hash function instead of two, can prevent this particular attack. Unfortunately, though, we show yet another ROS attack that leverages the BZ scheme’s structure to break the one-more unforgeability principle again, thus revealing that this variant is also vulnerable. These results indicate that, like other Schnorr-based strategies, it is hard to build a secure blind signature scheme using BZ’s underlying structure.

Keywords: Blind signature, Schnorr, ROS, Zero-knowledge proofs, Cryptanalysis

References

Barreto, P., Jr, M. S., and Zanon, G. (2022). Succinct non-interactive arguments of knowledge from supersingular isogenies. In Anais do XXII Simpósio Brasileiro de Segurança da Informação e de Sistemas Computacionais, pages 181–194, Porto Alegre, RS, Brasil. SBC.

Barreto, P., Reich, D., Jr., M. S., and Zanon, G. (2023). Blind signatures from zero knowledge in the kummer variety. In Anais do XXIII Simpósio Brasileiro de Segurança da Informação e de Sistemas Computacionais, pages 139–152, Porto Alegre, RS, Brasil. SBC.

Barreto, P., Simplicio, M., Ricardini, J., and Patil, H. (2020). Schnorr-based implicit certification: Improving the security and efficiency of vehicular communications. IEEE Transactions on Computers, 70(3):393–399.

Barreto, P. and Zanon, G. (2023). Blind signatures from zero-knowledge arguments. Cryptology ePrint Archive, Paper 2023/067.

Bellare, M., Crites, E., Komlo, C., Maller, M., Tessaro, S., and Zhu, C. (2022). Better than advertised security for non-interactive threshold signatures. In Annual International Cryptology Conference (Crypto’22), pages 517–550. Springer.

Bellare, M., Namprempre, C., Pointcheval, D., and Semanko, M. (2003). The one-more-rsa-inversion problems and the security of chaum’s blind signature scheme. Journal of Cryptology, 16(3):185–215.

Benhamouda, F., Lepoint, T., Loss, J., Orrù, M., and Raykova, M. (2021). On the (in)security of ros. In Advances in Cryptology – EUROCRYPT 2021, pages 33–53, Cham. Springer International Publishing.

Boldyreva, A. (2002). Threshold signatures, multisignatures and blind signatures based on the gap-diffie-hellman-group signature scheme. In Public Key Cryptography — PKC 2003, pages 31–46, Berlin, Heidelberg. Springer Berlin Heidelberg.

Chairattana-Apirom, R., Tessaro, S., and Zhu, C. (2024). Pairing-free blind signatures from cdh assumptions. In Advances in Cryptology – CRYPTO 2024, pages 174–209, Cham. Springer Nature Switzerland.

Chaum, D. (1983). Blind signatures for untraceable payments. In Advances in Cryptology, pages 199–203, Boston, MA. Springer US.

Coron, J. (2000). On the exact security of full domain hash. In Advances in Cryptology — CRYPTO 2000, pages 229–235, Berlin, Heidelberg. Springer Berlin Heidelberg.

Denis, F., Jacobs, F., and Wood, C. (2023). RSA Blind Signatures. RFC 9474.

Fuchsbauer, G. and Wolf, M. (2024). Concurrently secure blind schnorr signatures. In Advances in Cryptology – EUROCRYPT 2024, pages 124–160, Cham. Springer Nature Switzerland.

Fujioka, A., Okamoto, T., and Ohta, K. (1993). A practical secret voting scheme for large scale elections. In Advances in Cryptology — AUSCRYPT ’92, pages 244–251, Berlin, Heidelberg. Springer Berlin Heidelberg.

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 Berlin Heidelberg.

Hanzlik, L., Loss, J., and Wagner, B. (2023). Rai-choo! evolving blind signatures to the next level. In Advances in Cryptology – EUROCRYPT 2023, pages 753–783, Cham. Springer Nature Switzerland.

Hauck, E., Kiltz, E., and Loss, J. (2019). A modular treatment of blind signatures from identification schemes. In Advances in Cryptology – EUROCRYPT 2019, pages 345–375, Cham. Springer International Publishing.

Hauck, E., Kiltz, E., Loss, J., and Nguyen, N. (2020). Lattice-based blind signatures, revisited. In Advances in Cryptology – CRYPTO 2020, pages 500–529, Cham. Springer International Publishing.

Katsumata, S., Lai, Y., LeGrow, J., and Qin, L. (2024). Csi-otter: isogeny-based (partially) blind signatures from the class group action with a twist. Designs, Codes and Cryptography, 92(11):3587–3643.

Katz, J., Loss, J., and Rosenberg, M. (2021). Boosting the security of blind signature schemes. In Advances in Cryptology – ASIACRYPT 2021, pages 468–492, Cham. Springer International Publishing.

Lysyanskaya, A. (2023). Security analysis of rsa-bssa. In Public-Key Cryptography – PKC 2023, pages 251–280, Cham. Springer Nature Switzerland.

Qin, X., Cai, C., and Yuen, T. (2021). One-more unforgeability of blind ecdsa. In Computer Security – ESORICS 2021, pages 313–331, Cham. Springer International Publishing.

Randall, K. (2023). Nist Special Publication (SP) 800-186, Recommendations for Discrete Logarithm-based Cryptography: Elliptic Curve Domain Parameters — csrc.nist.gov. [link]. [Accessed 05-02-2025].

Schnorr, C. (1990). Efficient identification and signatures for smart cards. In Advances in Cryptology — CRYPTO’ 89 Proceedings, pages 239–252, New York, NY. Springer New York.

Schnorr, C. (2001). Security of blind discrete log signatures against interactive attacks. In Information and Communications Security, pages 1–12, Berlin, Heidelberg. Springer Berlin Heidelberg.

Wagner, D. (2002). A generalized birthday problem. In Advances in Cryptology — CRYPTO 2002, pages 288–304, Berlin, Heidelberg. Springer Berlin Heidelberg.

Wuille, P., Nick, J., and Ruffing, T. (2020a). Schnorr signatures for secp256k1. Bitcoin improvement proposals.

Wuille, P., Nick, J., and Towns, A. (2020b). Taproot: Segwit version 1 spending rules. Bitcoin improvement proposals.