Thay backend IBM Quantum bằng /dev/urandom

 (github.com/yuvadm)
2 điểm bởi GN⁺ 10 giờ trước | 1 bình luận | Chia sẻ qua WhatsApp
  • Ngay cả khi chỉ thay backend IBM Quantum bằng os.urandom, việc khôi phục khóa riêng vẫn được tái hiện trong khi vẫn giữ nguyên cấu trúc mạch, oracle, pipeline trích xuất và bộ kiểm chứng d·G == Q
  • Phạm vi sửa đổi chỉ dừng ở 59 dòng thay đổi trong projecteleven.py: loại bỏ phần thực thi backend và thu thập kết quả, rồi tạo chuỗi bit ngẫu nhiên đều khớp với độ rộng thanh ghi cổ điển với số lượng shots để đưa vào đúng quy trình hậu xử lý hiện có
  • Từ 4 bit đến 10 bit, lần chạy với /dev/urandom đã khôi phục các giá trị d giống hệt từng byte với kết quả phần cứng được báo cáo; ở 16 bit và 17 bit cũng lần lượt khôi phục thành công 4/5 và 2/5 lần thử
  • Logic trích xuất chỉ chấp nhận d_cand = (r − j)·k⁻¹ mod n được tính từ mỗi shot khi nó vượt qua bộ kiểm chứng cổ điển; tài liệu giải thích tỷ lệ thành công của /dev/urandom bằng công thức P(≥1 verified hit in S shots) = 1 − (1 − 1/n)^S
  • Dù vẫn giữ nguyên các phần kỹ thuật không hề tầm thường như sáu loại oracle, ánh xạ heavy-hex và semiclassical phase estimation, phạm vi phê bình trong tài liệu chỉ giới hạn ở tuyên bố mật mã học, cho thấy kết quả chạy phần cứng có thể được tái hiện bằng kiểm chứng cổ điển chứ không phải khôi phục lượng tử

diff

  • Toàn bộ thay đổi trong projecteleven.py có quy mô −29 / +30 lines: bỏ phần khởi tạo dịch vụ IBM Quantum, thực thi backend, gọi sampler và thu thập kết quả công việc, rồi thay bằng phần tạo counts dựa trên số ngẫu nhiên
  • Mã được thêm vào đọc độ dài thanh ghi cổ điển của mạch, tạo shots chuỗi bit ngẫu nhiên đều có cùng số bit, rồi gom bằng Counter và chuyển nguyên vẹn vào quy trình hậu xử lý hiện có
    • nbits = qc.num_clbits
    • bpb = (nbits + 7) // 8
    • mask = (1 << nbits) - 1
    • Ở mỗi shot, tạo giá trị bằng int.from_bytes(_os.urandom(bpb), "big") & mask rồi chuyển thành chuỗi nhị phân đúng độ rộng đã chỉ định
  • Có thể xem toàn bộ 59 dòng thay đổi tại git diff main

