Parallel Collision Search with Cryptanalytic Applications
Open accessThe claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
No quantum algorithm with better time-space product complexity than O(N^{1/2}), achieved by the state-of-the-art classical algorithm, had been reported.
“Quoting the work, no quantum algorithm with better time-space product complexity than O(N 1/2 ) which is achieved by the state-of-the-art classical algorithm [25] had not been reported.”
From Time–space complexity of quantum search algorithms in symmetric cryptanalysis: applying to AES and SHA-2 (2018) · cites this paper as [25]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
Special Feature Exhaustive Cryptanalysis of the NBS Data Encryption Standard
Diffie, W., & Hellman, M. E. (1977) · Computer · doi:10.1109/c-m.1977.217750 · Cited by 567 · see citing works
Flajolet, P., & Odlyzko, A. M. (2007) · Lecture Notes in Computer Science · doi:10.1007/3-540-46885-4_34 · Cited by 274 · see citing works
Flagged first, then by citations
Research works printed but not linked: 38
- G.B. Agnew, R.C. Mullin, and S.A. Vanstone, On the development of a fast elliptic curve cryptosystem. Advances in Cryptology-Eurocrypt '92 Proceedings, Lecture Notes in Computer Science, vol. 658, Springer-Verlag, Berlin, pp. 482-487.
- G.B. Agnew, R.C. Mullin, and S.A. Vanstone, An implementation of elliptic curve cryptosystems over F 2 155 , IEEE J. Selected Areas Commun., vol. 11, no. 5 (June 1993), pp. 804-813.
- H.R. Amirazizi and M.E. Hellman, Time-memory-processor tradeoffs, IEEE Trans. Inform. Theory, vol. 34, no. 3 (1988), pp. 505-512.
- E. Bach, Toward a theory of Pollard's rho method, Inform. and Comput., vol. 90 (1991), pp. 139-155.
- A. Bosselaers and B. Preneel, editors, Integrity Primitives for Secure Information Systems: Final Report of RACE Integrity Primitives Evaluation (RIPE-RACE 1040), Lecture Notes in Computer Science, vol. 1007, Springer-Verlag, Berlin, 1995.
- I.F. Blake, An Introduction to Applied Probability, Wiley, New York, 1979.
- R.P. Brent, An improved Monte Carlo factorization algorithm, BIT, vol. 20 (1980), pp. 176-184.
- R.P. Brent, Parallel algorithms for integer factorization, in Number Theory and Cryptography, J.H. Loxton (ed.), London Mathematical Society Lecture Note Series, vol. 154, Cambridge University Press, Cambridge, 1990, pp. 26-37.
- K.W. Campbell and M.J. Wiener, DES is not a group, Advances in Cryptology-Crypto '92 Proceedings, Lecture Notes in Computer Science, vol. 740, Springer-Verlag, Berlin, pp. 512-520.
- D.E. Denning, Cryptography and Data Security, Addison-Wesley, Reading, MA, 1982.
- B. Dixon and A.K. Lenstra, Factoring integers using SIMD sieves, Advances in Cryptology-Eurocrypt '93, Lecture Notes in Computer Science, vol. 765, Springer-Verlag, Berlin, pp. 28-39.
- H. Dobbertin, Cryptanalysis of MD4, Fast Software Encryption, Third Annual Workshop, Lecture Notes in Computer Science, vol. 1039, Springer-Verlag, Berlin, 1996, pp. 53-69.
- H. Dobbertin, A. Bosselaers, and B. Preneel, RIPEMD-160: A strengthened version of RIPEMD, Fast Software Encryption, Third Annual Workshop, Lecture Notes in Computer Science, vol. 1039, Springer- Verlag, Berlin, 1996, pp. 71-82.
- S. Even and O. Goldreich, On the power of cascade ciphers, ACM Trans. Comput. Systems, vol. 3, no. 2 (1985).
- A. Fiat and M. Naor, Rigorous time/space tradeoffs for inverting functions, Manuscript. Preliminary version in Proc. 23rd ACM STOC, 1991, pp. 534-541.
- R. Golliver, A.K. Lenstra, and K.S. McCurley, Lattice Sieving and Trial Division, presented at the Algorithmic Number Theory Symposium (ANTS '94), Cornell University, May 1994.
- R. Heiman, A note on discrete logarithms with special structure, Advances in Cryptology-Eurocrypt '92, Lecture Notes in Computer Science, vol. 658, Springer-Verlag, Berlin, pp. 454-457.
- M.E. Hellman, A cryptanalytic time-memory trade-off, IEEE Trans. Inform. Theory, vol. 6 (1980), pp. 401-406.
- B.S. Kaliski, Jr., R.L. Rivest, and A.T. Sherman, Is the Data Encryption Standard a group? (Results of cycling experiments on DES), J. Cryptology, vol. 1, no. 1 (1988), pp. 3-36.
- D.E. Knuth, The Art of Computer Programming, vol. 3, Addison-Wesley, Reading, MA, 1973.
- D.E. Knuth, The Art of Computer Programming, vol. 2, 2nd edition, Addison-Wesley, Reading, MA, 1981.
- A.K. Lenstra, H.W. Lenstra, M.S. Manasse, and J.M. Pollard, The factorization of the ninth Fermat number, Math. Comp., vol. 61 (1993), pp. 319-349.
- A.K. Lenstra and M.S. Manasse, Factoring by electronic mail, Advances in Cryptology-Eurocrypt '89 Proceedings, Lecture Notes in Computer Science, vol. 434, Springer-Verlag, Berlin, pp. 355-371.
- K.S. McCurley, The discrete logarithm problem, in Cryptology and Computational Number Theory, Proceedings of Symposia in Applied Mathematics, vol. 42, American Mathematical Society, Providence, RI, 1990, pp. 49-74.
- R. Merkle and M. Hellman, On the security of multiple encryption, Comm. ACM, vol. 24, no. 7 (1981), pp. 465-467. See also Comm. ACM, vol. 24, no. 11 (1981), p. 776.
- C.H. Meyer and M. Schilling, Secure program load with modification detection code, Proc. 6th Worldwide Congress on Computer and Communications Security and Protection (SECURICOM '88), Paris, March 1988, pp. 111-130.
- K. Nishimura and M. Sibuya, Probability to meet in the middle, J. Cryptology, vol. 2, no. 1 (1990), pp. 13-22.
- S.C. Pohlig and M.E. Hellman, An improved algorithm for computing discrete logarithms over GF( p) and its cryptographic significance, IEEE Trans. Inform. Theory, vol. 24 (1978), pp. 106-110.
- J.M. Pollard, A Monte Carlo method for factorization, BIT, vol. 15 (1975), pp. 331-334.
- J.M. Pollard, Monte Carlo methods for index computation (mod p), Math. Comp., vol. 32, no. 143 (1978), pp. 918-924.
- J.-J. Quisquater and J.-P. Delescaille, How easy is collision search? Application to DES, Advances in Cryptology-Eurocrypt '89 Proceedings, Lecture Notes in Computer Science, vol. 434, Springer-Verlag, Berlin, pp. 429-434.
- J.-J. Quisquater and J.-P. Delescaille, How easy is collision search. New results and applications to DES, Advances in Cryptology-Crypto '89 Proceedings, Lecture Notes in Computer Science, vol. 435, Springer-Verlag, Berlin, pp. 408-413.
- C.P. Schnorr, Efficient signature generation by smart cards, J. Cryptology, vol. 4, no. 3 (1991), pp. 161- 174.
- R. Sedgewick, T.G. Szymanski, and A.C. Yao, The complexity of finding cycles in periodic functions, SIAM J. Comput., vol. 11, no. 2 (1982), pp. 376-390.
- P.C. van Oorschot and M.J. Wiener, A known-plaintext attack on two-key triple encryption, Advances in Cryptology-Eurocrypt '90 Proceedings, Lecture Notes in Computer Science, vol. 473, Springer-Verlag, Berlin, pp. 318-325.
- P.C. van Oorschot and M.J. Wiener, Parallel collision search with application to hash functions and discrete logarithms, Proc. 2nd ACM Conf. on Computer and Communications Security, Fairfax, VA, November 1994, pp. 210-218.
- P.C. van Oorschot and M.J. Wiener, Improving implementable meet-in-the-middle attacks by orders of magnitude, Advances in Cryptology-Crypto '96 Proceedings, Lecture Notes in Computer Science, vol. 1109, Springer-Verlag, Berlin, pp. 229-236.
- G. Yuval, How to swindle Rabin, Cryptologia, vol. 3, no. 3 (1979), pp. 187-189.
Cited by
Sorted by citations
Curve25519: New Diffie-Hellman speed records
Bernstein, D. J. (2006) · Lecture Notes in Computer Science · doi:10.1007/11745853_14 · Cited by 859 · see citing works
Status report on the third round of the NIST Post-Quantum Cryptography Standardization process
Alagic, G., Apon, D., Cooper, D., Dang, Q., Dang, T., Kelsey, J., Lichtinger, J., Liu, Y.-K., Miller, C., Moody, D., et al. (2022) · doi:10.6028/nist.ir.8413-upd1 · Cited by 301 · see citing works
SoK: SSL and HTTPS: Revisiting Past Challenges and Evaluating Certificate Trust Model Enhancements
Clark, J., & van Oorschot, P. C. (2013) · 2013 IEEE Symposium on Security and Privacy · doi:10.1109/sp.2013.41 · Cited by 224 · see citing works
Quantum Resource Estimates for Computing Elliptic Curve Discrete Logarithms
Roetteler, M., Naehrig, M., Svore, K. M., & Lauter, K. (2017) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-70697-9_9 · Cited by 212 · see citing works
Kim, P., Han, D., & Jeong, K. C. (2018) · Quantum Information Processing · doi:10.1007/s11128-018-2107-3 · Cited by 80 · see citing works
Analysis of RSA and Shor’s algorithm for cryptography: A quantum perspective
Kute, S., Desai, C., & Jadhav, M. (2024) · AIP Conference Proceedings · doi:10.1063/5.0227773 · Cited by 5 · see citing works
- Authors
- van Oorschot, P. C., & Wiener, M. J.
- Affiliations
- Entrust (Canada) (CA)
- Venue
- Journal of Cryptology
- Published
- 1999-01
- Volume
- 12
- Issue
- 1
- Pages
- 1-28
- ISSN
- 0933-2790 (ISSN-L)
- 1432-1378
- OpenAlex
- W2008272678
- Cited by
- 639
- References
- 2
- Citations by year
- 2026: 5 · 2025: 25 · 2024: 21 · 2023: 15 · 2022: 18 · 2021: 41 · 2020: 49 · 2019: 20 · 2018: 18 · 2017: 20 · 2016: 27 · 2015: 30 · 2014: 27 · 2013: 23 · 2012: 42
- FWCI
- 24.84
- Type
- journal article
- Language
- en
- Open access
- bronze
- doi.org
- Licence
- www.springer.com/tdm (tdm)
- Locations
- Journal of Cryptology (publishedVersion)
- Carleton University's Institutional Repository (MacOdrum Library, Carleton University) (submittedVersion)
- Carleton University's Institutional Repository (MacOdrum Library, Carleton University) (submittedVersion, other-oa)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Cryptographic Implementations and Security
- Physical Sciences › Computer Science › Information Systems › Cryptography and Residue Arithmetic
- Physical Sciences › Computer Science › Artificial Intelligence › Cryptography and Data Security
- Keywords
- meet-in-the-middle attack, elliptic curve discrete logarithm problem, Schnorr signature, DSA, elliptic curve cryptography, known-plaintext attack, cryptanalysis
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
