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: