State-of-the-art implementations of homomorphic encryption exploit the Fan and Vercauteren (FV) scheme and the Residue Number System (RNS). While the RNS breaks down large integer arithmetic into smaller independent channels, its non-positional nature makes operations such as division and rounding hard to implement, and makes the representation of small values inefficient. In this work, we propose the application of the Hybrid Position-Residues Number System representation to the FV scheme. This is a positional representation of large radix where the digits are represented in RNS. It inherits the benefits from RNS and allows to accelerate the critical division and rounding operations while also making the representation of smaller values more compact. This directly benefits the decryption and the homomorphic multiplication procedures, reducing their asymptotic complexity, in dimension n, from O(n2log n) to O(n log n) and from O(n3log n) to O(n3), respectively and has resulted in noticeable speedups when experimentally compared to related art RNS implementations.

The conversion from a Residue Number System (RNS) to a weighted representation is a costly inter-modulo operation that introduces delay and area overhead to RNS processors, while also increasing power consumption. This paper proposes a new approach to decompose the reverse conversion into operations that can be processed by the arithmetic units already present in the RNS independent channels. This leads to a more effective reuse of the processor circuitry while enhancing parallelism. Experimental results show that, when the proposed techniques are applied to architectures based on ripple-carry adders for the traditional 3-moduli set, the delay is improved in average by 16 percent, the circuit area by 36 percent and the power consumption by 47 percent. When carry-lookahead adder topologies are considered, these improvements are in average of 45 percent for the circuit area and 58 percent for the power consumption while the delay is only slightly reduced. The proposed techniques are applied to a use case in digital filtering, showing an increase in throughput/area of up to 1.25 times, and average reductions in energy consumption of 15.6 percent. This work is a step forward to the usage of RNS in practice, since reverse conversion underpins other hard inter-modulo operations, like comparison, scaling and division.

In an ever more data-centric economy, machine learning models have risen in importance. With the large amounts of data companies collect, they are able to develop highly accurate models to predict the behaviours of their customers. It is thus important to safeguard the data used to build these models to prevent competitors from mimicking their services. In addition, as this type of techniques finds its way into areas that need to deal with more sensitive information, like the medical industry, the privacy of the data that needs to be classified also has to be ensured. Herein, this topic is addressed by homomorphically evaluating Support Vector Machine (SVM) models, in a way that guarantees that a client learns nothing about the model except for the classification of his data, and that the service provider learns nothing about the data. Whereas, previously, Fully Homomorphic Encryption (FHE) has mostly focused on either bit-wise or value-wise computations, SVMs present an additional challenge since they combine both: during an initial phase a kernel function is evaluated that makes use of real arithmetic, and during a second phase the sign bit has to be extracted. Novel techniques are herein proposed that allow for speedups of up to 2.7 and 6.6 for the evaluation of polynomials and the determination of sign, respectively, in comparison to the state of the art. Finally, it is shown that the proposed techniques do not deteriorate the classification accuracy of the SVM models.

The Residue Number System (RNS) is a numeral representation enabling for more efficient addition and multiplication implementations. However, due its non-positional nature, modular reductions, required for example by Elliptic Curve (EC) Cryptography (ECC), become costlier. Traditional approaches to RNS modular reduction resort to the Montgomery algorithm, underpinned by large basis extensions. Recently, Hybrid-Positional Residue Number Systems (HPRs) have been proposed, providing a trade-off between the efficiency of RNS and the flexibility of positional number representations. Numbers are represented in a positional representation with the coefficients represented in RNS. By crafting primes of a special form, the complexity of reductions modulo those primes is mitigated, relying on extensions of smaller bases. Due to the need of crafting special primes, this approach is not directly extensible to group operations over currently standardised elliptic curves. In this paper, the Hybrid-Polynomial Residue Number System (HyPoRes) is proposed, enabling for improved modular reductions for any prime. Experimental results show that the modular reduction of HyPoRes, although at most 1.4 times slower than HPR for HPR-crafted primes, is up to 1.4 times faster than a generic RNS approach for primes of ECC standards.

With Lattice-based cryptography (LBC), ciphertexts are represented as points near a lattice, and Babai's round-off algorithm allows to decrypt them when one knows the secret-key. Recently, an accelerated variant of the round-off, based on Residue Number Systems (RNSs), has been proposed. Herein, we combine this technique with the use of lattices of Optimal Hermite Normal Form (OHNF) and propose further refinements, so as to reduce the decryption complexity. This approach lends itself largely to data-level parallelism, allowing for low latency decryption operations on multi-core CPUs with Single Instruction Multiple Data (SIMD) extensions, and achieves high-throughput on GPUs. Finally, we are able to perform decryptions up to 20 times faster than the most efficient implementation in related art, which exploits the Mixed-Radix System (MRS), in an Intel i7 6700K CPU, and we are able to decrypt up to 11,832 messages/s in a Titan X GPU.

Should quantum computing become viable, current public-key cryptographic schemes will no longer be valid. Since cryptosystems take many years to mature, research on post-quantum cryptography is now more important than ever. Herein, lattice-based cryptography is focused on, as an alternative post-quantum cryptosystem, to improve its efficiency. We put together several theoretical developments so as to produce an efficient implementation that solves the Closest Vector Problem (CVP) on Goldreich-Goldwasser-Halevi (GGH)-like cryptosystems based on the Residue Number System (RNS). We were able to produce speed-ups of up to 5.9 and 11.2 on the GTX 780 Ti and i7 4770K devices, respectively, when compared to a single-core optimized implementation. Finally, we show that the proposed implementation is a competitive alternative to the Rivest-Shamir-Adleman (RSA).

The use of Voice over Internet Protocol (VoIP) is becoming ubiquitous due to the multiple shortcomings of traditional Public Switched Telephone Network (PSTN) systems. As a result, the development of secure key establishment protocols is becoming increasingly important. The Communications-Electronics Security Group (CESG), in response to this demand, has published new key agreement protocols for the Multimedia Internet KEYing (MIKEY) protocol to provide low-cost secure VoIP communications, supported on Identity-based Public-Key Cryptography (IDPKC). In the context of IDPKC, the identity of users is used to derive their public-keys, which eliminates the expenses of maintaining a Public-Key Infrastructure (PKI). However, IDPKC systems suffer from inefficient user revocation and key renewal. In this paper, we take advantage of the fact that users need to be connected to the Internet to communicate, for introducing a SEcurity Mediator (SEM), who possesses a share of the users' private-keys, and with whom the users must cooperate, to sign and decrypt cryptograms. By taking advantage of this sharing, we introduce mechanisms to provide immediate user revocation and key renewal.