tag:blogger.com,1999:blog-33291100153613445772024-03-13T20:27:36.562+01:00HEAT Project BlogThe blog for the EU H2020 funded project HEAT on Homomorphic EncryptionNigel Smarthttp://www.blogger.com/profile/17681184541012804026noreply@blogger.comBlogger35125tag:blogger.com,1999:blog-3329110015361344577.post-50633159598026326492017-04-28T16:30:00.002+02:002017-04-28T16:30:59.197+02:00Faster Homomorphic Function Evaluation using Non-Integral Base Encoding.<div dir="ltr" style="text-align: left;" trbidi="on">
Homomorphic evaluation of arithmetic circuits is exactly what FHE and SHE schemes were created for. In practice, those circuits imply the use of real numbers which seems inconsistent with the fact that the plaintext space of the most efficient and commonly used FHE/SHE schemes is of the form<br />
<div>
$$R_t = \mathbb{Z}_t[X]/(X^d+1).$$</div>
<div>
Thus, basically we must encode real values into polynomials, which is done by expansion with respect to a base $b$ and then replacing all occurrences of $b$ by $X$. But then the problem arises of what SHE parameters to choose. Indeed, each homomorphic operation increases the encoding coefficients, so after a few consecutive multiplications this may lead to wrapping around modulo $t$ and invalid decoding results. To solve this problem $t$ must be chosen big enough. However, at the same time it should be small to suppress the growth of the inherent noise inside ciphertexts, in order to decrypt correctly. In practice, this problem is solved by the Chinese Remainder theorem (CRT) that splits a homomorphic algorithm into a number of threads with different plaintext spaces each modulo a factor of $t$. Nevertheless, to reduce the number of threads it is desirable to be able to take $t$ as small as possible.<br />
To decrease the plaintext modulus one should choose an encoding scheme such that the encoding coefficients are as small as possible. The first such algorithm was presented by <a href="https://www.microsoft.com/en-us/research/wp-content/uploads/2015/11/ManualHE.pdf" target="_blank">Dowlin et al.</a> and studied by our colleagues <a href="http://heat-h2020-project.blogspot.be/2016/07/fixed-point-arithmetic.html" target="_blank">Costache et al.</a> This approach uses a balanced base $b=3$ representation where each coefficient belongs to the set $\{-1,0,1\}$. However, this choice is not optimal, because the degrees of the outcomes of the homomorphic computations are much smaller than required by the security recommendations of the underlying SHE scheme.<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjK5JdZHEk_HbBIex2h54iL1WB5BkVMfKHu5vwrug_MnM9g31xpSe4bBaFD0Nr8WvNHiN7oCT_mZzIxcdwvqjp7i1K_05HxnIliEA2HvCRsP1iDYpKcrOnjp_3rSCOfsyhyphenhyphen6dD-4A4yAXM/s1600/Screen+Shot+2017-04-12+at+11.09.20.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="220" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjK5JdZHEk_HbBIex2h54iL1WB5BkVMfKHu5vwrug_MnM9g31xpSe4bBaFD0Nr8WvNHiN7oCT_mZzIxcdwvqjp7i1K_05HxnIliEA2HvCRsP1iDYpKcrOnjp_3rSCOfsyhyphenhyphen6dD-4A4yAXM/s320/Screen+Shot+2017-04-12+at+11.09.20.png" width="320" /></a></div>
<br />
On the picture above the grey zone denotes the available plaintext space while the dark one is what actually was used. The lion's share of the plaintext space stays untouched. To use that space more efficiently, one might reduce the degree $d$ but it induces a significant decrease in the security level. Hence, informally, the optimisation problem consists in "squashing" the grey zone such that it almost coincides with the dark one as shown on the picture below.<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgYYlK-4zZf9WBFaeFJgNDJ3ZYoYss3IquY16XZnblMgkmBdG86b02XB1kVXGkNJoUeBbP2edufEGBo4q5QN5VZYXpah6hI1WCxG031C0P07b03TZm-tvRHShp5WmJFrjyJb2MpHYLs3XY/s1600/Screen+Shot+2017-04-12+at+11.09.42.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="189" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgYYlK-4zZf9WBFaeFJgNDJ3ZYoYss3IquY16XZnblMgkmBdG86b02XB1kVXGkNJoUeBbP2edufEGBo4q5QN5VZYXpah6hI1WCxG031C0P07b03TZm-tvRHShp5WmJFrjyJb2MpHYLs3XY/s320/Screen+Shot+2017-04-12+at+11.09.42.png" width="320" /></a></div>
Our idea is to encode real numbers with long but very sparse polynomials. In this setting the non-zero coefficients group together to a lesser extent, thereby hopefully decreasing the required plaintext modulus. One such representation is already well-known, namely, w-NAF. It is a base $b=2$ representation with coefficients from the set $\{0, \pm1, \pm3, \dots, \pm2^{w-1}-1\}$ and the property that any $w$ consecutive coefficients have at most one non-zero. Bigger $w$'s reduce the average number of non-zero digits but increase their size, which is problematic for our needs as it imposes the coefficients to grow exponentially. To address this issue we switch from the base $b=2$ to a smaller non-integral base $b>1$. Then it will be possible to construct a w-NAF-like encoding but only with the smallest possible set of digits $\{-1,0,1\}$. We called this representation "w-NIBNAF" which can be read as "non-integral base w-NAF".<br />
For any real number $a$ the w-NIBNAF algorithm generates a ternary sequence $a_0, \dots, a_n$ in the following way:<br />
<br />
<ol style="text-align: left;">
<li>Define the base $b_w$ as the unique positive root of the polynomial \[F_w(x) = x^{w+1} - x^w - x - 1.\]</li>
<li>Find a power $r$ such that $t = -b_w^r$ or $b_w^r$ is the closest number to $a$.</li>
<li>$a_r =$ sgn$(t)$</li>
<li>Go to step 2 with $a \leftarrow a - t$. </li>
</ol>
<br />
The algorithm stops when $t < \varepsilon$ for some real $\varepsilon$ which determines the precision of the encoding.<br />
<br />
Our w-NIBNAF representation drastically reduces the average number of non-zero coefficients per representation. We encoded 10 000 random integers in the range from $-2^{40}$ to $2^{40}$ with the precision $\varepsilon = 1$ and found that even for 1-NIBNAF the percentage of non-zeros is around 50 percent while it is 67 percent for balanced ternary expansions. It means that the w-NIBNAF encoding leads to smaller coefficients in the worst case where the input values of an arithmetic circuit are chosen such that the circuit output contains the maximal possible coefficient.<br />
<br />
To illustrate the practical impact of the new encoding scheme we applied 950-NIBNAF to a non-trivial arithmetic circuit containing multiplications and additions. The choice of the circuit was motivated by the load forecasting use-case of the HEAT discussed in <a href="http://heat-h2020-project.blogspot.be/2016/12/privacy-friendly-forecasting-for-smart.html" target="_blank">our previous paper</a>. In a nutshell, the prediction was performed there by a neural-network-like structure that can be expressed by a polynomial with real coefficients and degree 16. To preserve correct evaluation of the algorithm with balanced ternary expansion, it required to take the plaintext modulus around 104 bits long. This huge modulus imposes to use a CRT decomposition of the plaintext space that boosts up the execution time of the homomorphic algorithm to 32 seconds per run. Evaluated with 950-NIBNAF encodings the same circuit needs only 6 bits for a plaintext modulus, and as a consequence does not require to split the plaintext space. Hence, one run takes only 2.5 seconds that is a speed-up by a factor 13.<br />
<br />
A more thorough explanation with sharp bounds on the maximal coefficients can be found via <a href="http://eprint.iacr.org/2017/333" target="_blank">ePrint IACR archive</a>.<br />
<br />
The KU Leuven and NXP teams of the HEAT project.</div>
<span style="background-color: #bd081c; background-position: 3px 50%; background-repeat: no-repeat no-repeat; background-size: 14px 14px; border-bottom-left-radius: 2px; border-bottom-right-radius: 2px; border-top-left-radius: 2px; border-top-right-radius: 2px; border: none; color: white; cursor: pointer; display: none; font-family: "helvetica neue" , "helvetica" , sans-serif; font-size: 11px; font-style: normal; font-weight: bold; left: 193px; line-height: 20px; opacity: 1; padding: 0px 4px 0px 0px; position: absolute; text-align: center; text-indent: 20px; top: 634px; width: auto; z-index: 8675309;">Save</span><span style="background-color: #bd081c; background-position: 3px 50%; background-repeat: no-repeat no-repeat; background-size: 14px 14px; border-bottom-left-radius: 2px; border-bottom-right-radius: 2px; border-top-left-radius: 2px; border-top-right-radius: 2px; border: none; color: white; cursor: pointer; display: none; font-family: "helvetica neue" , "helvetica" , sans-serif; font-size: 11px; font-style: normal; font-weight: bold; left: 193px; line-height: 20px; opacity: 1; padding: 0px 4px 0px 0px; position: absolute; text-align: center; text-indent: 20px; top: 634px; width: auto; z-index: 8675309;">Save</span><span style="background-color: #bd081c; background-position: 3px 50%; background-repeat: no-repeat no-repeat; background-size: 14px 14px; border-bottom-left-radius: 2px; border-bottom-right-radius: 2px; border-top-left-radius: 2px; border-top-right-radius: 2px; border: none; color: white; cursor: pointer; display: none; font-family: "helvetica neue" , "helvetica" , sans-serif; font-size: 11px; font-style: normal; font-weight: bold; left: 193px; line-height: 20px; opacity: 1; padding: 0px 4px 0px 0px; position: absolute; text-align: center; text-indent: 20px; top: 634px; width: auto; z-index: 8675309;">Save</span><span style="background-color: #bd081c; background-position: 3px 50%; background-repeat: no-repeat no-repeat; background-size: 14px 14px; border-bottom-left-radius: 2px; border-bottom-right-radius: 2px; border-top-left-radius: 2px; border-top-right-radius: 2px; border: none; color: white; cursor: pointer; display: none; font-family: "helvetica neue" , "helvetica" , sans-serif; font-size: 11px; font-style: normal; font-weight: bold; left: 193px; line-height: 20px; opacity: 1; padding: 0px 4px 0px 0px; position: absolute; text-align: center; text-indent: 20px; top: 634px; width: auto; z-index: 8675309;">Save</span><br />
<span style="background-color: #bd081c; background-position: 3px 50%; background-repeat: no-repeat no-repeat; background-size: 14px 14px; border-bottom-left-radius: 2px; border-bottom-right-radius: 2px; border-top-left-radius: 2px; border-top-right-radius: 2px; border: none; color: white; cursor: pointer; display: none; font-family: "helvetica neue" , "helvetica" , sans-serif; font-size: 11px; font-style: normal; font-weight: bold; left: 193px; line-height: 20px; opacity: 1; padding: 0px 4px 0px 0px; position: absolute; text-align: center; text-indent: 20px; top: 324px; width: auto; z-index: 8675309;">Save</span><span style="background-color: #bd081c; background-position: 3px 50%; background-repeat: no-repeat no-repeat; background-size: 14px 14px; border-bottom-left-radius: 2px; border-bottom-right-radius: 2px; border-top-left-radius: 2px; border-top-right-radius: 2px; border: none; color: white; cursor: pointer; display: none; font-family: "helvetica neue" , "helvetica" , sans-serif; font-size: 11px; font-style: normal; font-weight: bold; left: 193px; line-height: 20px; opacity: 1; padding: 0px 4px 0px 0px; position: absolute; text-align: center; text-indent: 20px; top: 324px; width: auto; z-index: 8675309;">Save</span></div>
Anonymoushttp://www.blogger.com/profile/16933150924637510682noreply@blogger.com0tag:blogger.com,1999:blog-3329110015361344577.post-47747168011751485542017-02-21T21:20:00.000+01:002017-02-21T21:20:19.150+01:00Homomorphic Encryption API Software Library<div dir="ltr" style="text-align: left;" trbidi="on">
<div style="text-align: justify;">
The <i>Homomorphic Encryption Application Programming Interface</i> (HE-API) software library is an open source software library being developed as part of the <a href="http://heat-project.eu/">Homomorphic Encryption Applications and Technology</a> (HEAT) project, and is available <a href="http://github.com/bristolcrypto/HEAT">here</a>.
The main purpose of this software library is to provide a common
easy-to-use interface for various existing Somewhat Homomorphic
Encryption (SHE) libraries. Limited support for fixed-point arithmetic
is also provided by this library. Note that the HE-API library is still a
work in progress.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
Fully
Homomorphic Encryption (FHE) is a cryptographic primitive that allows
meaningful manipulation of ciphertexts. In spite of several recent
advances, FHE remains out of practical reach. Hence a reasonable
restriction to make is to limit the set of evaluated circuits to a
specified subclass, usually determined by the multiplicative depth of
the circuit. Such encryption schemes are called as SHE schemes. Various
libraries such as <a href="http://github.com/shaih/HElib">HElib</a>, <a href="http://sealcrypto.codeplex.com/">SEAL</a>, <a href="http://github.com/CryptoExperts/FV-NFLlib">FV-NFLlib</a>, <a href="http://github.com/tricosset/HElib-MP">HElib-MP</a>, etc., are already available that implement these SHE schemes.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
The
purpose of this HE-API software library is to provide a common,
generic, easy-to-use interface for various existing libraries that
implement SHE schemes. The SHE libraries that are currently integrated
in the HE-API library are HElib and FV-NFLlib. It may be noted that the
FV-NFLlib library is itself an outcome of the HEAT project. At a
high-level, the HE-API software library abstracts out the technicalities
present in the underlying SHE libraries. For instance, the HElib
library implements the <a href="http://eprint.iacr.org/2011/277">BGV SHE scheme</a>, while the FV-NFLlib implements the <a href="http://eprint.iacr.org/2012/144">FV SHE scheme</a>.
Needless to say, the syntax for various classes and routines in the
individual libraries will be different, though the underlying semantics
are very similar. The HE-API library integrates the underlying SHE
libraries under a single interface, thereby shielding the user from
syntactic differences. Another feature of the HE-API library is that it
contains minimal, yet complete, set of routines to perform homomorphic
computations. The design of this library is motivated by the ease of use
for non-experts.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
<b>Supported Data Types</b></div>
<div style="text-align: justify;">
The following application data types are supported by the HE-API software library. </div>
<div style="text-align: justify;">
<ul>
<li>Boolean</li>
<li><span style="font-family: inherit;">Unsigned long integers</span></li>
<li><a href="http://gmplib.org/">GMP</a>'s arbitrary precision integers class: <span style="font-family: "courier new" , "courier" , monospace;">mpz_class</span></li>
<li>Polynomials with coefficients of type: <span style="font-family: inherit;">unsigned long integers</span> or <span style="font-family: "courier new" , "courier" , monospace;">mpz_class</span></li>
<li>Vectors of : <span style="font-family: inherit;">unsigned long integers</span> or <span style="font-family: "courier new" , "courier" , monospace;">mpz_class</span></li>
<li>Fixed-point numbers</li>
</ul>
Note that all the data types and routines described above may <i>not</i> be currently supported by every underlying SHE library.</div>
<div style="text-align: justify;">
<br /></div>
</div>
Srinivas Vivekhttp://www.blogger.com/profile/12521171190366779104noreply@blogger.com0tag:blogger.com,1999:blog-3329110015361344577.post-532217744463200902016-12-20T16:05:00.002+01:002016-12-20T16:07:14.827+01:00Privacy-friendly Forecasting for the Smart Grid using Homomorphic Encryption and the Group Method of Data Handling<div dir="ltr" style="text-align: left;" trbidi="on">
<div style="text-align: justify;">
Machine learning has become more and more popular last years. Every day new applications appear on the market such as augmented reality, pattern recognition, intelligent search, personal recommendations, forecasting etc. Big companies like Google, Amazon, Apple use comprehensive statistical models to improve their business. They rely on immense amounts of data that clients provide through different on-line services. This information can be very privacy sensitive and causes immediate damage after unapproved disclosure.</div>
<div style="text-align: justify;">
The question, then, arises: how can private data be encrypted and managed at the same time by machine learning algorithms? In <a href="http://eprint.iacr.org/2016/1117" target="_blank">our recent paper</a> we tried to answer this question for the load forecasting problem in the <i>smart-grid </i>using homomorphic encryption.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: left;">
<div style="text-align: justify;">
The idea behind the smart-grid technology is very simple. It assumes that a client housing and a service provider are equipped with communication devices called <i>smart-meters</i>. These allow to transmit current information about load consumption, weather conditions, current financial information, structure of a local utility grid etc. A service provider can apply statistical techniques in order to forecast energy demand for a next period of time. Having predictions clients might control their consumption more efficiently and public utilities may optimise production and logistic costs to lower prices or avoid blackouts.<br />
<br />
One popular class of prediction algorithms is based on artificial neural networks. ANNs compute the so-called activation functions, in practice it is common to use a sigmoid function where the logistic function $t \mapsto 1/(1 + e^{−t})$ is a popular choice. Due to the highly non-linear nature computing such a sigmoid function homomorphically is far from practical. To overcome that issue one can substitute a sigmoid by a polynomial function that was done recently in papers of <a href="https://arxiv.org/abs/1412.6181" target="_blank">Xie et al.</a> and <a href="https://www.microsoft.com/en-us/research/publication/cryptonets-applying-neural-networks-to-encrypted-data-with-high-throughput-and-accuracy/" target="_blank">Dowlin et al.</a> for pattern recognition purposes. But there exist an older statistical approach built especially for prediction purposes by a Soviet computer scientist <a href="https://en.wikipedia.org/wiki/Alexey_Grigorevich_Ivakhnenko" target="_blank">Alexey Ivakhnenko</a> in <a href="http://www.sciencedirect.com/science/article/pii/0005109870900920" target="_blank">1970</a>. It is called the Group Method of Data Handling (GMDH).<br />
<br /></div>
</div>
<div style="text-align: justify;">
GMDH takes a history of the system outcome $\{x_i\}$ and construct truncated Wiener series to approach the next output value<br />
<br />
$a_0 + \sum_{i=1}^{n_0} a_i x_i + \sum_{i=1}^{n_0} \sum_{j=i}^{n_0} a_{ij} x_i x_j + \sum_{i=1}^{n_0} \sum_{j=i}^{n_0} \sum_{k=j}^{n_0} a_{ijk} x_i x_j x_k + \dots$<br />
<br />
In the original paper this polynomial is called a Kolmogorov-Gabor polynomial and it can be nicely illustrated in a neural network manner<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiV16tpUyMpOoJ8GVS8CMiLDdVtdiMA-nY6_gUQjE_LULoyvPB5d_OdM4_rTdlcA19pDvrtPwTwqZ0aEQ7Yblduq_sa4mcrhok3e4Dx35YACa1zfj5b1YM9Q3xSqKyMAaoxixWRD8CHlq0/s1600/Screen+Shot+2016-12-19+at+14.30.08.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiV16tpUyMpOoJ8GVS8CMiLDdVtdiMA-nY6_gUQjE_LULoyvPB5d_OdM4_rTdlcA19pDvrtPwTwqZ0aEQ7Yblduq_sa4mcrhok3e4Dx35YACa1zfj5b1YM9Q3xSqKyMAaoxixWRD8CHlq0/s1600/Screen+Shot+2016-12-19+at+14.30.08.png" /></a></div>
<br />
<br />
where each node has only two input edges and its own activation function described by a quadratic polynomial over real numbers<br />
<br />
$\nu_{ij} : \textbf{R}^2 \rightarrow \textbf{R}: (x, y) \mapsto b_{ij0} + b_{ij1} x + b_{ij2} y + b_{ij3} xy + b_{ij4} x^2 + b_{ij5} y^2.$<br />
<br />
The learning phase determines the polynomial coefficients and the wiring of nodes while the number of layers and the number of nodes at each layer are fixed in the beginning. Actually, one should solve a linear regression problem at each node and decide whether this node is among the "best" ones in a layer in terms of error performance. As a result a GMDH neural network can be expressed by an arithmetic circuit of multiplicative depth equal to the number of layers. This construction is a perfect match for homomorphic evaluation.<br />
<br />
To perform experiments on real data we found a <a href="http://www.ucd.ie/issda/data/commissionforenergyregulationcer/" target="_blank">source</a> provided by Irish government over 5000 housings and commercial buildings. It turns out that the prediction performance of ANNs for individual housings is quite <a href="https://arxiv.org/abs/1404.0200" target="_blank">low</a>. But combining a few houses makes the forecasting error decrease drastically. Thus we considered aggregated consumption for 10 house combinations which correspond to small apartment complexes where privacy issues still make sense.<br />
<br />
Finally, we applied an FV SHE scheme on top of the forecasting algorithm together with a fixed-point representation of real numbers recently studied by <a href="https://eprint.iacr.org/2016/250" target="_blank">Costache et al</a>. The simplest GMDH network with 4 layers was chosen to show reasonable error performance. The resulting algorithm evaluates a load demand for the next 30 min with relative error around 20% which is comparable with modern ANNs. The computation of one prediction takes 90 seconds in the sequential mode or 4 seconds in the parallel implementation on an average laptop equipped with an Intel Core i5-3427U CPU (running at 1.80GHz). <br />
<br />
Please, check <a href="http://eprint.iacr.org/2016/1117">http://eprint.iacr.org/2016/1117</a> for further details.<br />
</div>
</div>
Anonymoushttp://www.blogger.com/profile/16933150924637510682noreply@blogger.com0tag:blogger.com,1999:blog-3329110015361344577.post-73170842684577500962016-11-28T15:00:00.000+01:002016-11-28T15:00:12.767+01:00Interval arithmetic and practical lattice reduction<div dir="ltr" style="text-align: left;" trbidi="on">
<div style="text-align: left;">
</div>
<h2 style="text-align: left;">
IALatRed in a Nutshell</h2>
<div style="text-align: left;">
<div style="text-align: justify;">
Lattice reduction is fundamental in computational number theory and in computer science, especially in cryptography. The celebrated Lenstra–Lenstra–Lovász reduction algorithm (called <i>LLL</i> or <i>L3</i>) has been improved in many ways through the past decades and remains one of the central tool for reducing lattice basis. In particular, its floating-point variants — where the long-integer arithmetic required by Gram–Schmidt orthogonalization is replaced by floating-point arithmetic — are now the fastest known. Yet, the running time of these floating-point versions is mostly determined by the precision needed to perform sound computations: theoretical lower bounds are large whereas the precision actually needed on average is much lower. IALatRed is a proof-of-concept of an adaptive precision version of<i> LLL</i>, one of its variant <i>Potential-LLL</i> and the <i>BKZ</i> reduction. In these algorithms, floating-point arithmetic is replaced by Interval Arithmetic. The certification property of interval arithmetic enables runtime detection of precision defects in numerical computations and accordingly, makes it possible to run the reduction algorithms with guaranteed nearly optimal precision. As such, these adaptive reduction algorithms run faster than the state-of-the-art implementations, while still being provable.</div>
<br />
</div>
<h2 style="text-align: left;">
A brief history of lattice reduction</h2>
<div style="text-align: justify;">
Lattices are defined as additive discrete subgroups of $\mathbb{R}^n$, <i> i.e.</i> the integer span $L(\mathbf{b_1}, \ldots \mathbf{b_d}) = \bigoplus_{i=1}^d \mathbb{Z} \mathbf{b_i}$ of a linearly independent family of vectors $\mathbf{b_1}, \ldots, \mathbf{b_d}$ in $\mathbb{R}^n$. Such a family is called a <i>basis</i> of the lattice, and is not unique. Nevertheless, all the bases of a given lattice have the same number of elements, $d$, which is called the *dimension* of the lattice. Among the infinite number of different bases of a n-dimensional lattice with $n\geq 2$, some have interesting properties, such as having reasonably small vectors and low orthogonality defect. Finding such reduced bases is the goal of *lattice reduction* theory and has been crucial in several fields of computer science and mathematics, especially in cryptology. For instance, lattices have been used to break many public-key cryptosystems in the last decades, including knapsack cryptosystems or RSA in specific settings thanks to Coppersmith's method.<br />
<br />
The problem of finding good bases goes back to the early works of Lagrange and Gauss, for dimension two lattices, and the introduction of the Gauss algorithm, even though first introduced by Lagrange. This procedure can be seen as a 2-dimensional extension of the well-known Euclid algorithm for computing the greatest common divisor of two integers. In 1850, Hermite published the first reduction algorithm for arbitrary dimension. A century later, in 1982, Lenstra, Lenstra and Lovász designed the <i>LLL</i> algorithm, with the polynomial factorization problem as an application, after the celebrated work of Lenstra on integer programming. This algorithm is a milestone in the history of lattice reduction algorithms, being the first algorithm whose running-time is polynomial, for arbitrary dimension. This work has been improved in multiple ways among others by Kaltofen, Schnorr, and Gama and Nguyen, decreasing the time complexity or improving the quality of the reduction.</div>
<h2 style="text-align: left;">
</h2>
<h2 style="text-align: left;">
A bird's eye view on <i>Interval Arithmetic</i></h2>
<div style="text-align: left;">
<div style="text-align: justify;">
Interval arithmetic is a representation of reals by intervals — whose endpoints are floating-point numbers — that contain them. Arithmetic operations, in particular the basic operations $+$, $-$, $\times$ , $\div$ can be redefined in this context. The main interest of this representation lies in its <i>certification</i> property: if real numbers are represented by intervals, the interval resulting from the evaluation of an algebraic expression contains the exact value of the evaluated expression.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
If the birth of Lattice Reduction is well-dated, it is not the case of Interval Arithmetic. For some authors, it has been introduced by R. Moore in 1962 in his PhD thesis. For others it can be dated back in 1958 in an article of T. Sunaga which describes an algebraic interpretation of the lattice of real intervals, or even sooner in 1931 as a proposal in the PhD thesis of R.C. Young at Cambridge. Nonetheless its development and industrial applications have to wait for 1980, and the momentum of U. Kulisch in Karlsruhe, leading IBM to develop a specific instruction set and a compiler natively integrating Interval Arithmetic. Its main asset — calculating directly on sets — is nowadays used to deterministically determine the global extrema of a continuous function or determining the zeroes of a function and proving their existence. Another application of Interval Arithmetic is to be able to detect lack of precision at run-time of numerical algorithms, thanks to the guarantees it provides on computations.</div>
<br />
</div>
<h2 style="text-align: left;">
Mixing the two of them: IALatred</h2>
<div style="text-align: left;">
<div style="text-align: justify;">
This last application can lead to the design of adaptive precision numerical algorithms. In particular e transformed the celebrated <i>LLL</i> algorithm into an adaptive precision version, leading to design a <i>provable</i> reduction algorithm which in some cases even run faster than the state-of-the-art standard <i>FpLLL</i> of D. Stehle <i>et al. </i>We also applied this technique to a stronger variant of <i>LLL</i>, called <i>Potential-LLL</i>, first introduced by Fontain et al., with similar results, as well as the stronger <i>BKZ</i> algorithm.</div>
<br />
<br />
<div style="text-align: justify;">
<b>Paper available at</b> <a href="https://almasty.lip6.fr/~espitau/bin/AdaptiveLLL.pdf">https://almasty.lip6.fr/~espitau/bin/AdaptiveLLL.pdf</a> </div>
<div style="text-align: justify;">
<b>Code provided at </b><a href="https://almasty.lip6.fr/~espitau/latred.html">https://almasty.lip6.fr/~espitau/latred.html</a></div>
<br /></div>
</div>
Anonymoushttp://www.blogger.com/profile/05342055369323273918noreply@blogger.com0tag:blogger.com,1999:blog-3329110015361344577.post-31448227579143937052016-07-20T14:05:00.000+02:002016-07-21T15:28:09.939+02:00Full RNS Implementation of Fan Vercauteren scheme<div style="text-align: justify;">
In a paper (<a href="https://eprint.iacr.org/2016/510">https://eprint.iacr.org/2016/510</a>), Jean-Claude Bajard, Julien Eynard, Anwar Hasan and Vincent Zucca explain how to perform the division and rounding steps occurring during decryption and homomorphic multiplication procedures of scale invariant schemes such as FV and YASHE without using any multi-precision library. </div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
Such schemes, based on RLWE, usually lie in a power-of-two cyclotomic ring $\mathcal{R} = \mathbb{Z}[X]/(X^n+1)$ for efficiency reasons. In FV scheme, a ciphertext $\texttt{c} = (\texttt{c}_0, \texttt{c}_1)$ is a polynomial of degree 1 with coefficients in $\mathcal{R}_q = \mathbb{Z}_q[X]/(X^n+1)$. Each $\texttt{c}_i$ is then represented as a polynomial of degree $n-1$ with coefficients in $\mathbb{Z}_q$, $q$ is usually chosen as a product of several small prime moduli $q_i$. This allows to represent the integer coefficients of the $\texttt{c}_i$'s, through the Chinese Reminder Theorem (CRT), by their residues modulo the smaller $q_i$'s. However the use of the Residue Number System (a.k.a non-positional CRT representation) remains hardly compatible with procedures involving coefficient-wise division and rounding which require costly comparisons to be performed. Thus, until now, one had to invert the CRT representation and then use multi-precision arithmetic to perform these steps. </div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
The techniques presented in this paper allow to perform these steps directly in RNS permiting to avoid a costly conversion between RNS and positional system and the use of multi-precision library. Compared with the FV-NFLlib implementation (<a href="https://github.com/CryptoExperts/FV-NFLlib">https://github.com/CryptoExperts/FV-NFLlib</a>) it enables speed-ups from a factor 5 to 20 for decryption and from 2 to 4 for homomorphic multiplication. It may also lead to future implementations on highly parallel accelerator cards such as GPU. This paper will be presented at SAC (<a href="http://www.engr.mun.ca/~sac2016/">http://www.engr.mun.ca/~sac2016/</a>), in St John's Canada, in August, this blog post briefly presents it.</div>
<b><br /></b>
<br />
<div style="text-align: justify;">
<b>Decryption</b></div>
<div style="text-align: justify;">
A plaintext $\texttt{m}$ is an element of $\mathcal{R}_t = \mathbb{Z}_t[X]/(X^n+1)$, after being encrypted it becomes a ciphertext $\texttt{c} = (\texttt{c}_0,\texttt{c}_1)\in (\mathcal{R}_q)^2$ with $t < q$. To recover the message the decryption procedure consists in computing $[\lfloor t/q(\texttt{c}_0+\texttt{c}_1 \texttt{s}) \rceil]_t$ with $\texttt{s}$ the secret key.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
There are two difficulties to perform this computation in RNS. First $\texttt{c}'=t(\texttt{c}_0+\texttt{c}_1 \texttt{s})$ lies in $\mathcal{R}_q$ and is represented in the "native" RNS base $\mathcal{B}_q = \{q_1,....,q_k\}$ with $q = q_1...q_k$. Thus in base $\mathcal{B}_q$, it is impossible to perform the division by $q$. Second computing a rounding is unnatural in a non-positional systeme like RNS.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
To overcome the first difficulty we need to convert the elements in base $\mathcal{B}_q$ to another base coprime to $\mathcal{B}_q$. As we only need the result modulo $t$ we can use the single moduli base $\{ t \}$, as long as $t$ and $q$ are coprime (usually $t$ is a power of two while $q$ is odd). To achieve this conversion we use a fast base conversion which adds a multiple of $q$ called $q$-overflow. After the division by $q$ in the new base, $q$ is canceled and it only remains an error term $\tau$.<br />
<br />
To solve the second difficulty, we choose to compute a flooring, using the equality $\lfloor \frac{x}{q}\rfloor = \frac{x-|x|_q}{q}$ instead of the rounding. The computation of the residue modulo $q$ is achieved by using a Montgomery reduction, which fits well in RNS. Of course, as flooring and rounding are not the same, an error may occur. In such case we simply consider this error as part of the previous one $\tau$.<br />
<br />
At this step we need to cancel, the error $\tau$ due to the conversion and the flooring but also the inherent noise in the ciphertext to recover the message. To do this, we add an other moduli $\gamma$, coprime to $q$ to the base $\{t\}$, we multiply $\texttt{c}'$ by $\gamma$ in base $\mathcal{B}_q$ and we run the computations explained above in base $\{\gamma, t\}$ instead of $\{t\}$. Then, for a well-suited $\gamma$, we are able to cancel the noise in the residue modulo $t$ by subtracting the centered residue modulo $\gamma$ to it. Finally we are able to recover $[\texttt{m}]_t$.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
<b>Homomorphic multiplication</b><br />
<b></b><br />
To perform an homomorphic multiplication<b> </b>of two ciphertexts $\texttt{c}^{(1)}$ and $\texttt{c}^{(2)}$, you first have to scale the product $\texttt{c}^{(1)}\times\texttt{c}^{(2)}$ (which is a degree two polynomial with coefficients in $\mathcal{R}_q$) by $t/q$ and to round the result coefficient-wise as for the decryption. Then one has to relinearize this degree two polynomial to get back a degree one polynomial. But, to limit the noise growth during this step, it requires to decompose the coefficients of an element of $\mathcal{R}_q$ in some radix base $\omega$. Sadly, this is precisely the kind of thing we cannot do in a non-positional number representation.<br />
<br />
One should understand that the product $\texttt{c}^{(1)}\times\texttt{c}^{(2)}$ should be lifted in $\mathbb{Z}$ and because we scale down by $t/q$ the coefficients of the product fits back in $\mathcal{R}_q$. Instead of making the product computation in $\mathbb{Z}$, we use a second RNS base $\mathcal{B}'$ coprime to $\mathcal{B}_q$ of same size to not loose any information.<br />
<br />
Then we use a fast conversion to convert $\texttt{c}^{(1)}$ and $\texttt{c}^{(2)}$ from $\mathcal{B}_q$ to $\mathcal{B}'$. We manage to reduce the error in base $\mathcal{B}'$ (due to the $q$-overflow) in order to reduce its growth during the product and then we perform the product in both bases.<br />
<br /></div>
<div style="text-align: justify;">
Next, we use a fast conversion to convert the residues of the product in base $\mathcal{B}_q$ to base $\mathcal{B}'$. Then, as for decryption, we perform a flooring using Montgomery reduction instead of a rounding and we get $\lfloor t/q (\texttt{c}^{(1)}\times\texttt{c}^{(2)})\rfloor$ in base $\mathcal{B}'$. We consider the error due to the different conversions as part of the noise. </div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
For the next step, we convert the result back in base $\mathcal{B}_q$, but this time using an exact base conversion (more costly), because we cannot tolerate overflows from the base $\mathcal{B}'$. To overcome the last difficulty we have managed to decompose the elements belonging to $\mathcal{R}_q$ in a very similar way from the original, however we can perform this one in RNS. The end of the homomorphic multiplication procedure remains the same, we just replace the original decomposition function by our own. </div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
<b>Impact on the noise</b></div>
<div style="text-align: justify;">
Of course, using all this tricks add some errors which become part of the noise and thus make it bigger. One could wonder if, and how, our multiplicative depth has been affected. Indeed our methods modify the different bounds on the noise for the homomorphic multiplication and also the decryption bound. Nevertheless, by running an analysis with our new bounds, we have shown that our multiplicative depth remains unchanged from the one of the original scheme, for all the sets of parameters but one. </div>
Vincent Zuccahttp://www.blogger.com/profile/15345237115554901147noreply@blogger.com0tag:blogger.com,1999:blog-3329110015361344577.post-47644583093227266742016-07-07T12:28:00.000+02:002016-07-07T12:28:40.586+02:00WHEAT 2016: The Pre-history of Lattice-based Cryptanalysis<div dir="ltr" style="text-align: left;" trbidi="on">
<div>
<div style="text-align: justify;">
On the second day of the <a href="https://wheat2016.lip6.fr/">Workshop HEAT</a>, Antoine Joux gave an invited talk on the history of cryptanalytic applications of <i>lattice-basis reduction</i> algorithms.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
Lattice
is a discrete subgroup of $\mathbb{R}^n$. Equivalently, it is a span of
integer-linear combinations of $\mathbb{R}$-linearly independent
vectors in $\mathbb{R}^n$. Finding a short basis in $\mathbb{R}^2$ is
relatively easy and <i>Gauss' lattice-basis reduction</i> algorithm is
effective for this purpose. As the speaker emphasised, things become
more complicated when we move to higher dimensions. He then went on to
discuss the details of the famous <i>LLL</i> algorithm, invented by
Lenstra, Lenstra and Lovász in 1982, for lattice-basis reduction in
arbitrary dimensions. LLL is a polynomial-time algorithm but returns a
short vector within an exponential approximation factor of the length of
the shortest vector in the lattice. This algorithm, which performs well
in practice, may be viewed as a combination of the Gauss lattice
reduction and the <i>Gram-Schmidt orthogonalisation</i> methods.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
An early application of lattice-basis reduction is the cryptanalysis of <i>knapsack-based</i> cryptosystems. The knapsack problem, a.k.a. the <i>subset-sum</i> problem, is given integers $a_1, \ldots, a_n$, and $S$, find $\epsilon_1,\ldots,\epsilon_n \in \{0,1\}$ such that </div>
<div style="text-align: justify;">
\[S = \overset{n}{\underset{i=1}{\sum}} \epsilon_i \cdot a_ i.\] </div>
<div style="text-align: justify;">
This problem is NP-hard though some cases are easy, and it served as a basis for cryptosystems such as <i>Merkle-Hellman</i>
cryptosystem. The basic idea is to hide an easy knapsack in a
hard-looking one. However, at CRYPTO 1982, Shamir broke this
cryptosystem using lattice-basis reduction. This attacks works for <i>super-increasing</i> knapsacks, where we have $a_i > \sum_{j=1}^{i-1} a_j$. Other works starting with that of <i>Lagarias-Odlyzko</i> in 1985 lead to improved attacks on <i>low-density </i>knapsacks.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
The speaker also briefly spoke about the application of lattie-basis reduction to the problems of</div>
<div style="text-align: justify;">
<br /></div>
<ul style="text-align: justify;">
<li> <i>reconstructing small linear dependencies</i>: let
$(x_1,\ldots,x_n)$ be a sequence of real numbers, we need to find small
coefficients $v_i$ such that $\sum v_i\cdot x_i =0$, </li>
<li><i>constructing polynomials</i> for use in the <i>Number Field Sieve</i> for solving the <i>Discrete Logarithm Problem</i>, and</li>
<li><i>finding small roots</i> of univariate and bivariate integer polynomials <i>modulo</i> composite numbers: <i>Coppersmith's attack</i>.</li>
</ul>
</div>
</div>
Srinivas Vivekhttp://www.blogger.com/profile/12521171190366779104noreply@blogger.com0tag:blogger.com,1999:blog-3329110015361344577.post-76020094261150864672016-07-05T22:57:00.000+02:002016-07-05T22:57:05.116+02:00WHEAT Workshop 2016, ParisThe second HEAT workshop on Fully Homomorphic Encryption (otherwise known as WHEAT) kicked off this morning in (disappointingly cloudy) Paris.<br />
<br />
The first talk of the day was Martin Albrecht's invited talk on solving short secret LWE instances. This is joint work with Rachel Player and Sam Scott. He provided a clear summary of the state of the art in terms of algorithms available and thus set the grounds for the rest of the day. Attacks using parameter choices inspired by HElib and the LP model were discussed and where possible, estimate running times were provided. A partial conclusion was the latter should not be assumed. For a more detailed read, see https://eprint.iacr.org/2015/046.pdf.<br />
<br />
Also discussed was RLWE security in the FHE case, a talk given by Guillaume Bonnoron. This is joint work with Caroline Fontaine. They present an attack on specific FHE parameter choices and use the FV scheme for the reason that they wish to avoid doing a Modulus Switch Operation (see for example https://eprint.iacr.org/2015/889.pdf for a description). The conclusion of this talk is that their attack does work, but FHE and RLWE are not broken, because it does not scale up. A bigger parameter $n$ leads to bigger errors. Whilst they took one day to complete the attack versus a previous 3.5 days (https://eprint.iacr.org/2015/176.pdf), this talk's final conclusion was that more cryptanalysis is needed.<br />
<br />
The second invited talk in the afternoon was Leo Ducas', joint work with Martin Albrecht and Shi Bai. This discussed the subfield lattice attack on "over stretched NTRU assumptions"; for the full technical read, see https://eprint.iacr.org/2016/127.pdf. This attack is based on using a subfield of the field we are working in - they assume the latter is a power of two cyclotomic, but claim it can be done using any field which is Galois. We map down our RLWE instances using the (partial) norm map in order to solve a (hopefully) easier problem in the subfield. Given the right conditions, we can then map the solution we find back up and recover a short enough solution to carry through with the attack. The practicality grows with the modulus $q$, hence the "over stretched" condition. Although this does not seem (yet?) to affect the NTRU schemes used in practice, this talk's conclusion was to drop the NTRU assumption altogether.Anonymoushttp://www.blogger.com/profile/15365495822521605931noreply@blogger.com0tag:blogger.com,1999:blog-3329110015361344577.post-70712681427295400702016-07-04T17:49:00.001+02:002016-07-04T17:49:35.500+02:00Fixed Point Arithmetic<div dir="ltr" style="text-align: left;" trbidi="on">
<div style="text-align: justify;">
In a paper (<a href="http://eprint.iacr.org/2016/250">http://eprint.iacr.org/2016/250</a>) to be presented at SAC (<a href="http://www.engr.mun.ca/~sac2016/">http://www.engr.mun.ca/~sac2016/</a>), in St Johns Canada, in August HEAT researchers Ana Costache, Nigel P. Smart, Srinivas Vivek and Adrian Waller describe how to perform homomorphic operations on fixed point numbers. The work builds upon earlier work of Dowlin et al (<a href="http://research.microsoft.com/pubs/258435/ManualHEv2.pdf">http://research.microsoft.com/pubs/258435/ManualHEv2.pdf</a>). In this blog post we present a quick overview of the technique.<br /><br />To understand the technique you need to appreciate that all known efficient Somewhat Homomorphic Encryption (SHE) schemes are homomorphic over a given ring of polynomials. In particular the set of polymomials modulo both a prime $p$ (the so-called plaintext modulus) and a polynomial $F(X)$. Given such a plaintext space we can embed integers upto a bounded size within the plaintext space in a redundant manner as follows.<br /><br />Suppose we have two integers, say $x=127$ and $y=78$, we write these as polynomials in {\em balanced base} $B$, for $B-3$. This means we write the integers in base $B$, but we allow plus or minus signs in the representation and the coefficients lie in $[0,\ldots,(B-1)/2]$. Thus we have<br />$$ 127 \equiv 3^5-3^4 -3^3 -3^2+1 =X^5-X^4-X^3-X^2+1$$<br />and<br />$$ 78 \equiv 3^4-3 = X^4-X$$.<br />When we add and multiply two such polynomials, and then substitute back in $X=3$, we will obtain the same result as multiplying and adding the original integers. So for example<br />\begin{eqnarray*} (X^5-X^4-X^3&-&X^2+1)<br /> \cdot<br /> (X^4-X) \\<br /> &=& X^9-X^8-X^7-2 \cdot X^6+X^5+2 \cdot X^4+X^3-X.<br />\end{eqnarray*}<br />Notice how both the degree and the coefficient sizes have increased. If the resulting polynomial can still be represented in the plaintext space, i.e. the prime $p$ and the degree of $F(X)$ are large enough, then we can map the polynomial operation to the homomorphic operation. Thus assuming $p$ and $F(X)$ are {\em big enough} we can perform operations on integers; even though the homomorphic encryption scheme only supports operations on polynomials modulo $(p,F(X))$.<br /><br />To encode a fixed point number we then simply encode it as the ratio of an integer numerator and a power of $B$ denominator; so for example $4.7037 \approx 127/3^3$. We can then apply operations on these fractional numbers, as long as we keep track of which denominator we are working with, by simply operating on the numberators. Thus each encrypted fixed point number is represented by an encrypted integer (the numerator) and a public power of three (the denominator).<br /><br />Whilst this representation has been known before, and was given in the paper of Dowlin, a key issue was that one needed to know for a given homomorphic operation what the requisite sizes of $p$ and $F(X)$ should be to ensure correctness. It is this latter problem which our paper addresses; we show how to obtian lower bounds on the plaintext size which are needed to support a given homomorphic calculation. In addition we show that a technique of Dowlin et al, which appears at first sight to be more efficient, turns out to be actually just the same as the above encoding method for fixed point numbers.</div>
</div>
Nigel Smarthttp://www.blogger.com/profile/17681184541012804026noreply@blogger.com2tag:blogger.com,1999:blog-3329110015361344577.post-85930903482665833972016-07-04T13:44:00.000+02:002016-07-04T13:44:49.629+02:00Fourier Transforms in the Encrypted Domain<!--[if !mso]>
<style>
v\:* {behavior:url(#default#VML);}
o\:* {behavior:url(#default#VML);}
w\:* {behavior:url(#default#VML);}
.shape {behavior:url(#default#VML);}
</style>
<![endif]--><br />
<!--[if gte mso 9]><xml>
<w:WordDocument>
<w:View>Normal</w:View>
<w:Zoom>0</w:Zoom>
<w:TrackMoves/>
<w:TrackFormatting/>
<w:DoNotShowRevisions/>
<w:DoNotPrintRevisions/>
<w:DoNotShowInsertionsAndDeletions/>
<w:DoNotShowPropertyChanges/>
<w:PunctuationKerning/>
<w:ValidateAgainstSchemas/>
<w:SaveIfXMLInvalid>false</w:SaveIfXMLInvalid>
<w:IgnoreMixedContent>false</w:IgnoreMixedContent>
<w:AlwaysShowPlaceholderText>false</w:AlwaysShowPlaceholderText>
<w:DoNotPromoteQF/>
<w:LidThemeOther>EN-GB</w:LidThemeOther>
<w:LidThemeAsian>X-NONE</w:LidThemeAsian>
<w:LidThemeComplexScript>X-NONE</w:LidThemeComplexScript>
<w:Compatibility>
<w:BreakWrappedTables/>
<w:SnapToGridInCell/>
<w:WrapTextWithPunct/>
<w:UseAsianBreakRules/>
<w:DontGrowAutofit/>
<w:SplitPgBreakAndParaMark/>
<w:DontVertAlignCellWithSp/>
<w:DontBreakConstrainedForcedTables/>
<w:DontVertAlignInTxbx/>
<w:Word11KerningPairs/>
<w:CachedColBalance/>
</w:Compatibility>
<m:mathPr>
<m:mathFont m:val="Cambria Math"/>
<m:brkBin m:val="before"/>
<m:brkBinSub m:val="--"/>
<m:smallFrac m:val="off"/>
<m:dispDef/>
<m:lMargin m:val="0"/>
<m:rMargin m:val="0"/>
<m:defJc m:val="centerGroup"/>
<m:wrapIndent m:val="1440"/>
<m:intLim m:val="subSup"/>
<m:naryLim m:val="undOvr"/>
</m:mathPr></w:WordDocument>
</xml><![endif]--><!--[if gte mso 9]><xml>
<w:LatentStyles DefLockedState="false" DefUnhideWhenUsed="true"
DefSemiHidden="true" DefQFormat="false" DefPriority="99"
LatentStyleCount="267">
<w:LsdException Locked="false" Priority="0" SemiHidden="false"
UnhideWhenUsed="false" QFormat="true" Name="Normal"/>
<w:LsdException Locked="false" Priority="9" SemiHidden="false"
UnhideWhenUsed="false" QFormat="true" Name="heading 1"/>
<w:LsdException Locked="false" Priority="0" QFormat="true" Name="heading 2"/>
<w:LsdException Locked="false" Priority="0" QFormat="true" Name="heading 3"/>
<w:LsdException Locked="false" Priority="0" QFormat="true" Name="heading 4"/>
<w:LsdException Locked="false" Priority="0" QFormat="true" Name="heading 5"/>
<w:LsdException Locked="false" Priority="9" QFormat="true" Name="heading 6"/>
<w:LsdException Locked="false" Priority="9" QFormat="true" Name="heading 7"/>
<w:LsdException Locked="false" Priority="9" QFormat="true" Name="heading 8"/>
<w:LsdException Locked="false" Priority="9" QFormat="true" Name="heading 9"/>
<w:LsdException Locked="false" Priority="39" Name="toc 1"/>
<w:LsdException Locked="false" Priority="39" Name="toc 2"/>
<w:LsdException Locked="false" Priority="39" Name="toc 3"/>
<w:LsdException Locked="false" Priority="39" Name="toc 4"/>
<w:LsdException Locked="false" Priority="39" Name="toc 5"/>
<w:LsdException Locked="false" Priority="39" Name="toc 6"/>
<w:LsdException Locked="false" Priority="39" Name="toc 7"/>
<w:LsdException Locked="false" Priority="39" Name="toc 8"/>
<w:LsdException Locked="false" Priority="39" Name="toc 9"/>
<w:LsdException Locked="false" Priority="35" QFormat="true" Name="caption"/>
<w:LsdException Locked="false" Priority="10" SemiHidden="false"
UnhideWhenUsed="false" QFormat="true" Name="Title"/>
<w:LsdException Locked="false" Priority="1" Name="Default Paragraph Font"/>
<w:LsdException Locked="false" Priority="11" SemiHidden="false"
UnhideWhenUsed="false" QFormat="true" Name="Subtitle"/>
<w:LsdException Locked="false" Priority="22" SemiHidden="false"
UnhideWhenUsed="false" QFormat="true" Name="Strong"/>
<w:LsdException Locked="false" Priority="20" SemiHidden="false"
UnhideWhenUsed="false" QFormat="true" Name="Emphasis"/>
<w:LsdException Locked="false" Priority="59" SemiHidden="false"
UnhideWhenUsed="false" Name="Table Grid"/>
<w:LsdException Locked="false" UnhideWhenUsed="false" Name="Placeholder Text"/>
<w:LsdException Locked="false" Priority="1" SemiHidden="false"
UnhideWhenUsed="false" QFormat="true" Name="No Spacing"/>
<w:LsdException Locked="false" Priority="60" SemiHidden="false"
UnhideWhenUsed="false" Name="Light Shading"/>
<w:LsdException Locked="false" Priority="61" SemiHidden="false"
UnhideWhenUsed="false" Name="Light List"/>
<w:LsdException Locked="false" Priority="62" SemiHidden="false"
UnhideWhenUsed="false" Name="Light Grid"/>
<w:LsdException Locked="false" Priority="63" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium Shading 1"/>
<w:LsdException Locked="false" Priority="64" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium Shading 2"/>
<w:LsdException Locked="false" Priority="65" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium List 1"/>
<w:LsdException Locked="false" Priority="66" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium List 2"/>
<w:LsdException Locked="false" Priority="67" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium Grid 1"/>
<w:LsdException Locked="false" Priority="68" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium Grid 2"/>
<w:LsdException Locked="false" Priority="69" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium Grid 3"/>
<w:LsdException Locked="false" Priority="70" SemiHidden="false"
UnhideWhenUsed="false" Name="Dark List"/>
<w:LsdException Locked="false" Priority="71" SemiHidden="false"
UnhideWhenUsed="false" Name="Colorful Shading"/>
<w:LsdException Locked="false" Priority="72" SemiHidden="false"
UnhideWhenUsed="false" Name="Colorful List"/>
<w:LsdException Locked="false" Priority="73" SemiHidden="false"
UnhideWhenUsed="false" Name="Colorful Grid"/>
<w:LsdException Locked="false" Priority="60" SemiHidden="false"
UnhideWhenUsed="false" Name="Light Shading Accent 1"/>
<w:LsdException Locked="false" Priority="61" SemiHidden="false"
UnhideWhenUsed="false" Name="Light List Accent 1"/>
<w:LsdException Locked="false" Priority="62" SemiHidden="false"
UnhideWhenUsed="false" Name="Light Grid Accent 1"/>
<w:LsdException Locked="false" Priority="63" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium Shading 1 Accent 1"/>
<w:LsdException Locked="false" Priority="64" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium Shading 2 Accent 1"/>
<w:LsdException Locked="false" Priority="65" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium List 1 Accent 1"/>
<w:LsdException Locked="false" UnhideWhenUsed="false" Name="Revision"/>
<w:LsdException Locked="false" Priority="34" SemiHidden="false"
UnhideWhenUsed="false" QFormat="true" Name="List Paragraph"/>
<w:LsdException Locked="false" Priority="29" SemiHidden="false"
UnhideWhenUsed="false" QFormat="true" Name="Quote"/>
<w:LsdException Locked="false" Priority="30" SemiHidden="false"
UnhideWhenUsed="false" QFormat="true" Name="Intense Quote"/>
<w:LsdException Locked="false" Priority="66" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium List 2 Accent 1"/>
<w:LsdException Locked="false" Priority="67" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium Grid 1 Accent 1"/>
<w:LsdException Locked="false" Priority="68" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium Grid 2 Accent 1"/>
<w:LsdException Locked="false" Priority="69" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium Grid 3 Accent 1"/>
<w:LsdException Locked="false" Priority="70" SemiHidden="false"
UnhideWhenUsed="false" Name="Dark List Accent 1"/>
<w:LsdException Locked="false" Priority="71" SemiHidden="false"
UnhideWhenUsed="false" Name="Colorful Shading Accent 1"/>
<w:LsdException Locked="false" Priority="72" SemiHidden="false"
UnhideWhenUsed="false" Name="Colorful List Accent 1"/>
<w:LsdException Locked="false" Priority="73" SemiHidden="false"
UnhideWhenUsed="false" Name="Colorful Grid Accent 1"/>
<w:LsdException Locked="false" Priority="60" SemiHidden="false"
UnhideWhenUsed="false" Name="Light Shading Accent 2"/>
<w:LsdException Locked="false" Priority="61" SemiHidden="false"
UnhideWhenUsed="false" Name="Light List Accent 2"/>
<w:LsdException Locked="false" Priority="62" SemiHidden="false"
UnhideWhenUsed="false" Name="Light Grid Accent 2"/>
<w:LsdException Locked="false" Priority="63" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium Shading 1 Accent 2"/>
<w:LsdException Locked="false" Priority="64" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium Shading 2 Accent 2"/>
<w:LsdException Locked="false" Priority="65" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium List 1 Accent 2"/>
<w:LsdException Locked="false" Priority="66" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium List 2 Accent 2"/>
<w:LsdException Locked="false" Priority="67" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium Grid 1 Accent 2"/>
<w:LsdException Locked="false" Priority="68" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium Grid 2 Accent 2"/>
<w:LsdException Locked="false" Priority="69" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium Grid 3 Accent 2"/>
<w:LsdException Locked="false" Priority="70" SemiHidden="false"
UnhideWhenUsed="false" Name="Dark List Accent 2"/>
<w:LsdException Locked="false" Priority="71" SemiHidden="false"
UnhideWhenUsed="false" Name="Colorful Shading Accent 2"/>
<w:LsdException Locked="false" Priority="72" SemiHidden="false"
UnhideWhenUsed="false" Name="Colorful List Accent 2"/>
<w:LsdException Locked="false" Priority="73" SemiHidden="false"
UnhideWhenUsed="false" Name="Colorful Grid Accent 2"/>
<w:LsdException Locked="false" Priority="60" SemiHidden="false"
UnhideWhenUsed="false" Name="Light Shading Accent 3"/>
<w:LsdException Locked="false" Priority="61" SemiHidden="false"
UnhideWhenUsed="false" Name="Light List Accent 3"/>
<w:LsdException Locked="false" Priority="62" SemiHidden="false"
UnhideWhenUsed="false" Name="Light Grid Accent 3"/>
<w:LsdException Locked="false" Priority="63" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium Shading 1 Accent 3"/>
<w:LsdException Locked="false" Priority="64" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium Shading 2 Accent 3"/>
<w:LsdException Locked="false" Priority="65" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium List 1 Accent 3"/>
<w:LsdException Locked="false" Priority="66" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium List 2 Accent 3"/>
<w:LsdException Locked="false" Priority="67" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium Grid 1 Accent 3"/>
<w:LsdException Locked="false" Priority="68" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium Grid 2 Accent 3"/>
<w:LsdException Locked="false" Priority="69" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium Grid 3 Accent 3"/>
<w:LsdException Locked="false" Priority="70" SemiHidden="false"
UnhideWhenUsed="false" Name="Dark List Accent 3"/>
<w:LsdException Locked="false" Priority="71" SemiHidden="false"
UnhideWhenUsed="false" Name="Colorful Shading Accent 3"/>
<w:LsdException Locked="false" Priority="72" SemiHidden="false"
UnhideWhenUsed="false" Name="Colorful List Accent 3"/>
<w:LsdException Locked="false" Priority="73" SemiHidden="false"
UnhideWhenUsed="false" Name="Colorful Grid Accent 3"/>
<w:LsdException Locked="false" Priority="60" SemiHidden="false"
UnhideWhenUsed="false" Name="Light Shading Accent 4"/>
<w:LsdException Locked="false" Priority="61" SemiHidden="false"
UnhideWhenUsed="false" Name="Light List Accent 4"/>
<w:LsdException Locked="false" Priority="62" SemiHidden="false"
UnhideWhenUsed="false" Name="Light Grid Accent 4"/>
<w:LsdException Locked="false" Priority="63" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium Shading 1 Accent 4"/>
<w:LsdException Locked="false" Priority="64" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium Shading 2 Accent 4"/>
<w:LsdException Locked="false" Priority="65" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium List 1 Accent 4"/>
<w:LsdException Locked="false" Priority="66" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium List 2 Accent 4"/>
<w:LsdException Locked="false" Priority="67" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium Grid 1 Accent 4"/>
<w:LsdException Locked="false" Priority="68" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium Grid 2 Accent 4"/>
<w:LsdException Locked="false" Priority="69" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium Grid 3 Accent 4"/>
<w:LsdException Locked="false" Priority="70" SemiHidden="false"
UnhideWhenUsed="false" Name="Dark List Accent 4"/>
<w:LsdException Locked="false" Priority="71" SemiHidden="false"
UnhideWhenUsed="false" Name="Colorful Shading Accent 4"/>
<w:LsdException Locked="false" Priority="72" SemiHidden="false"
UnhideWhenUsed="false" Name="Colorful List Accent 4"/>
<w:LsdException Locked="false" Priority="73" SemiHidden="false"
UnhideWhenUsed="false" Name="Colorful Grid Accent 4"/>
<w:LsdException Locked="false" Priority="60" SemiHidden="false"
UnhideWhenUsed="false" Name="Light Shading Accent 5"/>
<w:LsdException Locked="false" Priority="61" SemiHidden="false"
UnhideWhenUsed="false" Name="Light List Accent 5"/>
<w:LsdException Locked="false" Priority="62" SemiHidden="false"
UnhideWhenUsed="false" Name="Light Grid Accent 5"/>
<w:LsdException Locked="false" Priority="63" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium Shading 1 Accent 5"/>
<w:LsdException Locked="false" Priority="64" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium Shading 2 Accent 5"/>
<w:LsdException Locked="false" Priority="65" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium List 1 Accent 5"/>
<w:LsdException Locked="false" Priority="66" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium List 2 Accent 5"/>
<w:LsdException Locked="false" Priority="67" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium Grid 1 Accent 5"/>
<w:LsdException Locked="false" Priority="68" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium Grid 2 Accent 5"/>
<w:LsdException Locked="false" Priority="69" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium Grid 3 Accent 5"/>
<w:LsdException Locked="false" Priority="70" SemiHidden="false"
UnhideWhenUsed="false" Name="Dark List Accent 5"/>
<w:LsdException Locked="false" Priority="71" SemiHidden="false"
UnhideWhenUsed="false" Name="Colorful Shading Accent 5"/>
<w:LsdException Locked="false" Priority="72" SemiHidden="false"
UnhideWhenUsed="false" Name="Colorful List Accent 5"/>
<w:LsdException Locked="false" Priority="73" SemiHidden="false"
UnhideWhenUsed="false" Name="Colorful Grid Accent 5"/>
<w:LsdException Locked="false" Priority="60" SemiHidden="false"
UnhideWhenUsed="false" Name="Light Shading Accent 6"/>
<w:LsdException Locked="false" Priority="61" SemiHidden="false"
UnhideWhenUsed="false" Name="Light List Accent 6"/>
<w:LsdException Locked="false" Priority="62" SemiHidden="false"
UnhideWhenUsed="false" Name="Light Grid Accent 6"/>
<w:LsdException Locked="false" Priority="63" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium Shading 1 Accent 6"/>
<w:LsdException Locked="false" Priority="64" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium Shading 2 Accent 6"/>
<w:LsdException Locked="false" Priority="65" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium List 1 Accent 6"/>
<w:LsdException Locked="false" Priority="66" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium List 2 Accent 6"/>
<w:LsdException Locked="false" Priority="67" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium Grid 1 Accent 6"/>
<w:LsdException Locked="false" Priority="68" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium Grid 2 Accent 6"/>
<w:LsdException Locked="false" Priority="69" SemiHidden="false"
UnhideWhenUsed="false" Name="Medium Grid 3 Accent 6"/>
<w:LsdException Locked="false" Priority="70" SemiHidden="false"
UnhideWhenUsed="false" Name="Dark List Accent 6"/>
<w:LsdException Locked="false" Priority="71" SemiHidden="false"
UnhideWhenUsed="false" Name="Colorful Shading Accent 6"/>
<w:LsdException Locked="false" Priority="72" SemiHidden="false"
UnhideWhenUsed="false" Name="Colorful List Accent 6"/>
<w:LsdException Locked="false" Priority="73" SemiHidden="false"
UnhideWhenUsed="false" Name="Colorful Grid Accent 6"/>
<w:LsdException Locked="false" Priority="19" SemiHidden="false"
UnhideWhenUsed="false" QFormat="true" Name="Subtle Emphasis"/>
<w:LsdException Locked="false" Priority="21" SemiHidden="false"
UnhideWhenUsed="false" QFormat="true" Name="Intense Emphasis"/>
<w:LsdException Locked="false" Priority="31" SemiHidden="false"
UnhideWhenUsed="false" QFormat="true" Name="Subtle Reference"/>
<w:LsdException Locked="false" Priority="32" SemiHidden="false"
UnhideWhenUsed="false" QFormat="true" Name="Intense Reference"/>
<w:LsdException Locked="false" Priority="33" SemiHidden="false"
UnhideWhenUsed="false" QFormat="true" Name="Book Title"/>
<w:LsdException Locked="false" Priority="37" Name="Bibliography"/>
<w:LsdException Locked="false" Priority="39" QFormat="true" Name="TOC Heading"/>
</w:LatentStyles>
</xml><![endif]--><!--[if gte mso 10]>
<style>
/* Style Definitions */
table.MsoNormalTable
{mso-style-name:"Table Normal";
mso-tstyle-rowband-size:0;
mso-tstyle-colband-size:0;
mso-style-noshow:yes;
mso-style-priority:99;
mso-style-qformat:yes;
mso-style-parent:"";
mso-padding-alt:0cm 5.4pt 0cm 5.4pt;
mso-para-margin-top:0cm;
mso-para-margin-right:0cm;
mso-para-margin-bottom:10.0pt;
mso-para-margin-left:0cm;
line-height:115%;
mso-pagination:widow-orphan;
font-size:11.0pt;
font-family:"Calibri","sans-serif";
mso-ascii-font-family:Calibri;
mso-ascii-theme-font:minor-latin;
mso-hansi-font-family:Calibri;
mso-hansi-theme-font:minor-latin;
mso-fareast-language:EN-US;}
</style>
<![endif]-->Thales UK has identified Synthetic Aperture Radar (SAR) as a
promising candidate for the application of Homomorphic Encryption (HE). It is
proposed that the data collected from SAR can be protected throughout its processing
up to the formation of image products. SAR data can be processed in many ways to produce different
types of images; the simplest of which is the Single Look Complex Image. The
main challenge of implementing the Single Look Complex Image algorithm in the
encrypted domain is that of implementing the Fourier Transform. <br />
<br />
<h4>
Discrete Fourier Transform </h4>
<div class="MsoCommentText">
Consider the Discrete Fourier Transform (DFT) for a
sequence of complex numbers $x_0, x_1, \ldots, x_{N-1}$:</div>
<div class="MsoCommentText">
</div>
<div class="MsoCommentText">
$X_k = \sum_{n=0}^{N-1} x_n \cdot e^{ -\frac{2\pi
i k n} {N} } , \quad k=0,\ldots, N-1$</div>
<div class="MsoCommentText">
</div>
<div class="MsoCommentText">
<span style="mso-fareast-font-family: "Times New Roman"; mso-fareast-theme-font: minor-fareast;">This is a linear transform; it requires
only the summation of sequence samples and multiplication by scalar values </span>$e^{-\frac{2\pi
i k n}{N} }$ <span style="mso-fareast-font-family: "Times New Roman"; mso-fareast-theme-font: minor-fareast;">(sometimes called <i style="mso-bidi-font-style: normal;">twiddle
factors</i>). We usually implement this via a Fast
Fourier Transform (FFT) which reduces the computational complexity by the use
of a few mathematical tricks. </span><br />
</div>
<h4>
<span style="mso-bidi-font-family: Arial; mso-fareast-font-family: Arial;"><span style="mso-list: Ignore;"><span style="font-size-adjust: none; font-stretch: normal; font: 7pt/normal "times new roman";"></span></span></span>Paillier Cryptosystem</h4>
<div class="MsoCommentText">
The Paillier cryptosystem [1]
encrypts plaintext messages $m\in \mathbb{Z}_n$<span style="mso-fareast-font-family: "Times New Roman"; mso-fareast-theme-font: minor-fareast;">, where $n$ is the
product of two large prime numbers, to a ciphertext </span>$c\in
\mathbb{Z}^*_{n^2}$<span style="mso-fareast-font-family: "Times New Roman"; mso-fareast-theme-font: minor-fareast;">. Let </span>$\text{Enc}$<span style="mso-fareast-font-family: "Times New Roman"; mso-fareast-theme-font: minor-fareast;">
and </span>$\text{Dec}$<span style="mso-fareast-font-family: "Times New Roman"; mso-fareast-theme-font: minor-fareast;"> denote the encryption and decryption
processes respectively. It can be shown that the Paillier cryptosystem
satisfies the two following properties:</span></div>
<div class="MsoBodyText" style="margin-left: 36pt; text-indent: -18pt;">
<span style="mso-bidi-font-family: Calibri; mso-bidi-theme-font: minor-latin;"><span style="mso-list: Ignore;">1)<span style="font-size-adjust: none; font-stretch: normal; font: 7pt/normal "times new roman";"> </span></span></span><span style="mso-fareast-font-family: "Times New Roman"; mso-fareast-theme-font: minor-fareast;">For
two plaintext messages $m_1, m_2\in \mathbb{Z}_n$</span><br />
$\text{Dec}( \text{Enc}(m_1) \cdot \text{Enc}(m_2) \text{ mod } n^2)$ $ = m_1 + m_2 \text{ mod } n$.</div>
<div class="MsoBodyText" style="margin-left: 36pt; text-indent: -18pt;">
<span style="mso-bidi-font-family: Calibri; mso-bidi-theme-font: minor-latin;"><span style="mso-list: Ignore;">2)<span style="font-size-adjust: none; font-stretch: normal; font: 7pt/normal "times new roman";"> </span></span></span><span style="mso-fareast-font-family: "Times New Roman"; mso-fareast-theme-font: minor-fareast;">For
a plaintext $m$ and any constant integer $k$ </span></div>
<div class="MsoCommentText" style="margin-left: 36pt; text-indent: 36pt;">
$\text{Dec}
( \text{Enc}(m)^k \text{ mod } n ) = km \text{ mod } n^2$.</div>
<div class="MsoBodyText">
<br /></div>
<div class="MsoBodyText">
<span style="mso-fareast-font-family: "Times New Roman"; mso-fareast-theme-font: minor-fareast;">Properties 1 and 2 allow us to add any
two plaintexts and multiply any plaintext by an integer constant in the
encrypted domain; these operations are sufficient to implement the Fourier Transform
(DFT/FFT). </span><br />
</div>
<h4>
The Fourier Transform under Paillier Encryption</h4>
<div class="MsoBodyText">
There
are two major challenges in the implementation of a Fourier Transform
under Paillier encryption:<span style="mso-spacerun: yes;"> </span><span style="mso-spacerun: yes;"> </span></div>
<div class="MsoBodyText" style="margin-left: 36pt; text-indent: -18pt;">
<span style="mso-bidi-font-family: Calibri; mso-bidi-theme-font: minor-latin;"><span style="mso-list: Ignore;">1)<span style="font-size-adjust: none; font-stretch: normal; font: 7pt/normal "times new roman";"> </span></span></span>Paillier
encrypts and allows operations only on integer values modulo $n$.<span style="mso-fareast-font-family: "Times New Roman"; mso-fareast-theme-font: minor-fareast;">
We must convert our sequence samples $x_0, x_1, \ldots, x_{N-1}$, and twiddle
factors $e^{-\frac{2\pi ikn}{N} }$, into integers modulo $n$. We achieve this
by multiplying by two appropriately chosen scale factors; one for the sequence
samples and one for the twiddle factors. These scale factors must be dealt with
throughout the Fourier Transform.</span></div>
<div class="MsoBodyText" style="margin-left: 36pt; text-indent: -18pt;">
<span style="mso-bidi-font-family: Calibri; mso-bidi-theme-font: minor-latin;"><span style="mso-list: Ignore;">2)<span style="font-size-adjust: none; font-stretch: normal; font: 7pt/normal "times new roman";"> </span></span></span>The
homomorphic addition and scalar multiplication operations result in plaintext
values modulo $n$.<span style="mso-fareast-font-family: "Times New Roman"; mso-fareast-theme-font: minor-fareast;"> That is, if we wish to sum two plaintext
values </span>$m_1, m_2$ <span style="mso-fareast-font-family: "Times New Roman"; mso-fareast-theme-font: minor-fareast;">in the encrypted domain we must ensure
the resulting plaintext is no greater than $n-1$. Otherwise, we can say nothing
about the magnitude of </span>$m_1 + m_2$<span style="font-family: "calibri" , "sans-serif";">.</span><span style="mso-spacerun: yes;"> </span>Since we wish to perform many additions and scalar
multiplications throughout the Fourier Transform, we require $n$ <span style="mso-fareast-font-family: "Times New Roman"; mso-fareast-theme-font: minor-fareast;">to
be large enough to cope with the growth from all of these operations. </span></div>
<div class="MsoBodyText">
<span style="mso-fareast-font-family: "Times New Roman"; mso-fareast-theme-font: minor-fareast;"></span><br />
<span style="mso-fareast-font-family: "Times New Roman"; mso-fareast-theme-font: minor-fareast;">These two challenges have been discussed
in </span><span style="mso-fareast-font-family: "Times New Roman"; mso-fareast-theme-font: minor-fareast;">[2]</span><span style="mso-fareast-font-family: "Times New Roman"; mso-fareast-theme-font: minor-fareast;">. Challenge 1 means that we need to deal
with the quantisation scale factors when performing operations. The analysis of
challenge 2 in [2] results in the following lower bound for the word length </span>$n_p$<span style="mso-fareast-font-family: "Times New Roman"; mso-fareast-theme-font: minor-fareast;">
of the modulus $n$ after radix-2 FFT operations:</span></div>
<div class="MsoCommentText">
$n_p \geq v + (v-2) n_2 + n_1 + 3$</div>
<div class="MsoBodyText">
<br /></div>
<div class="MsoBodyText">
<span style="mso-fareast-font-family: "Times New Roman"; mso-fareast-theme-font: minor-fareast;">Where:</span></div>
<div class="MsoCommentText">
$v = \log_2 (N)$</div>
<div class="MsoCommentText">
$n_1 = b_1-1$<span style="mso-fareast-font-family: "Times New Roman"; mso-fareast-theme-font: minor-fareast;">, where </span>$b_1$<span style="mso-fareast-font-family: "Times New Roman"; mso-fareast-theme-font: minor-fareast;">
is the number of bits of precision in the sequence samples </span></div>
<div class="MsoBodyText">
$n_2 = \left\lceil b_2 - \dfrac{v}{2} + \dfrac{1}{2} \right\rceil$<span style="mso-fareast-font-family: "Times New Roman"; mso-fareast-theme-font: minor-fareast;">
where </span>$b_2$<span style="mso-fareast-font-family: "Times New Roman"; mso-fareast-theme-font: minor-fareast;"> is the hardware register size in an
equivalent plaintext implementation of the Fourier Transform. Equivalently, </span>$n_2$
<span style="mso-fareast-font-family: "Times New Roman"; mso-fareast-theme-font: minor-fareast;">is the number of bits of precision required in the twiddle
factors to ensure the same precision in the result of the Fourier Transform as
a standard (in clear) hardware implementation.<span style="mso-spacerun: yes;">
</span></span></div>
<div class="MsoBodyText">
<br />
<span style="mso-fareast-font-family: "Times New Roman"; mso-fareast-theme-font: minor-fareast;">Typical SAR applications perform multiple
FFT operations, as well as other multiplications. For example, the Single Look
Complex Image processing employs four 2-dimensional FFTs and 3 Hadamard products. Using the
inequality above for one (1-dimensional) FFT operation, our analysis of the Single Look Complex
Image processing results in a lower bound: </span></div>
<div class="MsoCommentText">
</div>
<div class="MsoCommentText">
$n_p \geq 8v + 8(v-2) n_2 + n_1 + 3(n_3-1) + 24$</div>
<div class="MsoCommentText">
</div>
<div class="MsoCommentText">
<span style="mso-fareast-font-family: "Times New Roman"; mso-fareast-theme-font: minor-fareast;">for the modulus word length, where </span>$n_3$
<span style="mso-fareast-font-family: "Times New Roman"; mso-fareast-theme-font: minor-fareast;">is the word length associated with each of the inputs to the Hadamard
products. We expect values of the order </span>$v=13$, $n_1 = 7$, $n_2=10$,
$n_3=16$, <span style="mso-fareast-font-family: "Times New Roman"; mso-fareast-theme-font: minor-fareast;">giving a lower bound of </span>$n_p\geq
1060$<span style="mso-fareast-font-family: "Times New Roman"; mso-fareast-theme-font: minor-fareast;">. It is likely that the modulus word length is required to be
larger than this bound for security reasons </span><span style="mso-fareast-font-family: "Times New Roman"; mso-fareast-theme-font: minor-fareast;">so there is plenty of scope to perform Single Look Complex Image processing. </span></div>
<div class="MsoBodyText">
</div>
<h4>
<span style="mso-fareast-font-family: "Times New Roman"; mso-fareast-theme-font: minor-fareast;">References</span></h4>
<div class="MsoBodyText" style="margin-left: 36pt; text-indent: -18pt;">
[1] Paillier,
"Public-Key
Cryptosystems Based on Composite Degree Residuosity Classes", EUROCRYPT,
Springer. pp. 223–238 (1999).</div>
<div class="MsoBodyText" style="margin-left: 36pt; text-indent: -18pt;">
[2] Bianchi, T.,
Piva, A., Barni, M, "On the Implementation of the Discrete Fourier
Transform in the Encrypted Domain", IEE Transaction on Information and
Security , 86-97 (2009).</div>
Anonymoushttp://www.blogger.com/profile/17958284505244135897noreply@blogger.com0tag:blogger.com,1999:blog-3329110015361344577.post-3835947513645685442016-04-27T18:28:00.001+02:002016-04-27T18:28:39.926+02:00Tightness of the error bound in Ring-LWE<div dir="ltr" style="text-align: left;" trbidi="on">
About two months ago we have posted <a href="https://eprint.iacr.org/2016/240">a short paper</a> on eprint sharing some thoughts on the error size used in Ring-LWE, an increasingly important hard problem that was proposed by Lyubashevsky, Peikert and Regev [<a href="https://eprint.iacr.org/2012/230">LPR</a>] as a building block for cryptography. Besides resistance against quantum computers, one of the main features of Ring-LWE for HEAT is that it enables homomorphic encryption.<br />
<br />
Very briefly, in Ring-LWE one fixes a degree $n$ number field $K$ with ring of integers $R$ and discriminant $\Delta$. One also fixes an integer modulus $q$ and an error parameter $r \in \mathbb{R}_{> 0}$, which we think of as depending on $n$ only. We write $R_q$ and $R_q^\vee$ for the reduction of $R$ and its codifferent (or `dual') modulo $q$. The Ring-LWE problem is about guessing a secret $\mathbf{s} \in R_q^\vee$ from a number of samples of the form $(\mathbf{a}, \mathbf{a} \cdot \mathbf{s} + \mathbf{e} )$, where $\mathbf{a} \in R_q$ is random and $\mathbf{e}$ is sampled from the distribution on $(K \otimes \mathbb{R})/q\mathbb{Z}$ that one obtains by pulling back a spherical Gaussian of width $r$ under the canonical embedding $K \hookrightarrow \mathbb{R}^n$.<br />
<br />In a recent series of papers Elias, Lauter, Ozman and Stange [<a href="https://eprint.iacr.org/2015/106">ELOS</a>], and Chen, Lauter and Stange [<a href="https://eprint.iacr.org/2015/971">CLS1</a>], [<a href="https://eprint.iacr.org/2016/193">CLS2</a>] investigated whether the existence of a homomorphism $\phi : R_q \rightarrow S$ to some small ring $S$ can be exploited to leak information about the secret $\mathbf{s}$. For instance if $R_q$ is of the form $\mathbb{Z}[x]/(q,f(x))$ for some $f(x) \in \mathbb{Z}[x]$ satisfying $f(1) = 0$ mod $q$, then $\phi$ could be evaluation at $1$: $$ \phi : R_q \rightarrow \mathbb{F}_q: \mathbf{a} \mapsto \mathbf{a}(1).$$ Although this idea is attractive, the concrete vulnerable instances proposed by [<a href="https://eprint.iacr.org/2015/106">ELOS</a>], [<a href="https://eprint.iacr.org/2015/971">CLS1</a>], [<a href="https://eprint.iacr.org/2016/193">CLS2</a>] do not follow the original set-up from [<a href="https://eprint.iacr.org/2012/230">LPR</a>]. Instead they<br />
<ol style="text-align: left;">
<li>sample the secrets from the ring $R_q$, rather than its dual $R_q^\vee$,</li>
<li>use an error parameter of the form $|\Delta|^{1/2n}\cdot r$, rather than just $r$.</li>
</ol>
It is not entirely clear to us what the implications of 1. are, but at least one should scale up the error parameter in order to compensate for the relative sparseness of $R$, as is indeed done in 2. However the scalar $|\Delta|^{1/2n}$ is chosen from a Polynomial-LWE point of view and is not adapted to the way the Ring-LWE errors are generated. Indeed, the canonical embedding may be very skew, so even though `on average' things will be okay, there could exist a basis of $R$ with respect to which some of the coordinates of $\mathbf{e}$ are negligible. This in turn leads to <b>exact</b> linear equations in the secret $\mathbf{s}$, obtained by merely rounding, which allows for a recovery of the secret using elementary linear algebra.<br /><br />In a <a href="https://eprint.iacr.org/2016/239">previous paper</a> (reported upon in a <a href="http://heat-h2020-project.blogspot.be/2015/12/weak-instances-of-rlwe.html">blogpost below</a>) we showed that the families from [<a href="https://eprint.iacr.org/2015/106">ELOS</a>] indeed suffer from this skewness, and therefore were easy to start from. To some extent this also seems to apply to the examples from [<a href="https://eprint.iacr.org/2015/971">CLS1</a>] and [<a href="https://eprint.iacr.org/2016/193">CLS2</a>], as is discussed in the last section of our current paper, where we make a more systematic analysis of the skewness phenomenon. Our main contributions are as follows:<br />
<ul style="text-align: left;">
<li>We first give an informal motivation for why the most natural choice of
scalar is $|\Delta|^{1/n}$, rather than $|\Delta|^{1/2n}$, if one wants to set up a non-dual version of Ring-LWE as in 1.</li>
<li>Next we provide for any $\varepsilon > 0$ a family of number fields
in which non-dual Ring-LWE can again be broken using elementary linear
algebra as soon as the errors are scaled up by $|\Delta|^{(1 - \varepsilon)/n}$ only.</li>
<li>Finally we show that also the actual (i.e., dual) Ring-LWE problem is
easily broken for the same families, as soon as the errors proposed by
[<a href="https://eprint.iacr.org/2012/230">LPR</a>] as scaled down by $|\Delta|^{\varepsilon/n}$. </li>
</ul>
So our conclusions strongly suggest that the problems with the examples from [<a href="https://eprint.iacr.org/2015/106">ELOS</a>] are related to 2., rather than 1. They also provide a tightness statement on the error size proposed by [<a href="https://eprint.iacr.org/2012/230">LPR</a>], at least from a discriminant point of view. Immediate research questions that arise are whether there exist weak instances of non-dual Ring-LWE, when set up with the scalar $|\Delta|^{1/n}$, and, more specifically, whether there exist attacks involving a homomorphism $\phi : R_q \rightarrow S$ that apply here? Or that apply to the actual Ring-LWE problem as introduced in [<a href="https://eprint.iacr.org/2012/230">LPR</a>]?<br />
<br />
About a month ago Peikert posted <a href="https://eprint.iacr.org/2016/351">a paper</a> sharing similar (but more detailed) thoughts on the vulnerability of the Ring-LWE instantiations described in [<a href="https://eprint.iacr.org/2015/106">ELOS</a>], [<a href="https://eprint.iacr.org/2015/971">CLS1</a>] and [<a href="https://eprint.iacr.org/2016/193">CLS2</a>].<br />
<br />Wouter Castryck, Ilia Iliashenko, Frederik Vercauteren<br /></div>
Wouter Castryckhttp://www.blogger.com/profile/15365658488060888280noreply@blogger.com0tag:blogger.com,1999:blog-3329110015361344577.post-67583605394034122992016-03-30T13:52:00.001+02:002016-03-30T13:52:48.837+02:00CryptoExperts is hiring a Post-Doc Researcher<div dir="ltr" style="text-align: left;" trbidi="on">
<div>
CryptoExperts (Paris, France) is looking for an excellent postdoctoral fellow to work on the <b>design, the analysis, and the implementation of homomorphic encryption and lattice-based cryptography</b>, who will be primarily involved in the HEAT project.</div>
<div>
<br /></div>
<div>
In this position, the candidate will also be involved in the French CryptoComp project on homomorphic encryption, which aims at developing a fully automated “source to source” compiler which convert any function into a “secure” version of this function able to run on encrypted data. </div>
<div>
<br /></div>
<div>
In both projects, the challenging industrial use-cases will allow to ground the research in practical issues. The candidate will be able to carry research according to its research interests (theoretical and/or practical), and will be offered multiple travel opportunities and interactions with scientists all over Europe (including the HEAT partners). Participation to the open-source libraries on homomorphic encryption and proof-of-concept demonstrators, main outcomes of the HEAT project, will be expected.</div>
<div>
<br /></div>
<div>
Applicants should have a Ph.D. in a relevant subject or equivalent, have a strong publication record and interest in practical protocols. Implementation and coding experience are required.</div>
<div>
<br /></div>
<div>
The position is fully funded for two years (with a flexible starting date). Review of applications will begin immediately until the position has been filled. Knowledge of French is <i>not</i> mandatory. To apply, please send an e-mail to <b>jobs (at) cryptoexperts.com</b> with the following documents:</div>
<div>
<ul style="text-align: left;">
<li>Curriculum vitae, with publication list</li>
<li>Reference letters</li>
</ul>
</div>
<div>
<br /></div>
<div>
<br /></div>
</div>
Anonymousnoreply@blogger.com0tag:blogger.com,1999:blog-3329110015361344577.post-21006541345756659352016-02-06T09:12:00.000+01:002016-03-16T13:57:30.162+01:00NIST Draft on Post Quantum Cryptography<div dir="ltr" style="text-align: left;" trbidi="on">
<div style="text-align: justify;">
On February 4th 2016, the National Institute of Standards and Technology (NIST) released a draft entitled <i><a href="http://csrc.nist.gov/publications/drafts/nistir-8105/nistir_8105_draft.pdf">Report on Post-Quantum Cryptography</a>.</i> This draft presents NIST's current understanding about the status of quantum computers and post-quantum cryptography, and its initial plan to move forward.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
In particular, the NIST has decided that time has come to prepare for the transition to quantum-resistant cryptography. Some striking facts reported in the draft are:</div>
<div style="text-align: justify;">
<br /></div>
<ul style="text-align: justify;">
<li>"researchers working on building a quantum computer have estimated that it is likely that a
quantum computer capable of breaking RSA-2048 in a matter of hours could be built by 2030 for
a budget of about a billion dollars" (p.6)</li>
<li>"transitioning from 112 to 128 bits of security is perhaps less urgent than transitioning from
existing cryptosystems to post-quantum cryptosystems." (p.6)</li>
</ul>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
This engagement of the NIST to standardize post-quantum cryptography is a true opportunity for everyone to react before practical quantum computing is imminent. The NIST plan is as follows:</div>
<div style="text-align: justify;">
<br /></div>
<ol style="text-align: justify;">
<li><b>Feb. 3 2016 - Mar. 9 2016: </b>public comment period for the draft <i>Report on Post-Quantum Cryptography.</i></li>
<li><i><b style="font-style: normal;">2016:</b><span style="font-style: normal;"> proposition of a draft on the evaluation criteria for quantum-resistant public key cryptography, and public comment period.</span></i></li>
<li><i><span style="font-style: normal;"><b>until late 2017: </b>the NIST will accept proposals for </span></i>quantum-resistant public
key encryption, digital signatures, and key exchange algorithms.</li>
<li><b>2018 + 3/5 years: </b>public scrutiny of the candidates to be standardized.</li>
</ol>
<div style="text-align: justify;">
The NIST emphasizes that this process should not be considered as a competition. The institute see its role as a manager of a <i>transparent</i> process engaging with the cryptographic community, that will eventually reach a consensus on cryptographic standards to be endorsed by industry and other standards
organizations around the world.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
The HEAT project focuses on bringing <b>fully homomorphic encryption</b> one step further, into products and standards. Obviously, this cannot be, and is <i>not</i>, orthogonal to the quantum-resistant cryptography process. In particular, most of the fully homomorphic encryption schemes belong to one of the main family of post-quantum cryptographic primitives: <b>lattice-based cryptography</b>. As a consequence, all the research that is, and will be, done on fully homomorphic encryption goes hand in hand with the process initiated by the NIST. </div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
In particular, the <b>Security analysis and parameter recommendations </b>outcome will directly feed the research on analysis of post-quantum primitives. Our <b>open-source software and hardware libraries</b> will include algorithms that will help better understand the performance potential of lattice-based cryptography. Also a member of the HEAT consortium is involved in the ISO standardization, and the main editor of the upcoming WG 2 standard on Homomorphic Encryption, that is, encryption that supports computing over encrypted data. A workshop on <b><a href="https://www.cryptoexperts.com/awacs2016">Cryptographic Standards and Evaluations</a> (AWACS 2016) </b>will be organized by <a href="https://www.cryptoexperts.com/">CryptoExperts</a>, on behalf of the <a href="http://www.ecrypt.eu.org/csa/workshops.html">ECRYPT-CSA</a> project, <b><u>on May 8 2016</u></b>, and will include talks and a panel discussion on the <i>present and near-future trends in crypto standards (with an emphasis on the post-quantum rush). </i></div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
Last but not least, many members of the HEAT consortium are actively involved in the research on post-quantum primitives such as <a href="https://eprint.iacr.org/2014/599">key-exchange</a> or <a href="https://eprint.iacr.org/2013/383">digital signatures</a>.</div>
</div>
Anonymousnoreply@blogger.com0tag:blogger.com,1999:blog-3329110015361344577.post-71087309460643573602016-01-11T14:55:00.000+01:002016-01-11T14:57:42.222+01:00Satellite Applications of Homomorphic Encryption<!--[if gte mso 9]><xml>
<w:WordDocument>
<w:View>Normal</w:View>
<w:Zoom>0</w:Zoom>
<w:TrackMoves/>
<w:TrackFormatting/>
<w:DoNotShowRevisions/>
<w:DoNotPrintRevisions/>
<w:DoNotShowInsertionsAndDeletions/>
<w:DoNotShowPropertyChanges/>
<w:PunctuationKerning/>
<w:ValidateAgainstSchemas/>
<w:SaveIfXMLInvalid>false</w:SaveIfXMLInvalid>
<w:IgnoreMixedContent>false</w:IgnoreMixedContent>
<w:AlwaysShowPlaceholderText>false</w:AlwaysShowPlaceholderText>
<w:DoNotPromoteQF/>
<w:LidThemeOther>EN-GB</w:LidThemeOther>
<w:LidThemeAsian>X-NONE</w:LidThemeAsian>
<w:LidThemeComplexScript>X-NONE</w:LidThemeComplexScript>
<w:Compatibility>
<w:BreakWrappedTables/>
<w:SnapToGridInCell/>
<w:WrapTextWithPunct/>
<w:UseAsianBreakRules/>
<w:DontGrowAutofit/>
<w:SplitPgBreakAndParaMark/>
<w:DontVertAlignCellWithSp/>
<w:DontBreakConstrainedForcedTables/>
<w:DontVertAlignInTxbx/>
<w:Word11KerningPairs/>
<w:CachedColBalance/>
</w:Compatibility>
<m:mathPr>
<m:mathFont m:val="Cambria Math"/>
<m:brkBin m:val="before"/>
<m:brkBinSub m:val="--"/>
<m:smallFrac m:val="off"/>
<m:dispDef/>
<m:lMargin m:val="0"/>
<m:rMargin m:val="0"/>
<m:defJc m:val="centerGroup"/>
<m:wrapIndent m:val="1440"/>
<m:intLim m:val="subSup"/>
<m:naryLim m:val="undOvr"/>
</m:mathPr></w:WordDocument>
</xml><![endif]-->
<br />
<div style="border-bottom: solid #4F81BD 1.0pt; border: none; mso-border-bottom-themecolor: accent1; mso-element: para-border-div; padding: 0cm 0cm 4.0pt 0cm;">
<div class="MsoTitle">
<h2>
</h2>
</div>
</div>
<div class="MsoBodyText" style="text-align: justify;">
Thales UK has been investigating the use of Homomorphic Encryption
(HE) in satellite scenarios. In particular, our assessment has focused on the
data processing of imaging products; one of the many types of signal processing
applications which could have been chosen. <span style="mso-spacerun: yes;"> </span></div>
<div class="MsoBodyText" style="text-align: justify;">
<br />
It is relatively simple to find signal processing
satellite applications where HE could, in theory at least, provide real benefit. In particular, to
provide end-to-end security of data from the sensor on the satellite to the end
user, while allowing the potentially complex and specialised signal processing
to be performed on shared (and less trusted from the end user’s point of view)
infrastructure. The real challenge has been to find such applications that are
potentially practical in the near term, using Somewhat Homomorphic Encryption
(SHE).</div>
<div class="MsoBodyText" style="text-align: justify;">
<br />
Consider the <a href="http://www.esa.int/Our_Activities/Observing_the_Earth/Copernicus/Sentinel-2/Introducing_Sentinel-2">Sentinel 2 Multi Spectral Imager</a>
which is a representative example of an earth observation satellite (in this
case designed for environmental monitoring). In order to be suitable for the
application of HE to provide sensor to end user security, all the signal
processing algorithms would have to be amenable to HE. It turns out that many
of them potentially are, in particular the deconvolution algorithms that use
Fourier Transforms. However, other parts of the processing are more difficult
to deal with in HE. For example, processing to deal with imperfections such as:</div>
<ul>
<li><span style="font-family: Symbol; mso-ansi-language: EN-GB; mso-bidi-font-family: Symbol; mso-fareast-font-family: Symbol;"><span style="mso-list: Ignore;"><span style="font: 7.0pt "Times New Roman";"></span></span></span><span style="mso-ansi-language: EN-GB; mso-bidi-font-family: "Times New Roman"; mso-bidi-theme-font: minor-bidi; mso-fareast-font-family: Calibri; mso-fareast-theme-font: minor-latin;">saturated pixels</span></li>
<li><span style="font-family: Symbol; mso-ansi-language: EN-GB; mso-bidi-font-family: Symbol; mso-fareast-font-family: Symbol;"><span style="mso-list: Ignore;"><span style="font: 7.0pt "Times New Roman";"></span></span></span><span style="mso-ansi-language: EN-GB; mso-bidi-font-family: "Times New Roman"; mso-bidi-theme-font: minor-bidi; mso-fareast-font-family: Calibri; mso-fareast-theme-font: minor-latin;">no data pixels and
partially corrected pixels (crosstalk correction)</span></li>
<li><span style="mso-ansi-language: EN-GB; mso-bidi-font-family: "Times New Roman"; mso-bidi-theme-font: minor-bidi; mso-fareast-font-family: Calibri; mso-fareast-theme-font: minor-latin;">defective pixels</span></li>
</ul>
<div class="MsoNormal" style="text-align: justify;">
<span style="font-size: small;">These are very simple algorithms, but involve a lot of
conditional operators (<, >, etc. to test pixel values) that would<span style="font-family: inherit;"> <span style="line-height: 115%;">be expensive
when implemented on HE encrypted data</span></span>.</span><br />
</div>
<div class="MsoNormal" style="text-align: justify;">
A much more promising candidate is Synthetic Aperture Radar
(SAR) (e.g. <a href="http://www.esa.int/Our_Activities/Observing_the_Earth/Envisat/Mission_overview">Envisat</a>).
SAR is used to provide high precision, and often 3D, imaging for applications
such as sea ice and glacier monitoring, vegetation coverage analysis, disaster
monitoring and traffic surveillance. Being a radio-based technique, it is not
affected by weather or the lack of daylight. The raw data collected by the
satellite consists of a series of radar echoes, and these must be processed to
form an image. On examining the details of this processing, it can be seen that
the core functionality consists of a series of:</div>
<ul>
<li><span lang="EN-US">Fourier Transforms (and their
inverses)</span></li>
<li><span lang="EN-US">Hadamard products of matrices</span></li>
</ul>
<div class="MsoNormal" style="text-align: justify;">
These can be implemented, in theory at least, with a low
multiplicative depth, and without the need for conditional operators. This is
therefore a good candidate application for SHE, but much work needs to be done
to demonstrate its practicality.<span style="mso-spacerun: yes;"> </span></div>
Anonymoushttp://www.blogger.com/profile/17958284505244135897noreply@blogger.com0tag:blogger.com,1999:blog-3329110015361344577.post-10611929722474332182015-12-07T14:38:00.000+01:002015-12-07T21:15:21.310+01:00Provably Weak Instances of Ring-LWE Revisited<div dir="ltr" style="text-align: left;" trbidi="on">
<div style="text-align: justify;">
<div style="background-color: white;">
In Crypto 2015, Elias, Lauter, Ozman and Stange <a href="https://eprint.iacr.org/2015/106.pdf" style="color: #1155cc;" target="_blank">[ELOS15]</a> proposed a successful attack on the <i>decision</i> version of the non-dual Ring-LWE problem over number fields $K$ for two specific families of defining polynomials. Both families have the common feature that the coefficients of the polynomials are dependent on the modulus $q$.</div>
<div style="background-color: white;">
<br /></div>
<div style="background-color: white;">
We extended this attack to the <i>search</i> version of Ring-LWE by using that the error distributions in such number fields are very skewed by moving away from the Minkowski space. Particularly, the largest errors either wrap around modulo $q$ (and thus make it impossible to decrypt the secret), or the smallest ones are so negligible that we obtain exact linear equations that reveal the secret. Our attack applies to every modulus up to $q$, and requires less samples.</div>
<div style="background-color: white;">
<br /></div>
<div style="background-color: white;">
Let $M$ be the $n \times n$ matrix of the canonical embedding $K \to \mathbb{C}^n$ with respect to the polynomial basis of $K$, and let $N$ be its inverse. The "skewness" of the errors can be nicely described by the singular value decomposition (SVD) of the matrix $N$ and the condition number $k(N) = s_1(N)/s_n(N)$, where $s_1$ and $s_n$ are the biggest and the smallest singular values correspondingly.</div>
<div style="background-color: white;">
<br /></div>
<div style="background-color: white;">
Recall that the SVD is given by $N = U \cdot \Sigma \cdot \overline{V}^t$, where $U$, $V$ are unitary matrices and $\Sigma$ is a diagonal matrix containing the singular values. The image of a unit sphere under $N$ will result in an ellipsoid whose axes are defined by the columns of $U$, with length equal to the corresponding singular value. Hence, the condition number captures how heavily this ellipsoid is deformed.</div>
<div style="background-color: white;">
<br /></div>
<div style="background-color: white;">
All vulnerable instances in <a href="https://eprint.iacr.org/2015/106.pdf" style="color: #1155cc;" target="_blank">[ELOS15]</a> are defined by polynomials $f_{n, a, b} = x^n +ax + b$, where $a$ and $b$ are such that $f(1) = 0 \bmod q$, which is the property that they exploit, but that our attack does not need. If we consider their first family of samples, where $a = 0$ and $b = q - 1$, the SVD of $N$ is of the form $I_{n \times n} \cdot \Sigma \cdot \overline{V}^t$. Thus a spherical error distribution on the Minkowski space with the parameter $\sigma$ induces an elliptical distribution on the number field, where the $i$th coordinate is distributed by a Gaussian with $\sigma_i = s_i(N) \cdot \sigma$. Moreover, the condition number is close to the modulus $q$, that is, the elliptical distribution is stretched along axes whose lengths range roughly from $\sigma_1$ to $q \cdot \sigma_1$. For the second family we did not find such an explicit form of the SVD. Nevertheless, the unitary matrix $U$ remains close to being diagonal (see the heat map below) and the singular values form a near-geometric series again leading to a condition number close to $q$.</div>
</div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhMPU83npgi5s0mkqpY9yqUAXFHaV2ySq6uf9fnkOJ_kyG4bhkpQv6guaCFI_gVECqf0uYDs2yG7dfLBq06uG6nzfLBKcO3IQJV5b85ADU4jxKD25fkYrgzgTSJbHgaO9MOVyJxUvdBnX8/s1600/heatmapblue_legend.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="202" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhMPU83npgi5s0mkqpY9yqUAXFHaV2ySq6uf9fnkOJ_kyG4bhkpQv6guaCFI_gVECqf0uYDs2yG7dfLBq06uG6nzfLBKcO3IQJV5b85ADU4jxKD25fkYrgzgTSJbHgaO9MOVyJxUvdBnX8/s320/heatmapblue_legend.png" width="320" /></a></div>
<div style="background-color: white; clear: both; text-align: justify;">
It can be easily seen that for both families and for the choices of $\sigma$ made in <a href="https://eprint.iacr.org/2015/106.pdf" style="color: #1155cc;" target="_blank">[ELOS15]</a>, the Ring-LWE distribution generates negligible errors in the higher terms of the polynomial basis. More precisely each Ring-LWE sample $(a, b = a \cdot s + e)$ can be written as</div>
<div style="clear: both; text-align: justify;">
\[ M_{a} \cdot (s_0, s_1, \dots, s_{n-1})^t = (b_{0}, b_{1}, \dots, b_{n-1})^t - (e_{0}, e_{1}, \dots, e_{n-1})^t , \]</div>
<div class="separator" style="clear: both; text-align: justify;">
<span class="im" style="background-color: white; color: #500050; font-family: "arial" , sans-serif; font-size: 12.8px; text-align: start;"></span></div>
<div style="background-color: white; clear: both; text-align: justify;">
where $M_{a}$ corresponds to multiplication by $a$. By rounding, the higher error terms are removed and the last equations become exact equations in the coefficients of the secret. If the highest $\left\lceil n/k \right\rceil$ error terms round to zero then we need only $k$ Ring-LWE samples to reveal the secret (for these concrete examples 10 samples amply suffice).</div>
<div class="separator" style="clear: both; text-align: justify;">
<br /></div>
<div class="separator" style="clear: both; text-align: justify;">
The corresponding paper will appear soon on the Eprint.</div>
<div class="separator" style="clear: both; text-align: justify;">
<br /></div>
<div class="separator" style="clear: both; text-align: justify;">
Wouter Castryck, Ilia Iliashenko and Fre Vercauteren.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
<br /></div>
</div>
Anonymoushttp://www.blogger.com/profile/16933150924637510682noreply@blogger.com0tag:blogger.com,1999:blog-3329110015361344577.post-31219503513614917832015-12-04T04:37:00.001+01:002015-12-04T04:37:53.228+01:00Workshop on Lattice Cryptography<div dir="ltr" style="text-align: left;" trbidi="on">
<div style="text-align: justify;">
It is the day after AsiaCrypt 2015 and there are two workshops being
held in Auckland. The one which is most relevant for my research is that
on Lattice Based Cryptography; which consists of four talks. One by
Jung Hee Cheon on "Multilinear Maps and Their Cryptanalysis", one by
Amit Sahai on "Obfuscation", one by Fre Vercauteren on "Weak Instances
of RLWE" and one by Martin Albrecht on "Small Secret LWE".</div>
<div style="text-align: justify;">
</div>
<hr />
<div style="text-align: justify;">
<br />
Cheon first described a very naive version of multi-linear maps and then
went on to show how this can be attacked by creating non-trivial
encodings of zero, and then taking greatest common divisors. Then he
went on to generalise this naive scheme to the CLT scheme (which is a
bit like the DGHV FHE scheme). The naive attack does not apply to CLT as
the dimension increased, meaning taking naive greatest common divisors
would not work. Cheon then showed how to extend the naive attack to the
CLT case by turning the gcd extraction into an eigenvalue extraction
problem. This done by building quadratic forms which represent encodings
of zero. The result is that for the CLT scheme one can break the
equivalent of the DLP problem.</div>
<div style="text-align: justify;">
</div>
<div style="text-align: justify;">
Cheon then went on to present the GGH scheme, which is a bit like the
NTRU FHE scheme; except the instead of encrypting via c=[(m+r*p)/z] for
an integer p, one encodes via c=[(m+r*g)/z] for a polynomial g which
generates the ideal lattice <g>. Modifying the prior attack in
this situation allows us to recover a basis of this ideal. But finding a
short vector in this lattice can be hard. However, by utilizing
encodings of zero one can actually solve the equivalent of the CDH
problem.</div>
<div style="text-align: justify;">
</div>
<div style="text-align: justify;">
Both attacks rely heavily on the presence of encodings of zero. So the
attacks do not apply to situations in which one does not publish such
encodings; i.e. applications such as indistinguishability Obfuscation
(iO).</div>
<br />
<br />
<br />
<hr />
<br />
<br />
Amit Sahai then gave an introduction to iO; he motivated it via an
analogy of an attacker who captures your brain and is able to read and
tamper with every neuron, yet we still do not want the attacker to know
what we are thinking about. This is the problem which obfuscation tries
to solve in the computing realm. Martin pointed out that this would be a
great way to produce malware!<br />
<br />
Amit then put Multi-Party Computation within this analogy. He suggested
we can think of MPC as protecting our brain against the tampering
adversary, by dividing the brain up into portions. As long as one
portion is kept out of the adversaries control we can use MPC to protect
our thoughts. Obfuscation tries to do the same, without there needing
to be an honest part of the brain.<br />
<br />
Any program which is suitable for obfuscation must be unlearnable from
query access to the program. Since otherwise the adversary could learn
the program from the input/output behaviour. However, black-box
obfuscation has been shown to be impossible; essentially because their
are contrived programs which are unlearnable but for which one cannot
produce an obfuscation, since any obfuscated program has an explicit
attack against it.<br />
<br />
This is why iO as a concept was presented; since it at least seems
possible to achieve. The idea is that if you have two equivalent
programs and we obfuscate one of them, then the adversary cannot tell
which one we obfuscated. One way of thinking of this is as a
psuedo-canonicalizer. The question is what useful can one do if we could
create an obfuscator which satisfied the iO definition. Amit gave the
application of building demo versions of software, without needing to
re-engineer the software.<br />
<br />
<hr />
<br />
Fre Vercauteren then discussed a more in depth analysis of a paper from
CRYPTO this year on Weak Instances of Ring-LWE. The CRYPTO paper gave
instances where decision Ring-LWE was easy, but search appeared to be
hard. However, Fre's talk showed that the search problem was in fact
easy from the start, and thus the CRYPTO paper was less surprising than
it at first seemed to be. As with all things on Ring-LWE the question
arises as to how to choose the error distributions.<br />
<br />
Fre spend the first part of his talk discussing the geometry of number
fields, and in particular the Minkowski embedding. The Ring-LWE problem
generates errors according to a discrete Gaussian distribution in the
Minkowski embedding, Poly-LWE is to generate the errors according to a
discrete Gaussian in the polynomial embedding.<br />
<br />
Eisentrager et al discussed cases for which Poly-LWE was easy, these
were then extended by Elias et al to special cases of decision Ring-LWE.
They did this by mapping the special Ring-LWE instance to a special
Poly-LWE instance.This is done by pulling back the problem from Ring-LWE
to Poly-LWE via the matrix which defines the Minkowski embedding. The
Poly-LWE attack requires that q is larger than f(1), and hence q will
"kind of show up" in the coefficients of the defining polynomial f. So
the fields being attacked, are very special indeed.<br />
<br />
<br />
(This post originally appeared in the BristolCrypto blog)<br />
</div>
Nigel Smarthttp://www.blogger.com/profile/17681184541012804026noreply@blogger.com0tag:blogger.com,1999:blog-3329110015361344577.post-75518345971406653002015-12-01T14:31:00.000+01:002015-12-01T14:36:07.104+01:00C++ Library dedicated to arithmetic on cyclotomic rings: NFLlib<div style="text-align: justify;">
As a new Phd student working on the HEAT project at the UPMC, I spent the last two months reading some stuff about Fully Homomorphic Encryption. Among my different readings, I have noticed an article presenting a new promising open-source C++ library: NFLlib. It has been developed for both the HEAT project and CRYPTOCOMP and is dedicated to ideal lattice cryptography.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
This library deals with the arithmetic on the wide spread cyclotomic rings $\mathbb{Z}_q[X]/(X^n+1)$ with $n$ a power of two. At the difference of the Microsoft library SEAL which implements the YASHE encryption scheme, NFLlib provides the elementary functions to build any cryptosystems on those cyclotomic rings. By using Chinese Reminder Theorem, an optimized Number Theoretic Transform and different implementation optimization techniques for SIMD instructions it achieves better performances than the classical libraries NTL and FLINT.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
This library will be available soon on <a href="https://github.com/quarkslab/NFLlib">https://github.com/quarkslab/NFLlib</a>, in the meantime the Francophones can refer to the article "Quatre millions d'échanges de clés par seconde" (Four millions key-exchanges per second) <a href="https://www.sstic.org/media/SSTIC2015/SSTIC-actes/4M_kx_per_sec/SSTIC2015-Article-4M_kx_per_sec-guinet_aguilar_guelton_lepoint.pdf">https://www.sstic.org/media/SSTIC2015/SSTIC-actes/4M_kx_per_sec/SSTIC2015-Article-4M_kx_per_sec-guinet_aguilar_guelton_lepoint.pdf</a> which presents it as well as the performances of a key-exchange protocol using a lattice based encryption scheme. For the non-french speakers an english version has been accepted at CT-RSA 2016 and will be available soon on the Eprint. </div>
Vincent Zuccahttp://www.blogger.com/profile/15345237115554901147noreply@blogger.com0tag:blogger.com,1999:blog-3329110015361344577.post-62707260466187701122015-11-16T10:04:00.001+01:002015-11-16T10:04:12.670+01:00Microsoft Launch SEAL<div dir="ltr" style="text-align: left;" trbidi="on">
<div style="text-align: justify;">
It is not just the HEAT project which is working on trying to find applications of Somewhat Homomorphic Encryption in practice; others around the world are also doing this. In particular Microsoft Research Labs have just announced a project called SEAL(Simple Encrypted Arithmetic Library) which is detailed in the following paper: <a href="http://research.microsoft.com/pubs/258435/ManualHE.pdf">http://research.microsoft.com/pubs/258435/ManualHE.pdf</a> with code available here <a href="http://sealcrypto.codeplex.com/">http://sealcrypto.codeplex.com/</a></div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
The Microsoft work is aimed at medical information, in particular bioinfomatics algorithms related to genomic data. The SEAL project is built around the YASHE SHE scheme based on the cyclotomic ring defined by $X^n+1$, for $n$ a power of two. The associated paper explains how large integers and floating point operations can be encoded within the YASHE scheme.</div>
</div>
Nigel Smarthttp://www.blogger.com/profile/17681184541012804026noreply@blogger.com0tag:blogger.com,1999:blog-3329110015361344577.post-67026267280228285922015-11-04T14:07:00.000+01:002015-11-04T14:07:16.079+01:00Using the Rényi divergence rather than the statistical distance in lattice-based cryptography<div dir="ltr" style="text-align: left;" trbidi="on">
To analyze the efficiency of the homomorphic encryption schemes at the core of the HEAT project, we studied how the Rényi divergence can be used instead of the statistical distance. The Rényi divergence is a measure of closeness of two probability distributions. In the HEAT project, we obtained that the latter divergence can often be used as an alternative to the statistical distance in security proofs for lattice-based cryptography, and therefore in homomorphic encryption schemes.<br />
<br />
Our contributions are as follows:<br />
<br />
<ul style="text-align: left;">
<li>Smaller signatures for the Hash-and-Sign <a href="https://eprint.iacr.org/2007/432">Gentry-Peikert-Vaikuntanathan signature scheme</a></li>
<li>Smaller storage requirement for the Fiat-Shamir <a href="https://eprint.iacr.org/2013/383">BLISS signature scheme</a></li>
<li>Alternative proof that the Learning With Errors problem with noise
chosen uniformly in an interval is no easier than the Learning With Errors
problem with Gaussian noise (and tighter reduction!)</li>
<li>Smaller parameters for the <a href="https://eprint.iacr.org/2007/432">dual-Regev encryption scheme</a></li>
</ul>
<br />
and are described in the article<br />
<br />
<div style="text-align: center;">
<b style="background-color: white; text-align: start;"><a href="https://eprint.iacr.org/2015/483">Improved security proofs in lattice-based cryptography: using the Rényi divergence rather than the statistical distance</a></b></div>
<div style="text-align: center;">
<em style="background-color: white; text-align: start;">Shi Bai and Adeline Langlois and Tancrède Lepoint and Damien Stehlé and Ron Steinfeld</em></div>
<br />
<div>
This article has been accepted for publication at <a href="https://www.math.auckland.ac.nz/~sgal018/AC2015/" style="text-decoration: underline;">ASIACRYPT 2015</a> and will receive the <i><b>Best Paper Award</b></i>.</div>
<div>
<br /></div>
<div>
ASIACRYPT 2015 is one of the top-tier conference of cryptography, organized by the IACR, and will take place in December 2015 in New Zealand.</div>
</div>
Anonymousnoreply@blogger.com0tag:blogger.com,1999:blog-3329110015361344577.post-7738486154160196702015-10-20T09:23:00.000+02:002015-10-20T09:23:00.046+02:00HEAT Summer School on FHE and MLM in Paris<div class="MsoNormal">
Last week, the HEAT summer school on Mathematical and Practical aspects of Fully Homomorphic Encryption and Multilinear Maps took place in (almost) sunny Paris. The talks all covered a range of subjects, with around three talks per topic, which allowed for a good in-depth understanding of what was being presented.<o:p></o:p></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
The school started off with defining what Fully Homomorphic Encryption is, and why we would want to use it. The main application is, of course, outsourcing computation. I have a bunch of data I want to compute on, but do not want (or cannot) compute it all by myself, so I would like to outsource it to an external server. But I may not trust the server, and do not want it to learn anything about my data. So I would like to have an encryption scheme where I encrypt my data, then send it off to someone to perform computations on it, and at the end I recover the result of the computation. This is exactly what FHE gives us.<o:p></o:p></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
Most FHE schemes are based on the Learning with Errors problem, which was presented in detail on the first day. This was presented in <a href="http://www.cims.nyu.edu/~regev/papers/lwesurvey.pdf">[R05]</a>. This was followed by a discussion of the <a href="https://eprint.iacr.org/2013/340.pdf">[GSW13]</a> cryptosystem, based on the approximate eigenvector method.<o:p></o:p></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
This was followed by a discussion of the Ring Learning with Errors problems, and a brief presentation of the various reductions, as presented in <a href="https://eprint.iacr.org/2012/230.pdf">[LPR10]</a>. A presentation of the <a href="https://eprint.iacr.org/2011/277.pdf">BGV</a> cryptosystem was given, together with an introduction about the use of Galois theory in RLWE schemes, in order to use the “packed ciphertexts” method.<o:p></o:p></div>
<div class="MsoNormal">
<br /></div>
<div class="MsoNormal">
The third day of the summer school was the day for Multilinear Maps. The CLT and GGH schemes were discussed, and also a brief discussion on attacks. The summary is that although there are zeroizing attacks for all the constructions at the moment, these do not seem to affect the obfuscation applications. All the attacks are constructed from low-level encodings of zero, which is why the attacks do not apply to obfuscation applications.</div>
<div class="MsoNormal">
<br /></div>
<br />
<div class="MsoNormal">
The morning of the fourth day was very mathematical, and consisted of two talks on the algebraic geometry of numbers and the LLL and BKZ algorithms and on recovering short generators in principal ideal, see here. This was followed by a presentation of zeroizing attacks on multilinear maps. The final day of the school was devoted to obfuscation. This started with stating the surprising fact that if $P=NP$ then this implies that any program can be obfuscated. Thus, unlike any other cryptography, iO cannot imply hardness; but it can be used to leverage hardness. The idea of using straddling sets from [BGKPS] to construct obfuscation from branching programs was also discussed.</div>
Anonymoushttp://www.blogger.com/profile/15365495822521605931noreply@blogger.com0tag:blogger.com,1999:blog-3329110015361344577.post-50494737591283743652015-09-22T12:08:00.000+02:002015-09-22T12:08:51.315+02:00Which Ring Based Somewhat Homomorphic Encryption Scheme is Best?<div dir="ltr" style="text-align: left;" trbidi="on">
This post is based on HEAT output <a href="http://eprint.iacr.org/2015/889">http://eprint.iacr.org/2015/889</a><br />
<br />
<div style="text-align: justify;">
There are a number of different Ring-LWE based homomorphic encryption schemes. The two most famous being the BGV scheme (due to Brakerski, Gentry and Vaikuntanathan) and a modification of the famous NTRU encryption scheme. Each of these schemes comes in two flavours, in the first (traditional) flavour the messages are held in the lower order bits, whilst in the so-called scale-invariant flavours the messages are held in the upper order bits. The advantage of the scale-invariant systems are that they avoid the need for strong noise control procedures such as modulus switching.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
A lot of work has been conducted into optimizing these schemes, but many papers only consider a certain set of parameters (for example some consider characteristic two plaintext spaces only), or some consider only one form of key-switching operation (there are two main variants of key switching in the literature). Generally speaking the usual consensus is that the scale-invariant version of the NTRU scheme (called YASHE) is to be preferred. This consensus is because YASHE offers the benefits of scale-invariance. In addition ciphertexts consist of only one ring element; as opposed to the two needed for the BGV schemes.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
This consensus is however based on limited exploration of the design space. In HEAT output "<b>Which Ring Based Somewhat Homomorphic Encryption Scheme is Best?</b>"<b> </b>by Bristol researchers Ana Costache and Nigel P. Smart the authors explore the design space in more detail. They examine all four schemes using a consistent mathematical model of noise growth for the first time; previous work uses a different model for each scheme in each paper. They conclude that whilst YASHE may be preferable for small characteristic plaintext spaces, for large plaintext spaces the BGV scheme (in the non-scale invariant form) comes out being significantly more efficient. This conclusion holds irrespective of the number of levels (i.e. multiplicative depth) which one requires the homomorphic encryption scheme to support.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
Such an analysis has important implications for practical applications of homomorphic encryption. Different application domains will place different constraints on the plaintext spaces. For example if one is evaluating binary circuits in an application then a characteristic two plaintext space is to be preferred. However, if one is evaluating a complex arithmetic expression (such as in a statistical analysis) than one may model the plaintext as integers and hence utilize a large characteristic to avoid integer overflow.</div>
</div>
Nigel Smarthttp://www.blogger.com/profile/17681184541012804026noreply@blogger.com0tag:blogger.com,1999:blog-3329110015361344577.post-21524878244543537492015-07-13T16:28:00.000+02:002015-07-13T16:28:13.107+02:00Modular Hardware Architecture for Somewhat Homomorphic Function Evaluation<div dir="ltr" style="text-align: left;" trbidi="on">
<!--[if !mso]>
<style>
v\:* {behavior:url(#default#VML);}
o\:* {behavior:url(#default#VML);}
w\:* {behavior:url(#default#VML);}
.shape {behavior:url(#default#VML);}
</style>
<![endif]--><br />
<!--[if gte mso 9]><xml>
<o:OfficeDocumentSettings>
<o:TargetScreenSize>800x600</o:TargetScreenSize>
</o:OfficeDocumentSettings>
</xml><![endif]--><!--[if gte mso 9]><xml>
<w:WordDocument>
<w:View>Normal</w:View>
<w:Zoom>0</w:Zoom>
<w:TrackMoves/>
<w:TrackFormatting/>
<w:PunctuationKerning/>
<w:ValidateAgainstSchemas/>
<w:SaveIfXMLInvalid>false</w:SaveIfXMLInvalid>
<w:IgnoreMixedContent>false</w:IgnoreMixedContent>
<w:AlwaysShowPlaceholderText>false</w:AlwaysShowPlaceholderText>
<w:DoNotPromoteQF/>
<w:LidThemeOther>EN-GB</w:LidThemeOther>
<w:LidThemeAsian>X-NONE</w:LidThemeAsian>
<w:LidThemeComplexScript>X-NONE</w:LidThemeComplexScript>
<w:Compatibility>
<w:BreakWrappedTables/>
<w:SnapToGridInCell/>
<w:WrapTextWithPunct/>
<w:UseAsianBreakRules/>
<w:DontGrowAutofit/>
<w:SplitPgBreakAndParaMark/>
<w:EnableOpenTypeKerning/>
<w:DontFlipMirrorIndents/>
<w:OverrideTableStyleHps/>
<w:UseFELayout/>
</w:Compatibility>
<w:BrowserLevel>MicrosoftInternetExplorer4</w:BrowserLevel>
<m:mathPr>
<m:mathFont m:val="Cambria Math"/>
<m:brkBin m:val="before"/>
<m:brkBinSub m:val="--"/>
<m:smallFrac m:val="off"/>
<m:dispDef/>
<m:lMargin m:val="0"/>
<m:rMargin m:val="0"/>
<m:defJc m:val="centerGroup"/>
<m:wrapIndent m:val="1440"/>
<m:intLim m:val="subSup"/>
<m:naryLim m:val="undOvr"/>
</m:mathPr></w:WordDocument>
</xml><![endif]--><!--[if gte mso 9]><xml>
<w:LatentStyles DefLockedState="false" DefUnhideWhenUsed="false"
DefSemiHidden="false" DefQFormat="false" DefPriority="99"
LatentStyleCount="371">
<w:LsdException Locked="false" Priority="0" QFormat="true" Name="Normal"/>
<w:LsdException Locked="false" Priority="9" QFormat="true" Name="heading 1"/>
<w:LsdException Locked="false" Priority="9" SemiHidden="true"
UnhideWhenUsed="true" QFormat="true" Name="heading 2"/>
<w:LsdException Locked="false" Priority="9" SemiHidden="true"
UnhideWhenUsed="true" QFormat="true" Name="heading 3"/>
<w:LsdException Locked="false" Priority="9" SemiHidden="true"
UnhideWhenUsed="true" QFormat="true" Name="heading 4"/>
<w:LsdException Locked="false" Priority="9" SemiHidden="true"
UnhideWhenUsed="true" QFormat="true" Name="heading 5"/>
<w:LsdException Locked="false" Priority="9" SemiHidden="true"
UnhideWhenUsed="true" QFormat="true" Name="heading 6"/>
<w:LsdException Locked="false" Priority="9" SemiHidden="true"
UnhideWhenUsed="true" QFormat="true" Name="heading 7"/>
<w:LsdException Locked="false" Priority="9" SemiHidden="true"
UnhideWhenUsed="true" QFormat="true" Name="heading 8"/>
<w:LsdException Locked="false" Priority="9" SemiHidden="true"
UnhideWhenUsed="true" QFormat="true" Name="heading 9"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="index 1"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="index 2"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="index 3"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="index 4"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="index 5"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="index 6"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="index 7"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="index 8"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="index 9"/>
<w:LsdException Locked="false" Priority="39" SemiHidden="true"
UnhideWhenUsed="true" Name="toc 1"/>
<w:LsdException Locked="false" Priority="39" SemiHidden="true"
UnhideWhenUsed="true" Name="toc 2"/>
<w:LsdException Locked="false" Priority="39" SemiHidden="true"
UnhideWhenUsed="true" Name="toc 3"/>
<w:LsdException Locked="false" Priority="39" SemiHidden="true"
UnhideWhenUsed="true" Name="toc 4"/>
<w:LsdException Locked="false" Priority="39" SemiHidden="true"
UnhideWhenUsed="true" Name="toc 5"/>
<w:LsdException Locked="false" Priority="39" SemiHidden="true"
UnhideWhenUsed="true" Name="toc 6"/>
<w:LsdException Locked="false" Priority="39" SemiHidden="true"
UnhideWhenUsed="true" Name="toc 7"/>
<w:LsdException Locked="false" Priority="39" SemiHidden="true"
UnhideWhenUsed="true" Name="toc 8"/>
<w:LsdException Locked="false" Priority="39" SemiHidden="true"
UnhideWhenUsed="true" Name="toc 9"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Normal Indent"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="footnote text"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="annotation text"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="header"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="footer"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="index heading"/>
<w:LsdException Locked="false" Priority="35" SemiHidden="true"
UnhideWhenUsed="true" QFormat="true" Name="caption"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="table of figures"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="envelope address"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="envelope return"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="footnote reference"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="annotation reference"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="line number"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="page number"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="endnote reference"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="endnote text"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="table of authorities"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="macro"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="toa heading"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="List"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="List Bullet"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="List Number"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="List 2"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="List 3"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="List 4"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="List 5"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="List Bullet 2"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="List Bullet 3"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="List Bullet 4"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="List Bullet 5"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="List Number 2"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="List Number 3"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="List Number 4"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="List Number 5"/>
<w:LsdException Locked="false" Priority="10" QFormat="true" Name="Title"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Closing"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Signature"/>
<w:LsdException Locked="false" Priority="0" SemiHidden="true"
UnhideWhenUsed="true" Name="Default Paragraph Font"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Body Text"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Body Text Indent"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="List Continue"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="List Continue 2"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="List Continue 3"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="List Continue 4"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="List Continue 5"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Message Header"/>
<w:LsdException Locked="false" Priority="11" QFormat="true" Name="Subtitle"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Salutation"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Date"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Body Text First Indent"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Body Text First Indent 2"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Note Heading"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Body Text 2"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Body Text 3"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Body Text Indent 2"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Body Text Indent 3"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Block Text"/>
<w:LsdException Locked="false" Priority="0" SemiHidden="true"
UnhideWhenUsed="true" Name="Hyperlink"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="FollowedHyperlink"/>
<w:LsdException Locked="false" Priority="22" QFormat="true" Name="Strong"/>
<w:LsdException Locked="false" Priority="20" QFormat="true" Name="Emphasis"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Document Map"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Plain Text"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="E-mail Signature"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="HTML Top of Form"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="HTML Bottom of Form"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Normal (Web)"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="HTML Acronym"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="HTML Address"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="HTML Cite"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="HTML Code"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="HTML Definition"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="HTML Keyboard"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="HTML Preformatted"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="HTML Sample"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="HTML Typewriter"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="HTML Variable"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Normal Table"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="annotation subject"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="No List"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Outline List 1"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Outline List 2"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Outline List 3"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table Simple 1"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table Simple 2"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table Simple 3"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table Classic 1"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table Classic 2"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table Classic 3"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table Classic 4"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table Colorful 1"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table Colorful 2"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table Colorful 3"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table Columns 1"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table Columns 2"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table Columns 3"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table Columns 4"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table Columns 5"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table Grid 1"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table Grid 2"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table Grid 3"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table Grid 4"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table Grid 5"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table Grid 6"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table Grid 7"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table Grid 8"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table List 1"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table List 2"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table List 3"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table List 4"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table List 5"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table List 6"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table List 7"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table List 8"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table 3D effects 1"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table 3D effects 2"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table 3D effects 3"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table Contemporary"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table Elegant"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table Professional"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table Subtle 1"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table Subtle 2"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table Web 1"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table Web 2"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table Web 3"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Balloon Text"/>
<w:LsdException Locked="false" Priority="39" Name="Table Grid"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table Theme"/>
<w:LsdException Locked="false" SemiHidden="true" Name="Placeholder Text"/>
<w:LsdException Locked="false" Priority="1" QFormat="true" Name="No Spacing"/>
<w:LsdException Locked="false" Priority="60" Name="Light Shading"/>
<w:LsdException Locked="false" Priority="61" Name="Light List"/>
<w:LsdException Locked="false" Priority="62" Name="Light Grid"/>
<w:LsdException Locked="false" Priority="63" Name="Medium Shading 1"/>
<w:LsdException Locked="false" Priority="64" Name="Medium Shading 2"/>
<w:LsdException Locked="false" Priority="65" Name="Medium List 1"/>
<w:LsdException Locked="false" Priority="66" Name="Medium List 2"/>
<w:LsdException Locked="false" Priority="67" Name="Medium Grid 1"/>
<w:LsdException Locked="false" Priority="68" Name="Medium Grid 2"/>
<w:LsdException Locked="false" Priority="69" Name="Medium Grid 3"/>
<w:LsdException Locked="false" Priority="70" Name="Dark List"/>
<w:LsdException Locked="false" Priority="71" Name="Colorful Shading"/>
<w:LsdException Locked="false" Priority="72" Name="Colorful List"/>
<w:LsdException Locked="false" Priority="73" Name="Colorful Grid"/>
<w:LsdException Locked="false" Priority="60" Name="Light Shading Accent 1"/>
<w:LsdException Locked="false" Priority="61" Name="Light List Accent 1"/>
<w:LsdException Locked="false" Priority="62" Name="Light Grid Accent 1"/>
<w:LsdException Locked="false" Priority="63" Name="Medium Shading 1 Accent 1"/>
<w:LsdException Locked="false" Priority="64" Name="Medium Shading 2 Accent 1"/>
<w:LsdException Locked="false" Priority="65" Name="Medium List 1 Accent 1"/>
<w:LsdException Locked="false" SemiHidden="true" Name="Revision"/>
<w:LsdException Locked="false" Priority="34" QFormat="true"
Name="List Paragraph"/>
<w:LsdException Locked="false" Priority="29" QFormat="true" Name="Quote"/>
<w:LsdException Locked="false" Priority="30" QFormat="true"
Name="Intense Quote"/>
<w:LsdException Locked="false" Priority="66" Name="Medium List 2 Accent 1"/>
<w:LsdException Locked="false" Priority="67" Name="Medium Grid 1 Accent 1"/>
<w:LsdException Locked="false" Priority="68" Name="Medium Grid 2 Accent 1"/>
<w:LsdException Locked="false" Priority="69" Name="Medium Grid 3 Accent 1"/>
<w:LsdException Locked="false" Priority="70" Name="Dark List Accent 1"/>
<w:LsdException Locked="false" Priority="71" Name="Colorful Shading Accent 1"/>
<w:LsdException Locked="false" Priority="72" Name="Colorful List Accent 1"/>
<w:LsdException Locked="false" Priority="73" Name="Colorful Grid Accent 1"/>
<w:LsdException Locked="false" Priority="60" Name="Light Shading Accent 2"/>
<w:LsdException Locked="false" Priority="61" Name="Light List Accent 2"/>
<w:LsdException Locked="false" Priority="62" Name="Light Grid Accent 2"/>
<w:LsdException Locked="false" Priority="63" Name="Medium Shading 1 Accent 2"/>
<w:LsdException Locked="false" Priority="64" Name="Medium Shading 2 Accent 2"/>
<w:LsdException Locked="false" Priority="65" Name="Medium List 1 Accent 2"/>
<w:LsdException Locked="false" Priority="66" Name="Medium List 2 Accent 2"/>
<w:LsdException Locked="false" Priority="67" Name="Medium Grid 1 Accent 2"/>
<w:LsdException Locked="false" Priority="68" Name="Medium Grid 2 Accent 2"/>
<w:LsdException Locked="false" Priority="69" Name="Medium Grid 3 Accent 2"/>
<w:LsdException Locked="false" Priority="70" Name="Dark List Accent 2"/>
<w:LsdException Locked="false" Priority="71" Name="Colorful Shading Accent 2"/>
<w:LsdException Locked="false" Priority="72" Name="Colorful List Accent 2"/>
<w:LsdException Locked="false" Priority="73" Name="Colorful Grid Accent 2"/>
<w:LsdException Locked="false" Priority="60" Name="Light Shading Accent 3"/>
<w:LsdException Locked="false" Priority="61" Name="Light List Accent 3"/>
<w:LsdException Locked="false" Priority="62" Name="Light Grid Accent 3"/>
<w:LsdException Locked="false" Priority="63" Name="Medium Shading 1 Accent 3"/>
<w:LsdException Locked="false" Priority="64" Name="Medium Shading 2 Accent 3"/>
<w:LsdException Locked="false" Priority="65" Name="Medium List 1 Accent 3"/>
<w:LsdException Locked="false" Priority="66" Name="Medium List 2 Accent 3"/>
<w:LsdException Locked="false" Priority="67" Name="Medium Grid 1 Accent 3"/>
<w:LsdException Locked="false" Priority="68" Name="Medium Grid 2 Accent 3"/>
<w:LsdException Locked="false" Priority="69" Name="Medium Grid 3 Accent 3"/>
<w:LsdException Locked="false" Priority="70" Name="Dark List Accent 3"/>
<w:LsdException Locked="false" Priority="71" Name="Colorful Shading Accent 3"/>
<w:LsdException Locked="false" Priority="72" Name="Colorful List Accent 3"/>
<w:LsdException Locked="false" Priority="73" Name="Colorful Grid Accent 3"/>
<w:LsdException Locked="false" Priority="60" Name="Light Shading Accent 4"/>
<w:LsdException Locked="false" Priority="61" Name="Light List Accent 4"/>
<w:LsdException Locked="false" Priority="62" Name="Light Grid Accent 4"/>
<w:LsdException Locked="false" Priority="63" Name="Medium Shading 1 Accent 4"/>
<w:LsdException Locked="false" Priority="64" Name="Medium Shading 2 Accent 4"/>
<w:LsdException Locked="false" Priority="65" Name="Medium List 1 Accent 4"/>
<w:LsdException Locked="false" Priority="66" Name="Medium List 2 Accent 4"/>
<w:LsdException Locked="false" Priority="67" Name="Medium Grid 1 Accent 4"/>
<w:LsdException Locked="false" Priority="68" Name="Medium Grid 2 Accent 4"/>
<w:LsdException Locked="false" Priority="69" Name="Medium Grid 3 Accent 4"/>
<w:LsdException Locked="false" Priority="70" Name="Dark List Accent 4"/>
<w:LsdException Locked="false" Priority="71" Name="Colorful Shading Accent 4"/>
<w:LsdException Locked="false" Priority="72" Name="Colorful List Accent 4"/>
<w:LsdException Locked="false" Priority="73" Name="Colorful Grid Accent 4"/>
<w:LsdException Locked="false" Priority="60" Name="Light Shading Accent 5"/>
<w:LsdException Locked="false" Priority="61" Name="Light List Accent 5"/>
<w:LsdException Locked="false" Priority="62" Name="Light Grid Accent 5"/>
<w:LsdException Locked="false" Priority="63" Name="Medium Shading 1 Accent 5"/>
<w:LsdException Locked="false" Priority="64" Name="Medium Shading 2 Accent 5"/>
<w:LsdException Locked="false" Priority="65" Name="Medium List 1 Accent 5"/>
<w:LsdException Locked="false" Priority="66" Name="Medium List 2 Accent 5"/>
<w:LsdException Locked="false" Priority="67" Name="Medium Grid 1 Accent 5"/>
<w:LsdException Locked="false" Priority="68" Name="Medium Grid 2 Accent 5"/>
<w:LsdException Locked="false" Priority="69" Name="Medium Grid 3 Accent 5"/>
<w:LsdException Locked="false" Priority="70" Name="Dark List Accent 5"/>
<w:LsdException Locked="false" Priority="71" Name="Colorful Shading Accent 5"/>
<w:LsdException Locked="false" Priority="72" Name="Colorful List Accent 5"/>
<w:LsdException Locked="false" Priority="73" Name="Colorful Grid Accent 5"/>
<w:LsdException Locked="false" Priority="60" Name="Light Shading Accent 6"/>
<w:LsdException Locked="false" Priority="61" Name="Light List Accent 6"/>
<w:LsdException Locked="false" Priority="62" Name="Light Grid Accent 6"/>
<w:LsdException Locked="false" Priority="63" Name="Medium Shading 1 Accent 6"/>
<w:LsdException Locked="false" Priority="64" Name="Medium Shading 2 Accent 6"/>
<w:LsdException Locked="false" Priority="65" Name="Medium List 1 Accent 6"/>
<w:LsdException Locked="false" Priority="66" Name="Medium List 2 Accent 6"/>
<w:LsdException Locked="false" Priority="67" Name="Medium Grid 1 Accent 6"/>
<w:LsdException Locked="false" Priority="68" Name="Medium Grid 2 Accent 6"/>
<w:LsdException Locked="false" Priority="69" Name="Medium Grid 3 Accent 6"/>
<w:LsdException Locked="false" Priority="70" Name="Dark List Accent 6"/>
<w:LsdException Locked="false" Priority="71" Name="Colorful Shading Accent 6"/>
<w:LsdException Locked="false" Priority="72" Name="Colorful List Accent 6"/>
<w:LsdException Locked="false" Priority="73" Name="Colorful Grid Accent 6"/>
<w:LsdException Locked="false" Priority="19" QFormat="true"
Name="Subtle Emphasis"/>
<w:LsdException Locked="false" Priority="21" QFormat="true"
Name="Intense Emphasis"/>
<w:LsdException Locked="false" Priority="31" QFormat="true"
Name="Subtle Reference"/>
<w:LsdException Locked="false" Priority="32" QFormat="true"
Name="Intense Reference"/>
<w:LsdException Locked="false" Priority="33" QFormat="true" Name="Book Title"/>
<w:LsdException Locked="false" Priority="37" SemiHidden="true"
UnhideWhenUsed="true" Name="Bibliography"/>
<w:LsdException Locked="false" Priority="39" SemiHidden="true"
UnhideWhenUsed="true" QFormat="true" Name="TOC Heading"/>
<w:LsdException Locked="false" Priority="41" Name="Plain Table 1"/>
<w:LsdException Locked="false" Priority="42" Name="Plain Table 2"/>
<w:LsdException Locked="false" Priority="43" Name="Plain Table 3"/>
<w:LsdException Locked="false" Priority="44" Name="Plain Table 4"/>
<w:LsdException Locked="false" Priority="45" Name="Plain Table 5"/>
<w:LsdException Locked="false" Priority="40" Name="Grid Table Light"/>
<w:LsdException Locked="false" Priority="46" Name="Grid Table 1 Light"/>
<w:LsdException Locked="false" Priority="47" Name="Grid Table 2"/>
<w:LsdException Locked="false" Priority="48" Name="Grid Table 3"/>
<w:LsdException Locked="false" Priority="49" Name="Grid Table 4"/>
<w:LsdException Locked="false" Priority="50" Name="Grid Table 5 Dark"/>
<w:LsdException Locked="false" Priority="51" Name="Grid Table 6 Colorful"/>
<w:LsdException Locked="false" Priority="52" Name="Grid Table 7 Colorful"/>
<w:LsdException Locked="false" Priority="46"
Name="Grid Table 1 Light Accent 1"/>
<w:LsdException Locked="false" Priority="47" Name="Grid Table 2 Accent 1"/>
<w:LsdException Locked="false" Priority="48" Name="Grid Table 3 Accent 1"/>
<w:LsdException Locked="false" Priority="49" Name="Grid Table 4 Accent 1"/>
<w:LsdException Locked="false" Priority="50" Name="Grid Table 5 Dark Accent 1"/>
<w:LsdException Locked="false" Priority="51"
Name="Grid Table 6 Colorful Accent 1"/>
<w:LsdException Locked="false" Priority="52"
Name="Grid Table 7 Colorful Accent 1"/>
<w:LsdException Locked="false" Priority="46"
Name="Grid Table 1 Light Accent 2"/>
<w:LsdException Locked="false" Priority="47" Name="Grid Table 2 Accent 2"/>
<w:LsdException Locked="false" Priority="48" Name="Grid Table 3 Accent 2"/>
<w:LsdException Locked="false" Priority="49" Name="Grid Table 4 Accent 2"/>
<w:LsdException Locked="false" Priority="50" Name="Grid Table 5 Dark Accent 2"/>
<w:LsdException Locked="false" Priority="51"
Name="Grid Table 6 Colorful Accent 2"/>
<w:LsdException Locked="false" Priority="52"
Name="Grid Table 7 Colorful Accent 2"/>
<w:LsdException Locked="false" Priority="46"
Name="Grid Table 1 Light Accent 3"/>
<w:LsdException Locked="false" Priority="47" Name="Grid Table 2 Accent 3"/>
<w:LsdException Locked="false" Priority="48" Name="Grid Table 3 Accent 3"/>
<w:LsdException Locked="false" Priority="49" Name="Grid Table 4 Accent 3"/>
<w:LsdException Locked="false" Priority="50" Name="Grid Table 5 Dark Accent 3"/>
<w:LsdException Locked="false" Priority="51"
Name="Grid Table 6 Colorful Accent 3"/>
<w:LsdException Locked="false" Priority="52"
Name="Grid Table 7 Colorful Accent 3"/>
<w:LsdException Locked="false" Priority="46"
Name="Grid Table 1 Light Accent 4"/>
<w:LsdException Locked="false" Priority="47" Name="Grid Table 2 Accent 4"/>
<w:LsdException Locked="false" Priority="48" Name="Grid Table 3 Accent 4"/>
<w:LsdException Locked="false" Priority="49" Name="Grid Table 4 Accent 4"/>
<w:LsdException Locked="false" Priority="50" Name="Grid Table 5 Dark Accent 4"/>
<w:LsdException Locked="false" Priority="51"
Name="Grid Table 6 Colorful Accent 4"/>
<w:LsdException Locked="false" Priority="52"
Name="Grid Table 7 Colorful Accent 4"/>
<w:LsdException Locked="false" Priority="46"
Name="Grid Table 1 Light Accent 5"/>
<w:LsdException Locked="false" Priority="47" Name="Grid Table 2 Accent 5"/>
<w:LsdException Locked="false" Priority="48" Name="Grid Table 3 Accent 5"/>
<w:LsdException Locked="false" Priority="49" Name="Grid Table 4 Accent 5"/>
<w:LsdException Locked="false" Priority="50" Name="Grid Table 5 Dark Accent 5"/>
<w:LsdException Locked="false" Priority="51"
Name="Grid Table 6 Colorful Accent 5"/>
<w:LsdException Locked="false" Priority="52"
Name="Grid Table 7 Colorful Accent 5"/>
<w:LsdException Locked="false" Priority="46"
Name="Grid Table 1 Light Accent 6"/>
<w:LsdException Locked="false" Priority="47" Name="Grid Table 2 Accent 6"/>
<w:LsdException Locked="false" Priority="48" Name="Grid Table 3 Accent 6"/>
<w:LsdException Locked="false" Priority="49" Name="Grid Table 4 Accent 6"/>
<w:LsdException Locked="false" Priority="50" Name="Grid Table 5 Dark Accent 6"/>
<w:LsdException Locked="false" Priority="51"
Name="Grid Table 6 Colorful Accent 6"/>
<w:LsdException Locked="false" Priority="52"
Name="Grid Table 7 Colorful Accent 6"/>
<w:LsdException Locked="false" Priority="46" Name="List Table 1 Light"/>
<w:LsdException Locked="false" Priority="47" Name="List Table 2"/>
<w:LsdException Locked="false" Priority="48" Name="List Table 3"/>
<w:LsdException Locked="false" Priority="49" Name="List Table 4"/>
<w:LsdException Locked="false" Priority="50" Name="List Table 5 Dark"/>
<w:LsdException Locked="false" Priority="51" Name="List Table 6 Colorful"/>
<w:LsdException Locked="false" Priority="52" Name="List Table 7 Colorful"/>
<w:LsdException Locked="false" Priority="46"
Name="List Table 1 Light Accent 1"/>
<w:LsdException Locked="false" Priority="47" Name="List Table 2 Accent 1"/>
<w:LsdException Locked="false" Priority="48" Name="List Table 3 Accent 1"/>
<w:LsdException Locked="false" Priority="49" Name="List Table 4 Accent 1"/>
<w:LsdException Locked="false" Priority="50" Name="List Table 5 Dark Accent 1"/>
<w:LsdException Locked="false" Priority="51"
Name="List Table 6 Colorful Accent 1"/>
<w:LsdException Locked="false" Priority="52"
Name="List Table 7 Colorful Accent 1"/>
<w:LsdException Locked="false" Priority="46"
Name="List Table 1 Light Accent 2"/>
<w:LsdException Locked="false" Priority="47" Name="List Table 2 Accent 2"/>
<w:LsdException Locked="false" Priority="48" Name="List Table 3 Accent 2"/>
<w:LsdException Locked="false" Priority="49" Name="List Table 4 Accent 2"/>
<w:LsdException Locked="false" Priority="50" Name="List Table 5 Dark Accent 2"/>
<w:LsdException Locked="false" Priority="51"
Name="List Table 6 Colorful Accent 2"/>
<w:LsdException Locked="false" Priority="52"
Name="List Table 7 Colorful Accent 2"/>
<w:LsdException Locked="false" Priority="46"
Name="List Table 1 Light Accent 3"/>
<w:LsdException Locked="false" Priority="47" Name="List Table 2 Accent 3"/>
<w:LsdException Locked="false" Priority="48" Name="List Table 3 Accent 3"/>
<w:LsdException Locked="false" Priority="49" Name="List Table 4 Accent 3"/>
<w:LsdException Locked="false" Priority="50" Name="List Table 5 Dark Accent 3"/>
<w:LsdException Locked="false" Priority="51"
Name="List Table 6 Colorful Accent 3"/>
<w:LsdException Locked="false" Priority="52"
Name="List Table 7 Colorful Accent 3"/>
<w:LsdException Locked="false" Priority="46"
Name="List Table 1 Light Accent 4"/>
<w:LsdException Locked="false" Priority="47" Name="List Table 2 Accent 4"/>
<w:LsdException Locked="false" Priority="48" Name="List Table 3 Accent 4"/>
<w:LsdException Locked="false" Priority="49" Name="List Table 4 Accent 4"/>
<w:LsdException Locked="false" Priority="50" Name="List Table 5 Dark Accent 4"/>
<w:LsdException Locked="false" Priority="51"
Name="List Table 6 Colorful Accent 4"/>
<w:LsdException Locked="false" Priority="52"
Name="List Table 7 Colorful Accent 4"/>
<w:LsdException Locked="false" Priority="46"
Name="List Table 1 Light Accent 5"/>
<w:LsdException Locked="false" Priority="47" Name="List Table 2 Accent 5"/>
<w:LsdException Locked="false" Priority="48" Name="List Table 3 Accent 5"/>
<w:LsdException Locked="false" Priority="49" Name="List Table 4 Accent 5"/>
<w:LsdException Locked="false" Priority="50" Name="List Table 5 Dark Accent 5"/>
<w:LsdException Locked="false" Priority="51"
Name="List Table 6 Colorful Accent 5"/>
<w:LsdException Locked="false" Priority="52"
Name="List Table 7 Colorful Accent 5"/>
<w:LsdException Locked="false" Priority="46"
Name="List Table 1 Light Accent 6"/>
<w:LsdException Locked="false" Priority="47" Name="List Table 2 Accent 6"/>
<w:LsdException Locked="false" Priority="48" Name="List Table 3 Accent 6"/>
<w:LsdException Locked="false" Priority="49" Name="List Table 4 Accent 6"/>
<w:LsdException Locked="false" Priority="50" Name="List Table 5 Dark Accent 6"/>
<w:LsdException Locked="false" Priority="51"
Name="List Table 6 Colorful Accent 6"/>
<w:LsdException Locked="false" Priority="52"
Name="List Table 7 Colorful Accent 6"/>
</w:LatentStyles>
</xml><![endif]--><!--[if gte mso 10]>
<style>
/* Style Definitions */
table.MsoNormalTable
{mso-style-name:"Table Normal";
mso-tstyle-rowband-size:0;
mso-tstyle-colband-size:0;
mso-style-noshow:yes;
mso-style-priority:99;
mso-style-parent:"";
mso-padding-alt:0cm 5.4pt 0cm 5.4pt;
mso-para-margin:0cm;
mso-para-margin-bottom:.0001pt;
mso-pagination:widow-orphan;
font-size:10.0pt;
font-family:"Times New Roman",serif;}
</style>
<![endif]--><span lang="EN-US">This post is based on the paper <a href="https://eprint.iacr.org/2015/337">https://eprint.iacr.org/2015/337</a></span>
<br />
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<span lang="EN-US">This paper proposes an instruction-set hardware architecture for all
building blocks required in polynomial ring based fully homomorphic schemes and
uses the hardware architecture to instantiate the somewhat homomorphic
encryption scheme YASHE on a large Virtex 7 FPGA. The building blocks present
in the architecture are sufficiently generic to allow implementation of other
homomorphic schemes based on RLWE or NTRU.</span></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<b><span lang="EN-US">System Setup</span></b></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<b><span lang="EN-US"> </span></b><span lang="EN-US"> </span></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<span lang="EN-US">The computations are performed in a modular polynomial rings of the
form <i>R = Z[x]/(f(x))</i> where <i>f(x)</i> is a monic irreducible polynomial
<i>Φ<sub>d</sub>(x)</i> of degree <i>n</i>. To utilize single instruction
multiple data (SIMD) operations <i>f(x)</i> is a cyclotomic polynomial. The
plaintext space is <i>R<sub>2</sub></i>. </span>
</div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<span lang="EN-US">The used parameter supports homomorphic evaluations of SIMON-64/128
(having a multiplicative depth of 44); in particular <i>d</i> = 65535 (and thus
the degree of <i>f(x)</i> is <i>n</i>= 2<sup>15</sup>), log<sub>2</sub>(<i>q</i>)
= 1228 and the discrete Gaussian distribution with parameter is 8. The chosen
parameter set meets at least 128-bit security and SIMD in 2048 slots.</span></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<b><span lang="EN-US">High-level optimizations</span></b></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<span lang="EN-US">Two main operations in the YASHE scheme are the <i>YASHE.Add</i> for
homomorphic addition and the <i>YASHE.Mult</i> for homomorphic multiplication. While
<i>YASHE.Add </i>is relatively simple, <i>YASHE.Mult </i>is<i> </i>very costly
since one first needs to compute <i>c<sub>1</sub> · c<sub>2</sub></i> over the
integers, then scale the result by <i>t/q</i> and round, before mapping back
into the ring <i>R<sub>q</sub></i>. For the polynomial multiplication of such a
large degree <i>n</i> = 2<sup>15</sup>,<span style="mso-spacerun: yes;">
an </span>NTT is used over other polynomial multiplication algorithms thanks to
its almost linear time complexity. Moreover to tackle the problem of long integer
arithmetic CRT is used to split the coefficients into 30-bit small
coefficients. Application of the CRT helps to achieve parallelization and to
utilize the small DSP multipliers available in FPGAs. </span></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<b><span lang="EN-US">High-level Architecture</span></b></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<span lang="EN-US">The instruction-set architecture shown in the figure has three main
components: a computer, a HE-coprocessor and an external memory. The
HE-coprocessor is implemented on an FPGA and supports NTT of polynomials,
coefficient wise additions, subtractions and multiplications, computation of
the residues using the CRT, computation of the coefficients modulo a large
modulus from the CRT-residues, and scaling of the coefficients. The computer
works in master-mode and instructs the HE-coprocessor to perform the required
operations. Since the FPGA has a limited amount of internal memory in the form
of block RAMs, only few residue polynomials can be kept during a computation. A
large external memory is used to store the set of cipher-text polynomials. </span></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<span lang="EN-US">The HE-coprocessor has a set of parallel processors, where each
parallel processor is composed of several cores. The parallel processors are
independent of each other and supports a high degree of parallelism and
scalability. Since the architecture is very large, special care is taken to
reduce the routing complexity. For example, a routing-friendly parallel NTT algorithm
is used in the HE-coprocessor.<span style="mso-spacerun: yes;"> </span><span style="mso-spacerun: yes;"> </span></span></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div class="separator" style="clear: both; text-align: center;">
</div>
<div class="separator" style="clear: both; text-align: center;">
</div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEik3yTsPyu8RvoNrtEAdU_AdesZOMrLE7PiahyphenhyphenwxjxOjhDzPoVt-Ufdhw8gWBsOCUMLG5h1J6Z75o-X32sqgvkt2OhWNq88cQ5DYq-cW5R5z0m38NhL-IUGNfmRyiDALH_y6nBx6-6A8CDv/s1600/architecture.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="400" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEik3yTsPyu8RvoNrtEAdU_AdesZOMrLE7PiahyphenhyphenwxjxOjhDzPoVt-Ufdhw8gWBsOCUMLG5h1J6Z75o-X32sqgvkt2OhWNq88cQ5DYq-cW5R5z0m38NhL-IUGNfmRyiDALH_y6nBx6-6A8CDv/s400/architecture.png" width="356" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg5hJU4fsDItowW5IX5uvCd1Hu28-X6FT5kBfAuPuQ09ad41CWnpPkTCWDUxVPWBmqFFBz0rAA8mBO-jehGgcGrztYwtkbvNQSzIC8eLjP6hoj7gHrx-rsswBHiatI1JkAoRsDFwxEpYYWT/s1600/architecture.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><br /></a></div>
<br /></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<span lang="EN-US"></span></div>
<div class="separator" style="clear: both; text-align: center;">
</div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<b><span lang="EN-US">Experimental Results</span></b></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<span lang="EN-US">The designed HE-coprocessor with 8 parallel processors, each
processor having 16 parallel cores, 16 small-CRT units and 2 large-CRT units was
compiled for the Xilinx Virtex-7 XC7V1140T-2 FPGA, the largest device of the
Virtex-7 FPGA family. The architecture consumes 23 % of the available
registers, 50 % of LUTs, 53 % of DSP slices, and 38 % of block RAMs. This
implementation evaluates SIMON-64/128 in approximately 157.7s (at 143MHz) and
it processes 2048 cipher-texts at once giving a relative time of only 77ms per
block. This is 26.6 times faster than the leading software implementation on a
4-core Intel Core-i7 processor running at 3.4GHz. The timing values do not
consider the overhead of data transfer between the external memory and the
HE-coprocessor.</span></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<b><span lang="EN-US"> </span></b><b><span lang="EN-US">Future Work</span></b>
</div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<span lang="EN-US">1. The architecture does not implement the required interface
between the external memory and the FPGA-based HE-coprocessor. The cost of data
transfer is very important considering the vast amount of data exchange during
various operations; and hence the interface should be properly designed. It
should be noted that most of the memory access can be performed in parallel
with the computation using a ping-pong scheme of two sets of block RAMs in the
FPGA. The FPGA and the master-computer operate on these two sets alternatively
between two consecutive instructions: when the FPGA operates on the first set,
the master-computer operates on the second, and vice versa. Since only 38% of
the available block RAMs are utilized in the proposed architecture, such a
ping-pong styled memory access seems practical in order to reduce the cost of
memory access. </span></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<span lang="EN-US">2. The computation time can be reduced by performing low-level
optimizations in the architecture. For example, it might be possible to
increase the operating frequency beyond 200 MHz by optimizing the long critical
paths that are present in the architecture. The cycle requirement of the NTT
algorithm can also be reduced. Moreover, since the implemented architecture
consumes only ~50% of the available resources, it might be possible to put more
number of parallel processors in the FPGA. This will require area reduction of
each processor and a better placement-routing optimization.</span></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<br /></div>
<div class="MsoNormal" style="text-align: justify; text-justify: inter-ideograph;">
<span lang="EN-US">3. The results are obtained from a single FPGA. Since the
HE-coprocessor is composed of independent parallel processors, several FPGAs
can be used to scale down the computation time. </span><br />
<br />
<div class="iw" style="text-align: left;">
<span style="font-weight: normal;"><span class="gD" name="Sujoy Sinha Roy">Sujoy Sinha Roy</span></span></div>
</div>
</div>
Fre Vercauterenhttp://www.blogger.com/profile/05670274425599921874noreply@blogger.com0tag:blogger.com,1999:blog-3329110015361344577.post-36433303553202754102015-07-06T05:39:00.000+02:002015-07-06T05:39:08.900+02:00Cryptanalysis of the Co-ACD Assumption<div dir="ltr" style="text-align: left;" trbidi="on">
<span style="background-color: white; color: #212121; font-family: 'Helvetica Neue', Helvetica, Arial, sans-serif; font-size: 13.1999998092651px; line-height: 19.7999992370605px;">The HEAT project has a new public output: <a href="https://eprint.iacr.org/2014/1024">https://eprint.iacr.org/2014/1024</a></span><br />
<br />
Homomorphic cryptography (at the core of the HEAT project) allows to securely delegate computation over encrypted data and is a very active research area. At ACM-CCS 2014, a top-tier conference on computer and communications security, a <a href="http://dl.acm.org/citation.cfm?id=2660335">new scheme</a> claimed to be the "most efficient of those that support an additive homomorphic property" was proposed by Cheon, Lee and Seo.<br />
<br />
Understanding the <a href="http://heat-h2020-project.blogspot.com/2015/04/a-short-history-of-lattice-reduction-in.html">security</a> of the homomorphic cryptographic schemes is therefore of utmost importance, especially to select the most efficient and secure systems in HEAT. In this paper that will appear at <a href="http://www.iacr.org/conferences/crypto2015/">CRYPTO 2015</a>, a top-tier conference in cryptography, we show that the latter scheme is completely insecure. We present new lattice-based attacks that are effectively devastating for the proposed constructions. More precisely, we show that the parameters proposed by Cheon et al. and originally aiming at 128-bit security can be broken in a matter of seconds. And while it is possible to select parameters outside of the range in which our attacks run in polynomial time, they have to be so large as to render the proposed constructions severely uncompetitive (e.g. our asymptotic estimates indicate that 128 bits of security against our attacks require a modulus of at least 400,000 bits).</div>
Anonymousnoreply@blogger.com1tag:blogger.com,1999:blog-3329110015361344577.post-45725633791107526112015-07-03T09:28:00.003+02:002015-07-03T09:28:32.448+02:00Modular Hardware Architecture for Somewhat Homomorphic Function Evaluation<div dir="ltr" style="text-align: left;" trbidi="on">
The HEAT project has a new public output: <a href="https://eprint.iacr.org/2015/337">https://eprint.iacr.org/2015/337</a><br />
<br />
<div style="text-align: justify;">
This paper reports on a hardware architecture implementing all building blocks used in polynomial ring based fully
homomorphic schemes. As an example, the YASHE encryption
scheme is implemented on top of this architecture and the
SIMON-64/128 block cipher was executed in the encrypted domain.</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
The building blocks are integrated in an instruction-set
coprocessor, which can be controlled by a computer for
evaluating arbitrary functions (up to the multiplicative
depth 44 and 128-bit security level).</div>
<div style="text-align: justify;">
<br /></div>
<div style="text-align: justify;">
This implementation evaluates SIMON-64/128 in approximately
157.7s (at 143MHz) and it processes 2048 ciphertexts at once
giving a relative time of only 77ms per block. This is 26.6
times faster than the leading software implementation on a
4-core Intel Core-i7 processor running at 3.4GHz. </div>
</div>
Nigel Smarthttp://www.blogger.com/profile/17681184541012804026noreply@blogger.com0tag:blogger.com,1999:blog-3329110015361344577.post-7957971992497178452015-07-01T11:46:00.000+02:002015-07-02T12:59:08.713+02:00Yet Another Somewhat Homomorphic Encryption (YASHE) Scheme<!--[if gte mso 9]><xml>
<w:WordDocument>
<w:View>Normal</w:View>
<w:Zoom>0</w:Zoom>
<w:TrackMoves/>
<w:TrackFormatting/>
<w:PunctuationKerning/>
<w:ValidateAgainstSchemas/>
<w:SaveIfXMLInvalid>false</w:SaveIfXMLInvalid>
<w:IgnoreMixedContent>false</w:IgnoreMixedContent>
<w:AlwaysShowPlaceholderText>false</w:AlwaysShowPlaceholderText>
<w:DoNotPromoteQF/>
<w:LidThemeOther>EN-US</w:LidThemeOther>
<w:LidThemeAsian>X-NONE</w:LidThemeAsian>
<w:LidThemeComplexScript>X-NONE</w:LidThemeComplexScript>
<w:Compatibility>
<w:BreakWrappedTables/>
<w:SnapToGridInCell/>
<w:WrapTextWithPunct/>
<w:UseAsianBreakRules/>
<w:DontGrowAutofit/>
<w:SplitPgBreakAndParaMark/>
<w:EnableOpenTypeKerning/>
<w:DontFlipMirrorIndents/>
<w:OverrideTableStyleHps/>
</w:Compatibility>
<w:BrowserLevel>MicrosoftInternetExplorer4</w:BrowserLevel>
<m:mathPr>
<m:mathFont m:val="Cambria Math"/>
<m:brkBin m:val="before"/>
<m:brkBinSub m:val="--"/>
<m:smallFrac m:val="off"/>
<m:dispDef/>
<m:lMargin m:val="0"/>
<m:rMargin m:val="0"/>
<m:defJc m:val="centerGroup"/>
<m:wrapIndent m:val="1440"/>
<m:intLim m:val="subSup"/>
<m:naryLim m:val="undOvr"/>
</m:mathPr></w:WordDocument>
</xml><![endif]--><span style="font-family: inherit;"></span>
<!--[if gte mso 9]><xml>
<w:LatentStyles DefLockedState="false" DefUnhideWhenUsed="false"
DefSemiHidden="false" DefQFormat="false" DefPriority="99"
LatentStyleCount="371">
<w:LsdException Locked="false" Priority="0" QFormat="true" Name="Normal"/>
<w:LsdException Locked="false" Priority="9" QFormat="true" Name="heading 1"/>
<w:LsdException Locked="false" Priority="9" SemiHidden="true"
UnhideWhenUsed="true" QFormat="true" Name="heading 2"/>
<w:LsdException Locked="false" Priority="9" SemiHidden="true"
UnhideWhenUsed="true" QFormat="true" Name="heading 3"/>
<w:LsdException Locked="false" Priority="9" SemiHidden="true"
UnhideWhenUsed="true" QFormat="true" Name="heading 4"/>
<w:LsdException Locked="false" Priority="9" SemiHidden="true"
UnhideWhenUsed="true" QFormat="true" Name="heading 5"/>
<w:LsdException Locked="false" Priority="9" SemiHidden="true"
UnhideWhenUsed="true" QFormat="true" Name="heading 6"/>
<w:LsdException Locked="false" Priority="9" SemiHidden="true"
UnhideWhenUsed="true" QFormat="true" Name="heading 7"/>
<w:LsdException Locked="false" Priority="9" SemiHidden="true"
UnhideWhenUsed="true" QFormat="true" Name="heading 8"/>
<w:LsdException Locked="false" Priority="9" SemiHidden="true"
UnhideWhenUsed="true" QFormat="true" Name="heading 9"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="index 1"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="index 2"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="index 3"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="index 4"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="index 5"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="index 6"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="index 7"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="index 8"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="index 9"/>
<w:LsdException Locked="false" Priority="39" SemiHidden="true"
UnhideWhenUsed="true" Name="toc 1"/>
<w:LsdException Locked="false" Priority="39" SemiHidden="true"
UnhideWhenUsed="true" Name="toc 2"/>
<w:LsdException Locked="false" Priority="39" SemiHidden="true"
UnhideWhenUsed="true" Name="toc 3"/>
<w:LsdException Locked="false" Priority="39" SemiHidden="true"
UnhideWhenUsed="true" Name="toc 4"/>
<w:LsdException Locked="false" Priority="39" SemiHidden="true"
UnhideWhenUsed="true" Name="toc 5"/>
<w:LsdException Locked="false" Priority="39" SemiHidden="true"
UnhideWhenUsed="true" Name="toc 6"/>
<w:LsdException Locked="false" Priority="39" SemiHidden="true"
UnhideWhenUsed="true" Name="toc 7"/>
<w:LsdException Locked="false" Priority="39" SemiHidden="true"
UnhideWhenUsed="true" Name="toc 8"/>
<w:LsdException Locked="false" Priority="39" SemiHidden="true"
UnhideWhenUsed="true" Name="toc 9"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Normal Indent"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="footnote text"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="annotation text"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="header"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="footer"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="index heading"/>
<w:LsdException Locked="false" Priority="35" SemiHidden="true"
UnhideWhenUsed="true" QFormat="true" Name="caption"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="table of figures"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="envelope address"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="envelope return"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="footnote reference"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="annotation reference"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="line number"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="page number"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="endnote reference"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="endnote text"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="table of authorities"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="macro"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="toa heading"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="List"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="List Bullet"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="List Number"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="List 2"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="List 3"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="List 4"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="List 5"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="List Bullet 2"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="List Bullet 3"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="List Bullet 4"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="List Bullet 5"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="List Number 2"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="List Number 3"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="List Number 4"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="List Number 5"/>
<w:LsdException Locked="false" Priority="10" QFormat="true" Name="Title"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Closing"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Signature"/>
<w:LsdException Locked="false" Priority="1" SemiHidden="true"
UnhideWhenUsed="true" Name="Default Paragraph Font"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Body Text"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Body Text Indent"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="List Continue"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="List Continue 2"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="List Continue 3"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="List Continue 4"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="List Continue 5"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Message Header"/>
<w:LsdException Locked="false" Priority="11" QFormat="true" Name="Subtitle"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Salutation"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Date"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Body Text First Indent"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Body Text First Indent 2"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Note Heading"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Body Text 2"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Body Text 3"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Body Text Indent 2"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Body Text Indent 3"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Block Text"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Hyperlink"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="FollowedHyperlink"/>
<w:LsdException Locked="false" Priority="22" QFormat="true" Name="Strong"/>
<w:LsdException Locked="false" Priority="20" QFormat="true" Name="Emphasis"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Document Map"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Plain Text"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="E-mail Signature"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="HTML Top of Form"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="HTML Bottom of Form"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Normal (Web)"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="HTML Acronym"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="HTML Address"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="HTML Cite"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="HTML Code"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="HTML Definition"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="HTML Keyboard"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="HTML Preformatted"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="HTML Sample"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="HTML Typewriter"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="HTML Variable"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Normal Table"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="annotation subject"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="No List"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Outline List 1"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Outline List 2"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Outline List 3"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table Simple 1"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table Simple 2"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table Simple 3"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table Classic 1"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table Classic 2"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table Classic 3"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table Classic 4"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table Colorful 1"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table Colorful 2"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table Colorful 3"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table Columns 1"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table Columns 2"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table Columns 3"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table Columns 4"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table Columns 5"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table Grid 1"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table Grid 2"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table Grid 3"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table Grid 4"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table Grid 5"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table Grid 6"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table Grid 7"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table Grid 8"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table List 1"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table List 2"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table List 3"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table List 4"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table List 5"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table List 6"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table List 7"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table List 8"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table 3D effects 1"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table 3D effects 2"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table 3D effects 3"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table Contemporary"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table Elegant"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table Professional"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table Subtle 1"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table Subtle 2"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table Web 1"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table Web 2"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table Web 3"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Balloon Text"/>
<w:LsdException Locked="false" Priority="39" Name="Table Grid"/>
<w:LsdException Locked="false" SemiHidden="true" UnhideWhenUsed="true"
Name="Table Theme"/>
<w:LsdException Locked="false" SemiHidden="true" Name="Placeholder Text"/>
<w:LsdException Locked="false" Priority="1" QFormat="true" Name="No Spacing"/>
<w:LsdException Locked="false" Priority="60" Name="Light Shading"/>
<w:LsdException Locked="false" Priority="61" Name="Light List"/>
<w:LsdException Locked="false" Priority="62" Name="Light Grid"/>
<w:LsdException Locked="false" Priority="63" Name="Medium Shading 1"/>
<w:LsdException Locked="false" Priority="64" Name="Medium Shading 2"/>
<w:LsdException Locked="false" Priority="65" Name="Medium List 1"/>
<w:LsdException Locked="false" Priority="66" Name="Medium List 2"/>
<w:LsdException Locked="false" Priority="67" Name="Medium Grid 1"/>
<w:LsdException Locked="false" Priority="68" Name="Medium Grid 2"/>
<w:LsdException Locked="false" Priority="69" Name="Medium Grid 3"/>
<w:LsdException Locked="false" Priority="70" Name="Dark List"/>
<w:LsdException Locked="false" Priority="71" Name="Colorful Shading"/>
<w:LsdException Locked="false" Priority="72" Name="Colorful List"/>
<w:LsdException Locked="false" Priority="73" Name="Colorful Grid"/>
<w:LsdException Locked="false" Priority="60" Name="Light Shading Accent 1"/>
<w:LsdException Locked="false" Priority="61" Name="Light List Accent 1"/>
<w:LsdException Locked="false" Priority="62" Name="Light Grid Accent 1"/>
<w:LsdException Locked="false" Priority="63" Name="Medium Shading 1 Accent 1"/>
<w:LsdException Locked="false" Priority="64" Name="Medium Shading 2 Accent 1"/>
<w:LsdException Locked="false" Priority="65" Name="Medium List 1 Accent 1"/>
<w:LsdException Locked="false" SemiHidden="true" Name="Revision"/>
<w:LsdException Locked="false" Priority="34" QFormat="true"
Name="List Paragraph"/>
<w:LsdException Locked="false" Priority="29" QFormat="true" Name="Quote"/>
<w:LsdException Locked="false" Priority="30" QFormat="true"
Name="Intense Quote"/>
<w:LsdException Locked="false" Priority="66" Name="Medium List 2 Accent 1"/>
<w:LsdException Locked="false" Priority="67" Name="Medium Grid 1 Accent 1"/>
<w:LsdException Locked="false" Priority="68" Name="Medium Grid 2 Accent 1"/>
<w:LsdException Locked="false" Priority="69" Name="Medium Grid 3 Accent 1"/>
<w:LsdException Locked="false" Priority="70" Name="Dark List Accent 1"/>
<w:LsdException Locked="false" Priority="71" Name="Colorful Shading Accent 1"/>
<w:LsdException Locked="false" Priority="72" Name="Colorful List Accent 1"/>
<w:LsdException Locked="false" Priority="73" Name="Colorful Grid Accent 1"/>
<w:LsdException Locked="false" Priority="60" Name="Light Shading Accent 2"/>
<w:LsdException Locked="false" Priority="61" Name="Light List Accent 2"/>
<w:LsdException Locked="false" Priority="62" Name="Light Grid Accent 2"/>
<w:LsdException Locked="false" Priority="63" Name="Medium Shading 1 Accent 2"/>
<w:LsdException Locked="false" Priority="64" Name="Medium Shading 2 Accent 2"/>
<w:LsdException Locked="false" Priority="65" Name="Medium List 1 Accent 2"/>
<w:LsdException Locked="false" Priority="66" Name="Medium List 2 Accent 2"/>
<w:LsdException Locked="false" Priority="67" Name="Medium Grid 1 Accent 2"/>
<w:LsdException Locked="false" Priority="68" Name="Medium Grid 2 Accent 2"/>
<w:LsdException Locked="false" Priority="69" Name="Medium Grid 3 Accent 2"/>
<w:LsdException Locked="false" Priority="70" Name="Dark List Accent 2"/>
<w:LsdException Locked="false" Priority="71" Name="Colorful Shading Accent 2"/>
<w:LsdException Locked="false" Priority="72" Name="Colorful List Accent 2"/>
<w:LsdException Locked="false" Priority="73" Name="Colorful Grid Accent 2"/>
<w:LsdException Locked="false" Priority="60" Name="Light Shading Accent 3"/>
<w:LsdException Locked="false" Priority="61" Name="Light List Accent 3"/>
<w:LsdException Locked="false" Priority="62" Name="Light Grid Accent 3"/>
<w:LsdException Locked="false" Priority="63" Name="Medium Shading 1 Accent 3"/>
<w:LsdException Locked="false" Priority="64" Name="Medium Shading 2 Accent 3"/>
<w:LsdException Locked="false" Priority="65" Name="Medium List 1 Accent 3"/>
<w:LsdException Locked="false" Priority="66" Name="Medium List 2 Accent 3"/>
<w:LsdException Locked="false" Priority="67" Name="Medium Grid 1 Accent 3"/>
<w:LsdException Locked="false" Priority="68" Name="Medium Grid 2 Accent 3"/>
<w:LsdException Locked="false" Priority="69" Name="Medium Grid 3 Accent 3"/>
<w:LsdException Locked="false" Priority="70" Name="Dark List Accent 3"/>
<w:LsdException Locked="false" Priority="71" Name="Colorful Shading Accent 3"/>
<w:LsdException Locked="false" Priority="72" Name="Colorful List Accent 3"/>
<w:LsdException Locked="false" Priority="73" Name="Colorful Grid Accent 3"/>
<w:LsdException Locked="false" Priority="60" Name="Light Shading Accent 4"/>
<w:LsdException Locked="false" Priority="61" Name="Light List Accent 4"/>
<w:LsdException Locked="false" Priority="62" Name="Light Grid Accent 4"/>
<w:LsdException Locked="false" Priority="63" Name="Medium Shading 1 Accent 4"/>
<w:LsdException Locked="false" Priority="64" Name="Medium Shading 2 Accent 4"/>
<w:LsdException Locked="false" Priority="65" Name="Medium List 1 Accent 4"/>
<w:LsdException Locked="false" Priority="66" Name="Medium List 2 Accent 4"/>
<w:LsdException Locked="false" Priority="67" Name="Medium Grid 1 Accent 4"/>
<w:LsdException Locked="false" Priority="68" Name="Medium Grid 2 Accent 4"/>
<w:LsdException Locked="false" Priority="69" Name="Medium Grid 3 Accent 4"/>
<w:LsdException Locked="false" Priority="70" Name="Dark List Accent 4"/>
<w:LsdException Locked="false" Priority="71" Name="Colorful Shading Accent 4"/>
<w:LsdException Locked="false" Priority="72" Name="Colorful List Accent 4"/>
<w:LsdException Locked="false" Priority="73" Name="Colorful Grid Accent 4"/>
<w:LsdException Locked="false" Priority="60" Name="Light Shading Accent 5"/>
<w:LsdException Locked="false" Priority="61" Name="Light List Accent 5"/>
<w:LsdException Locked="false" Priority="62" Name="Light Grid Accent 5"/>
<w:LsdException Locked="false" Priority="63" Name="Medium Shading 1 Accent 5"/>
<w:LsdException Locked="false" Priority="64" Name="Medium Shading 2 Accent 5"/>
<w:LsdException Locked="false" Priority="65" Name="Medium List 1 Accent 5"/>
<w:LsdException Locked="false" Priority="66" Name="Medium List 2 Accent 5"/>
<w:LsdException Locked="false" Priority="67" Name="Medium Grid 1 Accent 5"/>
<w:LsdException Locked="false" Priority="68" Name="Medium Grid 2 Accent 5"/>
<w:LsdException Locked="false" Priority="69" Name="Medium Grid 3 Accent 5"/>
<w:LsdException Locked="false" Priority="70" Name="Dark List Accent 5"/>
<w:LsdException Locked="false" Priority="71" Name="Colorful Shading Accent 5"/>
<w:LsdException Locked="false" Priority="72" Name="Colorful List Accent 5"/>
<w:LsdException Locked="false" Priority="73" Name="Colorful Grid Accent 5"/>
<w:LsdException Locked="false" Priority="60" Name="Light Shading Accent 6"/>
<w:LsdException Locked="false" Priority="61" Name="Light List Accent 6"/>
<w:LsdException Locked="false" Priority="62" Name="Light Grid Accent 6"/>
<w:LsdException Locked="false" Priority="63" Name="Medium Shading 1 Accent 6"/>
<w:LsdException Locked="false" Priority="64" Name="Medium Shading 2 Accent 6"/>
<w:LsdException Locked="false" Priority="65" Name="Medium List 1 Accent 6"/>
<w:LsdException Locked="false" Priority="66" Name="Medium List 2 Accent 6"/>
<w:LsdException Locked="false" Priority="67" Name="Medium Grid 1 Accent 6"/>
<w:LsdException Locked="false" Priority="68" Name="Medium Grid 2 Accent 6"/>
<w:LsdException Locked="false" Priority="69" Name="Medium Grid 3 Accent 6"/>
<w:LsdException Locked="false" Priority="70" Name="Dark List Accent 6"/>
<w:LsdException Locked="false" Priority="71" Name="Colorful Shading Accent 6"/>
<w:LsdException Locked="false" Priority="72" Name="Colorful List Accent 6"/>
<w:LsdException Locked="false" Priority="73" Name="Colorful Grid Accent 6"/>
<w:LsdException Locked="false" Priority="19" QFormat="true"
Name="Subtle Emphasis"/>
<w:LsdException Locked="false" Priority="21" QFormat="true"
Name="Intense Emphasis"/>
<w:LsdException Locked="false" Priority="31" QFormat="true"
Name="Subtle Reference"/>
<w:LsdException Locked="false" Priority="32" QFormat="true"
Name="Intense Reference"/>
<w:LsdException Locked="false" Priority="33" QFormat="true" Name="Book Title"/>
<w:LsdException Locked="false" Priority="37" SemiHidden="true"
UnhideWhenUsed="true" Name="Bibliography"/>
<w:LsdException Locked="false" Priority="39" SemiHidden="true"
UnhideWhenUsed="true" QFormat="true" Name="TOC Heading"/>
<w:LsdException Locked="false" Priority="41" Name="Plain Table 1"/>
<w:LsdException Locked="false" Priority="42" Name="Plain Table 2"/>
<w:LsdException Locked="false" Priority="43" Name="Plain Table 3"/>
<w:LsdException Locked="false" Priority="44" Name="Plain Table 4"/>
<w:LsdException Locked="false" Priority="45" Name="Plain Table 5"/>
<w:LsdException Locked="false" Priority="40" Name="Grid Table Light"/>
<w:LsdException Locked="false" Priority="46" Name="Grid Table 1 Light"/>
<w:LsdException Locked="false" Priority="47" Name="Grid Table 2"/>
<w:LsdException Locked="false" Priority="48" Name="Grid Table 3"/>
<w:LsdException Locked="false" Priority="49" Name="Grid Table 4"/>
<w:LsdException Locked="false" Priority="50" Name="Grid Table 5 Dark"/>
<w:LsdException Locked="false" Priority="51" Name="Grid Table 6 Colorful"/>
<w:LsdException Locked="false" Priority="52" Name="Grid Table 7 Colorful"/>
<w:LsdException Locked="false" Priority="46"
Name="Grid Table 1 Light Accent 1"/>
<w:LsdException Locked="false" Priority="47" Name="Grid Table 2 Accent 1"/>
<w:LsdException Locked="false" Priority="48" Name="Grid Table 3 Accent 1"/>
<w:LsdException Locked="false" Priority="49" Name="Grid Table 4 Accent 1"/>
<w:LsdException Locked="false" Priority="50" Name="Grid Table 5 Dark Accent 1"/>
<w:LsdException Locked="false" Priority="51"
Name="Grid Table 6 Colorful Accent 1"/>
<w:LsdException Locked="false" Priority="52"
Name="Grid Table 7 Colorful Accent 1"/>
<w:LsdException Locked="false" Priority="46"
Name="Grid Table 1 Light Accent 2"/>
<w:LsdException Locked="false" Priority="47" Name="Grid Table 2 Accent 2"/>
<w:LsdException Locked="false" Priority="48" Name="Grid Table 3 Accent 2"/>
<w:LsdException Locked="false" Priority="49" Name="Grid Table 4 Accent 2"/>
<w:LsdException Locked="false" Priority="50" Name="Grid Table 5 Dark Accent 2"/>
<w:LsdException Locked="false" Priority="51"
Name="Grid Table 6 Colorful Accent 2"/>
<w:LsdException Locked="false" Priority="52"
Name="Grid Table 7 Colorful Accent 2"/>
<w:LsdException Locked="false" Priority="46"
Name="Grid Table 1 Light Accent 3"/>
<w:LsdException Locked="false" Priority="47" Name="Grid Table 2 Accent 3"/>
<w:LsdException Locked="false" Priority="48" Name="Grid Table 3 Accent 3"/>
<w:LsdException Locked="false" Priority="49" Name="Grid Table 4 Accent 3"/>
<w:LsdException Locked="false" Priority="50" Name="Grid Table 5 Dark Accent 3"/>
<w:LsdException Locked="false" Priority="51"
Name="Grid Table 6 Colorful Accent 3"/>
<w:LsdException Locked="false" Priority="52"
Name="Grid Table 7 Colorful Accent 3"/>
<w:LsdException Locked="false" Priority="46"
Name="Grid Table 1 Light Accent 4"/>
<w:LsdException Locked="false" Priority="47" Name="Grid Table 2 Accent 4"/>
<w:LsdException Locked="false" Priority="48" Name="Grid Table 3 Accent 4"/>
<w:LsdException Locked="false" Priority="49" Name="Grid Table 4 Accent 4"/>
<w:LsdException Locked="false" Priority="50" Name="Grid Table 5 Dark Accent 4"/>
<w:LsdException Locked="false" Priority="51"
Name="Grid Table 6 Colorful Accent 4"/>
<w:LsdException Locked="false" Priority="52"
Name="Grid Table 7 Colorful Accent 4"/>
<w:LsdException Locked="false" Priority="46"
Name="Grid Table 1 Light Accent 5"/>
<w:LsdException Locked="false" Priority="47" Name="Grid Table 2 Accent 5"/>
<w:LsdException Locked="false" Priority="48" Name="Grid Table 3 Accent 5"/>
<w:LsdException Locked="false" Priority="49" Name="Grid Table 4 Accent 5"/>
<w:LsdException Locked="false" Priority="50" Name="Grid Table 5 Dark Accent 5"/>
<w:LsdException Locked="false" Priority="51"
Name="Grid Table 6 Colorful Accent 5"/>
<w:LsdException Locked="false" Priority="52"
Name="Grid Table 7 Colorful Accent 5"/>
<w:LsdException Locked="false" Priority="46"
Name="Grid Table 1 Light Accent 6"/>
<w:LsdException Locked="false" Priority="47" Name="Grid Table 2 Accent 6"/>
<w:LsdException Locked="false" Priority="48" Name="Grid Table 3 Accent 6"/>
<w:LsdException Locked="false" Priority="49" Name="Grid Table 4 Accent 6"/>
<w:LsdException Locked="false" Priority="50" Name="Grid Table 5 Dark Accent 6"/>
<w:LsdException Locked="false" Priority="51"
Name="Grid Table 6 Colorful Accent 6"/>
<w:LsdException Locked="false" Priority="52"
Name="Grid Table 7 Colorful Accent 6"/>
<w:LsdException Locked="false" Priority="46" Name="List Table 1 Light"/>
<w:LsdException Locked="false" Priority="47" Name="List Table 2"/>
<w:LsdException Locked="false" Priority="48" Name="List Table 3"/>
<w:LsdException Locked="false" Priority="49" Name="List Table 4"/>
<w:LsdException Locked="false" Priority="50" Name="List Table 5 Dark"/>
<w:LsdException Locked="false" Priority="51" Name="List Table 6 Colorful"/>
<w:LsdException Locked="false" Priority="52" Name="List Table 7 Colorful"/>
<w:LsdException Locked="false" Priority="46"
Name="List Table 1 Light Accent 1"/>
<w:LsdException Locked="false" Priority="47" Name="List Table 2 Accent 1"/>
<w:LsdException Locked="false" Priority="48" Name="List Table 3 Accent 1"/>
<w:LsdException Locked="false" Priority="49" Name="List Table 4 Accent 1"/>
<w:LsdException Locked="false" Priority="50" Name="List Table 5 Dark Accent 1"/>
<w:LsdException Locked="false" Priority="51"
Name="List Table 6 Colorful Accent 1"/>
<w:LsdException Locked="false" Priority="52"
Name="List Table 7 Colorful Accent 1"/>
<w:LsdException Locked="false" Priority="46"
Name="List Table 1 Light Accent 2"/>
<w:LsdException Locked="false" Priority="47" Name="List Table 2 Accent 2"/>
<w:LsdException Locked="false" Priority="48" Name="List Table 3 Accent 2"/>
<w:LsdException Locked="false" Priority="49" Name="List Table 4 Accent 2"/>
<w:LsdException Locked="false" Priority="50" Name="List Table 5 Dark Accent 2"/>
<w:LsdException Locked="false" Priority="51"
Name="List Table 6 Colorful Accent 2"/>
<w:LsdException Locked="false" Priority="52"
Name="List Table 7 Colorful Accent 2"/>
<w:LsdException Locked="false" Priority="46"
Name="List Table 1 Light Accent 3"/>
<w:LsdException Locked="false" Priority="47" Name="List Table 2 Accent 3"/>
<w:LsdException Locked="false" Priority="48" Name="List Table 3 Accent 3"/>
<w:LsdException Locked="false" Priority="49" Name="List Table 4 Accent 3"/>
<w:LsdException Locked="false" Priority="50" Name="List Table 5 Dark Accent 3"/>
<w:LsdException Locked="false" Priority="51"
Name="List Table 6 Colorful Accent 3"/>
<w:LsdException Locked="false" Priority="52"
Name="List Table 7 Colorful Accent 3"/>
<w:LsdException Locked="false" Priority="46"
Name="List Table 1 Light Accent 4"/>
<w:LsdException Locked="false" Priority="47" Name="List Table 2 Accent 4"/>
<w:LsdException Locked="false" Priority="48" Name="List Table 3 Accent 4"/>
<w:LsdException Locked="false" Priority="49" Name="List Table 4 Accent 4"/>
<w:LsdException Locked="false" Priority="50" Name="List Table 5 Dark Accent 4"/>
<w:LsdException Locked="false" Priority="51"
Name="List Table 6 Colorful Accent 4"/>
<w:LsdException Locked="false" Priority="52"
Name="List Table 7 Colorful Accent 4"/>
<w:LsdException Locked="false" Priority="46"
Name="List Table 1 Light Accent 5"/>
<w:LsdException Locked="false" Priority="47" Name="List Table 2 Accent 5"/>
<w:LsdException Locked="false" Priority="48" Name="List Table 3 Accent 5"/>
<w:LsdException Locked="false" Priority="49" Name="List Table 4 Accent 5"/>
<w:LsdException Locked="false" Priority="50" Name="List Table 5 Dark Accent 5"/>
<w:LsdException Locked="false" Priority="51"
Name="List Table 6 Colorful Accent 5"/>
<w:LsdException Locked="false" Priority="52"
Name="List Table 7 Colorful Accent 5"/>
<w:LsdException Locked="false" Priority="46"
Name="List Table 1 Light Accent 6"/>
<w:LsdException Locked="false" Priority="47" Name="List Table 2 Accent 6"/>
<w:LsdException Locked="false" Priority="48" Name="List Table 3 Accent 6"/>
<w:LsdException Locked="false" Priority="49" Name="List Table 4 Accent 6"/>
<w:LsdException Locked="false" Priority="50" Name="List Table 5 Dark Accent 6"/>
<w:LsdException Locked="false" Priority="51"
Name="List Table 6 Colorful Accent 6"/>
<w:LsdException Locked="false" Priority="52"
Name="List Table 7 Colorful Accent 6"/>
</w:LatentStyles>
</xml><![endif]--><!--[if gte mso 10]>
<style>
/* Style Definitions */
table.MsoNormalTable
{mso-style-name:"Table Normal";
mso-tstyle-rowband-size:0;
mso-tstyle-colband-size:0;
mso-style-noshow:yes;
mso-style-priority:99;
mso-style-parent:"";
mso-padding-alt:0in 5.4pt 0in 5.4pt;
mso-para-margin:0in;
mso-para-margin-bottom:.0001pt;
mso-pagination:widow-orphan;
font-size:10.0pt;
font-family:"Times New Roman",serif;}
</style>
<![endif]-->
<br />
<div style="margin-bottom: .0001pt; margin: 0in;">
<span style="font-family: inherit;">In this blog post we outline the main
operations in the YASHE fully homomorphic encryption (FHE) scheme. For the exact details see <a href="https://eprint.iacr.org/2013/075" target="_blank">the paper introducing YASHE</a>. </span></div>
<div style="margin-bottom: .0001pt; margin: 0in;">
<span style="font-family: inherit;"><br /></span></div>
<div style="margin-bottom: .0001pt; margin: 0in;">
<span style="font-family: inherit;">López-Alt, Tromer, and
Vaikuntanathan <a href="https://eprint.iacr.org/2013/094" target="_blank">proposed</a> a (multi-key) FHE scheme based on <a href="https://eprint.iacr.org/2013/004" target="_blank">the work</a> by Stehlé and Steinfeld in which a provably secure version of <a href="http://link.springer.com/chapter/10.1007%2FBFb0054868" target="_blank">NTRUEncrypt</a> is presented with security based on standard problems in ideal lattices. The
FHE scheme from López-Alt, Tromer, and Vaikuntanathan needs to make an
additional assumption relating to the uniformity of the public key, the
so-called decisional small polynomial ratio (DSPR) assumption, to allow
homomorphic operations and remain semantically secure. Brakerski <a href="https://eprint.iacr.org/2012/078" target="_blank">introduced</a> an
approach to limit the noise growth during homomorphic operations via a
tensoring technique.
</span></div>
<div style="-qt-block-indent: 0; margin-bottom: .0001pt; margin: 0in;">
<span style="font-family: inherit;"><br /></span></div>
<div style="margin-bottom: .0001pt; margin: 0in;">
<span style="font-family: inherit;">In <a href="https://eprint.iacr.org/2013/075" target="_blank">this paper</a>, Yet Another Somewhat Homomorphic Encryption (YASHE) scheme is introduced which
incorporates the best of these techniques. YASHE avoids the DSPR assumption by
using the techniques described by Brakerski and construct a new fully
homomorphic encryption scheme from the Stehlé and Steinfeld version based on
standard lattice assumptions and a circular security assumption.</span></div>
<div style="margin-bottom: .0001pt; margin: 0in;">
<span style="font-family: inherit;"><br /></span></div>
<div style="margin-bottom: .0001pt; margin: 0in;">
<span style="font-family: inherit;">Besides this theoretical advantage,
YASHE has other attractive properties</span><br />
<ol>
<li><span style="font-family: inherit;">This new scheme is
<a href="https://eprint.iacr.org/2012/078" target="_blank">scale-invariant</a>:
this means it avoids the <a href="https://eprint.iacr.org/2011/277" target="_blank">modulus-switching technique</a> of Brakerski, Gentry and Vaikuntanathan.</span></li>
<li><span style="font-family: inherit;">The ciphertext consists of only a single ring element (as in <a href="https://eprint.iacr.org/2013/094" target="_blank">this paper</a>) as opposed to the two
or more ring elements for schemes based purely on the <a href="https://eprint.iacr.org/2012/230" target="_blank">ring learning witherrors</a> (RLWE) assumption.
</span></li>
</ol>
</div>
<div style="margin-bottom: .0001pt; margin: 0in;">
<span style="font-family: inherit;">In the following I will describe
the more practical variant of YASHE (denoted YASHE’ in the paper). Note that this practical variant YASHE' does need the DSPR </span><span style="font-family: inherit;"><span style="font-family: inherit;">assumption.</span></span></div>
<div style="margin-bottom: .0001pt; margin: 0in;">
<span style="font-family: inherit;"><br /></span></div>
<div class="MsoNormal">
<span style="font-family: inherit;">In
order to show how YASHE works we need to fix some parameters. Selecting secure
parameters is a difficult task by itself for which tools have been generated
(see for instance our <a href="http://heat-h2020-project.blogspot.de/2015/05/hardness-of-lwe-problem.html" target="_blank">previous blog</a><a href="http://heat-h2020-project.blogspot.de/2015/05/hardness-of-lwe-problem.html" target="_blank"> post</a>).
For this post I simply assume correct and secure parameters have been chosen
(but see the paper for some example parameters). Given the security parameter
$\lambda$, fix a positive integer $d$ and modulus $q$ that determine $R={\mathbb Z}[X]/(\Phi_d(X))$, and $t$ with $1< t < q$, and distributions $\chi_{\mathrm{key}}$, $\chi_{\mathrm{err}}$ on $R$.</span></div>
<div class="MsoNormal">
<span style="font-family: inherit;"><br /></span></div>
<span style="font-family: inherit;">The message space is $R/tR=({\mathbb Z}[X]/(\Phi_d(X)))/(t({\mathbb Z}[X]/(\Phi_d(X)))).$</span><br />
<span style="font-family: inherit;"><br /></span>
<span style="font-family: inherit;">The function $P_{w, q}$ is a generalization of the PowersofTwo and $D_{w, q}$ is a generalization of BitDecomp from <a href="https://eprint.iacr.org/2012/078" target="_blank">this paper</a>. Instead of a radix-2 representation these functions use a radix-$w$ system. These function take a single ring element and output $\ell_{w,q} = \lfloor\log_w(q)\rfloor + 2$ ring elements. The choice of $w$ is important since it allows for a trade-off between efficiency and error growth.</span><br />
<span style="font-family: inherit;"><br /></span>
<span style="font-family: inherit;"><b> Key generation</b>. KeyGen $(d,q,t,\chi_{\mathrm{key}}, \chi_{\mathrm{err}}, w)$</span><br />
<ol>
<li><span style="font-family: inherit;">Sample $f', g \leftarrow \chi_{\mathrm{key}}$ and let $f = [tf' + 1]_q $.</span></li>
<li><span style="font-family: inherit;">If $f$ is not invertible modulo $q$, choose a new $f'$.</span></li>
<li><span style="font-family: inherit;">Compute the inverse $f^{-1} \in R$ of $f$ modulo $q$ and set $h = [tgf^{-1}]_q$.</span></li>
<li><span style="font-family: inherit;">Sample $\vec{e},\vec{s}\leftarrow \chi_{\mathrm{err}}^{\ell_{w,q}}$, compute $\vec{\gamma} = [P_{w,q}(f) + \vec{e} + h \cdot \vec{s}]_q \in R^{\ell_{w,q}}$.</span></li>
<li><span style="font-family: inherit;">Output $({\sf pk}, {\sf sk}, {\sf evk}) = (h,f,\vec{\gamma})$.</span></li>
</ol>
<span style="font-family: inherit;"> <b>Encryption</b>. Encrypt $(m, {\sf pk})$</span><br />
<ol>
<li><span style="font-family: inherit;">For a message $m+tR$, choose $[m]_t$ as its representative.</span></li>
<li><span style="font-family: inherit;">Sample $s,e \leftarrow \chi_{\mathrm{err}}$.</span></li>
<li><span style="font-family: inherit;">Output the ciphertext $c = [\lfloor q/t \rfloor [m]_t + e + {\sf pk}\cdot s]_q \in R.$</span></li>
</ol>
<span style="font-family: inherit;"><b>Decryption</b>. Decrypt $(c, {\sf sk})$</span><br />
<ol>
<li><span style="font-family: inherit;">To decrypt a ciphertext $c$, compute $m = \left[\left\lfloor \frac{t}{q}\cdot[{\sf sk}\cdot c]_q \right\rceil \right]_t \in R.$</span></li>
</ol>
<span style="font-family: inherit;"><b>Key switching</b>. KeySwitch $(\tilde{c}_{\sf Mult}, {\sf evk})$</span><br />
<ol>
<li><span style="font-family: inherit;">Output the ciphertext $[\langle D_{w,q}(\tilde{c}_{\sf Mult}) , {\sf evk} \rangle]_q$.</span></li>
</ol>
<span style="font-family: inherit;">The key switching algorithm transforms an intermediate encryption into a ciphertext that can be decrypted with $f$ itself. The evaluation key is ${\sf evk} = [P_{w,q}(f) + \vec{e} + h \cdot \vec{s}]_q$, where $\vec{e}, \vec{s} \leftarrow \chi_{\mathrm{err}}^{\ell_{w,q}}$ are vectors of polynomials sampled from the error distribution $\chi_{\mathrm{err}}$. This key is a vector of quasi-encryptions of the secret key $f$ under its corresponding public key. It is required for the homomorphic multiplication operation and is therefore made public. This means, we need to make a circular security assumption, namely that the scheme is still secure even given that ${\sf evk}$ is publicly known.<br /><br /><b>Homomorphic addition</b>. Add $(c_1,c_2)$<br />Given two ciphertexts $c_1, c_2\in R$, which encrypt two messages $m_1, m_2$, their sum <i>modulo</i> $q$, $c_{\sf Add} = [c_1 + c_2]_q$, encrypts the sum of the messages <i>modulo</i> $t$, $[m_1 + m_2]_t$.<br /><br /><b>Homomorphic multiplication</b>. Mult $(c_1,c_2, {\sf evk})$<br />Output the ciphertext<br />$$c_{{\sf Mult}} = \textrm{KeySwitch} (\tilde{c}_{\sf Mult}, {\sf evk}), \mbox{ where } \tilde{c}_{\sf Mult} = \left[\left\lfloor\frac{t}{q} \cdot c_1 \cdot c_2\right\rceil\right]_q.$$</span><br />
<br />
<b><u>YASHE in practice</u></b> <br />
<span style="font-family: inherit;">This practical version of YASHE has been used in order to ensure <a href="http://eprint.iacr.org/2014/336" target="_blank">privacy of sensitive medical data</a>. In this work it is shown how to privately conduct predictive analysis tasks on encrypted data using homomorphic encryption. As a proof of concept a working implementation of a prediction service running in the cloud, which takes as input private encrypted health data, and returns the probability for suffering cardiovascular disease in encrypted form. Since the cloud service uses homomorphic encryption, it makes this prediction while handling only encrypted data, learning nothing about the submitted confidential medical data.</span><br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgT-1hFmk0kPpje8no2I78R1uavthoR6aB127So0VIckeKGq6iUSjsvumUvZdLggH-yr7as-2lrqnJ4ZAqstAEm_jkClNNJXswjT-c7kPZTJuYdh3f2LXRN-zosLxwyYeQm5AK1yAYrwZ9M/s1600/cloud.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="225" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgT-1hFmk0kPpje8no2I78R1uavthoR6aB127So0VIckeKGq6iUSjsvumUvZdLggH-yr7as-2lrqnJ4ZAqstAEm_jkClNNJXswjT-c7kPZTJuYdh3f2LXRN-zosLxwyYeQm5AK1yAYrwZ9M/s320/cloud.png" width="320" /></a></div>
<br />
<br />
<br />
<br />
<span style="font-family: inherit;">In a <a href="https://eprint.iacr.org/2015/337" target="_blank">recent paper</a> in <a href="https://heat-project.eu/publications.html" target="_blank">the framework of the HEAT project</a>, a modular hardware architecture for somewhat homomorphic function evaluation using YASHE is presented. I<span style="font-family: inherit;">n another <span style="font-family: inherit;"><a href="http://eprint.iacr.org/2015/631">recent publication</a>, YASHE is <span style="font-family: inherit;">implemented to </span></span></span></span>investigate the potential of FPGAs.<br />
<br />
<br />
<br />
<br />
<br />
<div class="MsoNormal">
<br /></div>
<br />Anonymoushttp://www.blogger.com/profile/06992379032518815181noreply@blogger.com0tag:blogger.com,1999:blog-3329110015361344577.post-59026680741719212382015-06-18T23:08:00.000+02:002015-06-18T23:08:49.572+02:00Optimizing the communication cost when using homomorphic encryption<div dir="ltr" style="text-align: left;" trbidi="on">
<h3 style="text-align: left;">
Scenario</h3>
<div style="text-align: justify;">
In typical applications of homomorphic encryption, one of the first steps consists for a user, let's call her Alice, to encrypt her data $m$ under a public key $\textsf{pk}$ and send the ciphertext $c = \textrm{Enc}(\textsf{pk}, m)$ to someone else, e.g. to the Cloud (see Fig. 1).</div>
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="http://4.bp.blogspot.com/-MpJUF2DCpcI/VYMQNFHWUSI/AAAAAAAAAA0/FJiWWsNLhbg/s1600/figure.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="142" src="http://4.bp.blogspot.com/-MpJUF2DCpcI/VYMQNFHWUSI/AAAAAAAAAA0/FJiWWsNLhbg/s400/figure.png" width="400" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Fig. 1. Alice sends her data $m$ encrypted to the Cloud, which publicly performs an operation $f$ on it.</td></tr>
</tbody></table>
<div style="text-align: justify;">
The Cloud then performs publicly a function $f$ on the data, and sends back the result to Alice. Unfortunately, even the most recent homomorphic encryption schemes (e.g. <a href="http://heat-h2020-project.blogspot.com/2015/04/the-bgv-scheme.html">BGV</a> or <a href="http://heat-h2020-project.blogspot.com/2015/06/ring-gsw.html">GSW</a>) are such that the size of the ciphertext $c = \textrm{Enc}(\textsf{pk}, m)$ is <b>much larger</b> than the size of $m$. Typically, to encrypt a 4MB image, the ciphertext will end up being at least 1 GB long!</div>
<div>
<br />
<h3 style="text-align: left;">
Using an Hybrid Approach</h3>
</div>
<div>
<div style="text-align: justify;">
In 2012, Michael Naehrig, Kristin Lauter and Vinod Vaikuntanathan suggested to use the following hybrid approach: encrypt the message $m$ under a scheme with <i>no</i> ciphertext expansion (i.e. the ciphertext will have the same size as $m$), e.g. under the <a href="https://en.wikipedia.org/wiki/Advanced_Encryption_Standard">Advanced Encryption Standard</a> $\hat c = \textsf{AES}_k(m)$ for a key $k$, and send to the Cloud $(\textsf{Enc}(\textsf{pk}, k), \hat c)$. Now, the communication cost becomes the cost of sending $\hat c$ (same size as $m$) and sending only<i> once</i> $\textsf{Enc}(\textsf{pk}, k)$, which is independent of the data $m$, i.e. is quasi-optimal.</div>
<div>
The Cloud has now to perform the $f\circ \textsf{AES}^{-1}_k$ instead of $f$ to publicly compute the expected result as in Fig. 1.</div>
</div>
<div>
<div style="text-align: justify;">
This solution was <a href="http://eprint.iacr.org/2012/099">first implemented</a> by Craig Gentry, Shai Halevi and Nigel Smart in 2012 (Nigel Smart is a member of the HEAT project). Recent timings (from early 2015) demonstrates the possibility to evaluate <i>only</i> $\textsf{AES}^{-1}_k$ (i.e. taking parameters to evaluate the latter function but nothing else) in <b>less than 7 minutes</b> on a classical laptop.</div>
<br />
<div style="text-align: justify;">
However, this approach has several drawbacks. First, AES was not at all designed in a context of homomorphic cryptography: the operations are not easily parallelizable, the multiplicative depth is large: AES does not appear to be particularly well suited for homomorphic evaluations. Second drawback, the latency of the homomorphic evaluation of $\textsf{AES}^{-1}_k$ is added to the latency of the homomorphic evaluation of $f$: in other words, the data will be homomorphically processed upon after being homomorphically decrypted (i.e. 7 minutes later!).</div>
<br />
<h3 style="text-align: left;">
Block Ciphers for Homomorphic Evaluations</h3>
<div style="text-align: justify;">
The first drawback has been investigated in a series of work (<a href="http://eprint.iacr.org/2014/062">LN14</a>, <a href="http://eprint.iacr.org/2014/233">DSES14</a>...), trying to replace AES by lighter primitives such as SIMON or PRINCE: the resulting homomorphic evaluations have a much smaller latency. Au EUROCRYPT 2015, Martin Albrecht, Christian Rechberger, Thomas Schneider, Tyge Tiessen and Michael Zohner presented a new family of block cipher especially designed for homomorphic encryption called <a href="http://link.springer.com/chapter/10.1007%2F978-3-662-46800-5_17">LowMC</a> (see also our <a href="http://heat-h2020-project.blogspot.com/2015/04/homomorphic-encryption-at-eurocrypt-2015.html">blog article</a> about EUROCRYPT). Designed to have a shallow decryption circuit (multiplicative depth of 11), they performed much better than previous approaches. Unfortunately, LowMC <a href="http://eprint.iacr.org/2015/418">was broken</a> soon after its publication because of weaknesses inherent in its low multiplicative complexity.</div>
<br />
<h3 style="text-align: left;">
Revisiting the Whole Hybrid System</h3>
</div>
<div>
<div style="text-align: justify;">
In 2015, partly founded by the HEAT project, Tancrède Lepoint and Pascal Paillier from CryptoExperts together with Anne Canteaut, Sergiu Carpov, Caroline Fontaine, María Naya-Plasencia and Renaud Sirdey proposed to<b> revisit the hybrid system entirely</b> to tackle both drawbacks mentioned earlier in an article <a href="http://eprint.iacr.org/2015/113">available on the Eprint archive</a>. The key idea is to identify that the homomorphic "decompression" phase is subject to an <i>offline phase</i> and an <i>online phase</i>. The offline phase is plaintext-independent and therefore can be performed in advance, whereas the online phase completes decompression upon reception of the plaintext-dependent part of the compressed ciphertext. </div>
<br />
<div style="text-align: justify;">
Using the notation of above, the offline phase consists in sending $\textsf{Enc}(\textsf{pk}, k)$ because this value does not depend on the data. And the online phase consists in sending the data $m$ encrypted under the key $k$.</div>
<br />
<div style="text-align: justify;">
The second drawback presented earlier is that the online phase has a long latency. Making the online phase as quick as technically doable leads us to choose an <i>additive IV-based stream cipher</i> instead of AES. Therefore the system performs as in Fig. 2.</div>
<br />
<table align="center" cellpadding="0" cellspacing="0" class="tr-caption-container" style="margin-left: auto; margin-right: auto; text-align: center;"><tbody>
<tr><td style="text-align: center;"><a href="http://1.bp.blogspot.com/-QpC5KW9oaa4/VYMvx8sL6PI/AAAAAAAAABE/EKEUY47ZiMw/s1600/figure2.png" imageanchor="1" style="margin-left: auto; margin-right: auto;"><img border="0" height="266" src="http://1.bp.blogspot.com/-QpC5KW9oaa4/VYMvx8sL6PI/AAAAAAAAABE/EKEUY47ZiMw/s400/figure2.png" width="400" /></a></td></tr>
<tr><td class="tr-caption" style="text-align: center;">Fig. 2. When receiving the encryption $\textsf{Enc}(\textsf{pk}, k)$ of the symmetric key $k$, the Cloud can perform during the offline phase (i.e. before getting any data $m$) the generation of the keystream using a stream cipher adapted to current homomorphic encryption constraints. Therefore the latency of the online phase is minimal: when receiving the one-time padded message $m\oplus\textsf{keystream}$, the Cloud can homomorphically and very efficiently evaluate the XOR to obtain $\textsf{Enc}(\textsf{pk}, m)$.</td></tr>
</tbody></table>
<br />
<div style="text-align: justify;">
To accelerate the offline phase (and tackle the first drawback), we propose our own stream cipher candidates adapted to homomophic encryption : the keystream generator Trivium, which belongs to the eSTREAM portfolio of recommended stream ciphers, and a new proposal called Kreyvium, which shares the same internal structure. The main advantage of Kreyvium over Trivium is that it provides 128-bit security (instead of 80-bit) with the same multiplicative depth, and inherits the same security arguments. </div>
<br />
<div style="text-align: justify;">
Finally, we show that the promising performances obtained by LowMC <i>can also be achieved</i> with Trivium, a well-known primitive whose security has been thoroughly analyzed, and by Kreyvium. The 10-year analysis effort from the whole community, initiated by the eSTREAM competition, enables us to gain confidence in its security. Also our variant Kreyvium, with a 128-bit security, benefits from the same analysis since the core of the cipher is essentially the same. Also the Cloud can also exploits the highly parallel structure of Trivium and Kreyvium to speed up the homomorphic evaluation.</div>
</div>
</div>
Anonymousnoreply@blogger.com0