5
$\begingroup$

Background: I've been reading GGH's Public-Key Cryptosystems from Lattice Reduction Problems, and have a question about a remark the authors make:

"It is important to remark at the outset, that messages which are close to each other will have the same signature. When applying the method in a setting where this property is desirable (e.g., signing analog signals which may change a little in time), this feature may be of great benefit. However, to get secure signatures in the sense of [14], this property pause a significant problem. When applying the method to a message space where such property is undesirable, we propose to first hash the message and only then sign it. This is good practice also in case that the scheme is subject to a chosen message attack, as otherwise being able to obtain different signatures of two messages which are close to each other when viewed as points in Rn will imply the ability to compute a small basis for the lattice which in turn will enable the attacker to find close vectors in a lattice and break the scheme. (Interestingly, a family of collision-free hash functions can be constructed assuming that Lattice-Reduction is hard on the worst-case, see [10]). Due to lack of space, we do not discuss that construction in this extended abstract."

Question: What is the attack they are thinking of here?

I found what appears to be the final version of the paper, and the construction does not appear to be detailed, unless I missed it - or perhaps "that construction" refers to the signature scheme.

I'm not asking people to read the authors minds, especially from a paper almost 15 years old, but hope that the attack is well-known. Another phrasing of my question is "What are some well-known attacks that could fit the bolded text in the authors description?"

Also, to clarify, I am not asking about the Nguyen/Regev attack, which works on the version of this signature scheme where one hashes first.

Thoughts: I can imagine an attack along the line of the outline given below, but it requires sending high precision chosen messages to the signature scheme. I wonder if there if there is a better attack, because I think my attack could be fooled if the adversary adds some small noise to the chosen messages before signing them. Also, in this attack-idea the actual basis the signature scheme is using would be extracted, while in the above quote they discuss extracting a short basis.

Let me emphasize that I'm not sure that this attack works, nor am I asking for a verification. Of course, it would be helpful for my learning if an attack along these lines was written down somewhere I could be pointed to, or if there was some obvious problem that could be pointed out. However, I'm mostly leaving the sketch below to force myself to think about this question before asking. Reading it is not necessary to answer my main question, which is mostly a reference request. :-)

Attack idea:

Recall that the signer is using the rounding algorithm $\textrm{int}( xR^{-1} )R$, where $R$ is the secret basis and $\textrm{int} : \mathbb{R}^n \to \mathbb{N}^n $ coordinate wise maps each number to the nearest integer, and breaking ties so that $[-1/2,1/2)$ is mapped to $0$ and so that in each coordinate it is $\mathbb{Z}$-periodic. Let $P = [-1/2,1/2)^nR$ be the fundamental parallelopiped associated to $R$. The idea of the attack is to extract $P$ facet by facet, and then figure out $R$ from it.

Also recall that these lattices are contained in $\mathbb{Z}^n$.

Notation: $\textrm{Aff}(F)$ gives the affine span of a set $F$, i.e. the smallest affine subspace containing $F$. $\textrm{vect}{A}$ takes an affine subspace and gives the subspace of differences of $A$ $\textrm{vect}(A) = \{ v - w : v , w \in A \}$; in other words, this operation rigidly translates $A$ to contain the origin.

Facet-affine span extraction subroutine - in addition to everything else, this takes as input a subspace $V$:

  1. Pick a random line $l = span(v)$ through the origin and contained in $V$. Then, using binary search, ask for signatures on $\lambda v$ , $\lambda > 0$, until you find $\lambda, \lambda'$ with $\lambda v , \lambda'v$ having different signatures, and $\lambda$ and $\lambda'$ "very close" in value.
  2. $\lambda v$ is thus very close to one of the two points where $l$ intersects a facet $F$ of $P$, say $w$. (The relevant point is that the signature is the label of the translate of the parallelopiped in the corresponding tesselation of $\mathbb{R}^n$ -- unless I've terribly misunderstood the scheme.)
  3. Then take "very small" perturbations of $l$ to get $n$ similar random approximate intersections with $F$.
  4. This gives $n$ random points almost on $F$ and near $w$, say $w_1, \ldots, w_n$. I believe one can error correct using knowledge about the lattice being integral and the longest vectors not being too long (based on the lattice sampling algorithm) to bound the bit length necessary to describe equations for $\textrm{aff}(F)$, and thus calculate $\textrm{aff}(F)$ from $\{w_1, \ldots, w_n\}$. (In addition to handling the approximation error, one also needs to make the perturbations sufficiently small to account for the intersection probably being near a face of the facet it intersects -- I haven't checked that either is possible, and am living dangerously by hand-waving without justification: '1) by binary search we can get exponentially close to the true intersections between the facets and the lines, and 2) we can pick a small perturbation angle so that we remain bounded away from the boundaries of the two facet $l$ intersects, since the vectors in $R$ are not too long.')
  5. Repeating this with $\lambda < 0$ instead will give $-F$.

Over all routine:

  1. Once you can learned the affine spans of facets $F_1, F_2, \ldots, F_k$ of P, then you take random lines through $0$ contained in $V = \text{vect} (\textrm{aff}(F_1) \cap \textrm{aff}(F_2) \ldots \cap \textrm{aff}(F_k))$ to learn the other affine-spans of facets using the facet extraction subroutine above. (Start with $V = \mathbb{R}^n = \bigcap_{\emptyset}$.)
  2. There are only 2n facets, so provided that 1) runs efficiently we can learn all of their affine spans in polynomial time. Given these affine subspaces, we greedily build a subset of n of them whose intersection is a point $p$, say $A_1, \ldots, A_n$, and then we take the intersections of the $n$ $n-1$-size subsets $\{A_1, \ldots, A_n\}$ to obtain lines $l_1, \ldots, l_n$. The lines $l_1, \ldots, l_n$ correspond to the spans of the basis vectors in $R$, and we can extract $R$ from them, for instance by taking the preimage of $l_i$ under the public basis $B$, and finding the smallest $\mathbb{Z}^n$ point along it. (One doesn't actually need $B$ in order to finish off the extraction -- since the lattice is in $\mathbb{Z}^n$, asking for signatures along $l_i$ and using binary search to find the smallest lattice points should also do it.)
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.