<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>InsPIRe Protocol Visualization</title>
<script src="https://d3js.org/d3.v7.min.js"></script>
<style>
:root {
--bg-primary: #0d1117;
--bg-secondary: #161b22;
--bg-tertiary: #21262d;
--text-primary: #e6edf3;
--text-secondary: #8b949e;
--accent-blue: #58a6ff;
--accent-green: #3fb950;
--accent-purple: #a371f7;
--accent-orange: #d29922;
--border-color: #30363d;
}
* {
box-sizing: border-box;
margin: 0;
padding: 0;
}
body {
font-family: -apple-system, BlinkMacSystemFont, 'Segoe UI', Roboto, Oxygen, Ubuntu, sans-serif;
background: var(--bg-primary);
color: var(--text-primary);
line-height: 1.6;
padding: 2rem;
}
.container {
max-width: 1200px;
margin: 0 auto;
}
h1 {
text-align: center;
margin-bottom: 0.5rem;
color: var(--accent-blue);
}
.subtitle {
text-align: center;
color: var(--text-secondary);
margin-bottom: 2rem;
}
.section {
background: var(--bg-secondary);
border: 1px solid var(--border-color);
border-radius: 8px;
padding: 1.5rem;
margin-bottom: 2rem;
}
.section h2 {
color: var(--accent-purple);
margin-bottom: 1rem;
font-size: 1.25rem;
}
.key-insight {
background: var(--bg-tertiary);
border-left: 4px solid var(--accent-green);
padding: 1rem;
margin: 1rem 0;
border-radius: 0 4px 4px 0;
}
.key-insight strong {
color: var(--accent-green);
}
#protocol-flow {
display: flex;
flex-direction: column;
align-items: center;
}
#flow-svg {
width: 100%;
max-width: 900px;
}
.flow-controls {
display: flex;
gap: 1rem;
margin-top: 1rem;
}
.flow-controls button {
background: var(--accent-blue);
color: white;
border: none;
padding: 0.5rem 1.5rem;
border-radius: 4px;
cursor: pointer;
font-size: 0.9rem;
transition: opacity 0.2s;
}
.flow-controls button:hover {
opacity: 0.85;
}
.flow-controls button:disabled {
opacity: 0.5;
cursor: not-allowed;
}
#size-breakdown {
display: flex;
gap: 2rem;
flex-wrap: wrap;
}
.chart-container {
flex: 1;
min-width: 300px;
}
.format-toggle {
display: flex;
gap: 0.5rem;
margin-bottom: 1rem;
flex-wrap: wrap;
}
.format-toggle button {
background: var(--bg-tertiary);
color: var(--text-secondary);
border: 1px solid var(--border-color);
padding: 0.4rem 1rem;
border-radius: 4px;
cursor: pointer;
font-size: 0.85rem;
transition: all 0.2s;
}
.format-toggle button.active {
background: var(--accent-purple);
color: white;
border-color: var(--accent-purple);
}
.format-toggle button:hover:not(.active) {
border-color: var(--text-secondary);
}
.model-toggle {
display: flex;
gap: 0.5rem;
margin-bottom: 0.75rem;
flex-wrap: wrap;
}
.model-toggle button {
background: var(--bg-tertiary);
color: var(--text-secondary);
border: 1px solid var(--border-color);
padding: 0.35rem 0.9rem;
border-radius: 4px;
cursor: pointer;
font-size: 0.8rem;
transition: all 0.2s;
}
.model-toggle button.active {
background: var(--accent-green);
color: white;
border-color: var(--accent-green);
}
.model-note {
font-size: 0.75rem;
color: var(--text-secondary);
margin-top: 0.5rem;
}
.tooltip {
position: absolute;
background: var(--bg-tertiary);
border: 1px solid var(--border-color);
border-radius: 4px;
padding: 0.75rem;
font-size: 0.85rem;
pointer-events: none;
opacity: 0;
transition: opacity 0.15s;
z-index: 100;
max-width: 280px;
}
.tooltip.visible {
opacity: 1;
}
.tooltip .label {
color: var(--accent-blue);
font-weight: 600;
margin-bottom: 0.25rem;
}
.tooltip .value {
color: var(--text-primary);
}
.tooltip .formula {
color: var(--text-secondary);
font-family: monospace;
font-size: 0.8rem;
margin-top: 0.5rem;
}
.crypto-tooltip {
position: fixed;
background: var(--bg-tertiary);
border: 1px solid var(--accent-purple);
border-radius: 6px;
padding: 0.75rem 1rem;
font-size: 0.85rem;
pointer-events: none;
opacity: 0;
transition: opacity 0.15s;
z-index: 200;
max-width: 320px;
box-shadow: 0 4px 12px rgba(0,0,0,0.4);
}
.crypto-tooltip.visible {
opacity: 1;
}
.crypto-tooltip .ct-title {
color: var(--accent-purple);
font-weight: 700;
margin-bottom: 0.4rem;
font-size: 0.9rem;
}
.crypto-tooltip .ct-desc {
color: var(--text-primary);
line-height: 1.4;
margin-bottom: 0.4rem;
}
.crypto-tooltip .ct-detail {
color: var(--text-secondary);
font-family: monospace;
font-size: 0.75rem;
border-top: 1px solid var(--border-color);
padding-top: 0.4rem;
margin-top: 0.3rem;
}
.sliders {
display: grid;
grid-template-columns: repeat(auto-fit, minmax(280px, 1fr));
gap: 1.5rem;
margin-bottom: 1.5rem;
}
.slider-group {
background: var(--bg-tertiary);
padding: 1rem;
border-radius: 6px;
}
.slider-group label {
display: flex;
justify-content: space-between;
margin-bottom: 0.5rem;
color: var(--text-secondary);
font-size: 0.9rem;
}
.slider-group label span {
color: var(--accent-orange);
font-weight: 600;
}
.slider-group input[type="range"] {
width: 100%;
height: 6px;
-webkit-appearance: none;
background: var(--border-color);
border-radius: 3px;
outline: none;
}
.slider-group input[type="range"]::-webkit-slider-thumb {
-webkit-appearance: none;
width: 18px;
height: 18px;
background: var(--accent-orange);
border-radius: 50%;
cursor: pointer;
}
.size-results {
display: grid;
grid-template-columns: repeat(auto-fit, minmax(200px, 1fr));
gap: 1rem;
}
.size-card {
background: var(--bg-tertiary);
padding: 1rem;
border-radius: 6px;
text-align: center;
}
.size-card .size-label {
color: var(--text-secondary);
font-size: 0.85rem;
margin-bottom: 0.25rem;
}
.size-card .size-value {
font-size: 1.5rem;
font-weight: 700;
}
.size-card.query .size-value {
color: var(--accent-blue);
}
.size-card.response .size-value {
color: var(--accent-green);
}
.size-card.total .size-value {
color: var(--accent-purple);
}
.size-card .size-formula {
font-size: 0.7rem;
color: var(--text-secondary);
font-family: monospace;
margin-top: 0.25rem;
}
.comparison-table {
width: 100%;
border-collapse: collapse;
font-size: 0.9rem;
}
.comparison-table th,
.comparison-table td {
padding: 0.75rem 1rem;
text-align: center;
border-bottom: 1px solid var(--border-color);
}
.comparison-table th {
background: var(--bg-tertiary);
color: var(--text-secondary);
font-weight: 600;
}
.comparison-table tr:hover td {
background: var(--bg-tertiary);
}
.comparison-table .same {
color: var(--accent-green);
}
.comparison-table .varies {
color: var(--accent-orange);
}
.legend {
display: flex;
gap: 1.5rem;
justify-content: center;
margin-top: 1rem;
flex-wrap: wrap;
}
.legend-item {
display: flex;
align-items: center;
gap: 0.5rem;
font-size: 0.85rem;
color: var(--text-secondary);
}
.legend-color {
width: 14px;
height: 14px;
border-radius: 3px;
}
.footer {
text-align: center;
color: var(--text-secondary);
font-size: 0.85rem;
margin-top: 2rem;
padding-top: 1rem;
border-top: 1px solid var(--border-color);
}
.footer a {
color: var(--accent-blue);
text-decoration: none;
}
.footer a:hover {
text-decoration: underline;
}
button:focus-visible,
input:focus-visible,
select:focus-visible {
outline: 2px solid var(--accent-blue);
outline-offset: 2px;
}
.bar:focus {
outline: 2px solid var(--accent-blue);
outline-offset: 1px;
}
@media (prefers-reduced-motion: reduce) {
*,
*::before,
*::after {
animation-duration: 0.01ms !important;
animation-iteration-count: 1 !important;
transition-duration: 0.01ms !important;
}
}
</style>
</head>
<body>
<div class="container">
<h1>InsPIRe Protocol Visualization</h1>
<p class="subtitle">Interactive visualization of PIR communication costs</p>
<div class="section">
<div class="key-insight">
<div class="model-toggle" id="model-toggle">
<button data-model="paper" class="active">Paper model</button>
<button data-model="implementation">Implementation (sharded)</button>
</div>
<div class="model-copy" data-model="paper">
<strong>Key Privacy Property (Paper model):</strong> For a given database and parameter set, every query uses the same amount of communication, regardless of which entry is requested.
Query size scales with database size N (via N/t indicator vector), and response size scales with entry size. If sizes varied with the target index, traffic analysis could reveal what's being queried.
</div>
<div class="model-copy" data-model="implementation" style="display: none;">
<strong>Key Privacy Property (Implementation):</strong> For fixed parameters (d, ell, coefficient size), query size is constant because the client sends only <code>shard_id</code> plus an RGSW ciphertext.
Database growth is handled by sharding, which keeps query size fixed but reveals shard granularity (which shard/range is accessed). Response size still scales with entry size; server time grows with shard count.
</div>
</div>
</div>
<div class="section">
<h2>1. Protocol Flow</h2>
<p class="section-caption" style="color: var(--text-secondary); font-size: 0.9rem; margin-bottom: 1rem;">
<strong style="color: var(--accent-green);">Key:</strong> One round-trip: client sends encrypted query, server computes on ciphertexts, returns encrypted result.
</p>
<div class="format-toggle" id="flow-variant-toggle" style="margin-bottom: 1rem;">
<button data-variant="inspire0">InsPIRe_0 (246 KB)</button>
<button data-variant="inspire1" class="active">InsPIRe (310 KB)</button>
<button data-variant="inspire2">InsPIRe^(2) (214 KB)</button>
</div>
<div id="protocol-flow">
<svg id="flow-svg" viewBox="0 0 900 320" role="img" aria-labelledby="flow-title" aria-describedby="flow-desc">
<title id="flow-title">PIR Protocol Flow Diagram</title>
<desc id="flow-desc">Animated sequence diagram showing client-server communication: Query (LWE indicator, optionally with RGSW for InsPIRe), Server Processing (external product), Response (RLWE ciphertext), and Client Extraction.</desc>
</svg>
<div class="flow-controls">
<button id="play-btn">Play Animation</button>
<button id="reset-btn">Reset</button>
</div>
</div>
</div>
<div class="section">
<h2>2. Size Breakdown</h2>
<p class="section-caption" style="color: var(--text-secondary); font-size: 0.9rem; margin-bottom: 1rem;">
<strong style="color: var(--accent-green);">Key:</strong> Three paper protocols (InsPIRe_0, InsPIRe^(2), InsPIRe) with different query structures. InsPIRe_0 and InsPIRe^(2) use LWE indicators only; InsPIRe adds RGSW for polynomial evaluation.
</p>
<p class="model-note" id="model-note-sizes">Paper model: query breakdown includes the LWE indicator vector, which scales with N/t.</p>
<div class="format-toggle">
<button data-format="inspire0">InsPIRe_0 (~246 KB)</button>
<button class="active" data-format="inspire1">InsPIRe (~310 KB)</button>
<button data-format="inspire2">InsPIRe^(2) (~214 KB)</button>
</div>
<p style="font-size: 0.75rem; color: var(--text-secondary); margin-top: 0.5rem;">
Sizes shown reflect single-modulus serialization (crt_moduli length 1). The default CRT mode stores two residues per coefficient and approximately doubles the serialized size.
</p>
<div id="size-breakdown" style="display: flex; flex-wrap: wrap; gap: 1rem; justify-content: center;">
<div class="chart-container">
<svg id="keys-chart" viewBox="0 0 420 280" preserveAspectRatio="xMidYMid meet" role="img" aria-labelledby="keys-chart-title" aria-describedby="keys-chart-desc">
<title id="keys-chart-title">Upload Keys Breakdown Chart</title>
<desc id="keys-chart-desc">Bar chart showing the size breakdown of uploaded keys including packing matrices and key-switching matrices.</desc>
</svg>
</div>
<div class="chart-container">
<svg id="query-chart" viewBox="0 0 420 280" preserveAspectRatio="xMidYMid meet" role="img" aria-labelledby="query-chart-title" aria-describedby="query-chart-desc">
<title id="query-chart-title">Upload Query Breakdown Chart</title>
<desc id="query-chart-desc">Bar chart showing the size breakdown of uploaded query components including LWE indicators and optional RGSW ciphertexts.</desc>
</svg>
</div>
<div class="chart-container">
<svg id="response-chart" viewBox="0 0 420 280" preserveAspectRatio="xMidYMid meet" role="img" aria-labelledby="response-chart-title" aria-describedby="response-chart-desc">
<title id="response-chart-title">Download Response Breakdown Chart</title>
<desc id="response-chart-desc">Bar chart showing the size breakdown of downloaded response containing RLWE ciphertexts.</desc>
</svg>
</div>
</div>
<div class="legend">
<div class="legend-item">
<div class="legend-color" style="background: #d29922;"></div>
<span>Upload Keys (packing/KS matrices)</span>
</div>
<div class="legend-item">
<div class="legend-color" style="background: #58a6ff;"></div>
<span>Upload Query (indicator / RGSW)</span>
</div>
<div class="legend-item">
<div class="legend-color" style="background: #3fb950;"></div>
<span>Download (RLWE response)</span>
</div>
</div>
<div class="tooltip" id="tooltip"></div>
<div class="crypto-tooltip" id="crypto-tooltip">
<div class="ct-title"></div>
<div class="ct-desc"></div>
<div class="ct-detail"></div>
</div>
</div>
<div class="section">
<h2>3. Parameter Effects <span id="variant-indicator" style="font-size: 0.85rem; font-weight: normal; color: var(--accent-purple);">(InsPIRe^1)</span></h2>
<p class="section-caption" style="color: var(--text-secondary); font-size: 0.9rem; margin-bottom: 1rem;">
<strong style="color: var(--accent-green);">Key:</strong> Sizes scale linearly with ring dimension (d) and gadget length (l). Select variant in Section 2 to update calculations.
</p>
<div class="sliders">
<div class="slider-group">
<label for="d-slider">Ring Dimension (d): <span id="d-value">2048</span></label>
<input type="range" id="d-slider" min="0" max="2" value="1" aria-describedby="d-value">
<div style="display: flex; justify-content: space-between; font-size: 0.75rem; color: var(--text-secondary); margin-top: 0.25rem;">
<span>1024</span>
<span>2048</span>
<span>4096</span>
</div>
</div>
<div class="slider-group">
<label for="entry-slider">Entry Size: <span id="entry-value">32 bytes</span></label>
<input type="range" id="entry-slider" min="0" max="2" value="0" aria-describedby="entry-value">
<div style="display: flex; justify-content: space-between; font-size: 0.75rem; color: var(--text-secondary); margin-top: 0.25rem;">
<span>32 B</span>
<span>64 B</span>
<span>128 B</span>
</div>
</div>
<div class="slider-group">
<label for="gadget-slider">Gadget Length (l): <span id="gadget-value">3</span></label>
<input type="range" id="gadget-slider" min="2" max="4" value="3" aria-describedby="gadget-value">
<div style="display: flex; justify-content: space-between; font-size: 0.75rem; color: var(--text-secondary); margin-top: 0.25rem;">
<span>2</span>
<span>3</span>
<span>4</span>
</div>
</div>
</div>
<div class="size-results">
<div class="size-card query">
<div class="size-label">Query Size (seeded)</div>
<div class="size-value" id="calc-query">96 KB</div>
<div class="size-formula" id="query-formula"></div>
</div>
<div class="size-card response">
<div class="size-label">Response Size (binary)</div>
<div class="size-value" id="calc-response">512 KB</div>
<div class="size-formula" id="response-formula"></div>
</div>
<div class="size-card total">
<div class="size-label">Total per Query</div>
<div class="size-value" id="calc-total">742 KB</div>
</div>
</div>
</div>
<div class="section">
<h2>4. Server Processing Visualization</h2>
<p class="section-caption" style="color: var(--text-secondary); font-size: 0.9rem; margin-bottom: 1rem;">
<strong style="color: var(--accent-green);">Key:</strong> Server processes one shard using parallel external products. Processing time is ~3ms regardless of total database size.
</p>
<div style="margin-bottom: 1.5rem;">
<h3 style="color: var(--accent-blue); font-size: 1rem; margin-bottom: 0.5rem;">Step 1: Shard Selection</h3>
<svg id="shard-svg" viewBox="0 0 900 180" role="img" aria-labelledby="shard-title" aria-describedby="shard-desc">
<title id="shard-title">Shard Selection visualization showing database partitioning</title>
<desc id="shard-desc">Visual grid of database shards with the target shard highlighted. Each shard contains entries encoded as polynomials.</desc>
</svg>
<div class="server-controls" style="margin-top: 0.5rem;">
<label style="color: var(--text-secondary); font-size: 0.9rem;">
Database size:
<select id="db-size-select" style="background: var(--bg-tertiary); color: var(--text-primary); border: 1px solid var(--border-color); padding: 0.3rem; border-radius: 4px;">
<option value="1024">1K entries (1 shard)</option>
<option value="65536">64K entries (32 shards)</option>
<option value="1048576" selected>1M entries (512 shards)</option>
<option value="100000000">100M entries (48K shards)</option>
</select>
</label>
</div>
</div>
<div style="margin-bottom: 1.5rem;">
<h3 style="color: var(--accent-green); font-size: 1rem; margin-bottom: 0.5rem;">Step 2: External Product (Parallel)</h3>
<svg id="pipeline-svg" viewBox="0 0 900 280" role="img" aria-labelledby="pipeline-title" aria-describedby="pipeline-desc">
<title id="pipeline-title">Server Processing Pipeline showing parallel external product operations</title>
<desc id="pipeline-desc">Animated diagram showing how the server computes external products between query ciphertexts and database polynomials in parallel.</desc>
</svg>
<div style="display: flex; gap: 1rem; margin-top: 0.5rem;">
<button id="animate-pipeline-btn" style="background: var(--accent-green); color: white; border: none; padding: 0.4rem 1rem; border-radius: 4px; cursor: pointer; font-size: 0.85rem;">
Animate Processing
</button>
</div>
</div>
<div>
<h3 style="color: var(--accent-purple); font-size: 1rem; margin-bottom: 0.5rem;">Step 3: Response Assembly</h3>
<svg id="output-svg" viewBox="0 0 900 150" role="img" aria-labelledby="output-title" aria-describedby="output-desc">
<title id="output-title">Response Assembly showing ServerResponse structure and network transmission</title>
<desc id="output-desc">Diagram showing how RLWE ciphertexts are assembled into the server response and transmitted back to the client.</desc>
</svg>
</div>
</div>
<div class="section">
<h2>4.5. LWE-to-RLWE Packing (InsPIRe^1/^2)</h2>
<p class="section-caption" style="color: var(--text-secondary); font-size: 0.9rem; margin-bottom: 1rem;">
<strong style="color: var(--accent-purple);">Key:</strong> Pack d LWE ciphertexts into 1 RLWE using Galois automorphisms. Two approaches available.
</p>
<div class="key-insight" style="margin-bottom: 1rem;">
<strong>Why packing?</strong> After external product, each column's value is in coefficient 0 of its RLWE.
Simple "shift and add" fails because noise spreads to ALL coefficients.
Automorphisms permute coefficients in a controlled way that preserves encryption structure.
</div>
<div style="display: flex; gap: 0.5rem; margin-bottom: 1rem;">
<button id="show-tree-algo" class="algo-toggle active" style="background: var(--accent-purple); color: white; border: none; padding: 0.5rem 1rem; border-radius: 4px; cursor: pointer; font-size: 0.85rem;">
Tree Packing (log d matrices)
</button>
<button id="show-inspiring-algo" class="algo-toggle" style="background: var(--bg-tertiary); color: var(--text-secondary); border: 1px solid var(--border-color); padding: 0.5rem 1rem; border-radius: 4px; cursor: pointer; font-size: 0.85rem;">
InspiRING (2 matrices) - ~35x faster
</button>
</div>
<svg id="tree-pack-svg" viewBox="0 0 900 420" role="img" aria-labelledby="tree-pack-title" aria-describedby="tree-pack-desc">
<title id="tree-pack-title">Tree Packing Algorithm showing how 8 LWE ciphertexts are combined into 1 RLWE</title>
<desc id="tree-pack-desc">Animated tree diagram showing the hierarchical packing process using Galois automorphisms to combine multiple LWE ciphertexts into a single RLWE ciphertext.</desc>
</svg>
<div style="display: flex; gap: 1rem; margin-top: 0.5rem; flex-wrap: wrap;">
<button id="animate-tree-btn" style="background: var(--accent-purple); color: white; border: none; padding: 0.4rem 1rem; border-radius: 4px; cursor: pointer; font-size: 0.85rem;">
Animate Tree Packing
</button>
<button id="reset-tree-btn" style="background: var(--bg-tertiary); color: var(--text-secondary); border: 1px solid var(--border-color); padding: 0.4rem 1rem; border-radius: 4px; cursor: pointer; font-size: 0.85rem;">
Reset
</button>
</div>
<div id="tree-pack-details" style="margin-top: 1rem; display: grid; grid-template-columns: repeat(auto-fit, minmax(250px, 1fr)); gap: 1rem;">
<div style="background: var(--bg-tertiary); padding: 1rem; border-radius: 6px;">
<h4 style="color: var(--accent-blue); font-size: 0.9rem; margin-bottom: 0.5rem;">Algorithm Steps</h4>
<ol style="color: var(--text-secondary); font-size: 0.85rem; padding-left: 1.2rem; margin: 0;">
<li>Extract LWE from each column RLWE (coeff 0)</li>
<li>Convert LWE a-vectors back to RLWE form</li>
<li>Recursively pair: ct_even + y·ct_odd</li>
<li>Apply automorphism τ_t and key-switch</li>
<li>Add scaled b-values to final result</li>
</ol>
</div>
<div style="background: var(--bg-tertiary); padding: 1rem; border-radius: 6px;">
<h4 style="color: var(--accent-green); font-size: 0.9rem; margin-bottom: 0.5rem;">Result</h4>
<p style="color: var(--text-secondary); font-size: 0.85rem; margin: 0;">
Column k's value appears at coefficient k of the packed RLWE, scaled by d.
<br><br>
<span style="font-family: monospace; color: var(--accent-orange);">
coeff[k] = message[k] × d
</span>
</p>
</div>
<div style="background: var(--bg-tertiary); padding: 1rem; border-radius: 6px;">
<h4 style="color: var(--accent-orange); font-size: 0.9rem; margin-bottom: 0.5rem;">Complexity</h4>
<p style="color: var(--text-secondary); font-size: 0.85rem; margin: 0;">
<strong>Keys:</strong> log(d) automorphism key-switching matrices<br>
<strong>Operations:</strong> O(n·log(d)) key-switches for n columns<br>
<strong>For d=2048:</strong> 11 KS matrices, ~948ms server time
</p>
</div>
</div>
<div id="inspiring-details" style="margin-top: 1rem; display: none;">
<div class="key-insight" style="border-left-color: var(--accent-green); margin-bottom: 1rem;">
<strong style="color: var(--accent-green);">InspiRING Innovation:</strong> Instead of log(d) key-switching matrices,
use only 2 matrices (K_g, K_h) by pre-rotating a single matrix offline using generator powers.
This is based on <a href="https://github.com/google/private-membership/tree/main/research/InsPIRe" style="color: var(--accent-blue);">Google's reference implementation</a>.
</div>
<div style="display: grid; grid-template-columns: repeat(auto-fit, minmax(250px, 1fr)); gap: 1rem;">
<div style="background: var(--bg-tertiary); padding: 1rem; border-radius: 6px;">
<h4 style="color: var(--accent-blue); font-size: 0.9rem; margin-bottom: 0.5rem;">Algorithm Steps</h4>
<ol style="color: var(--text-secondary); font-size: 0.85rem; padding-left: 1.2rem; margin: 0;">
<li><strong>Offline:</strong> Compute generator powers g^i mod 2d</li>
<li><strong>Offline:</strong> Pre-rotate K_g by τ_{g^i} for all i</li>
<li><strong>Offline:</strong> Backward recursion for gadget inversions</li>
<li><strong>Online:</strong> Single matrix-vector multiply</li>
<li><strong>Online:</strong> Add b-values at positions</li>
</ol>
</div>
<div style="background: var(--bg-tertiary); padding: 1rem; border-radius: 6px;">
<h4 style="color: var(--accent-green); font-size: 0.9rem; margin-bottom: 0.5rem;">Key Insight</h4>
<p style="color: var(--text-secondary); font-size: 0.85rem; margin: 0;">
Generator g=3 has order d/2 in Z*_{2d}. Pre-rotating ONE matrix by g^i
replaces storing log(d) separate matrices.
<br><br>
<span style="font-family: monospace; color: var(--accent-orange);">
τ_{g^i}(K_g) for i ∈ [0, n)
</span>
</p>
</div>
<div style="background: var(--bg-tertiary); padding: 1rem; border-radius: 6px;">
<h4 style="color: var(--accent-orange); font-size: 0.9rem; margin-bottom: 0.5rem;">Performance (d=2048)</h4>
<p style="color: var(--text-secondary); font-size: 0.85rem; margin: 0;">
<strong>Keys:</strong> 2 matrices (K_g, K_h) vs 11<br>
<strong>Packing keys:</strong> 64 bytes (seeds) vs 1056 KB (11 KS matrices)<br>
<strong>Online (16 LWEs):</strong> <span style="color: var(--accent-green);">115 μs</span><br>
<strong>Offline (16 LWEs):</strong> 6.1 ms (amortized)
</p>
</div>
</div>
<div style="margin-top: 1rem; background: var(--bg-tertiary); padding: 1rem; border-radius: 6px; border-left: 4px solid var(--accent-blue);">
<h4 style="color: var(--accent-blue); font-size: 0.9rem; margin-bottom: 0.5rem;">Google-Matching NTT Optimizations</h4>
<div style="display: grid; grid-template-columns: repeat(auto-fit, minmax(200px, 1fr)); gap: 1rem; color: var(--text-secondary); font-size: 0.85rem;">
<div>
<strong style="color: var(--accent-purple);">NTT-Domain Automorphisms</strong><br>
Precomputed permutation tables enable O(n) automorphisms vs O(n log n) NTT conversion
</div>
<div>
<strong style="color: var(--accent-purple);">Fused Multiply-Accumulate</strong><br>
mul_acc_ntt_domain() avoids intermediate allocations in inner loops
</div>
<div>
<strong style="color: var(--accent-purple);">Pre-cached bold_t_ntt</strong><br>
Zero NTT conversions in online phase - pure pointwise operations
</div>
</div>
</div>
<div style="margin-top: 1rem; overflow-x: auto;">
<table style="width: 100%; border-collapse: collapse; font-size: 0.85rem;">
<thead>
<tr style="background: var(--bg-tertiary);">
<th style="padding: 0.75rem; text-align: left; border-bottom: 1px solid var(--border-color);">Metric</th>
<th style="padding: 0.75rem; text-align: center; border-bottom: 1px solid var(--border-color);">Tree Packing</th>
<th style="padding: 0.75rem; text-align: center; border-bottom: 1px solid var(--border-color); color: var(--accent-green);">InspiRING</th>
<th style="padding: 0.75rem; text-align: center; border-bottom: 1px solid var(--border-color);">Improvement</th>
</tr>
</thead>
<tbody>
<tr>
<td style="padding: 0.75rem; border-bottom: 1px solid var(--border-color);">KS Matrices</td>
<td style="padding: 0.75rem; text-align: center; border-bottom: 1px solid var(--border-color);">11</td>
<td style="padding: 0.75rem; text-align: center; border-bottom: 1px solid var(--border-color); color: var(--accent-green);">2</td>
<td style="padding: 0.75rem; text-align: center; border-bottom: 1px solid var(--border-color);">5.5x</td>
</tr>
<tr>
<td style="padding: 0.75rem; border-bottom: 1px solid var(--border-color);">Packing Key Material</td>
<td style="padding: 0.75rem; text-align: center; border-bottom: 1px solid var(--border-color);">1056 KB (11 KS matrices)</td>
<td style="padding: 0.75rem; text-align: center; border-bottom: 1px solid var(--border-color); color: var(--accent-green);">64 bytes (seeds)</td>
<td style="padding: 0.75rem; text-align: center; border-bottom: 1px solid var(--border-color);">16,000x</td>
</tr>
<tr>
<td style="padding: 0.75rem; border-bottom: 1px solid var(--border-color);">Online Time (16 LWEs)</td>
<td style="padding: 0.75rem; text-align: center; border-bottom: 1px solid var(--border-color);">~4ms (legacy)</td>
<td style="padding: 0.75rem; text-align: center; border-bottom: 1px solid var(--border-color); color: var(--accent-green);">115 μs</td>
<td style="padding: 0.75rem; text-align: center; border-bottom: 1px solid var(--border-color); font-weight: bold; color: var(--accent-green);">35x</td>
</tr>
<tr>
<td style="padding: 0.75rem; border-bottom: 1px solid var(--border-color);">Offline Precomputation</td>
<td style="padding: 0.75rem; text-align: center; border-bottom: 1px solid var(--border-color);">N/A</td>
<td style="padding: 0.75rem; text-align: center; border-bottom: 1px solid var(--border-color); color: var(--accent-green);">6.1 ms</td>
<td style="padding: 0.75rem; text-align: center; border-bottom: 1px solid var(--border-color);">amortized</td>
</tr>
</tbody>
</table>
</div>
</div>
</div>
<div class="section">
<h2>5. Database Size Comparison</h2>
<p class="section-caption" style="color: var(--text-secondary); font-size: 0.9rem; margin-bottom: 1rem;">
<strong style="color: var(--accent-green);">Key:</strong> <span id="table-key-text">Query size scales with N/t (indicator vector length). Response size scales with entry size. For a <em>fixed</em> database, all queries use the same communication regardless of which entry is requested.</span>
</p>
<p class="model-note" id="model-note-table">Paper model: query grows with N/t; totals increase with database size.</p>
<div class="format-toggle" id="table-variant-toggle" style="margin-bottom: 1rem;">
<button data-variant="inspire0">InsPIRe_0</button>
<button data-variant="inspire1" class="active">InsPIRe</button>
<button data-variant="inspire2">InsPIRe^(2)</button>
</div>
<table class="comparison-table">
<thead>
<tr>
<th>Database Size</th>
<th>Entries</th>
<th>Shards</th>
<th id="table-query-header">Query Size</th>
<th id="table-response-header">Response Size</th>
<th>Total</th>
<th>Server Time</th>
</tr>
<tr class="annotation-row" style="background: var(--bg-tertiary);">
<td colspan="3" id="table-annotation-left" style="text-align: right; color: var(--text-secondary); font-size: 0.8rem; font-style: italic;">Varies with N --></td>
<td colspan="3" id="table-annotation-mid" style="text-align: center; color: var(--accent-blue); font-size: 0.85rem;">O(N/t) query, O(entry) response</td>
<td id="table-annotation-right" style="text-align: center; color: var(--accent-orange); font-size: 0.8rem; font-style: italic;">O(log N)</td>
</tr>
</thead>
<tbody id="comparison-table-body">
<tr>
<td>32 KB</td>
<td>1,024</td>
<td>1</td>
<td class="same" data-query>192 KB</td>
<td class="same" data-response>32 KB</td>
<td class="same" data-total>224 KB</td>
<td class="varies">~1 ms</td>
</tr>
<tr>
<td>2 MB</td>
<td>65,536</td>
<td>32</td>
<td class="same" data-query>192 KB</td>
<td class="same" data-response>32 KB</td>
<td class="same" data-total>224 KB</td>
<td class="varies">~1.5 ms</td>
</tr>
<tr>
<td>32 MB</td>
<td>1,048,576</td>
<td>512</td>
<td class="same" data-query>192 KB</td>
<td class="same" data-response>32 KB</td>
<td class="same" data-total>224 KB</td>
<td class="varies">~3 ms</td>
</tr>
<tr>
<td>3.2 GB</td>
<td>100,000,000</td>
<td>48,829</td>
<td class="same" data-query>192 KB</td>
<td class="same" data-response>32 KB</td>
<td class="same" data-total>224 KB</td>
<td class="varies">~3 ms</td>
</tr>
<tr>
<td style="color: var(--accent-purple);">73 GB (Ethereum)</td>
<td>2,400,000,000</td>
<td>1,171,875</td>
<td class="same" data-query>192 KB</td>
<td class="same" data-response>32 KB</td>
<td class="same" data-total>224 KB</td>
<td class="varies">~3 ms</td>
</tr>
</tbody>
</table>
<div style="margin-top: 1.5rem;">
<h3 style="color: var(--accent-purple); font-size: 1rem; margin-bottom: 0.75rem;">All Variants Summary (d=2048, 32-byte entries)</h3>
<table class="comparison-table" style="font-size: 0.9rem;">
<thead>
<tr>
<th>Variant</th>
<th>Query</th>
<th>Response</th>
<th>Total</th>
<th>Reduction</th>
<th>Notes</th>
</tr>
</thead>
<tbody>
<tr>
<td style="font-weight: 600;">InsPIRe^0</td>
<td>192 KB</td>
<td>545 KB</td>
<td style="color: var(--text-secondary);">737 KB</td>
<td>baseline</td>
<td style="font-size: 0.8rem; color: var(--text-secondary);">Full query + unpacked</td>
</tr>
<tr>
<td style="font-weight: 600; color: var(--accent-blue);">InsPIRe^1</td>
<td>192 KB</td>
<td style="color: var(--accent-green);">32 KB</td>
<td style="color: var(--accent-blue);">224 KB</td>
<td style="color: var(--accent-green);">3.3x</td>
<td style="font-size: 0.8rem; color: var(--text-secondary);">Packed response</td>
</tr>
<tr>
<td style="font-weight: 600; color: var(--accent-green);">InsPIRe^2</td>
<td style="color: var(--accent-green);">96 KB</td>
<td style="color: var(--accent-green);">32 KB</td>
<td style="color: var(--accent-green);">128 KB</td>
<td style="color: var(--accent-green);">5.7x</td>
<td style="font-size: 0.8rem; color: var(--text-secondary);">Seeded + packed</td>
</tr>
</tbody>
</table>
</div>
</div>
<div class="section" style="margin-top: 3rem;">
<h2 style="color: var(--accent-orange);">Appendix: Lattice Cryptography Foundations</h2>
<p style="color: var(--text-secondary); margin-bottom: 1.5rem;">
InsPIRe's security is based on the hardness of lattice problems. These visualizations explain the core concepts.
</p>
<div style="margin-bottom: 2rem;">
<h3 style="color: var(--accent-blue); font-size: 1rem; margin-bottom: 0.5rem;">A.1 Lattice Basics & Shortest Vector Problem</h3>
<p style="color: var(--text-secondary); font-size: 0.85rem; margin-bottom: 0.5rem;">
A lattice is a regular grid of points. Security comes from the hardness of finding short vectors.
</p>
<svg id="lattice-svg" viewBox="0 0 900 350" role="img" aria-labelledby="lattice-title" aria-describedby="lattice-desc">
<title id="lattice-title">2D Lattice visualization showing basis vectors and the Shortest Vector Problem</title>
<desc id="lattice-desc">Interactive 2D lattice grid showing basis vectors and demonstrating the Shortest Vector Problem which underlies lattice-based cryptography security.</desc>
</svg>
<div style="display: flex; gap: 1rem; margin-top: 0.5rem; flex-wrap: wrap;">
<button id="toggle-basis-btn" style="background: var(--accent-blue); color: white; border: none; padding: 0.4rem 1rem; border-radius: 4px; cursor: pointer; font-size: 0.85rem;">
Toggle Good/Bad Basis
</button>
<button id="show-svp-btn" style="background: var(--accent-green); color: white; border: none; padding: 0.4rem 1rem; border-radius: 4px; cursor: pointer; font-size: 0.85rem;">
Highlight Shortest Vector
</button>
</div>
</div>
<div style="margin-bottom: 2rem;">
<h3 style="color: var(--accent-green); font-size: 1rem; margin-bottom: 0.5rem;">A.2 RLWE Error Distribution</h3>
<p style="color: var(--text-secondary); font-size: 0.85rem; margin-bottom: 0.5rem;">
Gaussian noise hides the secret. Without noise, the problem would be easy linear algebra.
</p>
<svg id="error-svg" viewBox="0 0 900 280" role="img" aria-labelledby="error-title" aria-describedby="error-desc">
<title id="error-title">Discrete Gaussian Error Distribution histogram with adjustable sigma parameter</title>
<desc id="error-desc">Histogram showing the discrete Gaussian distribution used for RLWE noise. The sigma parameter controls the spread of the distribution.</desc>
</svg>
<div style="display: flex; gap: 1rem; align-items: center; margin-top: 0.5rem;">
<label style="color: var(--text-secondary); font-size: 0.85rem;">
Noise σ: <span id="sigma-value">6.4</span>
</label>
<input type="range" id="sigma-slider" min="1" max="10" step="0.5" value="6.4"
style="width: 150px;">
<button id="sample-error-btn" style="background: var(--accent-green); color: white; border: none; padding: 0.4rem 1rem; border-radius: 4px; cursor: pointer; font-size: 0.85rem;">
Sample New Errors
</button>
</div>
</div>
<div>
<h3 style="color: var(--accent-purple); font-size: 1rem; margin-bottom: 0.5rem;">A.3 Polynomial Ring Structure</h3>
<p style="color: var(--text-secondary); font-size: 0.85rem; margin-bottom: 0.5rem;">
R_q = Z_q[X]/(X^d + 1): Polynomials with cyclic structure. Multiplication by X rotates coefficients.
</p>
<svg id="ring-svg" viewBox="0 0 900 320" role="img" aria-labelledby="ring-title" aria-describedby="ring-desc">
<title id="ring-title">Polynomial Ring Structure showing cyclic coefficient rotation when multiplying by X</title>
<desc id="ring-desc">Interactive visualization of the polynomial ring R_q showing how multiplication by X causes cyclic rotation of coefficients with sign change.</desc>
</svg>
<div style="display: flex; gap: 1rem; margin-top: 0.5rem;">
<button id="rotate-ring-btn" style="background: var(--accent-purple); color: white; border: none; padding: 0.4rem 1rem; border-radius: 4px; cursor: pointer; font-size: 0.85rem;">
Multiply by X (Rotate)
</button>
<button id="reset-ring-btn" style="background: var(--bg-tertiary); color: var(--text-secondary); border: 1px solid var(--border-color); padding: 0.4rem 1rem; border-radius: 4px; cursor: pointer; font-size: 0.85rem;">
Reset
</button>
</div>
</div>
</div>
<div class="footer">
<p>
InsPIRe: Communication-Efficient PIR with Server-side Preprocessing |
<a href="https://github.com/igor53627/inspire-rs">GitHub</a> |
<a href="COMMUNICATION_COSTS.md">Full Analysis</a>
</p>
</div>
</div>
<script>
const COLORS = {
bgPrimary: '#0d1117',
bgSecondary: '#161b22',
bgTertiary: '#21262d',
textPrimary: '#e6edf3',
textSecondary: '#8b949e',
textMuted: '#6e7681',
blue: '#58a6ff',
green: '#3fb950',
purple: '#a371f7',
orange: '#d29922',
red: '#ff6b6b',
yellow: '#ffd93d',
border: '#30363d'
};
const prefersReducedMotion = window.matchMedia('(prefers-reduced-motion: reduce)').matches;
const getAnimDuration = (ms) => prefersReducedMotion ? 0 : ms;
function initSharedDefs() {
const defsSvg = d3.select("body").append("svg")
.attr("width", 0).attr("height", 0)
.style("position", "absolute");
const defs = defsSvg.append("defs");
const markerColors = {
'blue': COLORS.blue,
'green': COLORS.green,
'purple': COLORS.purple,
'orange': COLORS.orange,
'red': COLORS.red,
'yellow': COLORS.yellow
};
Object.entries(markerColors).forEach(([name, color]) => {
defs.append("marker")
.attr("id", `arrow-${name}`)
.attr("markerWidth", 10)
.attr("markerHeight", 7)
.attr("refX", 9)
.attr("refY", 3.5)
.attr("orient", "auto")
.append("polygon")
.attr("points", "0 0, 10 3.5, 0 7")
.attr("fill", color);
});
}
initSharedDefs();
const flowSvg = d3.select("#flow-svg");
const flowWidth = 900;
const flowHeight = 320;
const entities = [
{ id: "client", label: "Client", x: 120, color: COLORS.blue },
{ id: "server", label: "Server", x: 780, color: COLORS.green }
];
entities.forEach(e => {
flowSvg.append("rect")
.attr("x", e.x - 50)
.attr("y", 20)
.attr("width", 100)
.attr("height", 40)
.attr("rx", 6)
.attr("fill", e.color)
.attr("opacity", 0.2)
.attr("stroke", e.color)
.attr("stroke-width", 2);
flowSvg.append("text")
.attr("x", e.x)
.attr("y", 46)
.attr("text-anchor", "middle")
.attr("fill", e.color)
.attr("font-weight", "bold")
.attr("font-size", "14px")
.text(e.label);
flowSvg.append("line")
.attr("x1", e.x)
.attr("y1", 70)
.attr("x2", e.x)
.attr("y2", 300)
.attr("stroke", COLORS.border)
.attr("stroke-width", 2)
.attr("stroke-dasharray", "6,4");
});
const flowVariantData = {
"inspire0": {
steps: [
{ id: "step1", fromX: 120, toX: 780, y: 100,
label: "Upload: Keys (86 KB) + Query (128 KB)", sublabel: "LWE indicator, no RGSW",
color: COLORS.blue, arrow: "right" },
{ id: "step2", fromX: 780, toX: 780, y: 160,
label: "Process: Two-level LWE PIR", sublabel: "DoublePIR + InspiRING packing",
color: COLORS.purple, arrow: "none", isBox: true },
{ id: "step3", fromX: 780, toX: 120, y: 220,
label: "Download: RLWE(packed)", sublabel: "32 KB",
color: COLORS.green, arrow: "left" },
{ id: "step4", fromX: 120, toX: 120, y: 280,
label: "Extract: Decrypt packed result", sublabel: "32 bytes result",
color: COLORS.orange, arrow: "none", isBox: true }
]
},
"inspire1": {
steps: [
{ id: "step1", fromX: 120, toX: 780, y: 100,
label: "Upload: Keys (86 KB) + Query (192 KB)", sublabel: "LWE indicator + RGSW(X^(-k))",
color: COLORS.blue, arrow: "right" },
{ id: "step2", fromX: 780, toX: 780, y: 160,
label: "Process + Pack (InspiRING)", sublabel: "External product + 2-matrix packing",
color: COLORS.purple, arrow: "none", isBox: true },
{ id: "step3", fromX: 780, toX: 120, y: 220,
label: "Download: RLWE(packed)", sublabel: "32 KB",
color: COLORS.green, arrow: "left" },
{ id: "step4", fromX: 120, toX: 120, y: 280,
label: "Extract: Decrypt packed result", sublabel: "32 bytes result",
color: COLORS.orange, arrow: "none", isBox: true }
]
},
"inspire2": {
steps: [
{ id: "step1", fromX: 120, toX: 780, y: 100,
label: "Upload: Keys (86 KB) + Query (96 KB)", sublabel: "LWE indicator, no RGSW",
color: COLORS.blue, arrow: "right" },
{ id: "step2", fromX: 780, toX: 780, y: 160,
label: "Process + PartialInspiRING", sublabel: "Two-stage packing",
color: COLORS.purple, arrow: "none", isBox: true },
{ id: "step3", fromX: 780, toX: 120, y: 220,
label: "Download: RLWE(packed)", sublabel: "32 KB",
color: COLORS.green, arrow: "left" },
{ id: "step4", fromX: 120, toX: 120, y: 280,
label: "Extract: Decrypt packed result", sublabel: "32 bytes result",
color: COLORS.orange, arrow: "none", isBox: true }
]
},
};
let currentFlowVariant = "inspire1";
let steps = flowVariantData[currentFlowVariant].steps;
steps.forEach((step, i) => {
const g = flowSvg.append("g")
.attr("class", "flow-step")
.attr("id", step.id)
.attr("opacity", 0);
if (step.isBox) {
g.append("rect")
.attr("x", step.fromX - 80)
.attr("y", step.y - 18)
.attr("width", 160)
.attr("height", 36)
.attr("rx", 4)
.attr("fill", step.color)
.attr("opacity", 0.15)
.attr("stroke", step.color);
g.append("text")
.attr("x", step.fromX)
.attr("y", step.y - 2)
.attr("text-anchor", "middle")
.attr("fill", step.color)
.attr("font-size", "12px")
.attr("font-weight", "bold")
.text(step.label);
g.append("text")
.attr("x", step.fromX)
.attr("y", step.y + 12)
.attr("text-anchor", "middle")
.attr("fill", COLORS.textSecondary)
.attr("font-size", "11px")
.text(step.sublabel);
} else {
const midX = (step.fromX + step.toX) / 2;
const markerName = step.color === COLORS.blue ? 'blue' :
step.color === COLORS.green ? 'green' : 'purple';
g.append("line")
.attr("class", "arrow-line")
.attr("x1", step.fromX)
.attr("y1", step.y)
.attr("x2", step.fromX)
.attr("y2", step.y)
.attr("stroke", step.color)
.attr("stroke-width", 2)
.attr("marker-end", `url(#arrow-${markerName})`);
g.append("text")
.attr("x", midX)
.attr("y", step.y - 12)
.attr("text-anchor", "middle")
.attr("fill", step.color)
.attr("font-size", "12px")
.attr("font-weight", "bold")
.text(step.label);
g.append("text")
.attr("x", midX)
.attr("y", step.y + 18)
.attr("text-anchor", "middle")
.attr("fill", COLORS.textSecondary)
.attr("font-size", "11px")
.text(step.sublabel);
}
});
let animationRunning = false;
let animationTimers = [];
function playAnimation() {
if (animationRunning) return;
animationRunning = true;
document.getElementById("play-btn").disabled = true;
animationTimers.forEach(id => clearTimeout(id));
animationTimers = [];
flowSvg.selectAll(".flow-step").attr("opacity", 0);
flowSvg.selectAll(".arrow-line").attr("x2", function() {
return d3.select(this).attr("x1");
});
steps.forEach((step, i) => {
const delay = i * 800;
const timerId = setTimeout(() => {
const g = flowSvg.select(`#${step.id}`);
g.transition().duration(getAnimDuration(300)).attr("opacity", 1);
if (!step.isBox) {
g.select(".arrow-line")
.transition()
.duration(getAnimDuration(400))
.attr("x2", step.toX);
}
}, delay);
animationTimers.push(timerId);
});
const finalTimerId = setTimeout(() => {
animationRunning = false;
document.getElementById("play-btn").disabled = false;
}, steps.length * 800 + 500);
animationTimers.push(finalTimerId);
}
function resetAnimation() {
animationTimers.forEach(id => clearTimeout(id));
animationTimers = [];
flowSvg.selectAll(".flow-step").attr("opacity", 0);
flowSvg.selectAll(".arrow-line").attr("x2", function() {
return d3.select(this).attr("x1");
});
animationRunning = false;
document.getElementById("play-btn").disabled = false;
}
document.getElementById("play-btn").addEventListener("click", playAnimation);
document.getElementById("reset-btn").addEventListener("click", resetAnimation);
function rebuildFlowDiagram(variant) {
animationTimers.forEach(id => clearTimeout(id));
animationTimers = [];
animationRunning = false;
document.getElementById("play-btn").disabled = false;
flowSvg.selectAll(".flow-step").remove();
currentFlowVariant = variant;
steps = flowVariantData[variant].steps;
steps.forEach((step, i) => {
const g = flowSvg.append("g")
.attr("class", "flow-step")
.attr("id", step.id)
.attr("opacity", 0);
if (step.isBox) {
g.append("rect")
.attr("x", step.fromX - 100)
.attr("y", step.y - 18)
.attr("width", 200)
.attr("height", 36)
.attr("rx", 4)
.attr("fill", step.color)
.attr("opacity", 0.15)
.attr("stroke", step.color);
g.append("text")
.attr("x", step.fromX)
.attr("y", step.y - 2)
.attr("text-anchor", "middle")
.attr("fill", step.color)
.attr("font-size", "12px")
.attr("font-weight", "bold")
.text(step.label);
g.append("text")
.attr("x", step.fromX)
.attr("y", step.y + 12)
.attr("text-anchor", "middle")
.attr("fill", COLORS.textSecondary)
.attr("font-size", "11px")
.text(step.sublabel);
} else {
const midX = (step.fromX + step.toX) / 2;
const markerName = step.color === COLORS.blue ? 'blue' :
step.color === COLORS.green ? 'green' : 'purple';
g.append("line")
.attr("class", "arrow-line")
.attr("x1", step.fromX)
.attr("y1", step.y)
.attr("x2", step.fromX)
.attr("y2", step.y)
.attr("stroke", step.color)
.attr("stroke-width", 2)
.attr("marker-end", `url(#arrow-${markerName})`);
g.append("text")
.attr("x", midX)
.attr("y", step.y - 12)
.attr("text-anchor", "middle")
.attr("fill", step.color)
.attr("font-size", "12px")
.attr("font-weight", "bold")
.text(step.label);
g.append("text")
.attr("x", midX)
.attr("y", step.y + 18)
.attr("text-anchor", "middle")
.attr("fill", COLORS.textSecondary)
.attr("font-size", "11px")
.text(step.sublabel);
}
});
setTimeout(playAnimation, 200);
}
document.querySelectorAll("#flow-variant-toggle button").forEach(btn => {
btn.addEventListener("click", () => {
document.querySelectorAll("#flow-variant-toggle button").forEach(b => b.classList.remove("active"));
btn.classList.add("active");
const variant = btn.dataset.variant;
rebuildFlowDiagram(variant);
});
});
let currentModel = "paper";
function setModel(model) {
currentModel = model;
document.querySelectorAll("#model-toggle button").forEach(b => b.classList.remove("active"));
const activeBtn = document.querySelector(`#model-toggle button[data-model="${model}"]`);
if (activeBtn) {
activeBtn.classList.add("active");
}
document.querySelectorAll(".model-copy").forEach(el => {
el.style.display = el.dataset.model === model ? "block" : "none";
});
const sizesNote = document.getElementById("model-note-sizes");
const tableNote = document.getElementById("model-note-table");
const tableKeyText = document.getElementById("table-key-text");
if (model === "paper") {
if (sizesNote) {
sizesNote.textContent = "Paper model: query breakdown includes the LWE indicator vector, which scales with N/t.";
}
if (tableNote) {
tableNote.textContent = "Paper model: query grows with N/t; totals increase with database size.";
}
if (tableKeyText) {
tableKeyText.textContent = "Query size scales with N/t (indicator vector length). Response size scales with entry size. For a fixed database, all queries use the same communication regardless of which entry is requested.";
}
} else {
if (sizesNote) {
sizesNote.textContent = "Implementation: query is RGSW-only (seeded/switched variants) and does not include an LWE indicator; size is fixed by (d, ell).";
}
if (tableNote) {
tableNote.textContent = "Implementation: query/total are constant for fixed parameters; shard_id is sent in the clear (privacy is within a shard).";
}
if (tableKeyText) {
tableKeyText.textContent = "Implementation view: query size is constant for fixed parameters; response size scales with entry size; DB growth is via sharding.";
}
}
updateComparisonTable();
}
document.querySelectorAll("#model-toggle button").forEach(btn => {
btn.addEventListener("click", () => {
setModel(btn.dataset.model);
});
});
setTimeout(playAnimation, 500);
const formatData = {
"inspire0": {
name: "InsPIRe_0 (DoublePIR-based)",
description: "Two-level LWE PIR with ring packing (no RGSW in query)",
keys: [
{ name: "Packing keys (KS matrices)", size: 86, formula: "2 * d * l_ks * log2(q) / 8 = 2 * 2048 * 3 * 56 / 8" }
],
query: [
{ name: "LWE indicator vector", size: 128, formula: "(N/t) * log2(q) / 8 = indicator for column selection" }
],
response: [
{ name: "Packed RLWE ciphertext", size: 32, formula: "2 * d * log2(q) / 8 = 32 KB" }
],
totalKeys: 86,
totalQuery: 128,
totalResponse: 32
},
"inspire1": {
name: "InsPIRe (RGSW-based)",
description: "LWE indicator + RGSW ciphertext + InspiRING packing",
keys: [
{ name: "Packing keys (KS matrices)", size: 86, formula: "2 * d * l_ks * log2(q) / 8 = 2 * 2048 * 3 * 56 / 8" }
],
query: [
{ name: "LWE indicator vector", size: 64, formula: "(N/t) * log2(q) / 8 = indicator for column selection" },
{ name: "RGSW ciphertext", size: 128, formula: "4 * l_gsw * d * log2(q) / 8 = encrypted evaluation point" }
],
response: [
{ name: "1 packed RLWE", size: 32, formula: "2 * d * log2(q) / 8 = 32 KB" }
],
totalKeys: 86,
totalQuery: 192,
totalResponse: 32
},
"inspire2": {
name: "InsPIRe^(2) (Two-level packing)",
description: "LWE indicator query + PartialInspiRING two-stage packing (no RGSW)",
keys: [
{ name: "Packing keys (KS matrices)", size: 86, formula: "2 * d * l_ks * log2(q) / 8 = 2 * 2048 * 3 * 56 / 8" }
],
query: [
{ name: "LWE indicator vector", size: 96, formula: "(N/t) * log2(q) / 8 = indicator for column selection" }
],
response: [
{ name: "1 packed RLWE", size: 32, formula: "2 * d * log2(q) / 8 = 32 KB" }
],
totalKeys: 86,
totalQuery: 96,
totalResponse: 32
}
};
let currentFormat = "inspire1";
const tooltip = d3.select("#tooltip");
let chartTooltipRafId = null;
function throttledTooltipMove(event) {
if (!chartTooltipRafId) {
chartTooltipRafId = requestAnimationFrame(() => {
tooltip
.style("left", (event.pageX + 15) + "px")
.style("top", (event.pageY - 10) + "px");
chartTooltipRafId = null;
});
}
}
function drawChart(svgId, data, title, color) {
const svg = d3.select(svgId);
svg.selectAll("*").remove();
const width = 420;
const height = 280;
const margin = { top: 50, right: 40, bottom: 40, left: 140 };
const chartWidth = width - margin.left - margin.right;
const chartHeight = height - margin.top - margin.bottom;
const g = svg.append("g")
.attr("transform", `translate(${margin.left},${margin.top})`);
svg.append("text")
.attr("x", width / 2)
.attr("y", 25)
.attr("text-anchor", "middle")
.attr("fill", color)
.attr("font-weight", "bold")
.attr("font-size", "14px")
.text(title);
const total = data.reduce((sum, d) => sum + d.size, 0);
const x = d3.scaleLinear()
.domain([0, d3.max(data, d => d.size) * 1.1])
.range([0, chartWidth]);
const y = d3.scaleBand()
.domain(data.map(d => d.name))
.range([0, chartHeight])
.padding(0.3);
g.selectAll(".bar")
.data(data)
.join("rect")
.attr("class", "bar")
.attr("tabindex", "0")
.attr("aria-label", d => `${d.name}: ${d.size.toFixed(1)} KB (${((d.size / total) * 100).toFixed(1)}%)`)
.attr("x", 0)
.attr("y", d => y(d.name))
.attr("width", d => x(d.size))
.attr("height", y.bandwidth())
.attr("fill", color)
.attr("opacity", 0.7)
.attr("rx", 3)
.on("mouseenter focus", function(event, d) {
d3.select(this).attr("opacity", 1);
tooltip.classed("visible", true)
.html(`
<div class="label">${d.name}</div>
<div class="value">${d.size.toFixed(1)} KB (${((d.size / total) * 100).toFixed(1)}%)</div>
<div class="formula">${d.formula}</div>
`);
if (event.type === "focus") {
const rect = this.getBoundingClientRect();
tooltip.style("left", (rect.right + 10) + "px")
.style("top", (rect.top + window.scrollY) + "px");
}
})
.on("mousemove", throttledTooltipMove)
.on("mouseleave blur", function() {
d3.select(this).attr("opacity", 0.7);
tooltip.classed("visible", false);
});
g.selectAll(".label")
.data(data)
.join("text")
.attr("x", d => x(d.size) + 5)
.attr("y", d => y(d.name) + y.bandwidth() / 2 + 4)
.attr("fill", COLORS.textPrimary)
.attr("font-size", "11px")
.text(d => d.size >= 1 ? `${d.size.toFixed(0)} KB` : `${(d.size * 1024).toFixed(0)} B`);
g.append("g")
.call(d3.axisLeft(y).tickSize(0))
.select(".domain").remove();
g.selectAll(".tick text")
.attr("fill", COLORS.textSecondary)
.attr("font-size", "11px");
svg.append("text")
.attr("x", width / 2)
.attr("y", height - 10)
.attr("text-anchor", "middle")
.attr("fill", COLORS.textSecondary)
.attr("font-size", "12px")
.text(`Total: ${total.toFixed(0)} KB`);
const formulaText = title.includes("Query")
? "Formula: 2l × d × 8 bytes"
: "Formula: cols × 2 × d × 8 bytes";
svg.append("text")
.attr("x", width / 2)
.attr("y", 42)
.attr("text-anchor", "middle")
.attr("fill", COLORS.textSecondary)
.attr("font-size", "10px")
.attr("font-family", "monospace")
.text(formulaText);
}
function updateCharts() {
const data = formatData[currentFormat];
drawChart("#keys-chart", data.keys, "Upload Keys", COLORS.orange);
drawChart("#query-chart", data.query, "Upload Query", COLORS.blue);
drawChart("#response-chart", data.response, "Download", COLORS.green);
}
document.querySelectorAll(".format-toggle button").forEach((btn, index, buttons) => {
btn.setAttribute("role", "tab");
btn.setAttribute("aria-selected", btn.classList.contains("active") ? "true" : "false");
btn.setAttribute("tabindex", btn.classList.contains("active") ? "0" : "-1");
btn.addEventListener("click", function() {
document.querySelectorAll(".format-toggle button").forEach(b => {
b.classList.remove("active");
b.setAttribute("aria-selected", "false");
b.setAttribute("tabindex", "-1");
});
this.classList.add("active");
this.setAttribute("aria-selected", "true");
this.setAttribute("tabindex", "0");
currentFormat = this.dataset.format;
updateCharts();
calculateSizes();
});
btn.addEventListener("keydown", function(e) {
let targetIndex = index;
if (e.key === "ArrowRight" || e.key === "ArrowDown") {
targetIndex = (index + 1) % buttons.length;
e.preventDefault();
} else if (e.key === "ArrowLeft" || e.key === "ArrowUp") {
targetIndex = (index - 1 + buttons.length) % buttons.length;
e.preventDefault();
} else if (e.key === "Enter" || e.key === " ") {
this.click();
e.preventDefault();
return;
}
if (targetIndex !== index) {
buttons[targetIndex].click();
buttons[targetIndex].focus();
}
});
});
updateCharts();
const dValues = [1024, 2048, 4096];
const entryValues = [32, 64, 128];
const pModulus = 65536;
function calculateSizes() {
const dIndex = parseInt(document.getElementById("d-slider").value);
const entryIndex = parseInt(document.getElementById("entry-slider").value);
const gadgetLen = parseInt(document.getElementById("gadget-slider").value);
const d = dValues[dIndex];
const entrySize = entryValues[entryIndex];
document.getElementById("d-value").textContent = d;
document.getElementById("entry-value").textContent = `${entrySize} bytes`;
document.getElementById("gadget-value").textContent = gadgetLen;
const numColumns = Math.floor((entrySize * 8 + 15) / 16);
const singleRlweSize = (2 * d * 8) / 1024; const unpackedResponseSize = (numColumns * 2 * d * 8) / 1024;
let querySize, queryFormula, queryLabel;
let responseSize, responseFormula, responseLabel;
switch (currentFormat) {
case "inspire0": const indicatorSize0 = (numColumns * 8) + (d * gadgetLen * 8); querySize = indicatorSize0 / 1024;
queryLabel = "Query Size (LWE indicator + keys)";
queryFormula = `(N/t)*log2(q)/8 + d*l_ks*log2(q)/8 = ${indicatorSize0} bytes`;
responseSize = singleRlweSize;
responseLabel = "Response Size (packed)";
responseFormula = `1 RLWE = 2 * ${d} * 8 = ${2 * d * 8} bytes`;
break;
case "inspire1": const indicatorSize1 = numColumns * 8; const rgswSize = 4 * gadgetLen * d * 8; querySize = (indicatorSize1 + rgswSize) / 1024;
queryLabel = "Query Size (indicator + RGSW)";
queryFormula = `(N/t)*log2(q)/8 + 4*l_gsw*d*log2(q)/8 = ${indicatorSize1 + rgswSize} bytes`;
responseSize = singleRlweSize;
responseLabel = "Response Size (packed)";
responseFormula = `1 RLWE = 2 * ${d} * 8 = ${2 * d * 8} bytes`;
break;
case "inspire2": const indicatorSize2 = numColumns * 8; querySize = indicatorSize2 / 1024;
queryLabel = "Query Size (LWE indicator)";
queryFormula = `(N/t)*log2(q)/8 = ${indicatorSize2} bytes`;
responseSize = singleRlweSize;
responseLabel = "Response Size (packed)";
responseFormula = `1 RLWE = 2 * ${d} * 8 = ${2 * d * 8} bytes`;
break;
default: const defIndicator = numColumns * 8;
const defRgsw = 4 * gadgetLen * d * 8;
querySize = (defIndicator + defRgsw) / 1024;
queryLabel = "Query Size (indicator + RGSW)";
queryFormula = `(N/t)*log2(q)/8 + 4*l_gsw*d*log2(q)/8 = ${defIndicator + defRgsw} bytes`;
responseSize = singleRlweSize;
responseLabel = "Response Size (packed)";
responseFormula = `1 RLWE = 2 * ${d} * 8 = ${2 * d * 8} bytes`;
}
const totalSize = querySize + responseSize;
document.getElementById("calc-query").textContent = `${querySize.toFixed(0)} KB`;
document.getElementById("calc-response").textContent = `${responseSize.toFixed(0)} KB`;
document.getElementById("calc-total").textContent = `${totalSize.toFixed(0)} KB`;
document.querySelector(".size-card.query .size-label").textContent = queryLabel;
document.querySelector(".size-card.response .size-label").textContent = responseLabel;
const variantNames = {
"inspire0": "InsPIRe^0",
"inspire1": "InsPIRe^1",
"inspire2": "InsPIRe^2"
};
document.getElementById("variant-indicator").textContent = `(${variantNames[currentFormat] || currentFormat})`;
document.getElementById("query-formula").textContent = queryFormula;
document.getElementById("response-formula").textContent = responseFormula;
}
document.getElementById("d-slider").addEventListener("input", calculateSizes);
document.getElementById("entry-slider").addEventListener("input", calculateSizes);
document.getElementById("gadget-slider").addEventListener("input", calculateSizes);
calculateSizes();
const tableVariantSizes = {
"inspire0": { keys: 86, query: 128, response: 32, queryLabel: "LWE indicator", responseLabel: "packed" },
"inspire1": { keys: 86, query: 192, response: 32, queryLabel: "indicator+RGSW", responseLabel: "packed" },
"inspire2": { keys: 86, query: 96, response: 32, queryLabel: "seeded+packed", responseLabel: "packed" }
};
let currentTableVariant = "inspire1";
function updateComparisonTable() {
const sizes = tableVariantSizes[currentTableVariant];
const total = sizes.keys + sizes.query + sizes.response;
if (currentModel === "paper") {
document.querySelectorAll("[data-query]").forEach(cell => {
cell.textContent = "O(N/t)";
cell.classList.remove("same");
cell.classList.add("varies");
});
document.querySelectorAll("[data-response]").forEach(cell => {
cell.textContent = `${sizes.response} KB`;
cell.classList.remove("varies");
cell.classList.add("same");
});
document.querySelectorAll("[data-total]").forEach(cell => {
cell.textContent = "O(N/t)";
cell.classList.remove("same");
cell.classList.add("varies");
});
document.getElementById("table-query-header").textContent = "Upload (keys + indicator)";
document.getElementById("table-response-header").textContent = `Download (${sizes.responseLabel})`;
const left = document.getElementById("table-annotation-left");
const mid = document.getElementById("table-annotation-mid");
const right = document.getElementById("table-annotation-right");
if (left) left.textContent = "Varies with N -->";
if (mid) mid.textContent = "O(N/t) query, O(entry) response";
if (right) right.textContent = "O(log N)";
} else {
document.querySelectorAll("[data-query]").forEach(cell => {
cell.textContent = `${sizes.keys + sizes.query} KB`;
cell.classList.remove("varies");
cell.classList.add("same");
});
document.querySelectorAll("[data-response]").forEach(cell => {
cell.textContent = `${sizes.response} KB`;
cell.classList.remove("varies");
cell.classList.add("same");
});
document.querySelectorAll("[data-total]").forEach(cell => {
cell.textContent = `${total} KB`;
cell.classList.remove("varies");
cell.classList.add("same");
});
document.getElementById("table-query-header").textContent = `Upload (keys+${sizes.queryLabel})`;
document.getElementById("table-response-header").textContent = `Download (${sizes.responseLabel})`;
const left = document.getElementById("table-annotation-left");
const mid = document.getElementById("table-annotation-mid");
const right = document.getElementById("table-annotation-right");
if (left) left.textContent = "Fixed params -->";
if (mid) mid.textContent = "Constant query, O(entry) response";
if (right) right.textContent = "Shard lookup";
}
}
document.querySelectorAll("#table-variant-toggle button").forEach(btn => {
btn.addEventListener("click", function() {
document.querySelectorAll("#table-variant-toggle button").forEach(b => {
b.classList.remove("active");
});
this.classList.add("active");
currentTableVariant = this.dataset.variant;
updateComparisonTable();
});
});
setModel(currentModel);
const cryptoTooltipEl = document.getElementById("crypto-tooltip");
const cryptoTooltipData = {
"external_product": {
title: "External Product (⊡)",
desc: "Homomorphic multiplication between RLWE and RGSW ciphertexts. Computes RLWE(m₁ · m₂) from RLWE(m₁) and RGSW(m₂) without decrypting.",
detail: "Uses gadget decomposition to keep noise growth small."
},
"rlwe": {
title: "RLWE(h_i) — Database Polynomial",
desc: "Ring-LWE encryption of polynomial h_i(X). The polynomial stores database values as coefficients: h_i(X) = y₀ + y₁X + y₂X² + ...",
detail: "Ciphertext: (a, b) where b = -a·s + e + Δ·m"
},
"rgsw": {
title: "RGSW(X^{-k}) — Query Selector",
desc: "Ring-GSW encryption of the inverse monomial X^{-k}. This is the 'selector' that rotates coefficient k to position 0 when multiplied.",
detail: "Structure: 2ℓ RLWE rows encoding m·[1, z, z², ...]"
},
"result": {
title: "Why This Works",
desc: "h_i(X) · X^{-k} rotates all coefficients. The value at position k moves to position 0, which can then be extracted.",
detail: "In R_q = Z[X]/(X^d+1): X^d = -1, so X^{-k} = -X^{d-k}"
}
};
function showCryptoTooltip(event, key) {
const data = cryptoTooltipData[key];
if (!data) return;
cryptoTooltipEl.querySelector(".ct-title").textContent = data.title;
cryptoTooltipEl.querySelector(".ct-desc").textContent = data.desc;
cryptoTooltipEl.querySelector(".ct-detail").textContent = data.detail;
cryptoTooltipEl.classList.add("visible");
moveCryptoTooltip(event);
}
let tooltipRafId = null;
let pendingTooltipEvent = null;
function moveCryptoTooltip(event) {
pendingTooltipEvent = event;
if (!tooltipRafId) {
tooltipRafId = requestAnimationFrame(() => {
if (pendingTooltipEvent) {
const x = pendingTooltipEvent.clientX + 15;
const y = pendingTooltipEvent.clientY - 10;
cryptoTooltipEl.style.left = x + "px";
cryptoTooltipEl.style.top = y + "px";
}
tooltipRafId = null;
});
}
}
function hideCryptoTooltip() {
cryptoTooltipEl.classList.remove("visible");
if (tooltipRafId) {
cancelAnimationFrame(tooltipRafId);
tooltipRafId = null;
}
pendingTooltipEvent = null;
}
const RING_DIM = 2048;
const NUM_COLUMNS = 16; let currentTargetShard = 0;
function drawShardSelection(numEntries) {
const svg = d3.select("#shard-svg");
svg.selectAll("*").remove();
const numShards = Math.ceil(numEntries / RING_DIM);
currentTargetShard = Math.floor(Math.random() * numShards);
const width = 900;
const height = 180;
svg.append("text")
.attr("x", 20)
.attr("y", 25)
.attr("fill", COLORS.textSecondary)
.attr("font-size", "12px")
.text(`Total: ${numShards.toLocaleString()} shards | Target shard (selected by query; may be sent as metadata): ${currentTargetShard}`);
const gridY = 45;
const gridHeight = 80;
const maxVisible = Math.min(20, numShards);
const startShard = Math.max(0, Math.min(currentTargetShard - Math.floor(maxVisible / 2), numShards - maxVisible));
const endShard = Math.min(numShards, startShard + maxVisible);
const visibleCount = endShard - startShard;
const shardWidth = Math.min(38, (width - 100) / visibleCount);
const shardGap = 3;
const gridStartX = (width - visibleCount * (shardWidth + shardGap)) / 2;
const g = svg.append("g").attr("transform", `translate(${gridStartX}, ${gridY})`);
if (startShard > 0) {
g.append("text").attr("x", -20).attr("y", gridHeight / 2 + 4)
.attr("text-anchor", "middle").attr("fill", COLORS.textSecondary).attr("font-size", "14px").text("...");
}
if (endShard < numShards) {
g.append("text").attr("x", visibleCount * (shardWidth + shardGap) + 15).attr("y", gridHeight / 2 + 4)
.attr("text-anchor", "middle").attr("fill", COLORS.textSecondary).attr("font-size", "14px").text("...");
}
for (let i = 0; i < visibleCount; i++) {
const shardId = startShard + i;
const isTarget = shardId === currentTargetShard;
const x = i * (shardWidth + shardGap);
g.append("rect")
.attr("x", x).attr("y", 0)
.attr("width", shardWidth).attr("height", gridHeight)
.attr("rx", 3)
.attr("fill", isTarget ? COLORS.blue : COLORS.bgTertiary)
.attr("stroke", isTarget ? COLORS.blue : COLORS.border)
.attr("stroke-width", isTarget ? 2 : 1)
.attr("opacity", isTarget ? 1 : 0.5);
if (shardWidth >= 22) {
g.append("text")
.attr("x", x + shardWidth / 2).attr("y", gridHeight / 2 + 4)
.attr("text-anchor", "middle")
.attr("fill", isTarget ? "#fff" : COLORS.textMuted)
.attr("font-size", "11px")
.text(shardId);
}
}
svg.append("text")
.attr("x", width / 2).attr("y", gridY + gridHeight + 25)
.attr("text-anchor", "middle").attr("fill", COLORS.blue).attr("font-size", "12px")
.text(`Selected shard #${currentTargetShard} contains ${RING_DIM} entries encoded as ${NUM_COLUMNS} polynomials`);
}
function drawPipeline() {
const svg = d3.select("#pipeline-svg");
svg.selectAll("*").remove();
const width = 900;
const height = 280;
const inputX = 60;
const inputY = 30;
const queryGroup = svg.append("g")
.style("cursor", "pointer")
.on("mouseenter", function(event) {
showCryptoTooltip(event, "rgsw");
d3.select(this).select("rect").attr("stroke-width", 2);
})
.on("mousemove", moveCryptoTooltip)
.on("mouseleave", function() {
hideCryptoTooltip();
d3.select(this).select("rect").attr("stroke-width", 1);
});
queryGroup.append("rect")
.attr("x", inputX).attr("y", inputY)
.attr("width", 120).attr("height", 60)
.attr("rx", 4)
.attr("fill", COLORS.blue).attr("opacity", 0.2)
.attr("stroke", COLORS.blue);
queryGroup.append("text")
.attr("x", inputX + 60).attr("y", inputY + 25)
.attr("text-anchor", "middle").attr("fill", COLORS.blue).attr("font-size", "12px").attr("font-weight", "bold")
.text("Query");
queryGroup.append("text")
.attr("x", inputX + 60).attr("y", inputY + 42)
.attr("text-anchor", "middle").attr("fill", COLORS.textSecondary).attr("font-size", "11px")
.text("RGSW(X^{-k})");
const polyStartX = 220;
const polyY = 20;
const polyWidth = 50;
const polyHeight = 35;
const polyGap = 8;
svg.append("text")
.attr("x", polyStartX).attr("y", polyY)
.attr("fill", COLORS.textSecondary).attr("font-size", "11px")
.text("Shard polynomials (16 columns):");
for (let i = 0; i < 8; i++) {
const x = polyStartX + i * (polyWidth + polyGap);
const polyGroup = svg.append("g")
.style("cursor", "pointer")
.on("mouseenter", function(event) {
showCryptoTooltip(event, "rlwe");
d3.select(this).select("rect").attr("stroke-width", 2);
})
.on("mousemove", moveCryptoTooltip)
.on("mouseleave", function() {
hideCryptoTooltip();
d3.select(this).select("rect").attr("stroke-width", 1);
});
polyGroup.append("rect")
.attr("class", "poly-box")
.attr("data-col", i)
.attr("x", x).attr("y", polyY + 10)
.attr("width", polyWidth).attr("height", polyHeight)
.attr("rx", 3)
.attr("fill", COLORS.bgTertiary).attr("stroke", COLORS.green);
polyGroup.append("text")
.attr("x", x + polyWidth / 2).attr("y", polyY + 32)
.attr("text-anchor", "middle").attr("fill", COLORS.green).attr("font-size", "11px")
.text(`h_${i}(X)`);
}
svg.append("text")
.attr("x", polyStartX + 8 * (polyWidth + polyGap) + 10).attr("y", polyY + 32)
.attr("fill", COLORS.textSecondary).attr("font-size", "12px")
.text("... +8 more");
const opY = 110;
const opWidth = 145;
const opHeight = 50;
const opGap = 12;
const numVisibleOps = 3;
svg.append("text")
.attr("x", 20).attr("y", opY + 10)
.attr("fill", COLORS.orange).attr("font-size", "12px").attr("font-weight", "bold")
.text("Parallel:");
for (let i = 0; i < numVisibleOps; i++) {
const x = 90 + i * (opWidth + opGap);
const opGroup = svg.append("g")
.attr("class", "op-group")
.style("cursor", "pointer")
.on("mouseenter", function(event) {
showCryptoTooltip(event, "external_product");
d3.select(this).select("rect").attr("stroke-width", 2);
})
.on("mousemove", function(event) {
moveCryptoTooltip(event);
})
.on("mouseleave", function() {
hideCryptoTooltip();
d3.select(this).select("rect").attr("stroke-width", 1);
});
opGroup.append("rect")
.attr("class", "op-box")
.attr("data-op", i)
.attr("x", x).attr("y", opY)
.attr("width", opWidth).attr("height", opHeight)
.attr("rx", 4)
.attr("fill", COLORS.bgTertiary).attr("stroke", COLORS.orange);
opGroup.append("text")
.attr("x", x + opWidth / 2).attr("y", opY + 20)
.attr("text-anchor", "middle").attr("fill", COLORS.orange).attr("font-size", "11px").attr("font-weight", "bold")
.text("ext_product");
opGroup.append("text")
.attr("x", x + opWidth / 2).attr("y", opY + 36)
.attr("text-anchor", "middle").attr("fill", COLORS.textSecondary).attr("font-size", "10px")
.attr("font-family", "monospace")
.text(`h_${i}(X) ⊡ query`);
}
const afterOpsX = 90 + numVisibleOps * (opWidth + opGap);
svg.append("text")
.attr("x", afterOpsX + 5).attr("y", opY + 30)
.attr("fill", COLORS.textSecondary).attr("font-size", "12px")
.text("...×16");
const timingBoxWidth = 120;
const timingX = afterOpsX + 60;
svg.append("rect")
.attr("x", timingX).attr("y", opY)
.attr("width", timingBoxWidth).attr("height", opHeight)
.attr("rx", 4)
.attr("fill", COLORS.bgTertiary).attr("stroke", COLORS.border);
svg.append("text")
.attr("x", timingX + timingBoxWidth / 2).attr("y", opY + 18)
.attr("text-anchor", "middle").attr("fill", COLORS.textSecondary).attr("font-size", "11px")
.text("Processing time:");
svg.append("text")
.attr("x", timingX + timingBoxWidth / 2).attr("y", opY + 36)
.attr("text-anchor", "middle").attr("fill", COLORS.green).attr("font-size", "14px").attr("font-weight", "bold")
.text("~3 ms");
const outY = 190;
const outWidth = 45;
const outHeight = 30;
svg.append("text")
.attr("x", 20).attr("y", outY + 10)
.attr("fill", COLORS.purple).attr("font-size", "12px").attr("font-weight", "bold")
.text("Output:");
for (let i = 0; i < 10; i++) {
const x = 100 + i * (outWidth + 8);
svg.append("rect")
.attr("class", "out-box")
.attr("data-out", i)
.attr("x", x).attr("y", outY)
.attr("width", outWidth).attr("height", outHeight)
.attr("rx", 3)
.attr("fill", COLORS.bgTertiary).attr("stroke", COLORS.purple);
svg.append("text")
.attr("x", x + outWidth / 2).attr("y", outY + 19)
.attr("text-anchor", "middle").attr("fill", COLORS.purple).attr("font-size", "11px")
.text(`ct_${i}`);
}
svg.append("text")
.attr("x", 100 + 10 * (outWidth + 8) + 15).attr("y", outY + 19)
.attr("fill", COLORS.textSecondary).attr("font-size", "12px")
.text("... +6");
svg.append("text")
.attr("x", width / 2).attr("y", outY + 55)
.attr("text-anchor", "middle").attr("fill", COLORS.textSecondary).attr("font-size", "11px")
.attr("font-family", "monospace")
.text("Each ct_i = RLWE(h_i(X) · X^{-k}) where coefficient 0 contains y_k's column i");
}
function drawOutput() {
const svg = d3.select("#output-svg");
svg.selectAll("*").remove();
const width = 900;
const height = 150;
const respX = 50;
const respY = 20;
svg.append("text")
.attr("x", respX).attr("y", respY)
.attr("fill", COLORS.textSecondary).attr("font-size", "12px")
.text("ServerResponse struct:");
svg.append("rect")
.attr("x", respX).attr("y", respY + 10)
.attr("width", 350).attr("height", 100)
.attr("rx", 4)
.attr("fill", COLORS.bgTertiary).attr("stroke", COLORS.purple);
svg.append("text")
.attr("x", respX + 15).attr("y", respY + 35)
.attr("fill", COLORS.purple).attr("font-size", "11px").attr("font-family", "monospace")
.text("ciphertext: RlweCiphertext");
svg.append("text")
.attr("x", respX + 200).attr("y", respY + 35)
.attr("fill", COLORS.textMuted).attr("font-size", "11px")
.text("// combined");
svg.append("text")
.attr("x", respX + 15).attr("y", respY + 55)
.attr("fill", COLORS.purple).attr("font-size", "11px").attr("font-family", "monospace")
.text("column_ciphertexts: Vec<Rlwe>");
svg.append("text")
.attr("x", respX + 230).attr("y", respY + 55)
.attr("fill", COLORS.textMuted).attr("font-size", "11px")
.text("// 16 cts");
svg.append("text")
.attr("x", respX + 15).attr("y", respY + 85)
.attr("fill", COLORS.textSecondary).attr("font-size", "11px")
.text("Size: 16 * 2 * 2048 * 8 = ");
svg.append("text")
.attr("x", respX + 170).attr("y", respY + 85)
.attr("fill", COLORS.green).attr("font-size", "12px").attr("font-weight", "bold")
.text("512 KB (binary)");
svg.append("path")
.attr("d", "M 410 70 L 480 70")
.attr("stroke", COLORS.green).attr("stroke-width", 2)
.attr("marker-end", "url(#arrow-green)");
svg.append("rect")
.attr("x", 490).attr("y", respY + 30)
.attr("width", 120).attr("height", 80)
.attr("rx", 4)
.attr("fill", COLORS.green).attr("opacity", 0.15)
.attr("stroke", COLORS.green);
svg.append("text")
.attr("x", 550).attr("y", respY + 60)
.attr("text-anchor", "middle").attr("fill", COLORS.green).attr("font-size", "12px").attr("font-weight", "bold")
.text("Send to Client");
svg.append("text")
.attr("x", 550).attr("y", respY + 80)
.attr("text-anchor", "middle").attr("fill", COLORS.textSecondary).attr("font-size", "11px")
.text("bincode/JSON");
svg.append("rect")
.attr("x", 640).attr("y", respY + 10)
.attr("width", 240).attr("height", 100)
.attr("rx", 4)
.attr("fill", COLORS.bgTertiary)
.attr("stroke", COLORS.orange);
svg.append("text")
.attr("x", 650).attr("y", respY + 32)
.attr("fill", COLORS.orange).attr("font-size", "11px").attr("font-weight", "bold")
.text("Privacy Guarantee:");
svg.append("text")
.attr("x", 650).attr("y", respY + 50)
.attr("fill", COLORS.textPrimary).attr("font-size", "11px")
.text("Response size is ALWAYS 512 KB");
svg.append("text")
.attr("x", 650).attr("y", respY + 66)
.attr("fill", COLORS.textPrimary).attr("font-size", "11px")
.text("regardless of which entry or");
svg.append("text")
.attr("x", 650).attr("y", respY + 82)
.attr("fill", COLORS.textPrimary).attr("font-size", "11px")
.text("database size was queried.");
svg.append("text")
.attr("x", 650).attr("y", respY + 98)
.attr("fill", COLORS.textMuted).attr("font-size", "11px")
.text("(prevents traffic analysis)");
}
let pipelineAnimating = false;
let pipelineTimers = [];
function animatePipeline() {
if (pipelineAnimating) return;
pipelineAnimating = true;
pipelineTimers.forEach(id => clearTimeout(id));
pipelineTimers = [];
const svg = d3.select("#pipeline-svg");
svg.selectAll(".poly-box").attr("fill", COLORS.bgTertiary);
svg.selectAll(".op-box").attr("fill", COLORS.bgTertiary);
svg.selectAll(".out-box").attr("fill", COLORS.bgTertiary);
svg.selectAll(".poly-box").each(function(d, i) {
d3.select(this)
.transition().delay(i * 80).duration(getAnimDuration(200))
.attr("fill", COLORS.green).attr("opacity", 0.5)
.transition().duration(getAnimDuration(200))
.attr("fill", COLORS.bgTertiary).attr("opacity", 1);
});
const opsTimer = setTimeout(() => {
svg.selectAll(".op-box").each(function(d, i) {
d3.select(this)
.transition().delay(i * 100).duration(getAnimDuration(300))
.attr("fill", COLORS.orange).attr("opacity", 0.4)
.transition().duration(getAnimDuration(300))
.attr("fill", COLORS.bgTertiary).attr("opacity", 1);
});
}, 700);
pipelineTimers.push(opsTimer);
const outsTimer = setTimeout(() => {
svg.selectAll(".out-box").each(function(d, i) {
d3.select(this)
.transition().delay(i * 60).duration(getAnimDuration(200))
.attr("fill", COLORS.purple).attr("opacity", 0.5)
.transition().duration(getAnimDuration(200))
.attr("fill", COLORS.bgTertiary).attr("opacity", 1);
});
}, 1400);
pipelineTimers.push(outsTimer);
const finalTimer = setTimeout(() => { pipelineAnimating = false; }, 2500);
pipelineTimers.push(finalTimer);
}
drawShardSelection(1048576);
drawPipeline();
drawOutput();
document.getElementById("db-size-select").addEventListener("change", function() {
drawShardSelection(parseInt(this.value));
});
document.getElementById("animate-pipeline-btn").addEventListener("click", animatePipeline);
const treePackSvg = d3.select("#tree-pack-svg");
let treeAnimating = false;
let treeTimers = [];
function drawTreePacking(highlightLevel = -1) {
treePackSvg.selectAll("*").remove();
const width = 900;
const height = 420;
const nodeRadius = 22;
const levelHeight = 90;
const numInputs = 8;
const levels = Math.log2(numInputs) + 1;
const nodes = [];
const edges = [];
const leafY = height - 50;
const leafSpacing = width / (numInputs + 1);
for (let i = 0; i < numInputs; i++) {
nodes.push({
id: `leaf-${i}`,
level: 0,
x: leafSpacing * (i + 1),
y: leafY,
label: `LWE${i}`,
sublabel: `m${i}`,
isLeaf: true
});
}
const level1Y = leafY - levelHeight;
const level1Spacing = width / 5;
for (let i = 0; i < 4; i++) {
const nodeId = `l1-${i}`;
nodes.push({
id: nodeId,
level: 1,
x: level1Spacing * (i + 1),
y: level1Y,
label: `RLWE`,
sublabel: `[${i*2},${i*2+1}]`,
operation: `+ y₁·`
});
edges.push({ from: `leaf-${i*2}`, to: nodeId, level: 1 });
edges.push({ from: `leaf-${i*2+1}`, to: nodeId, level: 1, isOdd: true });
}
const level2Y = level1Y - levelHeight;
const level2Spacing = width / 3;
for (let i = 0; i < 2; i++) {
const nodeId = `l2-${i}`;
nodes.push({
id: nodeId,
level: 2,
x: level2Spacing * (i + 1),
y: level2Y,
label: `RLWE`,
sublabel: `[${i*4}..${i*4+3}]`,
operation: `+ y₂·`
});
edges.push({ from: `l1-${i*2}`, to: nodeId, level: 2 });
edges.push({ from: `l1-${i*2+1}`, to: nodeId, level: 2, isOdd: true });
}
const level3Y = level2Y - levelHeight;
nodes.push({
id: `root`,
level: 3,
x: width / 2,
y: level3Y,
label: `Packed`,
sublabel: `[0..7]`,
operation: `+ y₃·`,
isRoot: true
});
edges.push({ from: `l2-0`, to: `root`, level: 3 });
edges.push({ from: `l2-1`, to: `root`, level: 3, isOdd: true });
const nodeMap = {};
nodes.forEach(n => nodeMap[n.id] = n);
edges.forEach(e => {
const from = nodeMap[e.from];
const to = nodeMap[e.to];
const isHighlighted = highlightLevel === e.level;
const isPast = highlightLevel > e.level;
treePackSvg.append("line")
.attr("x1", from.x)
.attr("y1", from.y - nodeRadius)
.attr("x2", to.x)
.attr("y2", to.y + nodeRadius)
.attr("stroke", e.isOdd ? COLORS.orange : COLORS.blue)
.attr("stroke-width", isHighlighted ? 3 : 2)
.attr("opacity", highlightLevel === -1 ? 0.6 : (isHighlighted ? 1 : (isPast ? 0.8 : 0.2)))
.attr("stroke-dasharray", e.isOdd ? "5,3" : "none");
});
if (highlightLevel >= 1) {
const yLabels = [
{ level: 1, y: (leafY + level1Y) / 2, text: "×X^(d/2)" },
{ level: 2, y: (level1Y + level2Y) / 2, text: "×X^(d/4)" },
{ level: 3, y: (level2Y + level3Y) / 2, text: "×X^(d/8)" }
];
yLabels.forEach(yl => {
if (highlightLevel >= yl.level) {
treePackSvg.append("text")
.attr("x", width - 80)
.attr("y", yl.y)
.attr("fill", COLORS.orange)
.attr("font-size", "11px")
.attr("font-family", "monospace")
.attr("opacity", highlightLevel === yl.level ? 1 : 0.5)
.text(yl.text);
}
});
}
nodes.forEach(n => {
const isHighlighted = highlightLevel === n.level || (n.isRoot && highlightLevel >= 3);
const isPast = highlightLevel > n.level;
let fillColor = n.isLeaf ? COLORS.blue : (n.isRoot ? COLORS.green : COLORS.purple);
let opacity = highlightLevel === -1 ? 0.8 : (isHighlighted ? 1 : (isPast ? 0.7 : 0.3));
treePackSvg.append("circle")
.attr("cx", n.x)
.attr("cy", n.y)
.attr("r", n.isRoot ? nodeRadius + 4 : nodeRadius)
.attr("fill", fillColor)
.attr("opacity", opacity)
.attr("stroke", isHighlighted ? COLORS.textPrimary : "none")
.attr("stroke-width", 2);
treePackSvg.append("text")
.attr("x", n.x)
.attr("y", n.y - 3)
.attr("text-anchor", "middle")
.attr("fill", COLORS.textPrimary)
.attr("font-size", n.isLeaf ? "9px" : "10px")
.attr("font-weight", "bold")
.attr("opacity", opacity)
.text(n.label);
treePackSvg.append("text")
.attr("x", n.x)
.attr("y", n.y + 10)
.attr("text-anchor", "middle")
.attr("fill", COLORS.textSecondary)
.attr("font-size", "8px")
.attr("opacity", opacity)
.text(n.sublabel);
});
const levelLabels = [
{ y: leafY, text: "Input LWEs", color: COLORS.blue },
{ y: level1Y, text: "Level 1: τ₃", color: COLORS.purple },
{ y: level2Y, text: "Level 2: τ₅", color: COLORS.purple },
{ y: level3Y, text: "Level 3: τ₉", color: COLORS.green }
];
levelLabels.forEach((ll, i) => {
const isHighlighted = highlightLevel === i;
treePackSvg.append("text")
.attr("x", 15)
.attr("y", ll.y + 5)
.attr("fill", ll.color)
.attr("font-size", "11px")
.attr("font-weight", isHighlighted ? "bold" : "normal")
.attr("opacity", highlightLevel === -1 ? 0.8 : (isHighlighted ? 1 : 0.4))
.text(ll.text);
});
const legendY = 25;
treePackSvg.append("line")
.attr("x1", width - 200).attr("y1", legendY)
.attr("x2", width - 170).attr("y2", legendY)
.attr("stroke", COLORS.blue).attr("stroke-width", 2);
treePackSvg.append("text")
.attr("x", width - 165).attr("y", legendY + 4)
.attr("fill", COLORS.textSecondary).attr("font-size", "10px")
.text("even child");
treePackSvg.append("line")
.attr("x1", width - 100).attr("y1", legendY)
.attr("x2", width - 70).attr("y2", legendY)
.attr("stroke", COLORS.orange).attr("stroke-width", 2)
.attr("stroke-dasharray", "5,3");
treePackSvg.append("text")
.attr("x", width - 65).attr("y", legendY + 4)
.attr("fill", COLORS.textSecondary).attr("font-size", "10px")
.text("odd (×y)");
treePackSvg.append("text")
.attr("x", width / 2)
.attr("y", 20)
.attr("text-anchor", "middle")
.attr("fill", COLORS.purple)
.attr("font-size", "14px")
.attr("font-weight", "bold")
.text("Automorphism Tree Packing: 8 LWEs → 1 RLWE");
}
function animateTreePacking() {
if (treeAnimating) return;
treeAnimating = true;
treeTimers.forEach(t => clearTimeout(t));
treeTimers = [];
let level = 0;
function step() {
drawTreePacking(level);
level++;
if (level <= 4) {
const timer = setTimeout(step, 1200);
treeTimers.push(timer);
} else {
treeAnimating = false;
}
}
step();
}
drawTreePacking();
document.getElementById("animate-tree-btn").addEventListener("click", animateTreePacking);
document.getElementById("reset-tree-btn").addEventListener("click", () => {
treeTimers.forEach(t => clearTimeout(t));
treeTimers = [];
treeAnimating = false;
drawTreePacking();
});
document.getElementById("show-tree-algo").addEventListener("click", () => {
document.getElementById("show-tree-algo").style.background = "var(--accent-purple)";
document.getElementById("show-tree-algo").style.color = "white";
document.getElementById("show-tree-algo").style.border = "none";
document.getElementById("show-inspiring-algo").style.background = "var(--bg-tertiary)";
document.getElementById("show-inspiring-algo").style.color = "var(--text-secondary)";
document.getElementById("show-inspiring-algo").style.border = "1px solid var(--border-color)";
document.getElementById("tree-pack-details").style.display = "grid";
document.getElementById("inspiring-details").style.display = "none";
document.getElementById("tree-pack-svg").style.display = "block";
document.getElementById("animate-tree-btn").style.display = "inline-block";
document.getElementById("reset-tree-btn").style.display = "inline-block";
});
document.getElementById("show-inspiring-algo").addEventListener("click", () => {
document.getElementById("show-inspiring-algo").style.background = "var(--accent-green)";
document.getElementById("show-inspiring-algo").style.color = "white";
document.getElementById("show-inspiring-algo").style.border = "none";
document.getElementById("show-tree-algo").style.background = "var(--bg-tertiary)";
document.getElementById("show-tree-algo").style.color = "var(--text-secondary)";
document.getElementById("show-tree-algo").style.border = "1px solid var(--border-color)";
document.getElementById("tree-pack-details").style.display = "none";
document.getElementById("inspiring-details").style.display = "block";
document.getElementById("tree-pack-svg").style.display = "none";
document.getElementById("animate-tree-btn").style.display = "none";
document.getElementById("reset-tree-btn").style.display = "none";
});
let useGoodBasis = true;
let showSVP = false;
function drawLattice() {
const svg = d3.select("#lattice-svg");
svg.selectAll("*").remove();
const width = 900;
const height = 350;
const centerX = 300;
const centerY = 175;
const scale = 25;
const goodB1 = [3, 0.5];
const goodB2 = [0.5, 3];
const badB1 = [3, 0.5];
const badB2 = [3.5, 3.5];
const b1 = useGoodBasis ? goodB1 : badB1;
const b2 = useGoodBasis ? goodB2 : badB2;
svg.append("line")
.attr("x1", 0).attr("y1", centerY)
.attr("x2", width).attr("y2", centerY)
.attr("stroke", "#30363d").attr("stroke-width", 1);
svg.append("line")
.attr("x1", centerX).attr("y1", 0)
.attr("x2", centerX).attr("y2", height)
.attr("stroke", "#30363d").attr("stroke-width", 1);
const range = 6;
const points = [];
for (let i = -range; i <= range; i++) {
for (let j = -range; j <= range; j++) {
const x = centerX + (i * goodB1[0] + j * goodB2[0]) * scale;
const y = centerY - (i * goodB1[1] + j * goodB2[1]) * scale;
if (x > 20 && x < 580 && y > 20 && y < height - 20) {
points.push({ x, y, i, j });
}
}
}
let shortest = null;
let shortestLen = Infinity;
points.forEach(p => {
if (p.i === 0 && p.j === 0) return;
const len = Math.sqrt(Math.pow(p.x - centerX, 2) + Math.pow(p.y - centerY, 2));
if (len < shortestLen) {
shortestLen = len;
shortest = p;
}
});
points.forEach(p => {
const isOrigin = p.i === 0 && p.j === 0;
const isShortest = showSVP && shortest && p.i === shortest.i && p.j === shortest.j;
svg.append("circle")
.attr("cx", p.x).attr("cy", p.y)
.attr("r", isOrigin ? 6 : (isShortest ? 8 : 4))
.attr("fill", isOrigin ? COLORS.orange : (isShortest ? COLORS.green : COLORS.blue))
.attr("opacity", isShortest ? 1 : 0.7);
});
svg.append("line")
.attr("x1", centerX).attr("y1", centerY)
.attr("x2", centerX + b1[0] * scale).attr("y2", centerY - b1[1] * scale)
.attr("stroke", COLORS.red).attr("stroke-width", 3)
.attr("marker-end", "url(#arrow-red)");
svg.append("text")
.attr("x", centerX + b1[0] * scale + 10).attr("y", centerY - b1[1] * scale)
.attr("fill", COLORS.red).attr("font-size", "12px").attr("font-weight", "bold")
.text("b₁");
svg.append("line")
.attr("x1", centerX).attr("y1", centerY)
.attr("x2", centerX + b2[0] * scale).attr("y2", centerY - b2[1] * scale)
.attr("stroke", COLORS.yellow).attr("stroke-width", 3)
.attr("marker-end", "url(#arrow-yellow)");
svg.append("text")
.attr("x", centerX + b2[0] * scale + 10).attr("y", centerY - b2[1] * scale)
.attr("fill", COLORS.yellow).attr("font-size", "12px").attr("font-weight", "bold")
.text("b₂");
if (showSVP && shortest) {
svg.append("line")
.attr("x1", centerX).attr("y1", centerY)
.attr("x2", shortest.x).attr("y2", shortest.y)
.attr("stroke", COLORS.green).attr("stroke-width", 2)
.attr("stroke-dasharray", "5,3");
}
const infoX = 620;
svg.append("rect")
.attr("x", infoX).attr("y", 20)
.attr("width", 260).attr("height", 310)
.attr("rx", 6).attr("fill", COLORS.bgTertiary).attr("stroke", COLORS.border);
svg.append("text").attr("x", infoX + 15).attr("y", 45)
.attr("fill", useGoodBasis ? COLORS.green : COLORS.red).attr("font-size", "13px").attr("font-weight", "bold")
.text(useGoodBasis ? "Good Basis (Short Vectors)" : "Bad Basis (Long Vectors)");
const explanations = useGoodBasis ? [
"Basis vectors are nearly orthogonal",
"Easy to find short combinations",
"Attacker could solve SVP easily",
"",
"This is what we DON'T want to reveal!"
] : [
"Basis vectors are skewed/long",
"Hard to see short combinations",
"SVP is computationally hard",
"",
"This is what the attacker sees."
];
explanations.forEach((line, i) => {
svg.append("text").attr("x", infoX + 15).attr("y", 70 + i * 18)
.attr("fill", line ? COLORS.textSecondary : "transparent").attr("font-size", "11px")
.text(line);
});
svg.append("text").attr("x", infoX + 15).attr("y", 180)
.attr("fill", COLORS.green).attr("font-size", "12px").attr("font-weight", "bold")
.text("Shortest Vector Problem (SVP):");
const svpLines = [
"Given a lattice basis, find the",
"shortest non-zero lattice vector.",
"",
"Believed to be hard for quantum",
"computers (post-quantum secure)."
];
svpLines.forEach((line, i) => {
svg.append("text").attr("x", infoX + 15).attr("y", 200 + i * 16)
.attr("fill", COLORS.textSecondary).attr("font-size", "11px")
.text(line);
});
svg.append("circle").attr("cx", infoX + 25).attr("cy", 290).attr("r", 5).attr("fill", COLORS.orange);
svg.append("text").attr("x", infoX + 40).attr("y", 294).attr("fill", COLORS.textSecondary).attr("font-size", "11px").text("Origin");
svg.append("circle").attr("cx", infoX + 120).attr("cy", 290).attr("r", 5).attr("fill", COLORS.blue);
svg.append("text").attr("x", infoX + 135).attr("y", 294).attr("fill", COLORS.textSecondary).attr("font-size", "11px").text("Lattice points");
if (showSVP) {
svg.append("circle").attr("cx", infoX + 25).attr("cy", 310).attr("r", 6).attr("fill", COLORS.green);
svg.append("text").attr("x", infoX + 40).attr("y", 314).attr("fill", COLORS.textSecondary).attr("font-size", "11px").text("Shortest vector");
}
}
drawLattice();
document.getElementById("toggle-basis-btn").addEventListener("click", () => {
useGoodBasis = !useGoodBasis;
drawLattice();
});
document.getElementById("show-svp-btn").addEventListener("click", () => {
showSVP = !showSVP;
drawLattice();
});
let currentSigma = 6.4;
let errorSamples = [];
function sampleGaussian(sigma) {
const u1 = Math.random();
const u2 = Math.random();
return sigma * Math.sqrt(-2 * Math.log(u1)) * Math.cos(2 * Math.PI * u2);
}
function generateErrorSamples(sigma, count = 100) {
return Array.from({ length: count }, () => Math.round(sampleGaussian(sigma)));
}
function drawErrorDistribution() {
const svg = d3.select("#error-svg");
svg.selectAll("*").remove();
const width = 900;
const height = 280;
const margin = { top: 40, right: 40, bottom: 50, left: 60 };
const chartWidth = width - margin.left - margin.right;
const chartHeight = height - margin.top - margin.bottom;
const g = svg.append("g").attr("transform", `translate(${margin.left}, ${margin.top})`);
if (errorSamples.length === 0) {
errorSamples = generateErrorSamples(currentSigma, 200);
}
const bins = {};
const range = Math.ceil(currentSigma * 4);
for (let i = -range; i <= range; i++) bins[i] = 0;
errorSamples.forEach(s => {
const clamped = Math.max(-range, Math.min(range, s));
bins[clamped] = (bins[clamped] || 0) + 1;
});
const binData = Object.entries(bins).map(([k, v]) => ({ x: parseInt(k), count: v }));
const maxCount = Math.max(...binData.map(d => d.count));
const xScale = d3.scaleLinear().domain([-range, range]).range([0, chartWidth]);
const yScale = d3.scaleLinear().domain([0, maxCount * 1.1]).range([chartHeight, 0]);
const gaussPoints = [];
for (let x = -range; x <= range; x += 0.1) {
const y = (1 / (currentSigma * Math.sqrt(2 * Math.PI))) *
Math.exp(-0.5 * Math.pow(x / currentSigma, 2));
gaussPoints.push({ x, y: y * errorSamples.length * 0.8 });
}
const line = d3.line()
.x(d => xScale(d.x))
.y(d => yScale(d.y))
.curve(d3.curveBasis);
g.append("path")
.datum(gaussPoints)
.attr("d", line)
.attr("fill", "none")
.attr("stroke", "#3fb950")
.attr("stroke-width", 2)
.attr("opacity", 0.8);
const barWidth = chartWidth / (2 * range + 1) * 0.8;
g.selectAll(".bar")
.data(binData)
.join("rect")
.attr("class", "bar")
.attr("x", d => xScale(d.x) - barWidth / 2)
.attr("y", d => yScale(d.count))
.attr("width", barWidth)
.attr("height", d => chartHeight - yScale(d.count))
.attr("fill", "#58a6ff")
.attr("opacity", 0.7)
.attr("rx", 2);
g.append("g")
.attr("transform", `translate(0, ${chartHeight})`)
.call(d3.axisBottom(xScale).ticks(range * 2))
.selectAll("text").attr("fill", "#8b949e");
g.selectAll(".domain, .tick line").attr("stroke", "#30363d");
g.append("g")
.call(d3.axisLeft(yScale).ticks(5))
.selectAll("text").attr("fill", "#8b949e");
svg.append("text")
.attr("x", margin.left + chartWidth / 2).attr("y", height - 10)
.attr("text-anchor", "middle").attr("fill", "#8b949e").attr("font-size", "11px")
.text("Error value (discrete Gaussian)");
svg.append("text")
.attr("x", 15).attr("y", margin.top + chartHeight / 2)
.attr("text-anchor", "middle").attr("fill", "#8b949e").attr("font-size", "11px")
.attr("transform", `rotate(-90, 15, ${margin.top + chartHeight / 2})`)
.text("Count");
svg.append("text")
.attr("x", margin.left).attr("y", 25)
.attr("fill", "#3fb950").attr("font-size", "12px").attr("font-weight", "bold")
.text(`Discrete Gaussian Distribution (σ = ${currentSigma})`);
const infoX = 720;
svg.append("rect")
.attr("x", infoX).attr("y", 45)
.attr("width", 170).attr("height", 125)
.attr("rx", 4).attr("fill", "#21262d").attr("stroke", "#30363d");
const infoLines = [
"RLWE adds small errors:",
"b = a·s + e + Δ·m",
"",
"Small σ → less noise → easier",
"Large σ → more noise → secure",
"",
`σ = ${currentSigma} provides`,
"128-bit security"
];
infoLines.forEach((line, i) => {
svg.append("text")
.attr("x", infoX + 10).attr("y", 58 + i * 14)
.attr("fill", i === 0 ? "#3fb950" : "#8b949e")
.attr("font-size", "10px")
.attr("font-weight", i === 0 ? "bold" : "normal")
.text(line);
});
}
drawErrorDistribution();
document.getElementById("sigma-slider").addEventListener("input", function() {
currentSigma = parseFloat(this.value);
document.getElementById("sigma-value").textContent = currentSigma;
errorSamples = generateErrorSamples(currentSigma, 200);
drawErrorDistribution();
});
document.getElementById("sample-error-btn").addEventListener("click", () => {
errorSamples = generateErrorSamples(currentSigma, 200);
drawErrorDistribution();
});
const RING_SIZE = 8; let ringCoeffs = [3, 1, 4, 1, 5, 9, 2, 6]; let rotationCount = 0;
function drawRingStructure() {
const svg = d3.select("#ring-svg");
svg.selectAll("*").remove();
const width = 900;
const height = 320;
const centerX = 200;
const centerY = 160;
const radius = 120;
const angleStep = (2 * Math.PI) / RING_SIZE;
const coeffPositions = [];
for (let i = 0; i < RING_SIZE; i++) {
const angle = -Math.PI / 2 + i * angleStep;
const x = centerX + radius * Math.cos(angle);
const y = centerY + radius * Math.sin(angle);
coeffPositions.push({ x, y, angle, index: i });
}
svg.append("circle")
.attr("cx", centerX).attr("cy", centerY)
.attr("r", radius)
.attr("fill", "none")
.attr("stroke", "#30363d")
.attr("stroke-width", 2);
coeffPositions.forEach((pos, i) => {
svg.append("circle")
.attr("cx", pos.x).attr("cy", pos.y)
.attr("r", 24)
.attr("fill", i === 0 ? "#a371f7" : "#21262d")
.attr("stroke", i === 0 ? "#a371f7" : "#58a6ff")
.attr("stroke-width", 2);
svg.append("text")
.attr("x", pos.x).attr("y", pos.y + 5)
.attr("text-anchor", "middle")
.attr("fill", i === 0 ? "#fff" : "#58a6ff")
.attr("font-size", "13px")
.attr("font-weight", "bold")
.text(ringCoeffs[i]);
});
coeffPositions.forEach((pos, i) => {
const labelRadius = radius + 40;
const labelX = centerX + labelRadius * Math.cos(pos.angle);
const labelY = centerY + labelRadius * Math.sin(pos.angle);
svg.append("text")
.attr("x", labelX).attr("y", labelY + 4)
.attr("text-anchor", "middle")
.attr("fill", "#6e7681")
.attr("font-size", "10px")
.text(`X^${i}`);
});
svg.append("defs").append("marker")
.attr("id", "arrow-rotate")
.attr("markerWidth", 8).attr("markerHeight", 6)
.attr("refX", 7).attr("refY", 3).attr("orient", "auto")
.append("polygon").attr("points", "0 0, 8 3, 0 6").attr("fill", "#d29922");
const arrowArcRadius = radius - 45;
svg.append("path")
.attr("d", `M ${centerX + 35} ${centerY - 35} A ${arrowArcRadius} ${arrowArcRadius} 0 0 1 ${centerX + 50} ${centerY + 5}`)
.attr("fill", "none")
.attr("stroke", "#d29922")
.attr("stroke-width", 2)
.attr("marker-end", "url(#arrow-rotate)");
svg.append("text")
.attr("x", centerX + 60).attr("y", centerY - 20)
.attr("fill", "#d29922").attr("font-size", "11px").attr("font-weight", "bold")
.text("×X");
const polyX = 450;
const polyY = 40;
svg.append("text")
.attr("x", polyX).attr("y", polyY)
.attr("fill", "#a371f7").attr("font-size", "13px").attr("font-weight", "bold")
.text("Current polynomial:");
const polyStr = ringCoeffs.map((c, i) => {
if (i === 0) return c.toString();
return `${c >= 0 ? '+' : ''}${c}X^${i}`;
}).join(' ');
svg.append("text")
.attr("x", polyX).attr("y", polyY + 25)
.attr("fill", "#e6edf3").attr("font-size", "12px")
.attr("font-family", "monospace")
.text(`f(X) = ${polyStr.substring(0, 50)}${polyStr.length > 50 ? '...' : ''}`);
svg.append("text")
.attr("x", polyX).attr("y", polyY + 50)
.attr("fill", "#8b949e").attr("font-size", "11px")
.text(`Rotations applied: ${rotationCount}`);
svg.append("rect")
.attr("x", polyX).attr("y", 90)
.attr("width", 420).attr("height", 200)
.attr("rx", 6).attr("fill", "#21262d").attr("stroke", "#30363d");
const explainLines = [
{ text: "Ring: R_q = Z_q[X]/(X^d + 1)", color: "#a371f7", bold: true },
{ text: "", color: "transparent" },
{ text: "Key property: X^d = -1", color: "#3fb950", bold: true },
{ text: "So X^d ≡ -1 (mod X^d + 1)", color: "#8b949e" },
{ text: "", color: "transparent" },
{ text: "Multiplying by X:", color: "#d29922", bold: true },
{ text: "• Shifts all coefficients right by 1", color: "#8b949e" },
{ text: "• Top coefficient wraps to position 0", color: "#8b949e" },
{ text: "• Gets negated (because X^d = -1)", color: "#8b949e" },
{ text: "", color: "transparent" },
{ text: "This cyclic structure enables efficient PIR!", color: "#58a6ff" }
];
explainLines.forEach((line, i) => {
svg.append("text")
.attr("x", polyX + 15).attr("y", 115 + i * 17)
.attr("fill", line.color)
.attr("font-size", "11px")
.attr("font-weight", line.bold ? "bold" : "normal")
.text(line.text);
});
svg.append("text")
.attr("x", centerX).attr("y", centerY + radius + 60)
.attr("text-anchor", "middle")
.attr("fill", "#a371f7").attr("font-size", "11px")
.text("Coefficient 0 (extracted after rotation)");
}
function rotateRing() {
const last = ringCoeffs[RING_SIZE - 1];
for (let i = RING_SIZE - 1; i > 0; i--) {
ringCoeffs[i] = ringCoeffs[i - 1];
}
ringCoeffs[0] = -last; rotationCount++;
drawRingStructure();
}
function resetRing() {
ringCoeffs = [3, 1, 4, 1, 5, 9, 2, 6];
rotationCount = 0;
drawRingStructure();
}
drawRingStructure();
document.getElementById("rotate-ring-btn").addEventListener("click", rotateRing);
document.getElementById("reset-ring-btn").addEventListener("click", resetRing);
</script>
</body>
</html>