Ta sẽ mô tả hai sơ đồ ràng buộc bit thuộc loại này và sau đó đánh giá các kiểu sử dụng chúng trong giao thức tô đồ thị bằng ba màu. Sơ đồ đầu tiên được xây dựng trên bái toán các thặng dư bậc hai. Giả sử n = pq, trong đó p và q là các số nguyên tố và cho m ∈QR(n) (chú ý rằng trong sơ đồ trước m là một thặng dư giả bậc hai) | Vietebooks Nguyễn Hoàng Cương Ta sẽ mô tả hai sơ đồ ràng buộc bit thuộc loại này và sau đó đánh giá các kiểu sử dụng chúng trong giao thức tô đồ thị bằng ba màu. Sơ đồ đầu tiên được xây dựng trên bái toán các thặng dư bậc hai. Giả sử n pq trong đó p và q là các số nguyên tố và cho m e QR n chú ý rằng trong sơ đồ trước m là một thặng dư giả bậc hai . Trong sơ dồ nàyPeggy không nhất thiết phải biết phân tích của n và căn bậc hai của m. Bởi vậy Vic hoặc phải xây dựng được các giá trị này hoặc chúng phải được thu nhận từ một người thứ ba tin cậy được . Cho X Zn và Y QR n và định nghĩa f b n mbx2 mod n Cũng như trước đây Peggy sẽ mã hoá giá trị b bằng cách chọn một giá trị ngẫu nhiên x và tính blob y f b x . Trong sơ đồ này tất cả các blob đều là các thặng dư bậc hai. Hơn nữa một giá trị bất kỳ ye QR n có thể là bản mã hoá của 0 hay của 1. Giả sử y x2 mod n và m k2 mod n. Khi đó y f 0 x f 1 x k-1 mod n Điều đó có nghĩa là sơ đồ này đạt được tính dấu kín không điều kiện. Vậy điều kiện gì sẽ xảy ra đối với tính ràng buộc Peggy có thể mở một blob bất kỳ cho trước thành 0 hoặc 1 khi và chỉ khi cô ta có thể tính được k là một căn bậc hai của m . Như vậy để cho sơ đồ này là ràng buộc về mặt tính toán cần phải giả thiết rằng Peggy không có khả năng tính căn bậc hai của m. Nếu Peggy có đầy đủ sức mạnhthì dĩ nhiên cô ta có thể làm được điều đó. Đó là lý do phải giả thiết Peggy có khả năng tính toán hạn chế . Để làm ví dụ cho một sơ đồ cam kết bit thứ hai thuộc loại này xét một sơ đồ xây dựng trên bái toán logarithm rời rạc. Cho p là một số nguyên tố sao cho bái toán logarithm rời rạc trong Zp là một bái toán bất khả giải cho a là một phần tử nguyên thuỷ của Zp và cho p eZp . Giá trị p phải được chọn bởi Vic hoặc một người thứ ba tin cậy chứ không phải bởi Peggy . Sơ đồ này sẽ có X 0 . p-1 Y Zp và f được xác định bằng f b x pbax mod p Không khó khăn lắm có thể thấy rằng sơ đồ này có tính dấu kín không điều kiện và nó có tính dàng buộc khi và chỉ khi Peggy không có khả năng tính .
