mirror of
https://github.com/Sunscreen-tech/Sunscreen.git
synced 2026-01-14 16:17:56 -05:00
576 lines
37 KiB
HTML
576 lines
37 KiB
HTML
<!DOCTYPE HTML>
|
|
<html lang="en" class="sidebar-visible no-js light">
|
|
<head>
|
|
<!-- Book generated using mdBook -->
|
|
<meta charset="UTF-8">
|
|
<title>Take 1 - 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"><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" class="active"><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="warm-up-a-very-simple-pir-algorithm"><a class="header" href="#warm-up-a-very-simple-pir-algorithm">Warm up: a very simple PIR algorithm</a></h1>
|
|
<p>We'll start with a very simple algorithm that uses a dot product to return an item privately. </p>
|
|
<h2 id="how-will-our-algorithm-work"><a class="header" href="#how-will-our-algorithm-work">How will our algorithm work?</a></h2>
|
|
<p>Everything in the database will be <em>un</em>encrypted. We'll represent our database as a <a href="https://en.wikipedia.org/wiki/Euclidean_vector">vector</a> of <code>n</code> items.</p>
|
|
<p>Let's say that Alice wants to retrieve the 2nd item from the database. Alice will send a query to the server; we'll represent this query as a vector of length <code>n</code> as well.</p>
|
|
<h3 id="information-retrieval-without-privacy"><a class="header" href="#information-retrieval-without-privacy">Information retrieval (<strong>without privacy</strong>)</a></h3>
|
|
<p>Every element of this query vector, <em>except</em> the one Alice is interested in, will have a 0 in its place. Alice will place a 1 in the 2nd entry (since she's interested in the 2nd item). When the server take the dot product of these two vectors, Alice will get back the item she wanted to retrieve:</p>
|
|
<p>[item<sub>1</sub>, item<sub>2</sub>, item<sub>3</sub>, ... , item<sub>n</sub>] · [0, 1, 0, ... , 0]<sup>t</sup> </p>
|
|
<p>= item<sub>1</sub> · 0 + item<sub>2</sub> · 1 + item<sub>3</sub> · 0 + ... + item<sub>n</sub> · 0 </p>
|
|
<p>= item<sub>2</sub></p>
|
|
<p>Of course, the server can observe that Alice is interested in retrieving the 2nd item. How do we make this query private?</p>
|
|
<h3 id="making-the-query-private"><a class="header" href="#making-the-query-private">Making the query private</a></h3>
|
|
<p>For simplicity, let Enc(x) denote that we encrypt x.<sup class="footnote-reference"><a href="#1">1</a></sup></p>
|
|
<p>Since Alice doesn't want to reveal to the server <em>which</em> item she's interested in, she encrypts each of the elements in her query vector with respect to her FHE public key. Voila! We can now retrieve the information privately:</p>
|
|
<p>[item<sub>1</sub>, item<sub>2</sub>, item<sub>3</sub>, ... , item<sub>n</sub>] · [Enc(0), Enc(1), Enc(0), ... , Enc(0)]<sup>t</sup> </p>
|
|
<p>= item<sub>1</sub> · Enc(0) + item<sub>2</sub> · Enc(1) + item<sub>3</sub> · Enc(0) + ... + item<sub>n</sub> · Enc(0) </p>
|
|
<p>= Enc(item<sub>2</sub>)</p>
|
|
<div class="footnote-definition" id="1"><sup class="footnote-definition-label">1</sup>
|
|
<p>The encryption scheme must be <a href="https://en.wikipedia.org/wiki/Probabilistic_encryption">probabilistic</a> (such that different randomness is used for encrypting each element in the query vector). Otherwise, the server <em>would</em> be able to tell apart Enc(1) from Enc(0) and deduce what Alice wants to retrieve. You don't have to worry about this issue when using Sunscreen's compiler.</p>
|
|
</div>
|
|
<h2 id="program-walkthrough"><a class="header" href="#program-walkthrough">Program walkthrough</a></h2>
|
|
<p>Our database will have 100 items in it. We'll represent the vectors from earlier as <a href="./types/types.html">arrays</a>, one of Sunscreen's supported types.</p>
|
|
<h3 id="setup"><a class="header" href="#setup">Setup</a></h3>
|
|
<pre><pre class="playground"><code class="language-rust no_run edition2021">
|
|
<span class="boring">#![allow(unused)]
|
|
</span><span class="boring">fn main() {
|
|
</span>use sunscreen::{
|
|
fhe_program,
|
|
types::{bfv::Signed, Cipher},
|
|
};
|
|
|
|
const DATABASE_SIZE: usize = 100;
|
|
|
|
#[fhe_program(scheme = "bfv")]
|
|
/// This program takes a user's query and looks up the entry in the database.
|
|
/// Queries are arrays containing a single 1 element at the
|
|
/// desired item's index and 0s elsewhere.
|
|
fn lookup(query: [Cipher<Signed>; DATABASE_SIZE], database: [Signed; DATABASE_SIZE]) -> Cipher<Signed> {
|
|
let mut sum = query[0] * database[0];
|
|
|
|
for i in 1..DATABASE_SIZE {
|
|
sum = sum + query[i] * database[i]
|
|
}
|
|
|
|
sum
|
|
}
|
|
<span class="boring">}
|
|
</span></code></pre></pre>
|
|
<p>We begin by importing the stuff we're going to use.</p>
|
|
<p>We declare our <code>lookup</code> function as an FHE program with the appropriate attribute (<code>#[fhe_program(scheme = "bfv")]</code>).</p>
|
|
<p><code>lookup</code> implements the dot product formula discussed above. It takes in the unencrypted <code>database</code> and the encrypted <code>query</code> from the user to retrieve an item privately. The database is an array of length <code>DATABASE_SIZE</code> where each item in the database is a signed integer (<code>Signed</code>). Hence, the user's <code>query</code> is an array of length <code>DATABASE_SIZE</code> as well, where each entry is of type <code>Cipher<Signed></code>.</p>
|
|
<h3 id="alice"><a class="header" href="#alice">Alice</a></h3>
|
|
<pre><pre class="playground"><code class="language-rust no_run edition2021">
|
|
<span class="boring">#![allow(unused)]
|
|
</span><span class="boring">fn main() {
|
|
</span><span class="boring">use sunscreen::{
|
|
</span><span class="boring"> fhe_program,
|
|
</span><span class="boring"> types::{bfv::Signed, Cipher},
|
|
</span><span class="boring"> Ciphertext, CompiledFheProgram, Compiler, Error, FheProgramInput, Params, PrivateKey,
|
|
</span><span class="boring"> PublicKey, Runtime,
|
|
</span><span class="boring">};
|
|
</span><span class="boring">
|
|
</span>/// Alice is a party that wants to look up a value in the database without
|
|
/// revealing what she looked up.
|
|
struct Alice {
|
|
/// Alice's public key
|
|
pub public_key: PublicKey,
|
|
|
|
/// Alice's private key
|
|
private_key: PrivateKey,
|
|
|
|
/// Alice's runtime
|
|
runtime: Runtime,
|
|
}
|
|
<span class="boring">}
|
|
</span></code></pre></pre>
|
|
<p>Alice wants to retrieve an item from the database privately. She'll need a public/private key pair to do this (since she needs to encrypt her query with respect to her public key).</p>
|
|
<pre><pre class="playground"><code class="language-rust no_run edition2021">
|
|
<span class="boring">#![allow(unused)]
|
|
</span><span class="boring">fn main() {
|
|
</span><span class="boring">use sunscreen::{
|
|
</span><span class="boring"> fhe_program,
|
|
</span><span class="boring"> types::{bfv::Signed, Cipher},
|
|
</span><span class="boring"> Ciphertext, CompiledFheProgram, Compiler, Error, FheProgramInput, Params, PrivateKey,
|
|
</span><span class="boring"> PublicKey, Runtime,
|
|
</span><span class="boring">};
|
|
</span><span class="boring">
|
|
</span><span class="boring">const DATABASE_SIZE: usize = 100;
|
|
</span><span class="boring">
|
|
</span><span class="boring">/// Alice is a party that wants to look up a value in the database without
|
|
</span><span class="boring">/// revealing what she looked up.
|
|
</span><span class="boring">struct Alice {
|
|
</span><span class="boring"> /// Alice's public key
|
|
</span><span class="boring"> pub public_key: PublicKey,
|
|
</span><span class="boring">
|
|
</span><span class="boring"> /// Alice's private key
|
|
</span><span class="boring"> private_key: PrivateKey,
|
|
</span><span class="boring">
|
|
</span><span class="boring"> /// Alice's runtime
|
|
</span><span class="boring"> runtime: Runtime,
|
|
</span><span class="boring">}
|
|
</span><span class="boring">
|
|
</span>impl Alice {
|
|
pub fn setup(params: &Params) -> Result<Alice, Error> {
|
|
let runtime = Runtime::new(params)?;
|
|
|
|
let (public_key, private_key) = runtime.generate_keys()?;
|
|
|
|
Ok(Alice {
|
|
public_key,
|
|
private_key,
|
|
runtime,
|
|
})
|
|
}
|
|
|
|
pub fn create_query(&self, index: usize) -> Result<Ciphertext, Error> {
|
|
let mut query = [Signed::from(0); DATABASE_SIZE];
|
|
query[index] = Signed::from(1);
|
|
|
|
Ok(self.runtime.encrypt(query, &self.public_key)?)
|
|
}
|
|
|
|
pub fn check_response(&self, value: Ciphertext) -> Result<(), Error> {
|
|
let value: Signed = self.runtime.decrypt(&value, &self.private_key)?;
|
|
|
|
let value: i64 = value.into();
|
|
|
|
println!("Alice received {}", value);
|
|
|
|
Ok(())
|
|
}
|
|
}
|
|
<span class="boring">}
|
|
</span></code></pre></pre>
|
|
<p>Alice will need to construct a runtime. Once that's done, she can generate her public/private key pair. </p>
|
|
<p>Alice can create her unencrypted query "vector" (actually an <a href="./types/types.html">array</a>) of 0's and 1's by calling <code>create_query</code>. Recall that the we'll have a 1 in the place of her desired item's index and a 0 elsewhere. Since she wants her query to be private, she'll <code>encrypt</code> her <code>query</code>, passing in her <code>public_key</code> as necessary.</p>
|
|
<p>We won't use this until the very end but <code>check_response</code> allows Alice to decrypt the server's response by passing in the ciphertext she received (<code>value</code>) along with her <code>private_key</code>.</p>
|
|
<h3 id="server"><a class="header" href="#server">Server</a></h3>
|
|
<p>Let's look at the server next.</p>
|
|
<pre><pre class="playground"><code class="language-rust no_run edition2021">
|
|
<span class="boring">#![allow(unused)]
|
|
</span><span class="boring">fn main() {
|
|
</span><span class="boring">use sunscreen::{
|
|
</span><span class="boring"> fhe_program,
|
|
</span><span class="boring"> types::{bfv::Signed, Cipher},
|
|
</span><span class="boring"> Ciphertext, CompiledFheProgram, Compiler, Error, FheProgramInput, Params, PrivateKey,
|
|
</span><span class="boring"> PublicKey, Runtime,
|
|
</span><span class="boring">};
|
|
</span>/// This is the server that processes Alice's query.
|
|
struct Server {
|
|
/// The compiled database lookup program
|
|
pub compiled_lookup: CompiledFheProgram,
|
|
|
|
/// The server's runtime
|
|
runtime: Runtime,
|
|
}
|
|
<span class="boring">}
|
|
</span></code></pre></pre>
|
|
<p>Recall that the server is responsible for retrieving Alice's item from the database; thus, it will have to run the compiled <code>lookup</code> program (<code>compiled_lookup</code>).</p>
|
|
<pre><pre class="playground"><code class="language-rust no_run edition2021">
|
|
<span class="boring">#![allow(unused)]
|
|
</span><span class="boring">fn main() {
|
|
</span><span class="boring">use sunscreen::{
|
|
</span><span class="boring"> fhe_program,
|
|
</span><span class="boring"> types::{bfv::Signed, Cipher},
|
|
</span><span class="boring"> Ciphertext, CompiledFheProgram, Compiler, Error, FheProgramInput, Params, PrivateKey,
|
|
</span><span class="boring"> PublicKey, Runtime,
|
|
</span><span class="boring">};
|
|
</span><span class="boring">
|
|
</span><span class="boring">const DATABASE_SIZE: usize = 100;
|
|
</span><span class="boring">
|
|
</span><span class="boring">#[fhe_program(scheme = "bfv")]
|
|
</span><span class="boring">/// This program takes a user's query and looks up the entry in the database.
|
|
</span><span class="boring">/// Queries are arrays containing a single 1 element at the
|
|
</span><span class="boring">/// desired item's index and 0s elsewhere.
|
|
</span><span class="boring">fn lookup(query: [Cipher<Signed>; DATABASE_SIZE], database: [Signed; DATABASE_SIZE]) -> Cipher<Signed> {
|
|
</span><span class="boring"> let mut sum = query[0] * database[0];
|
|
</span><span class="boring">
|
|
</span><span class="boring"> for i in 1..DATABASE_SIZE {
|
|
</span><span class="boring"> sum = sum + query[i] * database[i]
|
|
</span><span class="boring"> }
|
|
</span><span class="boring">
|
|
</span><span class="boring"> sum
|
|
</span><span class="boring">}
|
|
</span><span class="boring">
|
|
</span><span class="boring">/// This is the server that processes Alice's query.
|
|
</span><span class="boring">struct Server {
|
|
</span><span class="boring"> /// The compiled database lookup program
|
|
</span><span class="boring"> pub compiled_lookup: CompiledFheProgram,
|
|
</span><span class="boring">
|
|
</span><span class="boring"> /// The server's runtime
|
|
</span><span class="boring"> runtime: Runtime,
|
|
</span><span class="boring">}
|
|
</span><span class="boring">
|
|
</span>impl Server {
|
|
pub fn setup() -> Result<Server, Error> {
|
|
let compiled_lookup = Compiler::with_fhe_program(lookup).compile()?;
|
|
|
|
let runtime = Runtime::new(&compiled_lookup.metadata.params)?;
|
|
|
|
Ok(Server {
|
|
compiled_lookup,
|
|
runtime,
|
|
})
|
|
}
|
|
|
|
pub fn run_query(
|
|
&self,
|
|
query: Ciphertext,
|
|
public_key: &PublicKey,
|
|
) -> Result<Ciphertext, Error> {
|
|
// Our database will consist of values between 400 and 500.
|
|
let database: [Signed; DATABASE_SIZE] = (400..(400 + DATABASE_SIZE))
|
|
.map(|x| Signed::from(x as i64))
|
|
.collect::<Vec<Signed>>()
|
|
.try_into()
|
|
.unwrap();
|
|
|
|
let args: Vec<FheProgramInput> = vec![query.into(), database.into()];
|
|
|
|
let results = self.runtime.run(&self.compiled_lookup, args, public_key)?;
|
|
|
|
Ok(results[0].clone())
|
|
}
|
|
}
|
|
<span class="boring">}
|
|
</span></code></pre></pre>
|
|
<p>The server constructs a runtime so that it can run the compiled FHE program <code>compiled_lookup</code>.</p>
|
|
<p>Using <code>run_query</code>, the server can return an (encrypted) response to Alice's query.</p>
|
|
<p>The items in the database will be the integers from 400 to 499, stored in ascending order. Recall that <code>lookup</code> takes in two arguments---the encrypted query and the unencrypted database. Unfortunately, we'll need to do some type conversion for the <code>database</code> as Sunscreen's compiler needs the <code>Signed</code> type <em>not</em> <code>i64</code> for its programs.</p>
|
|
<p>Additionally, to <code>run</code> FHE programs, we need to pass in arguments as a <code>vec</code>. Thus, we create a <code>vec</code> called <code>args</code> that contains our encrypted <code>query</code> and unencrypted <code>database</code> (which now has <code>Signed</code> entries rather than <code>i64</code> entries in it). </p>
|
|
<p>Once all that's done, the server can <code>run</code> the FHE program by passing in the <code>compiled_lookup</code> program, the arguments to the program <code>args</code> (now contained in a <code>vec</code>), and Alice's <code>public_key</code>. </p>
|
|
<h3 id="retrieving-the-item-privately"><a class="header" href="#retrieving-the-item-privately">Retrieving the item privately</a></h3>
|
|
<pre><pre class="playground"><code class="language-rust no_run edition2021"><span class="boring">use sunscreen::{
|
|
</span><span class="boring"> fhe_program,
|
|
</span><span class="boring"> types::{bfv::Signed, Cipher},
|
|
</span><span class="boring"> Ciphertext, CompiledFheProgram, Compiler, Error, FheProgramInput, Params, PrivateKey,
|
|
</span><span class="boring"> PublicKey, Runtime,
|
|
</span><span class="boring">};
|
|
</span><span class="boring">
|
|
</span><span class="boring">const DATABASE_SIZE: usize = 100;
|
|
</span><span class="boring">
|
|
</span><span class="boring">#[fhe_program(scheme = "bfv")]
|
|
</span><span class="boring">/// This program takes a user's query and looks up the entry in the database.
|
|
</span><span class="boring">/// Queries are arrays containing a single 1 element at the
|
|
</span><span class="boring">/// desired item's index and 0s elsewhere.
|
|
</span><span class="boring">fn lookup(query: [Cipher<Signed>; DATABASE_SIZE], database: [Signed; DATABASE_SIZE]) -> Cipher<Signed> {
|
|
</span><span class="boring"> let mut sum = query[0] * database[0];
|
|
</span><span class="boring">
|
|
</span><span class="boring"> for i in 1..DATABASE_SIZE {
|
|
</span><span class="boring"> sum = sum + query[i] * database[i]
|
|
</span><span class="boring"> }
|
|
</span><span class="boring">
|
|
</span><span class="boring"> sum
|
|
</span><span class="boring">}
|
|
</span><span class="boring">
|
|
</span><span class="boring">/// Alice is a party that wants to look up a value in the database without
|
|
</span><span class="boring">/// revealing what she looked up.
|
|
</span><span class="boring">struct Alice {
|
|
</span><span class="boring"> /// Alice's public key
|
|
</span><span class="boring"> pub public_key: PublicKey,
|
|
</span><span class="boring">
|
|
</span><span class="boring"> /// Alice's private key
|
|
</span><span class="boring"> private_key: PrivateKey,
|
|
</span><span class="boring">
|
|
</span><span class="boring"> /// Alice's runtime
|
|
</span><span class="boring"> runtime: Runtime,
|
|
</span><span class="boring">}
|
|
</span><span class="boring">
|
|
</span><span class="boring">impl Alice {
|
|
</span><span class="boring"> pub fn setup(params: &Params) -> Result<Alice, Error> {
|
|
</span><span class="boring"> let runtime = Runtime::new(params)?;
|
|
</span><span class="boring">
|
|
</span><span class="boring"> let (public_key, private_key) = runtime.generate_keys()?;
|
|
</span><span class="boring">
|
|
</span><span class="boring"> Ok(Alice {
|
|
</span><span class="boring"> public_key,
|
|
</span><span class="boring"> private_key,
|
|
</span><span class="boring"> runtime,
|
|
</span><span class="boring"> })
|
|
</span><span class="boring"> }
|
|
</span><span class="boring">
|
|
</span><span class="boring"> pub fn create_query(&self, index: usize) -> Result<Ciphertext, Error> {
|
|
</span><span class="boring"> let mut query = [Signed::from(0); DATABASE_SIZE];
|
|
</span><span class="boring"> query[index] = Signed::from(1);
|
|
</span><span class="boring">
|
|
</span><span class="boring"> Ok(self.runtime.encrypt(query, &self.public_key)?)
|
|
</span><span class="boring"> }
|
|
</span><span class="boring">
|
|
</span><span class="boring"> pub fn check_response(&self, value: Ciphertext) -> Result<(), Error> {
|
|
</span><span class="boring"> let value: Signed = self.runtime.decrypt(&value, &self.private_key)?;
|
|
</span><span class="boring">
|
|
</span><span class="boring"> let value: i64 = value.into();
|
|
</span><span class="boring">
|
|
</span><span class="boring"> println!("Alice received {}", value);
|
|
</span><span class="boring">
|
|
</span><span class="boring"> Ok(())
|
|
</span><span class="boring"> }
|
|
</span><span class="boring">}
|
|
</span><span class="boring">
|
|
</span><span class="boring">/// This is the server that processes Alice's query.
|
|
</span><span class="boring">struct Server {
|
|
</span><span class="boring"> /// The compiled database lookup program
|
|
</span><span class="boring"> pub compiled_lookup: CompiledFheProgram,
|
|
</span><span class="boring">
|
|
</span><span class="boring"> /// The server's runtime
|
|
</span><span class="boring"> runtime: Runtime,
|
|
</span><span class="boring">}
|
|
</span><span class="boring">
|
|
</span><span class="boring">impl Server {
|
|
</span><span class="boring"> pub fn setup() -> Result<Server, Error> {
|
|
</span><span class="boring"> let compiled_lookup = Compiler::with_fhe_program(lookup).compile()?;
|
|
</span><span class="boring">
|
|
</span><span class="boring"> let runtime = Runtime::new(&compiled_lookup.metadata.params)?;
|
|
</span><span class="boring">
|
|
</span><span class="boring"> Ok(Server {
|
|
</span><span class="boring"> compiled_lookup,
|
|
</span><span class="boring"> runtime,
|
|
</span><span class="boring"> })
|
|
</span><span class="boring"> }
|
|
</span><span class="boring">
|
|
</span><span class="boring"> pub fn run_query(
|
|
</span><span class="boring"> &self,
|
|
</span><span class="boring"> query: Ciphertext,
|
|
</span><span class="boring"> public_key: &PublicKey,
|
|
</span><span class="boring"> ) -> Result<Ciphertext, Error> {
|
|
</span><span class="boring"> // Our database will consist of values between 400 and 500.
|
|
</span><span class="boring"> let database: [Signed; DATABASE_SIZE] = (400..(400 + DATABASE_SIZE))
|
|
</span><span class="boring"> .map(|x| Signed::from(x as i64))
|
|
</span><span class="boring"> .collect::<Vec<Signed>>()
|
|
</span><span class="boring"> .try_into()
|
|
</span><span class="boring"> .unwrap();
|
|
</span><span class="boring">
|
|
</span><span class="boring"> let args: Vec<FheProgramInput> = vec![query.into(), database.into()];
|
|
</span><span class="boring">
|
|
</span><span class="boring"> let results = self.runtime.run(&self.compiled_lookup, args, public_key)?;
|
|
</span><span class="boring">
|
|
</span><span class="boring"> Ok(results[0].clone())
|
|
</span><span class="boring"> }
|
|
</span><span class="boring">}
|
|
</span><span class="boring">
|
|
</span>fn main() -> Result<(), Error> {
|
|
// Set up the database
|
|
let server = Server::setup()?;
|
|
|
|
// Alice sets herself up. The FHE scheme parameters are public to the
|
|
// protocol, so Alice has them.
|
|
let alice = Alice::setup(&server.compiled_lookup.metadata.params)?;
|
|
|
|
let query = alice.create_query(94)?;
|
|
|
|
let response = server.run_query(query, &alice.public_key)?;
|
|
|
|
alice.check_response(response)?;
|
|
|
|
Ok(())
|
|
}
|
|
</code></pre></pre>
|
|
<p>We set up the server first and then Alice (notice that Alice relies on parameters generated from the server's setup). Both of them must use the same set of FHE scheme parameters for compatibility. In deployment, these values would likely be fixed at the protocol level.</p>
|
|
<p>Alice would like to privately retrieve the item at the 94th position from the database so she calls <code>create_query</code> which encrypts her query value of <code>94</code> (i.e. we get an array that has encryptions of <code>0</code> in all positions except the 94th position which contains an encryption of <code>1</code>).</p>
|
|
<p>The server calls <code>run_query</code> to privately retrieve Alice's desired item to her. It passes in Alice's encrypted <code>query</code> along with Alice's public key (<code>alice.public_key</code>).</p>
|
|
<p>Finally, Alice can decrypt to check what item she received via <code>check_response</code>.</p>
|
|
<h3 id="performance"><a class="header" href="#performance">Performance</a></h3>
|
|
<p>The entire program (not including compilation time) takes ~5 ms on an Intel Xeon @ 3.0 GHz (with 8 cores and 16 GB RAM) and ~42 ms on a Macbook Air M1.</p>
|
|
|
|
</main>
|
|
|
|
<nav class="nav-wrapper" aria-label="Page navigation">
|
|
<!-- Mobile navigation buttons -->
|
|
<a rel="prev" href="../fhe_programs/pir_intro.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="../fhe_programs/pir_matrix.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="../fhe_programs/pir_intro.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="../fhe_programs/pir_matrix.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>
|