Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [An toàn thông tin] Fiat-Shamir nhiều vòng: xác suất gian lận

    Fiat-Shamir: t vòng độc lập

    Giao thức chạy ttt vòng; mỗi vòng prover gửi (x,b,y)(x, b, y)(x,b,y) và verifier kiểm tra y2≡x⋅vb(modn)y^2 \equiv x \cdot v^{b} \pmod ny2≡x⋅vb(modn). Prover trung thực luôn qua; kẻ gian lận chỉ qua mỗi vòng với xác suất 1/21/21/2, nên qua ttt vòng với xác suất 2−t2^{-t}2−t.

    Đếm số vòng hợp lệ. In IDENTIFIED nếu tất cả ttt vòng đều qua, kèm xác suất gian lận dạng phân số 1/2^t; ngược lại in REJECTED round <số vòng đầu sai>.

    • Định dạng đầu vào:

      Dòng 1: hai số n v và t. ttt dòng tiếp theo: x b y.

    • Ràng buộc đầu vào:
      • b∈{0,1}b \in \{0,1\}b∈{0,1}, 1≤t≤601 \le t \le 601≤t≤60.
    • Định dạng đầu ra:

      Như mô tả.

    Ví dụ:

    Đầu vào:

    3233 25 2
49 0 7
49 1 35

    Đầu ra:

    IDENTIFIED 1/4

    Giải thích:

    2 vòng đều qua → xác suất gian lận 1/4.

    Đang tải editor...