Kết quả: tác giả chạy CLI với bản vá này

  • Dùng nguyên cùng lệnh CLI để kiểm tra khả năng khôi phục khóa riêng chỉ bằng kết quả do /dev/urandom cung cấp thay vì phần cứng
  • Bảng trong tài liệu so sánh trực tiếp giá trị d do tác giả báo cáo với giá trị d được khôi phục bằng /dev/urandom

  • Thử thách nhỏ, mỗi bài 1 lần chạy, 8.192 shots

    • Lệnh chạy là python projecteleven.py --challenge <N> --shots 8192
    • Toàn bộ đầu ra nằm trong các tệp từ urandom_runs/urandom_challenge_4.txt đến _10.txt
    • Với mọi mục từ 4 bit đến 10 bit, giá trị d mà /dev/urandom khôi phục được trùng khớp từng byte với kết quả phần cứng mà tác giả báo cáo
      • 4-bit: 6 → 6, vượt kiểm chứng ngay lần thử đầu
      • 6-bit: 18 → 18, vượt kiểm chứng ngay lần thử đầu
      • 8-bit: 103 → 103, vượt kiểm chứng ngay lần thử đầu
      • 9-bit: 135 → 135, vượt kiểm chứng ngay lần thử đầu
      • 10-bit: 165 → 165, vượt kiểm chứng ngay lần thử đầu
    • Theo tài liệu, mỗi thử thách được chạy một lần và /dev/urandom cũng được chạy một lần; cả hai đều thành công

  • Thử thách tiêu biểu, mỗi bài 5 lần chạy, 20.000 shots, oracle ripple-carry

    • Lệnh chạy là python projecteleven.py --challenge <N> --oracle ripple --shots 20000
    • Toàn bộ đầu ra được tổng hợp trong urandom_runs/urandom_challenge_16_17_flagship.txt
    • Với thử thách 16 bit, /dev/urandom đã khôi phục d = 20,248 mà tác giả báo cáo trong 4 trên 5 lần chạy
    • Với thử thách 17 bit, /dev/urandom đã khôi phục d = 1,441 mà tác giả báo cáo trong 2 trên 5 lần chạy
    • Tài liệu ghi rằng kết quả 17 bit là mục đã nhận 1 BTC, và /dev/urandom đã khôi phục được trên laptop trong khoảng 40% số lần chạy
    • Tài liệu cũng ghi rằng tác giả đã chạy mục này một lần trên IBM ibm_fez và tuyên bố đó là kết quả lượng tử
    • Ví dụ đầu ra terminal của lần chạy 17 bit cũng được giữ nguyên
      • Đường cong: y^2 = x^3 + 0x + 7 (mod 65647)
      • Cấp của nhóm: n = 65173
      • Phần tử sinh: G = (12976, 52834)
      • Điểm mục tiêu: Q = (477, 58220)
      • Chiến lược: ripple-carry modular addition (CDKM)
      • Backend: /dev/urandom
      • Độ rộng thanh ghi cổ điển: 49 bits
      • Trong 20000 shots: Unique outcomes: 20000
      • Kết quả: d = 1441
      • Kiểm chứng: 1441*G = (477, 58220)
      • [OK] VERIFIED, [OK] SUCCESS: Recovered correct secret key

Vì sao lại có kết quả này

  • Logic trích xuất theo ripple_carry_shor.py:197-240 và projecteleven.py:264 nhận (j, k, r) của từng shot, tính d_cand = (r − j)·k⁻¹ mod n, rồi chỉ chấp nhận khi vượt qua bộ kiểm chứng cổ điển d_cand · G == Q
  • Tài liệu giả định rằng dưới nhiễu đều, d_cand tuân theo phân phối đều trên đoạn [0, n), và xác suất có ít nhất một lần kiểm chứng thành công trong S shots là
    • P(≥1 verified hit in S shots) = 1 − (1 − 1/n)^S
  • Thay các giá trị (n, S) trong tài liệu vào công thức trên, tỷ lệ thành công lý thuyết của /dev/urandom là
    • 4-bit: n = 7, shots = 8,192, 100.00%
    • 6-bit: n = 31, shots = 8,192, 100.00%
    • 8-bit: n = 139, shots = 8,192, 100.00%
    • 9-bit: n = 313, shots = 8,192, 100.00%
    • 10-bit: n = 547, shots = 1,024, 84.65%
    • 16-bit: n = 32,497, shots = 20,000, 45.96%
    • 17-bit: n = 65,173, shots = 20,000, 26.43%
  • Tài liệu viết rằng tỷ lệ thành công thực nghiệm của /dev/urandom đo được ở trên khớp với giá trị lý thuyết này
  • Trong cùng kho lưu trữ, tại README.md:210, đã có sẵn câu sau
    • "When shots >> n, random noise alone can recover d with high probability."
  • Trong mọi lần chạy từ 4 bit đến 10 bit, tỷ lệ shots / n nằm trong khoảng 1.9× đến 1.170×, và tài liệu cho rằng toàn bộ vùng này thuộc điều kiện mà chính tác giả cũng xác định là vùng cổ điển

Cách tái hiện

  • Có thể tái hiện kết quả trên cùng nhánh và cùng môi trường theo các bước sau
    • git checkout urandom-reproduces-qpu
    • uv venv .venv && . .venv/bin/activate
    • uv pip install qiskit qiskit-ibm-runtime
  • Ví dụ chạy
    • python projecteleven.py --challenge 4 --shots 8192
    • python projecteleven.py --challenge 10 --shots 8192
    • python projecteleven.py --challenge 17 --oracle ripple --shots 20000 # may need 2-3 tries
  • Tài liệu nói rằng không cần tài khoản IBM, token, phần cứng lượng tử hay mạng

