This paper proposes a general framework for designing a one-time signature scheme using “certain types of linear collision-resistant hash functions.” Using a standard transformation (for example, signatures based on hash trees), a general digital signature scheme can be created from a one-time signature scheme. The paper presents “a direct construction of one-time signatures, where each signature just requires two applications of the lattice-based collision-resistant function.” The general setup is then realized by three concrete examples to get new digital signature schemes that can be proved to be as hard as breaking famous difficult problems in lattices. One of the instantiations achieves an essentiallyoptimal performance/security tradeoff.
The abstract framework is defined on a certain (finite commutative) ring R with integer parameters n, m, and k. One chooses a set ℋ ⊂ Rn×m, secretkey space 𝒦 ⊂ Rm×k, message space ℳ ⊂ Rk, and signature space S ⊂ Rm. To set up a system, one specifies a random matrix H ∈ ℋ publicly. The user’s secret key K ∈ 𝒦 “is chosen uniformly at random” and the corresponding public key is (H,HK) ⊂ Rn×(m+k). The (one-time) signature of a message m ∈ ℳ is σ = Km. The signature is accepted if a verifier gets (H,HK) = 0.The paper abstracts three conditions that must be satisfied by this signature system:
- (1) closure: for every K ∈ 𝒦,K(ℳ) ⊂ S;
- (2) collision resistance: “the function family {H : S → Rn｜H ∈ ℋ} is collision resistant”; and
- (3) (½-hiding): define 𝒟H(K,m) = {K′ ∈ 𝒦｜HK = HK′,Km = K′m}; for any distinct m,m′ ∈ ℳ, the probability of ｜𝒟H(K,m)∩𝒟H(K,m′)｜≤½｜𝒟H(K,m)｜ is overwhelmingly close to one. (Note: the paper actually defines a more general concept of (ε,δ-hiding)).
One of the paper’s main results is that, if all of these three conditions are met, “then the one-time signature scheme is strongly unforgeable.” The authors present a nice proof of this result by assuming the system satisfies (1) and (3), and arguing that “if there is an adversary that succeeds in breaking the strong unforgeability of the ... scheme with probability ϒ,” then one can design an algorithm that can break (2) with probability at least (ϒ-n-ω(1))/3 “in essentially the same running time as the forgery attack.”
The paper describes three instantiations of their general one-time signature scheme. When R = ℤp with parameters being suitably chosen, the security of the scheme is based on the small integer solution (SIS) problem. When R = ℤ2, the security of the scheme is based on the small codeword problem for a set of well-selected parameters. When R = ℤp[x]/(xn + 1) with n being a power of two, the hardness of the ring-SIS problem gives the strong unforgeability of the one-time signature scheme. Due to the cyclic nature of this (cyclotomic) ring, this scheme is essentially optimal in that the key and signature size can be made almost linear in n. Also, “the time complexity of the signing and verification algorithms ... is almost linear ... in n.”
