{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:01:01Z","timestamp":1750309261365,"version":"3.41.0"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2024,9,17]],"date-time":"2024-09-17T00:00:00Z","timestamp":1726531200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Reconfigurable Technol. Syst."],"published-print":{"date-parts":[[2024,9,30]]},"abstract":"<jats:p>tThe CSAIL2019 time-lock puzzle is an unsolved cryptographic challenge introduced by Ron Rivest in 2019, replacing the solved LCS35 puzzle. Solving these types of puzzles requires large amounts of intrinsically sequential computations, with each iteration performing a very large (3,072-bit for CSAIL2019) modular multiplication operation. The complexity of each iteration is several times greater than known field-programmable gate array (FPGA) implementations, and the number of iterations has been increased by about 1,000x compared with LCS35. Because of the high complexity of this new puzzle, a number of intermediate, or milestone, versions of the puzzle have been specified. In this article, we present several FPGA architectures for the CSAIL2019 solver, which we implement on a medium-sized Intel Agilex device. We develop a new multi-cycle modular multiplication method, which is flexible and can fit on a wide variety of sizes of current FPGAs. We introduce a class of multi-cycle squarer-based architectures that allow for better resource and area trade-offs. We also demonstrate a new approach for improving the fitting and timing closure of large, chip-filling arithmetic designs. We used the solver to compute the first 23 out of 28 milestone solutions of the puzzle, which are the first reported results for this problem.<\/jats:p>","DOI":"10.1145\/3639056","type":"journal-article","created":{"date-parts":[[2023,12,29]],"date-time":"2023-12-29T22:05:01Z","timestamp":1703887501000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["CSAIL2019 Crypto-Puzzle Solver Architecture"],"prefix":"10.1145","volume":"17","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3339-7705","authenticated-orcid":false,"given":"Sergey","family":"Gribok","sequence":"first","affiliation":[{"name":"Intel Corporation, San Jose, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5454-4375","authenticated-orcid":false,"given":"Bogdan","family":"Pasca","sequence":"additional","affiliation":[{"name":"Intel Corporation, Toulouse, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8206-2077","authenticated-orcid":false,"given":"Martin","family":"Langhammer","sequence":"additional","affiliation":[{"name":"Intel Corporation, Swindon, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,9,17]]},"reference":[{"key":"e_1_3_2_2_2","unstructured":"2018. Intel Stratix\u00ae10 GX\/SX Device Overview. https:\/\/www.intel.com\/content\/dam\/www\/programmable\/us\/en\/pdfs\/literature\/hb\/stratix-10\/s10-overview.pdf"},{"key":"e_1_3_2_3_2","unstructured":"2018. Intel\u00ae Stratix\u00ae 10 Variable Precision DSP Blocks User Guide. https:\/\/www.intel.com\/content\/dam\/support\/us\/en\/programmable\/support-resources\/bulk-container\/pdfs\/literature\/hb\/stratix-10\/archives\/ug-s10-dsp-18-1.pdfAccessed: 2023-08-24"},{"key":"e_1_3_2_4_2","unstructured":"2019. Cryptophage LCS35 Solver. https:\/\/github.com\/supranational\/lcs35\/blob\/master\/README.md\/ (2019). Accessed: 2022-09-14."},{"key":"e_1_3_2_5_2","unstructured":"2019. Intel Agilex F-Series FPGA and SoC Product Table. https:\/\/www.intel.com\/content\/dam\/www\/programmable\/us\/en\/pdfs\/literature\/pt\/intel-agilex-f-series-product-table.pdf"},{"key":"e_1_3_2_6_2","unstructured":"2019. Intel Agilex Variable Precision DSP Blocks User Guide. https:\/\/www.intel.com\/content\/dam\/altera-www\/global\/en_US\/pdfs\/literature\/hb\/agilex\/ug-ag-dsp.pdf"},{"key":"e_1_3_2_7_2","unstructured":"2019. VDF Alliance FPGA competition. https:\/\/supranational.atlassian.net\/wiki\/spaces\/VA\/pages\/36569208\/FPGA+Competition (2019)."},{"key":"e_1_3_2_8_2","unstructured":"2019. VDF Alliance FPGA Competition - Round 2 - Eric Pearson. https:\/\/github.com\/supranational\/vdf-fpga-round2-results\/tree\/master\/eric_pearson_2. (2019). Accessed: 2022-09-14."},{"key":"e_1_3_2_9_2","unstructured":"2019. VDF Alliance FPGA Competition Round 1 Results and Announcements. https:\/\/www.vdfalliance.org\/news\/fpga-competition-round-1-results (2019)."},{"key":"e_1_3_2_10_2","unstructured":"2021. UltraFast Design Methodology Guide for Xilinx FPGAs and SoCs. https:\/\/docs.xilinx.com\/r\/2021.2-English\/ug949-vivado-design-methodology\/Super-Logic-Region-SLR (2021). Accessed: 2021-11-19."},{"key":"e_1_3_2_11_2","unstructured":"2021. UltraScale Architecture DSP Slice. https:\/\/docs.xilinx.com\/v\/u\/en-US\/ug579-ultrascale-dsp (2021). Accessed: 2021-08-30."},{"key":"e_1_3_2_12_2","unstructured":"2022. Amazon EC2 F1 Instances. https:\/\/aws.amazon.com\/ec2\/instance-types\/f1\/ (2022). Accessed: 2022-09-14."},{"key":"e_1_3_2_13_2","unstructured":"2022. Description of the CSAIL2019 Time Capsule Crypto-Puzzle. https:\/\/people.csail.mit.edu\/rivest\/pubs\/Riv19f.new-puzzle.txt (2022)."},{"key":"e_1_3_2_14_2","unstructured":"2022. Description of the LCS35 Time Capsule Crypto-Puzzle. http:\/\/people.csail.mit.edu\/rivest\/pubs\/Riv99b.lcs35-puzzle-description.txt (2022)."},{"volume-title":"Intel\u00ae Agilex\u2122 F-Series FPGA Development Kit","year":"2022","key":"e_1_3_2_15_2","unstructured":"2022. Intel\u00ae Agilex\u2122 F-Series FPGA Development Kit. Accessed: 2022-09-14."},{"key":"e_1_3_2_16_2","unstructured":"2022. Intel\u00ae Agilex\u2122 Power Analyser. https:\/\/www.intel.com\/content\/www\/us\/en\/support\/programmable\/support-resources\/power\/pow-powerplay.htmlAccessed: 2022-09-14."},{"key":"e_1_3_2_17_2","unstructured":"2022. Programmers Solve MITs 20-year-old Cryptographic Puzzle. https:\/\/www.csail.mit.edu\/news\/programmers-solve-mits-20-year-old-cryptographic-puzzle (2022). Accessed: 2022-09-14."},{"key":"e_1_3_2_18_2","unstructured":"2022. Virtex UltraScale+ Product Tables. https:\/\/www.xilinx.com\/products\/silicon-devices\/fpga\/virtex-ultrascale-plus.html (2022). Accessed: 2022-09-14."},{"key":"e_1_3_2_19_2","unstructured":"2022. Xilinx Power Estimator User Guide. https:\/\/www.xilinx.com\/support\/documents\/sw_manuals\/xilinx2022_1\/ug440-xilinx-power-estimator.pdf"},{"key":"e_1_3_2_20_2","first-page":"311","volume-title":"Advances in Cryptology \u2014 CRYPTO\u201986","author":"Barrett Paul","year":"1987","unstructured":"Paul Barrett. 1987. Implementing the Rivest Shamir and Adleman public key encryption algorithm on a standard digital signal processor. In Advances in Cryptology \u2014 CRYPTO\u201986, Andrew M. Odlyzko (Ed.). Springer, Berlin,311\u2013323."},{"key":"e_1_3_2_21_2","doi-asserted-by":"crossref","unstructured":"Daniel J. Bernstein Jonathan Sorenson and P. Sorenson. 2007. Modular exponentiation via the explicit Chinese remainder theorem. Journal Math. Comp. 76 257 (2007) 443\u2013454.","DOI":"10.1090\/S0025-5718-06-01849-7"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2008.102"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1093\/qjmam\/4.2.236"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/3373087.3375308"},{"key":"e_1_3_2_25_2","volume-title":"International Conference on Field Programmable Logic and Applications","author":"Dinechin Florent de","year":"2009","unstructured":"Florent de Dinechin and Bogdan Pasca. 2009. Large multipliers with fewer DSP blocks. In International Conference on Field Programmable Logic and Applications. IEEE."},{"key":"e_1_3_2_26_2","unstructured":"Benjamin Devlin. 2020. Really low latency multipliers and cryptographic puzzles. https:\/\/blog.janestreet.com\/really-low-latency-multipliers-and-cryptographic-puzzles. (2020)."},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1109\/ETCS.2010.375"},{"key":"e_1_3_2_28_2","first-page":"293","article-title":"Multiplication of multidigit numbers on automata","volume":"145","author":"Karatsuba A.","year":"1962","unstructured":"A. Karatsuba and Y. Ofman. 1962. Multiplication of multidigit numbers on automata. USSR Academy of Sciences 145 (1962), 293\u2013294. DANKAS","journal-title":"USSR Academy of Sciences"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1109\/ARITH.2018.8464809"},{"key":"e_1_3_2_30_2","article-title":"Low-latency modular exponentiation for FPGAs","author":"Langhammer M.","year":"2022","unstructured":"M. Langhammer, S. Gribok, and B. Pasca. 2022. Low-latency modular exponentiation for FPGAs. IEEE 30th Annual International Symposium on Field-Programmable Custom Computing Machines (2022).","journal-title":"IEEE 30th Annual International Symposium on Field-Programmable Custom Computing Machines"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/3431920.3439306"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/3431920.3439299"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1985-0777282-X"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1049\/iet-cdt.2015.0055"},{"key":"e_1_3_2_35_2","unstructured":"T. D. Noe. 2008. The On-Line Encyclopedia of Integer Sequences: Sequence A141305. (2008). https:\/\/oeis.org\/A141305Accessed: 2022-08-16."},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1109\/PRIME.2019.8787740"},{"key":"e_1_3_2_37_2","first-page":"4","article-title":"LLMonPro: Low-latency Montgomery modular multiplication suitable for verifiable delay functions","author":"San Ismail","year":"2021","unstructured":"Ismail San. 2021. LLMonPro: Low-latency Montgomery modular multiplication suitable for verifiable delay functions. IACR Cryptol. ePrint Arch. (2021), 4. https:\/\/eprint.iacr.org\/2021\/004","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"e_1_3_2_38_2","unstructured":"Phil Sun. 2020. Modular Exponentiation via Nested Reduction in a Residue Number System. https:\/\/github.com\/supranational\/vdf-fpga-round3-results\/blob\/master\/papers\/phil_sun_rns.pdf. (2020)."},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.23919\/DATE51398.2021.9473908"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCSI.2020.2966755"}],"container-title":["ACM Transactions on Reconfigurable Technology and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3639056","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3639056","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T23:57:09Z","timestamp":1750291029000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3639056"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,17]]},"references-count":39,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,9,30]]}},"alternative-id":["10.1145\/3639056"],"URL":"https:\/\/doi.org\/10.1145\/3639056","relation":{},"ISSN":["1936-7406","1936-7414"],"issn-type":[{"type":"print","value":"1936-7406"},{"type":"electronic","value":"1936-7414"}],"subject":[],"published":{"date-parts":[[2024,9,17]]},"assertion":[{"value":"2023-09-15","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-12-14","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-09-17","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}