#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