mirror of
https://github.com/Sunscreen-tech/Sunscreen.git
synced 2026-01-14 16:17:56 -05:00
225 lines
18 KiB
HTML
225 lines
18 KiB
HTML
<!DOCTYPE HTML>
|
|
<html lang="en" class="sidebar-visible no-js light">
|
|
<head>
|
|
<!-- Book generated using mdBook -->
|
|
<meta charset="UTF-8">
|
|
<title>Why is a compiler needed for FHE? - Sunscreen Documentation</title>
|
|
|
|
|
|
<!-- Custom HTML head -->
|
|
|
|
<meta content="text/html; charset=utf-8" http-equiv="Content-Type">
|
|
<meta name="description" content="">
|
|
<meta name="viewport" content="width=device-width, initial-scale=1">
|
|
<meta name="theme-color" content="#ffffff" />
|
|
|
|
<link rel="icon" href="../favicon.svg">
|
|
<link rel="shortcut icon" href="../favicon.png">
|
|
<link rel="stylesheet" href="../css/variables.css">
|
|
<link rel="stylesheet" href="../css/general.css">
|
|
<link rel="stylesheet" href="../css/chrome.css">
|
|
<link rel="stylesheet" href="../css/print.css" media="print">
|
|
|
|
<!-- Fonts -->
|
|
<link rel="stylesheet" href="../FontAwesome/css/font-awesome.css">
|
|
<link rel="stylesheet" href="../fonts/fonts.css">
|
|
|
|
<!-- Highlight.js Stylesheets -->
|
|
<link rel="stylesheet" href="../highlight.css">
|
|
<link rel="stylesheet" href="../tomorrow-night.css">
|
|
<link rel="stylesheet" href="../ayu-highlight.css">
|
|
|
|
<!-- Custom theme stylesheets -->
|
|
|
|
<!-- MathJax -->
|
|
<script async type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>
|
|
</head>
|
|
<body>
|
|
<!-- Provide site root to javascript -->
|
|
<script type="text/javascript">
|
|
var path_to_root = "../";
|
|
var default_theme = window.matchMedia("(prefers-color-scheme: dark)").matches ? "navy" : "light";
|
|
</script>
|
|
|
|
<!-- Work around some values being stored in localStorage wrapped in quotes -->
|
|
<script type="text/javascript">
|
|
try {
|
|
var theme = localStorage.getItem('mdbook-theme');
|
|
var sidebar = localStorage.getItem('mdbook-sidebar');
|
|
|
|
if (theme.startsWith('"') && theme.endsWith('"')) {
|
|
localStorage.setItem('mdbook-theme', theme.slice(1, theme.length - 1));
|
|
}
|
|
|
|
if (sidebar.startsWith('"') && sidebar.endsWith('"')) {
|
|
localStorage.setItem('mdbook-sidebar', sidebar.slice(1, sidebar.length - 1));
|
|
}
|
|
} catch (e) { }
|
|
</script>
|
|
|
|
<!-- Set the theme before any content is loaded, prevents flash -->
|
|
<script type="text/javascript">
|
|
var theme;
|
|
try { theme = localStorage.getItem('mdbook-theme'); } catch(e) { }
|
|
if (theme === null || theme === undefined) { theme = default_theme; }
|
|
var html = document.querySelector('html');
|
|
html.classList.remove('no-js')
|
|
html.classList.remove('light')
|
|
html.classList.add(theme);
|
|
html.classList.add('js');
|
|
</script>
|
|
|
|
<!-- Hide / unhide sidebar before it is displayed -->
|
|
<script type="text/javascript">
|
|
var html = document.querySelector('html');
|
|
var sidebar = 'hidden';
|
|
if (document.body.clientWidth >= 1080) {
|
|
try { sidebar = localStorage.getItem('mdbook-sidebar'); } catch(e) { }
|
|
sidebar = sidebar || 'visible';
|
|
}
|
|
html.classList.remove('sidebar-visible');
|
|
html.classList.add("sidebar-" + sidebar);
|
|
</script>
|
|
|
|
<nav id="sidebar" class="sidebar" aria-label="Table of contents">
|
|
<div class="sidebar-scrollbox">
|
|
<ol class="chapter"><li class="chapter-item expanded "><a href="../intro/intro.html"><strong aria-hidden="true">1.</strong> Introduction</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../intro/prelim.html"><strong aria-hidden="true">1.1.</strong> Prerequisites</a></li><li class="chapter-item expanded "><a href="../intro/why.html" class="active"><strong aria-hidden="true">1.2.</strong> Why is a compiler needed for FHE?</a></li><li class="chapter-item expanded "><a href="../intro/compiler.html"><strong aria-hidden="true">1.3.</strong> Sunscreen's compiler</a></li></ol></li><li class="chapter-item expanded "><a href="../getting_started/getting_started.html"><strong aria-hidden="true">2.</strong> Getting started</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../getting_started/installation.html"><strong aria-hidden="true">2.1.</strong> Installation</a></li><li class="chapter-item expanded "><a href="../getting_started/example.html"><strong aria-hidden="true">2.2.</strong> My first FHE program</a></li></ol></li><li class="chapter-item expanded "><a href="../fhe_programs/fhe_programs.html"><strong aria-hidden="true">3.</strong> What's in an FHE program?</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../fhe_programs/types/types.html"><strong aria-hidden="true">3.1.</strong> Types</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../fhe_programs/types/signed.html"><strong aria-hidden="true">3.1.1.</strong> Signed</a></li><li class="chapter-item expanded "><a href="../fhe_programs/types/fractional.html"><strong aria-hidden="true">3.1.2.</strong> Fractional</a></li><li class="chapter-item expanded "><a href="../fhe_programs/types/rational.html"><strong aria-hidden="true">3.1.3.</strong> Rational</a></li></ol></li><li class="chapter-item expanded "><a href="../fhe_programs/writing_an_fhe_program/writing_an_fhe_program.html"><strong aria-hidden="true">3.2.</strong> How to write an FHE program</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../fhe_programs/factoring_fhe_programs.html"><strong aria-hidden="true">3.2.1.</strong> Factoring FHE programs</a></li><li class="chapter-item expanded "><a href="../fhe_programs/writing_an_fhe_program/limitations.html"><strong aria-hidden="true">3.2.2.</strong> Limitations</a></li></ol></li><li class="chapter-item expanded "><a href="../troubleshooting.html"><strong aria-hidden="true">3.3.</strong> Troubleshooting</a></li></ol></li><li class="chapter-item expanded "><a href="../fhe_programs/runtime/runtime.html"><strong aria-hidden="true">4.</strong> Runtime</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../fhe_programs/runtime/key_generation.html"><strong aria-hidden="true">4.1.</strong> Key generation</a></li><li class="chapter-item expanded "><a href="../fhe_programs/runtime/encryption.html"><strong aria-hidden="true">4.2.</strong> Encryption</a></li><li class="chapter-item expanded "><a href="../fhe_programs/runtime/running_fhe_programs.html"><strong aria-hidden="true">4.3.</strong> Running FHE programs</a></li><li class="chapter-item expanded "><a href="../fhe_programs/runtime/decryption.html"><strong aria-hidden="true">4.4.</strong> Decryption</a></li><li class="chapter-item expanded "><a href="../fhe_programs/runtime/serialization.html"><strong aria-hidden="true">4.5.</strong> Serialization</a></li></ol></li><li class="chapter-item expanded "><a href="../fhe_programs/apps.html"><strong aria-hidden="true">5.</strong> Applications</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../fhe_programs/example.html"><strong aria-hidden="true">5.1.</strong> AMMs & private token swaps</a></li><li class="chapter-item expanded "><a href="../fhe_programs/pir_intro.html"><strong aria-hidden="true">5.2.</strong> Private information retrieval</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../fhe_programs/pir_simple.html"><strong aria-hidden="true">5.2.1.</strong> Take 1</a></li><li class="chapter-item expanded "><a href="../fhe_programs/pir_matrix.html"><strong aria-hidden="true">5.2.2.</strong> Take 2</a></li></ol></li><li class="chapter-item expanded "><div><strong aria-hidden="true">5.3.</strong> Genomics & private tests</div></li></ol></li><li class="chapter-item expanded "><a href="../advanced/faq.html"><strong aria-hidden="true">6.</strong> FAQ</a></li><li class="chapter-item expanded "><a href="../advanced/advanced.html"><strong aria-hidden="true">7.</strong> Advanced topics</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../advanced/bfv.html"><strong aria-hidden="true">7.1.</strong> Why the BFV scheme?</a></li><li class="chapter-item expanded "><a href="../advanced/good_fhe_programs.html"><strong aria-hidden="true">7.2.</strong> Writing even better FHE programs</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../advanced/plain_modulus/plain_modulus.html"><strong aria-hidden="true">7.2.1.</strong> Plaintext modulus</a></li><li class="chapter-item expanded "><a href="../advanced/noise_margin.html"><strong aria-hidden="true">7.2.2.</strong> Noise</a></li><li class="chapter-item expanded "><a href="../advanced/pruning_keys.html"><strong aria-hidden="true">7.2.3.</strong> Pruning public keys</a></li></ol></li><li class="chapter-item expanded "><a href="../advanced/wasm.html"><strong aria-hidden="true">7.3.</strong> WASM support</a></li><li class="chapter-item expanded "><a href="../advanced/carryless_arithmetic.html"><strong aria-hidden="true">7.4.</strong> Funky math: carryless arithmetic</a></li><li class="chapter-item expanded "><div><strong aria-hidden="true">7.5.</strong> Batching</div></li></ol></li></ol>
|
|
</div>
|
|
<div id="sidebar-resize-handle" class="sidebar-resize-handle"></div>
|
|
</nav>
|
|
|
|
<div id="page-wrapper" class="page-wrapper">
|
|
|
|
<div class="page">
|
|
<div id="menu-bar-hover-placeholder"></div>
|
|
<div id="menu-bar" class="menu-bar sticky bordered">
|
|
<div class="left-buttons">
|
|
<button id="sidebar-toggle" class="icon-button" type="button" title="Toggle Table of Contents" aria-label="Toggle Table of Contents" aria-controls="sidebar">
|
|
<i class="fa fa-bars"></i>
|
|
</button>
|
|
<button id="theme-toggle" class="icon-button" type="button" title="Change theme" aria-label="Change theme" aria-haspopup="true" aria-expanded="false" aria-controls="theme-list">
|
|
<i class="fa fa-paint-brush"></i>
|
|
</button>
|
|
<ul id="theme-list" class="theme-popup" aria-label="Themes" role="menu">
|
|
<li role="none"><button role="menuitem" class="theme" id="light">Light (default)</button></li>
|
|
<li role="none"><button role="menuitem" class="theme" id="rust">Rust</button></li>
|
|
<li role="none"><button role="menuitem" class="theme" id="coal">Coal</button></li>
|
|
<li role="none"><button role="menuitem" class="theme" id="navy">Navy</button></li>
|
|
<li role="none"><button role="menuitem" class="theme" id="ayu">Ayu</button></li>
|
|
</ul>
|
|
<button id="search-toggle" class="icon-button" type="button" title="Search. (Shortkey: s)" aria-label="Toggle Searchbar" aria-expanded="false" aria-keyshortcuts="S" aria-controls="searchbar">
|
|
<i class="fa fa-search"></i>
|
|
</button>
|
|
</div>
|
|
|
|
<h1 class="menu-title">Sunscreen Documentation</h1>
|
|
|
|
<div class="right-buttons">
|
|
<a href="../print.html" title="Print this book" aria-label="Print this book">
|
|
<i id="print-button" class="fa fa-print"></i>
|
|
</a>
|
|
|
|
</div>
|
|
</div>
|
|
|
|
<div id="search-wrapper" class="hidden">
|
|
<form id="searchbar-outer" class="searchbar-outer">
|
|
<input type="search" id="searchbar" name="searchbar" placeholder="Search this book ..." aria-controls="searchresults-outer" aria-describedby="searchresults-header">
|
|
</form>
|
|
<div id="searchresults-outer" class="searchresults-outer hidden">
|
|
<div id="searchresults-header" class="searchresults-header"></div>
|
|
<ul id="searchresults">
|
|
</ul>
|
|
</div>
|
|
</div>
|
|
|
|
<!-- Apply ARIA attributes after the sidebar and the sidebar toggle button are added to the DOM -->
|
|
<script type="text/javascript">
|
|
document.getElementById('sidebar-toggle').setAttribute('aria-expanded', sidebar === 'visible');
|
|
document.getElementById('sidebar').setAttribute('aria-hidden', sidebar !== 'visible');
|
|
Array.from(document.querySelectorAll('#sidebar a')).forEach(function(link) {
|
|
link.setAttribute('tabIndex', sidebar === 'visible' ? 0 : -1);
|
|
});
|
|
</script>
|
|
|
|
<div id="content" class="content">
|
|
<main>
|
|
<h1 id="why-is-a-compiler-needed-for-fhe"><a class="header" href="#why-is-a-compiler-needed-for-fhe">Why is a compiler needed for FHE?</a></h1>
|
|
<blockquote>
|
|
<p>Why is it so hard to write FHE programs?</p>
|
|
</blockquote>
|
|
<p><em>Note:</em> The following is not a <em>precise description</em> of the math behind FHE. Our goal is to give you a high level overview as to why it's hard to work with FHE directly. </p>
|
|
<p>FHE makes use of some pretty fancy math—namely, <a href="https://en.wikipedia.org/wiki/Lattice_(group)">lattices</a>. In fact, all known FHE schemes use lattice-based cryptography. Something special about lattice-based cryptography is that it's <a href="https://en.wikipedia.org/wiki/Post-quantum_cryptography">post-quantum</a>.</p>
|
|
<p>You're likely familiar with matrices and vectors. Imagine that instead of having <em>numbers</em> as the entries in a matrix or vector, we replace them with <em>polynomials</em> (e.g. \(8x^5+5x^2+x+13\)). You might wonder: why would we want to have polynomials instead of numbers as entries? Well, replacing a number with a polynomial allows us to embed <em>many</em> numbers (as coefficients) in a single matrix entry, thus leading to better efficiency/performance. Recall that polynomials consist of coefficients (these would be <code>8</code>, <code>5</code>, <code>1</code>, <code>13</code> in our example) and a degree/order (this is 5 in our example). However, these polynomials behave a bit differently than what you've seen in grade school. </p>
|
|
<p>Let's take a brief detour and discuss modular arithmetic (aka clock arithmetic). Modular arithmetic is just integer arithmetic that "wraps" around. Alternatively, you can think of it as division with remainder. For example, <code>13 mod 12 = 1</code>.</p>
|
|
<p>The polynomials in FHE make use of modular arithmetic. The degree is actually mod some value; we'll say degree mod <code>N</code>. The coefficients are also mod some value; we'll say coefficient mod <code>P</code>. </p>
|
|
<p>So if I tell you to take the degree <code>mod 3</code> and the coefficients <code>mod 7</code>, \(8x^5+5x^2+x+13\) becomes \(1x^2+5x^2+x+6\). </p>
|
|
<p>To get good performance in FHE, you need to know how to set these parameters (N, P) <em>just right</em>. If the parameters are too small, you'll be very limited in terms of the computations you can do. Alternatively, if you make the parameters too big, you'll end with poor performance and large ciphertext sizes. Even worse, you need to base your parameter choices off the maximum sequence of multiplications you plan on doing along with the desired security level.</p>
|
|
<p>Finally, I've neglected to mention how FHE programs actually work. Under the hood, FHE uses circuits. For the BFV scheme, we have arithmetic circuits (some other FHE schemes use binary circuits). When was the last time you tried to work directly with circuits (if ever)? </p>
|
|
<p>Our compiler handles picking all parameters and the appropriate keys for you. We abstract away the polynomials and circuits too.</p>
|
|
|
|
</main>
|
|
|
|
<nav class="nav-wrapper" aria-label="Page navigation">
|
|
<!-- Mobile navigation buttons -->
|
|
<a rel="prev" href="../intro/prelim.html" class="mobile-nav-chapters previous" title="Previous chapter" aria-label="Previous chapter" aria-keyshortcuts="Left">
|
|
<i class="fa fa-angle-left"></i>
|
|
</a>
|
|
|
|
<a rel="next" href="../intro/compiler.html" class="mobile-nav-chapters next" title="Next chapter" aria-label="Next chapter" aria-keyshortcuts="Right">
|
|
<i class="fa fa-angle-right"></i>
|
|
</a>
|
|
|
|
<div style="clear: both"></div>
|
|
</nav>
|
|
</div>
|
|
</div>
|
|
|
|
<nav class="nav-wide-wrapper" aria-label="Page navigation">
|
|
<a rel="prev" href="../intro/prelim.html" class="nav-chapters previous" title="Previous chapter" aria-label="Previous chapter" aria-keyshortcuts="Left">
|
|
<i class="fa fa-angle-left"></i>
|
|
</a>
|
|
|
|
<a rel="next" href="../intro/compiler.html" class="nav-chapters next" title="Next chapter" aria-label="Next chapter" aria-keyshortcuts="Right">
|
|
<i class="fa fa-angle-right"></i>
|
|
</a>
|
|
</nav>
|
|
|
|
</div>
|
|
|
|
<!-- Livereload script (if served using the cli tool) -->
|
|
<script type="text/javascript">
|
|
var socket = new WebSocket("ws://localhost:3000/__livereload");
|
|
socket.onmessage = function (event) {
|
|
if (event.data === "reload") {
|
|
socket.close();
|
|
location.reload();
|
|
}
|
|
};
|
|
|
|
window.onbeforeunload = function() {
|
|
socket.close();
|
|
}
|
|
</script>
|
|
|
|
|
|
|
|
<script type="text/javascript">
|
|
window.playground_copyable = true;
|
|
</script>
|
|
|
|
|
|
<script src="../elasticlunr.min.js" type="text/javascript" charset="utf-8"></script>
|
|
<script src="../mark.min.js" type="text/javascript" charset="utf-8"></script>
|
|
<script src="../searcher.js" type="text/javascript" charset="utf-8"></script>
|
|
|
|
<script src="../clipboard.min.js" type="text/javascript" charset="utf-8"></script>
|
|
<script src="../highlight.js" type="text/javascript" charset="utf-8"></script>
|
|
<script src="../book.js" type="text/javascript" charset="utf-8"></script>
|
|
|
|
<!-- Custom JS scripts -->
|
|
|
|
|
|
</body>
|
|
</html>
|