Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Journal of Cryptology
Published in: Journal of Cryptology 4/2022

01-10-2022 | Research Article

On the (in)Security of ROS

Authors: Fabrice Benhamouda, Tancrède Lepoint, Julian Loss, Michele Orrù, Mariana Raykova

Published in: Journal of Cryptology | Issue 4/2022

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

We present an algorithm solving the ROS (Random inhomogeneities in a Overdetermined Solvable system of linear equations) problem mod p in polynomial time for \(\ell > \log p\) dimensions. Our algorithm can be combined with Wagner’s attack, and leads to a sub-exponential solution for any dimension \(\ell \) with the best complexity known so far. When concurrent executions are allowed, our algorithm leads to practical attacks against unforgeability of blind signature schemes such as Schnorr and Okamoto–Schnorr blind signatures, threshold signatures such as GJKR and the original version of FROST, multisignatures such as CoSI and the two-round version of MuSig, partially blind signatures such as Abe–Okamoto, and conditional blind signatures such as ZGP17. Schemes for e-cash (such as Brands’ signature) and anonymous credentials (such as Anonymous Credentials Light) inspired from the above are also affected.
previous article Breaking the Decisional Diffie–Hellman Problem for Class Group Actions Using Genus Theory: Extended Version
next article Signed (Group) Diffie–Hellman Key Exchange with Tight Security

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
Appendix
Available only for authorised users
Footnotes
1
Okamoto–Schnorr signatures are proven secure only for \(\ell \) parallel executions s.t. \(Q^\ell /p\ll 1\), where Q is the number of queries to \(\textsc {H}_{{\text {ros}}}\). Our attack does not contradict their analysis as our attack requires \(\ell> \log _2 p > \log _Q p\).
 
2
In the actual attack, part of the second step is executed before to allow to choose these polynomials properly.
 
3
Indeed, when considering the exact values of the constants in the asymptotics, the actual complexity of Wagner’s attack is \(2^{\lfloor \log (\ell +1)\rfloor }\cdot 2^{\frac{\lambda }{1 + \lfloor \log (\ell +1)\rfloor }}\).
 
4
We do not use the fact that only a threshold \(t+1\) of the parties are required to sign in our attack. We assume that all the parties come to sign, to simplify the description of the attack.
 
5
Pedersen commitments are unrelated to Pedersen’s DKG, apart from the fact that both were invented by Pedersen.
 
8
From the specification: Multiple U-Prove tokens generated using identical common inputs MAY be issued in parallel [and the computation of M, Z] can be shared among all parallel protocol executions.
 
9
For further information, read the C10K problem (’99) and the C10M problem (’11).
 
