The Problem To Be Solved
For the Raw NTRUsign, Key Recovery can be modeled as:
Learning a Parrallelepiped P(V) [NgRe06]
For an invertible n×n matrix V
Given samples x = y V ∈ Rn where y is unif. over [-1,1]n
Recover one (or all) Column Vector of V
Learning a Zonotope Z(V)
For a full-rank m×n matrix V
Given samples x = y V ∈ Rn where y is unif. over [-1,1]m
Recover one (or all) Column Vector of V
For the Perturbed NTRUsign, this can be generalized as: