Introduction to the Shortest Vector Problem

Introduction

Imagine an infinite sheet of graph paper, but the grid is tilted and stretched. You are given just two arrows — call them a basis — and every point you can reach by stepping forward and backward along those arrows, any whole number of times, is a point of the lattice. Two short, almost-perpendicular arrows draw a clean grid. Two long, nearly-parallel arrows draw the same grid in a clumsy, skewed way.

Now a simple-sounding question: among all the lattice points, which nonzero one sits closest to the origin? That is the Shortest Vector Problem (SVP).

With a tidy basis you can almost see the answer. But cryptographers deliberately hand you a bad basis — long, tangled arrows that describe the very same grid — and finding that shortest point suddenly becomes one of the hardest problems we know. That gap between easy to describe and hard to solve is exactly what protects your data after quantum computers arrive.

Find the Shortest Vector

Below is a 2D lattice generated by two basis vectors. Every blue dot is a combination a· $b_{1}$ + b· $b_{2}$ for whole numbers a and b. Your job: find the shortest nonzero vector — the dot nearest the center.

<p class="hint">Every blue dot is a lattice point <b>a·b&#8321; + b·b&#8322;</b> for whole
numbers a, b. The two arrows are the <b>basis</b>. Find the <b>shortest nonzero</b>
vector — the dot nearest the center. The same grid has a tangled basis and a tidy one;
measuring a vector is instant, searching for the shortest one is the hard part.</p>
<canvas id="lat" width="380" height="380"></canvas>
<div class="status" id="status">Pick a basis, then search.</div>
<div class="btns">
  <button id="bad" type="button" class="ghost">Bad basis</button>
  <button id="good" type="button" class="ghost">Good (reduced) basis</button>
  <button id="find" type="button">Find shortest vector</button>
</div>
<div class="readout" id="readout"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
canvas { background: #fafcff; border: 1px solid #cdd9e3; border-radius: 10px;
         display: block; max-width: 100%; touch-action: none; }
.status { font-size: 1rem; font-weight: 600; margin: .6rem 0 .4rem; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
.readout { font: 500 .85rem ui-monospace, monospace; color: #1d3557; margin-top: .6rem;
           min-height: 1.2em; white-space: pre-line; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button.active { background: #2a6f97; border-color: #2a6f97; color: #fff; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Shortest Vector Problem (SVP) in 2D. A lattice is all integer combinations
// a*b1 + b*b2 of two basis vectors. The SHORTEST nonzero vector is fixed by the
// grid itself — it does NOT depend on which basis you choose. Two bases below
// describe the SAME lattice (one is a sheared version of the other), yet one
// makes the answer obvious and one hides it. Checking |v| is O(1); finding the minimum means scanning many integer combinations (NP-hard in high dimension).
const cv = document.getElementById('lat'), ctx = cv.getContext('2d');
const W = cv.width, H = cv.height, cx = W/2, cy = H/2, S = 26; // px per unit

// Same lattice, two bases. GOOD = short & near-orthogonal; BAD = sheared (b2 += 3*b1).
const GOOD = [[1, 2], [2, -1]];          // reduced basis
const BAD  = [[1, 2], [5, 5]];           // = b1 and b2+3*b1 -> same lattice, long & skewed
let basis = BAD, mode = 'bad', best = null;

function toPx(x, y){ return [cx + x*S, cy - y*S]; }

function draw(){
  ctx.clearRect(0,0,W,H);
  // axes
  ctx.strokeStyle = '#e3e9ef'; ctx.lineWidth = 1;
  ctx.beginPath(); ctx.moveTo(0,cy); ctx.lineTo(W,cy); ctx.moveTo(cx,0); ctx.lineTo(cx,H); ctx.stroke();
  // lattice points within view
  const R = 9;
  for(let a=-R;a<=R;a++) for(let b=-R;b<=R;b++){
    const x = a*basis[0][0] + b*basis[1][0];
    const y = a*basis[0][1] + b*basis[1][1];
    const [px,py] = toPx(x,y);
    if(px<0||px>W||py<0||py>H) continue;
    const isOrigin = (a===0 && b===0);
    ctx.fillStyle = isOrigin ? '#1d3557' : '#7aa7d8';
    ctx.beginPath(); ctx.arc(px,py, isOrigin?4:3, 0, 7); ctx.fill();
  }
  // basis arrows
  drawArrow(0,0, basis[0][0],basis[0][1], '#2a6f97', 'b₁');
  drawArrow(0,0, basis[1][0],basis[1][1], '#9d4edd', 'b₂');
  // best (shortest) vector found
  if(best){
    drawArrow(0,0, best.x,best.y, '#e63946', '');
    const [px,py] = toPx(best.x,best.y);
    ctx.fillStyle = '#e63946'; ctx.beginPath(); ctx.arc(px,py,5,0,7); ctx.fill();
  }
}
function drawArrow(x0,y0,x1,y1,color,label){
  const [ax,ay]=toPx(x0,y0), [bx,by]=toPx(x1,y1);
  ctx.strokeStyle=color; ctx.fillStyle=color; ctx.lineWidth=2.4;
  ctx.beginPath(); ctx.moveTo(ax,ay); ctx.lineTo(bx,by); ctx.stroke();
  const ang=Math.atan2(by-ay,bx-ax), h=8;
  ctx.beginPath(); ctx.moveTo(bx,by);
  ctx.lineTo(bx-h*Math.cos(ang-0.4), by-h*Math.sin(ang-0.4));
  ctx.lineTo(bx-h*Math.cos(ang+0.4), by-h*Math.sin(ang+0.4));
  ctx.closePath(); ctx.fill();
  if(label){ ctx.font='600 13px system-ui'; ctx.fillText(label, bx+6, by-6); }
}

// Brute-force SVP: scan integer combinations and keep the shortest NONZERO vector.
function findShortest(){
  const R = 12; let bx=0,by=0,bn=Infinity,tries=0;
  for(let a=-R;a<=R;a++) for(let b=-R;b<=R;b++){
    if(a===0 && b===0) continue;
    const x = a*basis[0][0] + b*basis[1][0];
    const y = a*basis[0][1] + b*basis[1][1];
    const n = x*x + y*y; tries++;
    if(n < bn){ bn=n; bx=x; by=y; }
  }
  best = { x:bx, y:by, len2:bn };
  return { tries, len: Math.sqrt(bn), x:bx, y:by };
}

function setStatus(t,cls){ const s=document.getElementById('status'); s.textContent=t; s.className='status '+cls; }
function len(v){ return Math.sqrt(v[0]*v[0]+v[1]*v[1]); }

function pick(m){
  mode=m; basis = (m==='good')?GOOD:BAD; best=null;
  document.getElementById('good').classList.toggle('active', m==='good');
  document.getElementById('bad').classList.toggle('active', m==='bad');
  document.getElementById('readout').textContent =
    fmt(`basis b₁ = (%v%),  |b₁| = %len%
basis b₂ = (%v2%),  |b₂| = %len2%`, { v: basis[0], len: len(basis[0]).toFixed(2), v2: basis[1], len2: len(basis[1]).toFixed(2) });
  setStatus(m==='good' ? `Good basis: short, near-perpendicular arrows.` :
                         `Bad basis: long, skewed arrows hide the answer.`, '');
  draw();
}
document.getElementById('bad').addEventListener('click',()=>pick('bad'));
document.getElementById('good').addEventListener('click',()=>pick('good'));
document.getElementById('find').addEventListener('click',()=>{
  const r = findShortest();
  setStatus(fmt(`Shortest vector = (%x%, %y%),  length %len%  — — checked %tries% combinations.`, { x: r.x, y: r.y, len: r.len.toFixed(3), tries: r.tries }), 'ok');
  draw();
  console.log(`SVP result`, r, `mode`, mode);
});
pick('bad');

<p class="hint">Every blue dot is a lattice point <b>a·b&#8321; + b·b&#8322;</b> for whole
numbers a, b. The two arrows are the <b>basis</b>. Find the <b>shortest nonzero</b>
vector — the dot nearest the center. The same grid has a tangled basis and a tidy one;
measuring a vector is instant, searching for the shortest one is the hard part.</p>
<canvas id="lat" width="380" height="380"></canvas>
<div class="status" id="status">Pick a basis, then search.</div>
<div class="btns">
  <button id="bad" type="button" class="ghost">Bad basis</button>
  <button id="good" type="button" class="ghost">Good (reduced) basis</button>
  <button id="find" type="button">Find shortest vector</button>
</div>
<div class="readout" id="readout"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
canvas { background: #fafcff; border: 1px solid #cdd9e3; border-radius: 10px;
         display: block; max-width: 100%; touch-action: none; }
.status { font-size: 1rem; font-weight: 600; margin: .6rem 0 .4rem; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
.readout { font: 500 .85rem ui-monospace, monospace; color: #1d3557; margin-top: .6rem;
           min-height: 1.2em; white-space: pre-line; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button.active { background: #2a6f97; border-color: #2a6f97; color: #fff; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Shortest Vector Problem (SVP) in 2D. A lattice is all integer combinations
// a*b1 + b*b2 of two basis vectors. The SHORTEST nonzero vector is fixed by the
// grid itself — it does NOT depend on which basis you choose. Two bases below
// describe the SAME lattice (one is a sheared version of the other), yet one
// makes the answer obvious and one hides it. Checking |v| is O(1); finding the minimum means scanning many integer combinations (NP-hard in high dimension).
const cv = document.getElementById('lat'), ctx = cv.getContext('2d');
const W = cv.width, H = cv.height, cx = W/2, cy = H/2, S = 26; // px per unit

// Same lattice, two bases. GOOD = short & near-orthogonal; BAD = sheared (b2 += 3*b1).
const GOOD = [[1, 2], [2, -1]];          // reduced basis
const BAD  = [[1, 2], [5, 5]];           // = b1 and b2+3*b1 -> same lattice, long & skewed
let basis = BAD, mode = 'bad', best = null;

function toPx(x, y){ return [cx + x*S, cy - y*S]; }

function draw(){
  ctx.clearRect(0,0,W,H);
  // axes
  ctx.strokeStyle = '#e3e9ef'; ctx.lineWidth = 1;
  ctx.beginPath(); ctx.moveTo(0,cy); ctx.lineTo(W,cy); ctx.moveTo(cx,0); ctx.lineTo(cx,H); ctx.stroke();
  // lattice points within view
  const R = 9;
  for(let a=-R;a<=R;a++) for(let b=-R;b<=R;b++){
    const x = a*basis[0][0] + b*basis[1][0];
    const y = a*basis[0][1] + b*basis[1][1];
    const [px,py] = toPx(x,y);
    if(px<0||px>W||py<0||py>H) continue;
    const isOrigin = (a===0 && b===0);
    ctx.fillStyle = isOrigin ? '#1d3557' : '#7aa7d8';
    ctx.beginPath(); ctx.arc(px,py, isOrigin?4:3, 0, 7); ctx.fill();
  }
  // basis arrows
  drawArrow(0,0, basis[0][0],basis[0][1], '#2a6f97', 'b₁');
  drawArrow(0,0, basis[1][0],basis[1][1], '#9d4edd', 'b₂');
  // best (shortest) vector found
  if(best){
    drawArrow(0,0, best.x,best.y, '#e63946', '');
    const [px,py] = toPx(best.x,best.y);
    ctx.fillStyle = '#e63946'; ctx.beginPath(); ctx.arc(px,py,5,0,7); ctx.fill();
  }
}
function drawArrow(x0,y0,x1,y1,color,label){
  const [ax,ay]=toPx(x0,y0), [bx,by]=toPx(x1,y1);
  ctx.strokeStyle=color; ctx.fillStyle=color; ctx.lineWidth=2.4;
  ctx.beginPath(); ctx.moveTo(ax,ay); ctx.lineTo(bx,by); ctx.stroke();
  const ang=Math.atan2(by-ay,bx-ax), h=8;
  ctx.beginPath(); ctx.moveTo(bx,by);
  ctx.lineTo(bx-h*Math.cos(ang-0.4), by-h*Math.sin(ang-0.4));
  ctx.lineTo(bx-h*Math.cos(ang+0.4), by-h*Math.sin(ang+0.4));
  ctx.closePath(); ctx.fill();
  if(label){ ctx.font='600 13px system-ui'; ctx.fillText(label, bx+6, by-6); }
}

// Brute-force SVP: scan integer combinations and keep the shortest NONZERO vector.
function findShortest(){
  const R = 12; let bx=0,by=0,bn=Infinity,tries=0;
  for(let a=-R;a<=R;a++) for(let b=-R;b<=R;b++){
    if(a===0 && b===0) continue;
    const x = a*basis[0][0] + b*basis[1][0];
    const y = a*basis[0][1] + b*basis[1][1];
    const n = x*x + y*y; tries++;
    if(n < bn){ bn=n; bx=x; by=y; }
  }
  best = { x:bx, y:by, len2:bn };
  return { tries, len: Math.sqrt(bn), x:bx, y:by };
}

function setStatus(t,cls){ const s=document.getElementById('status'); s.textContent=t; s.className='status '+cls; }
function len(v){ return Math.sqrt(v[0]*v[0]+v[1]*v[1]); }

function pick(m){
  mode=m; basis = (m==='good')?GOOD:BAD; best=null;
  document.getElementById('good').classList.toggle('active', m==='good');
  document.getElementById('bad').classList.toggle('active', m==='bad');
  document.getElementById('readout').textContent =
    fmt(`basis b₁ = (%v%),  |b₁| = %len%
basis b₂ = (%v2%),  |b₂| = %len2%`, { v: basis[0], len: len(basis[0]).toFixed(2), v2: basis[1], len2: len(basis[1]).toFixed(2) });
  setStatus(m==='good' ? `Good basis: short, near-perpendicular arrows.` :
                         `Bad basis: long, skewed arrows hide the answer.`, '');
  draw();
}
document.getElementById('bad').addEventListener('click',()=>pick('bad'));
document.getElementById('good').addEventListener('click',()=>pick('good'));
document.getElementById('find').addEventListener('click',()=>{
  const r = findShortest();
  setStatus(fmt(`Shortest vector = (%x%, %y%),  length %len%  — — checked %tries% combinations.`, { x: r.x, y: r.y, len: r.len.toFixed(3), tries: r.tries }), 'ok');
  draw();
  console.log(`SVP result`, r, `mode`, mode);
});
pick('bad');

Result

Console

Try the Bad basis first: the two arrows are long and nearly parallel, so the true shortest vector is hard to spot. Switch to the Good (reduced) basis and the same grid suddenly reveals its short, near-perpendicular arrows. Notice the asymmetry: checking a candidate is instant — just measure its length — but searching the grid means trying every combination a· $b_{1}$ + b· $b_{2}$ , and the number of combinations explodes with the range and the dimension.

The Real Complexity

How hard is finding the shortest vector, really?

Checking a candidate is trivial: a vector is just a list of coordinates — square them, add, compare. Fast and exact.
Brute force enumerates lattice points within some radius. In dimension n the number of candidate combinations grows exponentially, so naive search dies quickly past a few dozen dimensions.
It's NP-hard. In 1998 Miklós Ajtai proved SVP is NP-hard under randomized reductions, and later work (Micciancio, then Subhash Khot and others) showed it stays hard even to approximate the shortest vector within small factors. So there is no known efficient algorithm, and strong evidence there never will be.
Lattice reduction (the famous LLL algorithm, Lenstra–Lenstra–Lovász, 1982) finds a fairly short vector in polynomial time — that is the "good basis" trick — but the gap it leaves grows with dimension, which is exactly why high-dimensional lattices stay secure.
Even quantum computers don't help. Shor's algorithm shatters RSA by solving factoring and discrete logs, but it offers no comparable shortcut for SVP. That is the whole reason lattices were chosen for the post-quantum era.

The punchline: the same grid can be described by an easy basis or an impossibly tangled one, and there is no fast way to untangle it. Like P vs NP, the verifying side is effortless while the solving side appears genuinely intractable.

Where It Matters

The hardness of SVP isn't an academic curiosity — it is being baked into the internet right now:

Post-quantum cryptography: when NIST chose new standards to survive quantum computers, the winners — Kyber (key exchange) and Dilithium (signatures) — are built on lattice problems closely related to SVP. Your browser may already be negotiating keys this way.
Fully homomorphic encryption: lattices let a server compute on data it can never read, because peeling away the answer would require solving a short-vector problem.
Breaking weak crypto: turn it around and lattice reduction becomes an attack — LLL has cracked knapsack ciphers and flawed RSA setups by finding a hidden short vector.
Coding and signal processing: the same "nearest lattice point" question appears in error-correcting codes and in decoding multi-antenna wireless signals.

Understand why the shortest vector is hard and you've met the engine behind tomorrow's encryption — a cousin of factoring that quantum computers can't unwind.

Conclusion

The Shortest Vector Problem hides a beautiful tension: a lattice is just an infinite grid of dots, and asking for the dot nearest the origin sounds like something you could eyeball. Yet hand someone a deliberately tangled basis and that question becomes NP-hard — so stubborn that not even a quantum computer offers a clean way in.

That stubbornness is now a feature. The same gap between checking a vector and finding it is being turned into the locks that will protect your messages, payments, and secrets long after today's encryption falls. The next time your browser whispers a quantum-safe handshake, remember the humble grid behind it — and that, much like P vs NP, the hard direction may simply have no shortcut at all.

Comments

Loading comments...

https://www.kipuhub.com/en/article/lattices-svp/Content licensed under CC BY-NC 4.0.

Cookies & privacy

The Shortest Vector Problem

When finding the closest point becomes the hardest thing in cryptography