303 lines
4.7 KiB
Plaintext
303 lines
4.7 KiB
Plaintext
|
#LyX 2.3 created this file. For more info see http://www.lyx.org/
|
||
|
|
\lyxformat 544
|
||
|
|
\begin_document
|
||
|
|
\begin_header
|
||
|
|
\save_transient_properties true
|
||
|
|
\origin unavailable
|
||
|
|
\textclass article
|
||
|
|
\begin_preamble
|
||
|
|
\usepackage{newpxtext,newpxmath}
|
||
|
|
\end_preamble
|
||
|
|
\use_default_options false
|
||
|
|
\begin_modules
|
||
|
|
theorems-ams
|
||
|
|
theorems-sec
|
||
|
|
eqs-within-sections
|
||
|
|
figs-within-sections
|
||
|
|
tabs-within-sections
|
||
|
|
theorems-named
|
||
|
|
\end_modules
|
||
|
|
\maintain_unincluded_children false
|
||
|
|
\language british
|
||
|
|
\language_package default
|
||
|
|
\inputencoding utf8
|
||
|
|
\fontencoding global
|
||
|
|
\font_roman "default" "default"
|
||
|
|
\font_sans "default" "default"
|
||
|
|
\font_typewriter "default" "default"
|
||
|
|
\font_math "auto" "auto"
|
||
|
|
\font_default_family default
|
||
|
|
\use_non_tex_fonts false
|
||
|
|
\font_sc false
|
||
|
|
\font_osf false
|
||
|
|
\font_sf_scale 100 100
|
||
|
|
\font_tt_scale 100 100
|
||
|
|
\use_microtype false
|
||
|
|
\use_dash_ligatures true
|
||
|
|
\graphics default
|
||
|
|
\default_output_format default
|
||
|
|
\output_sync 0
|
||
|
|
\bibtex_command default
|
||
|
|
\index_command default
|
||
|
|
\paperfontsize default
|
||
|
|
\spacing other 1.15
|
||
|
|
\use_hyperref true
|
||
|
|
\pdf_bookmarks true
|
||
|
|
\pdf_bookmarksnumbered false
|
||
|
|
\pdf_bookmarksopen false
|
||
|
|
\pdf_bookmarksopenlevel 1
|
||
|
|
\pdf_breaklinks false
|
||
|
|
\pdf_pdfborder true
|
||
|
|
\pdf_colorlinks false
|
||
|
|
\pdf_backref false
|
||
|
|
\pdf_pdfusetitle true
|
||
|
|
\papersize a5paper
|
||
|
|
\use_geometry true
|
||
|
|
\use_package amsmath 2
|
||
|
|
\use_package amssymb 2
|
||
|
|
\use_package cancel 0
|
||
|
|
\use_package esint 1
|
||
|
|
\use_package mathdots 0
|
||
|
|
\use_package mathtools 0
|
||
|
|
\use_package mhchem 0
|
||
|
|
\use_package stackrel 0
|
||
|
|
\use_package stmaryrd 0
|
||
|
|
\use_package undertilde 0
|
||
|
|
\cite_engine basic
|
||
|
|
\cite_engine_type default
|
||
|
|
\biblio_style plain
|
||
|
|
\use_bibtopic false
|
||
|
|
\use_indices false
|
||
|
|
\paperorientation landscape
|
||
|
|
\suppress_date false
|
||
|
|
\justification true
|
||
|
|
\use_refstyle 0
|
||
|
|
\use_minted 0
|
||
|
|
\index Index
|
||
|
|
\shortcut idx
|
||
|
|
\color #008000
|
||
|
|
\end_index
|
||
|
|
\leftmargin 1cm
|
||
|
|
\topmargin 2cm
|
||
|
|
\rightmargin 1cm
|
||
|
|
\bottommargin 2cm
|
||
|
|
\secnumdepth 3
|
||
|
|
\tocdepth 2
|
||
|
|
\paragraph_separation indent
|
||
|
|
\paragraph_indentation default
|
||
|
|
\is_math_indent 0
|
||
|
|
\math_numbering_side default
|
||
|
|
\quotes_style english
|
||
|
|
\dynamic_quotes 0
|
||
|
|
\papercolumns 1
|
||
|
|
\papersides 1
|
||
|
|
\paperpagestyle default
|
||
|
|
\tracking_changes false
|
||
|
|
\output_changes false
|
||
|
|
\html_math_output 0
|
||
|
|
\html_css_as_file 0
|
||
|
|
\html_be_strict false
|
||
|
|
\end_header
|
||
|
|
|
||
|
|
\begin_body
|
||
|
|
|
||
|
|
\begin_layout Title
|
||
|
|
Private Information Retrieval
|
||
|
|
\end_layout
|
||
|
|
|
||
|
|
\begin_layout Author
|
||
|
|
Alexander, Casper, Thomas
|
||
|
|
\end_layout
|
||
|
|
|
||
|
|
\begin_layout Section
|
||
|
|
Private Information Retrieval
|
||
|
|
\end_layout
|
||
|
|
|
||
|
|
\begin_layout Itemize
|
||
|
|
Allows a user to retrieve an item from an database, without revealing the
|
||
|
|
item to the server
|
||
|
|
\end_layout
|
||
|
|
|
||
|
|
\begin_layout Itemize
|
||
|
|
Naïve: Send the entire database to the user
|
||
|
|
\end_layout
|
||
|
|
|
||
|
|
\begin_layout Standard
|
||
|
|
\begin_inset Newpage newpage
|
||
|
|
\end_inset
|
||
|
|
|
||
|
|
|
||
|
|
\end_layout
|
||
|
|
|
||
|
|
\begin_layout Section
|
||
|
|
Simple Scheme — Definitions
|
||
|
|
\end_layout
|
||
|
|
|
||
|
|
\begin_layout Itemize
|
||
|
|
\begin_inset Formula $n=2^{s}$
|
||
|
|
\end_inset
|
||
|
|
|
||
|
|
|
||
|
|
\end_layout
|
||
|
|
|
||
|
|
\begin_layout Itemize
|
||
|
|
\begin_inset Formula $s=\log_{2}n$
|
||
|
|
\end_inset
|
||
|
|
|
||
|
|
|
||
|
|
\end_layout
|
||
|
|
|
||
|
|
\begin_layout Itemize
|
||
|
|
\begin_inset Formula $k=\log_{2}n+1=s+1$
|
||
|
|
\end_inset
|
||
|
|
|
||
|
|
|
||
|
|
\end_layout
|
||
|
|
|
||
|
|
\begin_layout Itemize
|
||
|
|
\begin_inset Formula $i\in\left[n\right]\equiv\left\{ 0,1\right\} ^{s}$
|
||
|
|
\end_inset
|
||
|
|
|
||
|
|
|
||
|
|
\end_layout
|
||
|
|
|
||
|
|
\begin_layout Itemize
|
||
|
|
\begin_inset Formula $x=x_{1},\dots,x_{n}\in\left\{ 0,1\right\} ^{n}$
|
||
|
|
\end_inset
|
||
|
|
|
||
|
|
|
||
|
|
\end_layout
|
||
|
|
|
||
|
|
\begin_layout Itemize
|
||
|
|
\begin_inset Graphics
|
||
|
|
filename simpleprop.png
|
||
|
|
scale 60
|
||
|
|
|
||
|
|
\end_inset
|
||
|
|
|
||
|
|
|
||
|
|
\end_layout
|
||
|
|
|
||
|
|
\begin_layout Standard
|
||
|
|
\begin_inset Newpage newpage
|
||
|
|
\end_inset
|
||
|
|
|
||
|
|
|
||
|
|
\end_layout
|
||
|
|
|
||
|
|
\begin_layout Section
|
||
|
|
Simple Scheme — Protocol
|
||
|
|
\end_layout
|
||
|
|
|
||
|
|
\begin_layout Standard
|
||
|
|
\begin_inset Graphics
|
||
|
|
filename simpleprot.png
|
||
|
|
width 100text%
|
||
|
|
|
||
|
|
\end_inset
|
||
|
|
|
||
|
|
|
||
|
|
\end_layout
|
||
|
|
|
||
|
|
\begin_layout Standard
|
||
|
|
|
||
|
|
\end_layout
|
||
|
|
|
||
|
|
\begin_layout Standard
|
||
|
|
\begin_inset Newpage newpage
|
||
|
|
\end_inset
|
||
|
|
|
||
|
|
|
||
|
|
\end_layout
|
||
|
|
|
||
|
|
\begin_layout Section
|
||
|
|
General Case — Definitions
|
||
|
|
\end_layout
|
||
|
|
|
||
|
|
\begin_layout Itemize
|
||
|
|
\begin_inset Formula $k$
|
||
|
|
\end_inset
|
||
|
|
|
||
|
|
databases, where
|
||
|
|
\begin_inset Formula $k\leq\log_{2}n$
|
||
|
|
\end_inset
|
||
|
|
|
||
|
|
|
||
|
|
\end_layout
|
||
|
|
|
||
|
|
\begin_layout Itemize
|
||
|
|
Integers represented using
|
||
|
|
\begin_inset Formula $s$
|
||
|
|
\end_inset
|
||
|
|
|
||
|
|
-bit long sequences with exactly
|
||
|
|
\begin_inset Formula $k-1$
|
||
|
|
\end_inset
|
||
|
|
|
||
|
|
occurrences of
|
||
|
|
\begin_inset Formula $1$
|
||
|
|
\end_inset
|
||
|
|
|
||
|
|
in them
|
||
|
|
\end_layout
|
||
|
|
|
||
|
|
\begin_layout Itemize
|
||
|
|
\begin_inset Formula $s$
|
||
|
|
\end_inset
|
||
|
|
|
||
|
|
defined as minimum
|
||
|
|
\begin_inset Formula $s$
|
||
|
|
\end_inset
|
||
|
|
|
||
|
|
satisfying
|
||
|
|
\begin_inset Formula $\left(\begin{array}{c}
|
||
|
|
s\\
|
||
|
|
k-1
|
||
|
|
\end{array}\right)\geq n$
|
||
|
|
\end_inset
|
||
|
|
|
||
|
|
|
||
|
|
\end_layout
|
||
|
|
|
||
|
|
\begin_layout Itemize
|
||
|
|
Our case:
|
||
|
|
\begin_inset Formula $k=2\implies s=n$
|
||
|
|
\end_inset
|
||
|
|
|
||
|
|
|
||
|
|
\end_layout
|
||
|
|
|
||
|
|
\begin_layout Itemize
|
||
|
|
\begin_inset Graphics
|
||
|
|
filename generalprops.png
|
||
|
|
scale 60
|
||
|
|
|
||
|
|
\end_inset
|
||
|
|
|
||
|
|
|
||
|
|
\end_layout
|
||
|
|
|
||
|
|
\begin_layout Section
|
||
|
|
General Case — Protocol
|
||
|
|
\end_layout
|
||
|
|
|
||
|
|
\begin_layout Standard
|
||
|
|
\begin_inset Graphics
|
||
|
|
filename advancedprot.png
|
||
|
|
width 100line%
|
||
|
|
|
||
|
|
\end_inset
|
||
|
|
|
||
|
|
|
||
|
|
\end_layout
|
||
|
|
|
||
|
|
\begin_layout Standard
|
||
|
|
\begin_inset Newpage newpage
|
||
|
|
\end_inset
|
||
|
|
|
||
|
|
|
||
|
|
\end_layout
|
||
|
|
|
||
|
|
\end_body
|
||
|
|
\end_document
|