Literature
1.
Masayuki Abe. A secure three-move blind signature scheme for polynomially many signatures. In Birgit Pfitzmann, editor, EUROCRYPT 2001, volume 2045 of LNCS, pages 136–151. Springer, Heidelberg, May 2001.
2.
Masayuki Abe and Tatsuaki Okamoto. Provably secure partially blind signatures. In Mihir Bellare, editor, CRYPTO 2000, volume 1880 of LNCS, pages 271–286. Springer, Heidelberg, August 2000.
3.
Foteini Baldimtsi, Anna Lysyanskaya. Anonymous credentials light. In Ahmad-Reza Sadeghi, Virgil D. Gligor, and Moti Yung, editors, ACM CCS 2013, pages 1087–1098. ACM Press, November 2013.
4.
Alexandra Boldyreva. Threshold signatures, multisignatures and blind signatures based on the gap-Diffie-Hellman-group signature scheme. In Yvo Desmedt, editor, PKC 2003, volume 2567 of LNCS, pages 31–46. Springer, Heidelberg, January 2003.
5.
Stefan Brands. Untraceable off-line cash in wallets with observers (extended abstract). In Douglas R. Stinson, editor, CRYPTO’93, volume 773 of LNCS, pages 302–318. Springer, Heidelberg, August 1994.
6.
Tony K. Chan, Karyin Fung, Joseph K. Liu, and Victor K. Wei. Blind spontaneous anonymous group signatures for ad hoc groups. In ESAS, volume 3313 of Lecture Notes in Computer Science, pages 82–94. Springer, 2004.
7.
David Chaum. Blind signatures for untraceable payments. In David Chaum, Ronald L. Rivest, and Alan T. Sherman, editors, CRYPTO’82, pages 199–203. Plenum Press, New York, USA, 1982.
8.
Sherman S. M. Chow, Lucas Chi Kwong Hui, Siu-Ming Yiu, and K. P. Chow. Two improved partially blind signature schemes from bilinear pairings. In Colin Boyd and Juan Manuel González Nieto, editors, ACISP 05, volume 3574 of LNCS, pages 316–328. Springer, Heidelberg, July 2005.
9.
Xiaofeng Chen, Fangguo Zhang, Yi Mu, and Willy Susilo. Efficient provably secure restrictive partially blind signatures from bilinear pairings. In Giovanni Di Crescenzo and Avi Rubin, editors, FC 2006, volume 4107 of LNCS, pages 251–265. Springer, Heidelberg, February / March 2006.
10.
Manu Drijvers, Kasra Edalatnejad, Bryan Ford, Eike Kiltz, Julian Loss, Gregory Neven, and Igors Stepanovs. On the security of two-round multi-signatures. In 2019 IEEE Symposium on Security and Privacy, pages 1084–1101. IEEE Computer Society Press, May 2019.
11.
Paul Feldman. A practical scheme for non-interactive verifiable secret sharing. In 28th FOCS, pages 427–437. IEEE Computer Society Press, October 1987.
12.
Georg Fuchsbauer, Antoine Plouviez, and Yannick Seurin. Blind schnorr signatures and signed ElGamal encryption in the algebraic group model. In Anne Canteaut and Yuval Ishai, editors, EUROCRYPT 2020, Part II, volume 12106 of LNCS, pages 63–95. Springer, Heidelberg, May 2020.
13.
Rosario Gennaro, Stanislaw Jarecki, Hugo Krawczyk, and Tal Rabin. Secure distributed key generation for discrete-log based cryptosystems. Journal of Cryptology, 20(1):51–83, January 2007.MathSciNetCrossRef
14.
Panagiotis Grontas, Aris Pagourtzis, Alexandros Zacharakis, and Bingsheng Zhang. Towards everlasting privacy and efficient coercion resistance in remote electronic voting. In Aviv Zohar, Ittay Eyal, Vanessa Teague, Jeremy Clark, Andrea Bracciali, Federico Pintore, and Massimiliano Sala, editors, FC 2018 Workshops, volume 10958 of LNCS, pages 210–231. Springer, Heidelberg, March 2019.
15.
Eduard Hauck, Eike Kiltz, and Julian Loss. A modular treatment of blind signatures from identification schemes. In Yuval Ishai and Vincent Rijmen, editors, EUROCRYPT 2019, Part III, volume 11478 of LNCS, pages 345–375. Springer, Heidelberg, May 2019.
16.
Eduard Hauck, Eike Kiltz, Julian Loss, and Ngoc Khanh Nguyen. Lattice-based blind signatures, revisited. In Daniele Micciancio and Thomas Ristenpart, editors, CRYPTO 2020, Part II, volume 12171 of LNCS, pages 500–529. Springer, Heidelberg, August 2020.
17.
18.
19.
Julia Kaster, Julian Loss, Michael Rosenberg, and Jiayu Xu. On pairing-free blind signature schemes in the algebraic group model. Cryptology ePrint Archive, Report 2020/1071, 2020.
20.
21.
22.
Lorenz Minder and Alistair Sinclair. The extended k-tree algorithm. In Claire Mathieu, editor, 20th SODA, pages 586–595. ACM-SIAM, January 2009.
23.
David Pointcheval and Jacques Stern. Security arguments for digital signatures and blind signatures. Journal of Cryptology, 13(3):361–396, June 2000.CrossRef
24.
Christian Paquin and Greg Zaverucha. U-prove cryptographic specification v1. 1. Technical Report, Microsoft Corporation, 2011.
25.
26.
Claus-Peter Schnorr. Security of blind discrete log signatures against interactive attacks. In Sihan Qing, Tatsuaki Okamoto, and Jianying Zhou, editors, ICICS 01, volume 2229 of LNCS, pages 1–12. Springer, Heidelberg, November 2001.
27.
Ewa Syta, Iulia Tamas, Dylan Visher, David Isaac Wolinsky, Philipp Jovanovic, Linus Gasser, Nicolas Gailly, Ismail Khoffi, and Bryan Ford. Keeping authorities “honest or bust” with decentralized witness cosigning. In 2016 IEEE Symposium on Security and Privacy, pages 526–545. IEEE Computer Society Press, May 2016.
28.
29.
David Wagner. A generalized birthday problem. In Moti Yung, editor, CRYPTO 2002, volume 2442 of LNCS, pages 288–303. Springer, Heidelberg, August 2002.
30.
Tsz Hon Yuen and Victor K. Wei. Fast and proven secure blind identity-based signcryption from pairings. In Alfred Menezes, editor, CT-RSA 2005, volume 3376 of LNCS, pages 305–322. Springer, Heidelberg, February 2005.
31.
Metadata
Title
On the (in)Security of ROS
Authors
Fabrice Benhamouda
Tancrède Lepoint
Julian Loss
Michele Orrù
Mariana Raykova
Publication date
01-10-2022
Publisher
Springer US
Published in
Journal of Cryptology / Issue 4/2022
Print ISSN: 0933-2790
Electronic ISSN: 1432-1378
DOI
https://doi.org/10.1007/s00145-022-09436-0

Other articles of this Issue 4/2022

Journal of Cryptology 4/2022 Go to the issue

Research Article

Signed (Group) Diffie–Hellman Key Exchange with Tight Security

Research Article

The Inverse of and Its Applications to Rasta-Like Ciphers

Research Article

Improved Differential-Linear Attacks with Applications to ARX Ciphers

Research Article

Efficient Perfectly Secure Computation with Optimal Resilience

Research Article

Breaking the Decisional Diffie–Hellman Problem for Class Group Actions Using Genus Theory: Extended Version

Research Article

ZK-PCPs from Leakage-Resilient Secret Sharing

Premium Partner

    Image Credits