<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40"><head><meta http-equiv=Content-Type content="text/html; charset=us-ascii"><meta name=Generator content="Microsoft Word 15 (filtered medium)"><style><!--
/* Font Definitions */
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri","sans-serif";}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:#0563C1;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:#954F72;
text-decoration:underline;}
p.MsoListParagraph, li.MsoListParagraph, div.MsoListParagraph
{mso-style-priority:34;
margin-top:0in;
margin-right:0in;
margin-bottom:0in;
margin-left:.5in;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri","sans-serif";}
span.EmailStyle17
{mso-style-type:personal-compose;
font-family:"Calibri","sans-serif";
color:windowtext;}
.MsoChpDefault
{mso-style-type:export-only;
font-family:"Calibri","sans-serif";}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
div.WordSection1
{page:WordSection1;}
/* List Definitions */
@list l0
{mso-list-id:1497068012;
mso-list-type:hybrid;
mso-list-template-ids:-658752346 67698705 67698713 67698715 67698703 67698713 67698715 67698703 67698713 67698715;}
@list l0:level1
{mso-level-text:"%1\)";
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l0:level2
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l0:level3
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
@list l0:level4
{mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l0:level5
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l0:level6
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
@list l0:level7
{mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l0:level8
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l0:level9
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
ol
{margin-bottom:0in;}
ul
{margin-bottom:0in;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]--></head><body lang=EN-US link="#0563C1" vlink="#954F72"><div class=WordSection1><p class=MsoNormal>“Fully Homomorphic Encryption” is all the rage in academic communities, and there is general consensus that it’s performance is unacceptable except in certain special cases, but it’s also true that lots of people are coming up with new mechanisms to speed it up – both in general and in the form of finding more special cases.<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>I’m trying to figure out what the performance penalty is in the most general case, and in particular whether that performance penalty is bounded or unbounded. In other words, could I do anything I wanted if I were willing to pay – say – a 2^64 performance penalty, or are there some calculations whose performance penalty would be larger than that.<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>I imagine the following as a “proof of principle” Turing-machine sort of computational engine:<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoListParagraph style='text-indent:-.25in;mso-list:l0 level1 lfo1'><![if !supportLists]><span style='mso-list:Ignore'>1)<span style='font:7.0pt "Times New Roman"'> </span></span><![endif]>Given the encryption key K, I can encrypt a single bit (0 or 1) and get an encrypted quantity X bits long.<o:p></o:p></p><p class=MsoListParagraph style='text-indent:-.25in;mso-list:l0 level1 lfo1'><![if !supportLists]><span style='mso-list:Ignore'>2)<span style='font:7.0pt "Times New Roman"'> </span></span><![endif]>Given the encryption key K and any value X bits long, I can decrypt and get either 0, 1, or “invalid” (where if the value was generated by an encrypt operation, I’ll get back the value I encrypted).<o:p></o:p></p><p class=MsoListParagraph style='text-indent:-.25in;mso-list:l0 level1 lfo1'><![if !supportLists]><span style='mso-list:Ignore'>3)<span style='font:7.0pt "Times New Roman"'> </span></span><![endif]>Without knowing the encryption key K, but given two validly encrypted values A and B – each X bits long – I can compute a third value C this is a validly encrypted representation of A NAND B.<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>If I had these primitives, I believe I could compute any computable quantity without knowing the encryption key, and I could measure the performance of the system according to how big X is, how long it takes to do the computation of step 3, and to a lesser degree how long the encryption and decryption operations take.<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>Is the state of the art in Homomorphic Encryption such that a simple system like the above possible? If so, what is the required size of X and how long do each of the operations take?<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal> --Charlie<o:p></o:p></p></div></body></html>