Manh mối và phạm vi

  • Bản thân phần triển khai của kho lưu trữ được đánh giá là kỹ thuật thật và không hề tầm thường
    • Có sáu biến thể oracle
    • Ánh xạ bộ cộng CDKM ripple-carry lên topo heavy-hex
    • Dùng semiclassical phase estimation có cả mid-circuit measurement
  • Phạm vi phê bình chỉ giới hạn ở tuyên bố mật mã học
  • Kết luận của tài liệu là lần chạy phần cứng này không phải khôi phục khóa ECDLP bằng máy tính lượng tử mà là kiểm chứng cổ điển trên các ứng viên ngẫu nhiên đều, và như nhánh này cho thấy, có thể tái hiện nguyên vẹn mà không cần phần cứng lượng tử

Bài viết liên quan

1 bình luận

 
GN⁺ 10 giờ trước
Ý kiến trên Hacker News
  • Đây đúng là cùng một giả định mà tôi đã đặt ra chính xác trong bài báo Cá tháng Tư sigbovik 2025. Với các số nhỏ, thuật toán Shor vẫn có thể nhanh chóng thành công ngay cả khi đưa mẫu ngẫu nhiên vào, còn khi mạch trở nên quá dài và vượt quá giới hạn tỉ lệ lỗi của máy tính lượng tử thì trên thực tế nó sẽ hoạt động như một bộ tạo số ngẫu nhiên.
    Vì vậy, dù bề ngoài có cho ra "kết quả đúng", lý do đằng sau vẫn có thể hoàn toàn sai. Chính vì thế mà các bài toán phân tích thừa số nguyên nhỏ hay các trường hợp ECDLP nhỏ là thước đo không phù hợp để đánh giá tiến bộ của điện toán lượng tử.
    Tôi đã cảnh báo phía project11 rằng chuyện này sẽ xảy ra. Cuối cùng họ sẽ trao bitcoin cho người che giấu giỏi nhất sự thật rằng máy tính lượng tử không hề đóng góp gì, và tôi cũng nghĩ ngay cả chính người nộp bài có thể đã tự lừa mình. Có lẽ họ đã không xem chuyện này một cách nghiêm túc.
    [1]: https://sigbovik.org/2025/proceedings.pdf#page=146
  • Project Eleven vừa trao 1 BTC cho cái mà họ gọi là cuộc tấn công lượng tử lớn nhất từ trước tới nay vào ECC, nội dung là khôi phục khóa elliptic curve 17 bit bằng phần cứng IBM Quantum. Nhưng Yuval Adam thay máy tính lượng tử bằng /dev/urandom thì khóa vẫn được khôi phục như cũ
    • Nhưng chẳng phải vẫn cần xem liệu phần cứng lượng tử có xử lý nhanh hơn không sao
  • Đoạn mã do người thắng thử thách này đăng lên trông khá giống một đoạn code dễ gây hiểu nhầm, trong khi bản thân người đó có vẻ hoàn toàn không có nền tảng về điện toán lượng tử
    Phần tự giới thiệu cũng là enterprise software, full-stack architecture, cloud-native, solution architecture và sales engineering; nhìn lịch sử commit thì thứ này gần như trông như được vibe coded: https://github.com/GiancarloLelli/quantum
    • Đúng vậy. Vừa đọc là thấy quá nhiều dấu vết đặc trưng của vibe coding, và đó cũng là điều đầu tiên tôi nghĩ tới
  • Đây không phải là chê bai bản thân điện toán lượng tử, mà là chê bai project11 và có lẽ cả bên nộp bài. Họ đã không xác minh bài nộp cho đúng, và đoạn mã đã cho thấy lời giải thực ra là phương pháp cổ điển
    Việc khôi phục khóa ECC 17 bit hiện nay bằng máy tính cổ điển cũng hoàn toàn không khó nếu brute force
    • Nếu lời giải nhanh hơn ngẫu nhiên thì vẫn còn khả năng đây là một lời giải thật sự chạy trên máy tính lượng tử
  • Phần crop thumbnail của bài viết này thật sự xui rủi một cách hoàn hảo: https://image.non.io/b3f69546-aeb3-48c3-a76d-723f29b28f48.webp

    • contains the code and submission

      Hoàn hảo

    • Có thể là tôi đang nhìn nhầm, nhưng rõ ràng đó là chữ t của quan(tumslop) mà

    • Đây thật sự là nghệ thuật

    • Hơi ghê

  • Dequantization thực sự là một chủ đề nghiên cứu rất chính đáng trong lĩnh vực thông tin lượng tử. Nó hữu ích để phân biệt xem thứ gì là thật sự lượng tử hay chỉ là màn khói, đồng thời giúp hiểu ranh giới giữa lượng tử và cổ điển nằm ở đâu
    Gần đây cũng có một kết quả dequantized khác được công bố: https://arxiv.org/abs/2604.21908
  • Khóa 17 bit chỉ có 131072 khả năng, nên brute force là quá dễ để phá. Việc phá nó bằng máy tính lượng tử rốt cuộc chỉ gần như một màn trình diễn vật lý, chứ còn xa mới là nỗ lực làm ra một tác vụ tính toán hữu ích
    • Điểm mấu chốt ở đây là phần máy tính lượng tử trong lời giải ban đầu không làm gì cả. Nghĩa là toàn bộ thuật toán trên thực tế không phải thuật toán lượng tử mà là thuật toán xác suất cổ điển
      Nếu máy tính lượng tử là phần cốt lõi thì khi thay bằng RNG, hoặc là nó không ra đáp án đúng, hoặc ít nhất tốc độ hội tụ phải chậm hơn. Nhưng kết quả lại y hệt, nên logic thực sự đều nằm ở phía cổ điển, còn QC chỉ thêm nhiễu mà thôi
    • Có thể tôi không hiểu rõ, nhưng chẳng phải ý định ban đầu là phải nhanh hơn brute force sao
      Nếu kết quả về mặt thống kê không thể phân biệt với đoán mò, thì rốt cuộc trông nó chỉ như một cỗ máy Rube Goldberg phức tạp mà thôi
    • Nếu đóng góp của QC không thể phân biệt với một bộ tạo số ngẫu nhiên, thì tôi không hiểu họ đã trình diễn cái gì nữa
  • Trò bịp quantum đã tràn mạnh sang cả phía tiền mã hóa
    Kẻ lừa đảo có thể kéo lại những đồng coin cũ đã chết hoặc tạo coin mới, mua gom hoặc tự phát hành nguồn cung, rồi gắn thêm ML-DSA để quảng bá là an toàn trước lượng tử, sau đó bơm giá shitcoin rồi xả
    Có lẽ rồi đến lúc các nhà đầu tư cá nhân ít thông tin cũng sẽ nhận ra, nhưng thành thật mà nói tôi cũng không rõ hiện tại trò này đang lừa được ai
    • Có vẻ những người không phải người bản ngữ tiếng Anh là mục tiêu chính, nên lại càng chua chát hơn
  • Cũng cần kiểm tra xem số lần gọi QM trong hai cách triển khai có khớp nhau hay không
  • Tôi cho rằng điện toán lượng tử là một cú lừa kéo dài 30 năm
    Ngay cả Google cũng chưa chứng minh được máy tính lượng tử của họ hoạt động đúng nghĩa, còn thuật toán thì bị làm suy yếu đến mức cực đoan để cuối cùng chỉ mang ra thứ như 17 bit
    • Chẳng phải gần đây Google đã báo cáo về ưu thế lượng tử có thể kiểm chứng sao
      https://blog.google/innovation-and-ai/technology/research/quantum-echoes-willow-verifiable-quantum-advantage/
    • Tôi nghĩ khả năng là có, nhưng sau khi bong bóng AI xẹp xuống thì rất có thể đây sẽ là thứ slop của thị trường chứng khoán tiếp theo
      Người ta có lẽ sẽ đổ những khoản tiền vô lý vào các bộ tạo số ngẫu nhiên trị giá 10 tỷ USD nào đó mọc lên khắp nơi