Microsoft Launch SEAL

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: http://research.microsoft.com/pubs/258435/ManualHE.pdf with code available here http://sealcrypto.codeplex.com/

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.

Using the Rényi divergence rather than the statistical distance in lattice-based cryptography

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.

Our contributions are as follows:

• Smaller signatures for the Hash-and-Sign Gentry-Peikert-Vaikuntanathan signature scheme
• Smaller storage requirement for the Fiat-Shamir BLISS signature scheme
• 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!)
• Smaller parameters for the dual-Regev encryption scheme

and are described in the article

Improved security proofs in lattice-based cryptography: using the Rényi divergence rather than the statistical distance

Shi Bai and Adeline Langlois and Tancrède Lepoint and Damien Stehlé and Ron Steinfeld

This article has been accepted for publication at ASIACRYPT 2015 and will receive the Best Paper Award.

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.

HEAT Summer School on FHE and MLM in Paris

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.

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.

Most FHE schemes are based on the Learning with Errors problem, which was presented in detail on the first day. This was presented in [R05]. This was followed by a discussion of the [GSW13] cryptosystem, based on the approximate eigenvector method.

This was followed by a discussion of the Ring Learning with Errors problems, and a brief presentation of the various reductions, as presented in [LPR10].  A presentation of the BGV cryptosystem was given, together with an introduction about the use of Galois theory in RLWE schemes, in order to use the “packed ciphertexts” method.

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.

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.

Which Ring Based Somewhat Homomorphic Encryption Scheme is Best?

This post is based on HEAT output http://eprint.iacr.org/2015/889

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.

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.

This consensus is however based on limited exploration of the design space. In HEAT output "Which Ring Based Somewhat Homomorphic Encryption Scheme is Best?" 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.

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.

Modular Hardware Architecture for Somewhat Homomorphic Function Evaluation

This post is based on the paper https://eprint.iacr.org/2015/337

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.

System Setup

  

The computations are performed in a modular polynomial rings of the form R = Z[x]/(f(x)) where f(x) is a monic irreducible polynomial Φ_d(x) of degree n. To utilize single instruction multiple data (SIMD) operations f(x) is a cyclotomic polynomial. The plaintext space is R₂.

The used parameter supports homomorphic evaluations of SIMON-64/128 (having a multiplicative depth of 44); in particular d = 65535 (and thus the degree of f(x) is n= 2¹⁵), log₂(q) = 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.

High-level optimizations

Two main operations in the YASHE scheme are the YASHE.Add for homomorphic addition and the YASHE.Mult for homomorphic multiplication. While YASHE.Add is relatively simple, YASHE.Mult is very costly since one first needs to compute c₁ · c₂ over the integers, then scale the result by t/q and round, before mapping back into the ring R_q. For the polynomial multiplication of such a large degree n = 2¹⁵,  an 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.

High-level Architecture

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.

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.    

Experimental Results

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.

 Future Work

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.

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.

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. 

Sujoy Sinha Roy

Cryptanalysis of the Co-ACD Assumption

The HEAT project has a new public output: https://eprint.iacr.org/2014/1024

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 new scheme claimed to be the "most efficient of those that support an additive homomorphic property" was proposed by Cheon, Lee and Seo.

Understanding the security 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 CRYPTO 2015, 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).

Modular Hardware Architecture for Somewhat Homomorphic Function Evaluation

The HEAT project has a new public output: https://eprint.iacr.org/2015/337

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.

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).

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.