We present a privacy-preserving indoor localization scheme based on received signal strength measurements, e.g., from WiFi access points. Our scheme preserves the privacy of both the client's location and the service provider's database by using secure two-party computation instantiated with known cryptographic primitives, namely, Paillier encryption and garbled circuits. We describe a number of optimizations that reduce the computation and communication overheads of the scheme and provide theoretical evaluations of these overheads. We also demonstrate the feasibility of the scheme by developing a proof-of-concept implementation for Android smartphones and commodity servers. This implementation allows us to validate the practical performance of our scheme and to show that it is feasible for practical use in certain types of indoor localization applications.

Quantum computing is a serious threat for contemporary cryptography and, in order to address this threat, key sizes used for symmetric cryptography should be doubled, most typically from 128 to 256 bits. The third-generation partnership project (3GPP), the standards organization for mobile communications, is currently in the process of adding support for 256-bit keys into future mobile standards for the purpose of confidentiality and integrity protection. The current standard defines three ciphers with 128-bit keys: AES, SNOW 3G, and ZUC. There are two competing stream ciphers for the replacement of the 128-bit SNOW 3G: a 256-bit variant of SNOW 3G and a new design SNOW-V. SNOW-V has superior performance in software platforms. In this article, we investigate the implementations of these ciphers on field-programmable gate arrays (FPGAs) for both confidentiality and integrity protection. We develop optimized architectures and introduce a new parallelization technique that applies to both ciphers and offers significant throughput improvements in particular when the ciphers are used in the integrity protection modes. Our results show that SNOW-V has a significant performance advantage over the 256-bit SNOW 3G also on FPGAs.

Additively homomorphic encryption has many applications in privacy-enhancing technologies because it allows a cloud service provider to perform simple computations with users' data without learning the contents. The performance overhead of additively homomorphic encryption is a major obstacle for practical adaptation. Hardware accelerators could reduce this overhead substantially. In this paper, we present an implementation of the DGK cryptosystem for programmable systems-on-chip and evaluate it in real hardware. We demonstrate its efficiency for accelerating privacy-enhancing technologies by using it for computing squared Euclidean distances between a user's input and a server's database. We also provide comparisons with a recent implementation of Paillier cryptosystem and show that DGK offers major speedups. This work represents the first implementation of the DGK cryptosystem that uses hardware acceleration and demonstrates that the DGK benefits greatly from the hardware/software codesign approach.

Cryptographic pairings are important primitives for many advanced cryptosystems. Efficient computation of pairings requires the use of several layers of algorithms as well as optimizations in different algorithm and implementation levels. This makes implementing cryptographic pairings a difficult task particularly in hardware. Many existing hardware implementations fix the parameters of the pairing to improve efficiency but this significantly limits the generality and practicality of the solution. In this paper, we present a compact and programmable yet high-performance architecture for programmable system-on-chip platforms designed for efficient computation of different cryptographic pairings. We demonstrate with real hardware that this architecture can compute optimal ate pairings on a Barreto-Naehrig curve with 126-bit security in 2.18ms in a Xilinx Zynq-7020 device and occupies only about 3200 slices, 36 DSPs, and 18 BRAMs. We also show that the architecture can support different types of pairings via microcode updates and can be implemented on other reprogrammable devices with very minor modifications.

In the last decade, location information became easily obtainable using off‐the‐shelf mobile devices. This gave momentum to developing location‐based services (LBSs) such as location proximity detection, which can be used to find friends or taxis nearby. LBSs can, however, be easily misused to track users, which draws attention to the need for protecting the privacy of these users. In this work, the authors address this issue by designing, implementing, and evaluating multiple algorithms for privacy‐preserving location proximity (PPLP) that are based on different secure computation protocols. Their PPLP protocols support both circle and polygon range queries and have runtimes from a few to some hundreds of milliseconds and bandwidth requirements from a few hundreds of bytes to one megabyte. Consequently, they are well suited for different scenarios and offer faster runtimes and savings in bandwidth and computational power as well as security improvements compared to previous PPLP schemes. In addition, the computationally most expensive parts of the PPLP computation can be precomputed in their protocols, such that the input‐dependent online phase runs in just a few milliseconds.

A multitude of privacy-enhancing technologies (PETs) has been presented recently to solve the privacy problems of contemporary services utilizing cloud computing. Many of them are based on additively homomorphic encryption (AHE) that allows the computation of additions on encrypted data. The main technical obstacles for adaptation of PETs in practical systems are related to performance overheads compared with current privacy-violating alternatives. In this article, we present a hardware/software (HW/SW) codesign for programmable systems-on-chip (SoCs) that is designed for accelerating applications based on the Paillier encryption. Our implementation is a microcode-based multicore architecture that is suitable for accelerating various PETs using AHE with large integer modular arithmetic. We instantiate the implementation in a Xilinx Zynq-7000 programmable SoC and provide performance evaluations in real hardware. We also investigate its efficiency in a high-end Xilinx UltraScale+ programmable SoC. We evaluate the implementation with two target use cases that have relevance in PETs: privacy-preserving computation of squared Euclidean distances over encrypted data and multi-input functional encryption (FE) for inner products. Both of them represent the first hardware acceleration results for such operations, and in particular, the latter one is among the very first published implementation results of FE on any platform.

In the last decade, we observed a constantly growing number of Location-Based Services (LBSs) used in indoor environments, such as for targeted advertising in shopping malls or finding nearby friends. Although privacy-preserving LBSs were addressed in the literature, there was a lack of attention to the problem of enhancing privacy of indoor localization, i.e., the process of obtaining the users' locations indoors and, thus, a prerequisite for any indoor LBS. In this work we present PILOT, the first practically efficient solution for Privacy-Preserving Indoor Localization (PPIL) that was obtained by a synergy of the research areas indoor localization and applied cryptography. We design, implement, and evaluate protocols for Wi-Fi fingerprint-based PPIL that rely on 4 different distance metrics. To save energy and network bandwidth for the mobile end devices in PPIL, we securely outsource the computations to two non-colluding semi-honest parties. Our solution mixes different secure two-party computation protocols and we design size-and depth-optimized circuits for PPIL. We construct efficient circuit building blocks that are of independent interest: Single Instruction Multiple Data (SIMD) capable oblivious access to an array with low circuit depth and selection of the k-Nearest Neighbors with small circuit size. Additionally, we reduce Received Signal Strength (RSS) values from 8 bits to 4 bits without any significant accuracy reduction. Our most efficient PPIL protocol is 553x faster than that of Li et al. (INFOCOM'14) and 500× faster than that of Ziegeldorf et al. (WiSec'14). Our implementation on commodity hardware has practical run-times of less than 1 second even for the most accurate distance metrics that we consider, and it can process more than half a million PPIL queries per day.

Homomorphic encryption is a tool that enables computation on encrypted data and thus has applications in privacy-preserving cloud computing. Though conceptually amazing, implementation of homomorphic encryption is very challenging and typically software implementations on general purpose computers are extremely slow. In this paper we present our year long effort to design a domain specific architecture in a heterogeneous Arm+FPGA platform to accelerate homomorphic computing on encrypted data. We design a custom co-processor for the computationally expensive operations of the well-known Fan-Vercauteren (FV) homomorphic encryption scheme on the FPGA, and make the Arm processor a server for executing different homomorphic applications in the cloud, using this FPGA-based co-processor. We use the most recent arithmetic and algorithmic optimization techniques and perform designspace exploration on different levels of the implementation hierarchy. In particular we apply circuit-level and block-level pipeline strategies to boost the clock frequency and increase the throughput respectively. To reduce computation latency, we use parallel processing at all levels. Starting from the highly optimized building blocks, we gradually build our multi-core multi-processor architecture for computing. We implemented and tested our optimized domain specific programmable architecture on a single Xilinx Zynq UltraScale+ MPSoC ZCU102 Evaluation Kit. At 200 MHz FPGA-clock, our implementation achieves over 13x speedup with respect to a highly optimized software implementation of the FV homomorphic encryption scheme on an Intel i5 processor running at 1.8 GHz.

Localization based on premeasured WiFi fingerprints is a popular method for indoor localization where satellite based positioning systems are unavailable. In these systems, privacy of the user's location is lost because the location is computed by the service provider. In INFOCOM'14, Li et al. presented PriWFL, a WiFi fingerprint localization system based on additively homomorphic Paillier encryption, that was claimed to protect both the users' location privacy and the service provider's database privacy. In this paper, we demonstrate a severe weakness in PriWFL that allows an attacker to compromise the service provider's database under a realistic attack model and also identify certain other problems in PriWFL that decrease its localization accuracy. Hence, we show that PriWFL does not solve the privacy problems of WiFi fingerprint localization. We also explore different solutions to implement secure privacy-preserving WiFi fingerprint localization and propose two schemes based on Paillier encryption which do not suffer from the weakness of PriWFL and offer the same localization accuracy as the privacy-violating schemes.

In this paper, we present an FPGA based hardware accelerator ‘$\mathsf{HEPCloud}$’ for homomorphic evaluations of medium depth functions which has applications in cloud computing. Our$\mathsf{HEPCloud}$architecture supports the polynomial ring based homomorphic encryption scheme FV for a ring-LWE parameter set of dimension$2^{15}$, modulus size 1,228-bit, and a standard deviation 50. This parameter-set offers a multiplicative depth 36 and at least 85 bit security. The processor of$\mathsf{HEPCloud}$is composed of multiple parallel cores. To achieve fast computation time for such a large parameter-set, various optimizations in both algorithm and architecture levels are performed. For fast polynomial multiplications, we use CRT with NTT and achieve two dimensional parallelism in$\mathsf{HEPCloud}$. We optimize the BRAM access, use a fast Barrett like polynomial reduction method, optimize the cost of CRT, and design a fast divide-and-round unit. Beside parallel processing, we apply pipelining strategy in several of the sequential building blocks to reduce the impact of sequential computations. Finally, we implement$\mathsf{HEPCloud}$on a medium-size Xilinx Virtex 6 FPGA board ML605 board and measure its on-board performance. To store the ciphertexts during a homomorphic function evaluation, we use the large DDR3 memory of the ML605 board. Our FPGA-based implementation of$\mathsf{HEPCloud}$computes a homomorphic multiplication in 26.67 s, of which the actual computation takes only 3.36 s and the rest is spent for off-chip memory access. It requires about 37,551 s to evaluate the SIMON-64/128 block cipher, but the per-block timing is only about 18 s because$\mathsf{HEPCloud}$processes 2,048 blocks simultaneously. The results show that FPGA-based acceleration of homomorphic function evaluations is feasible, but fast memory interface is crucial for the performance.

Multiplication of large integers is a fundamental operation for public key cryptography. In contemporary public key cryptography, the sizes of integers are typically from more than one hundred bits to even several thousands of bits. Because these sizes exceed the bit widths of all general-purpose processors, these multiplications must be performed with a multiprecision multiplication algorithm which splits the operation into multiple partial products and accumulation steps. To ensure efficiency, multiprecision multiplication algorithms must be designed with special care and optimized for the instruction sets of specific processors. Consequently, developing efficient multiprecision multiplication algorithms and optimizing them for specific platforms has been an active research topic. In this paper, we optimize multiprecision multiplication and squaring specifically for the 64-bit ARMv8 processors which are widely used, for example, in modern smart phones and tablets. We combine the subtractive Karatsuba algorithm, operand-scanning techniques (for multiplication) and sliding-block-doubling methods (for squaring) to accelerate the performance of the 256-bit multiprecision multiplication and squaring by 7.6% and 7.0% compared to the OpenSSL implementations. We focus particularly on the multiprecision multiplications that are required in elliptic curve cryptography. Our implementation supports general elliptic curves of various sizes and all source codes are available in public domain.

Verification of an ECDSA signature requires a double scalar multiplication on an elliptic curve. In this work, we study the computation of this operation on a twisted Edwards curve with an efficiently computable endomorphism, which allows reducing the number of point doublings by approximately 50 percent compared to a conventional implementation. In particular, we focus on a curve defined over the 207-bit prime field Fpwith p = 2207- 5,131. We develop several optimizations to the operation and we describe two hardware architectures for computing the operation. The first architecture is a small processor implemented in 0.13 μm CMOS ASIC and is useful in resource-constrained devices for the Internet of Things (IoT) applications. The second architecture is designed for fast signature verifications by using FPGA acceleration and can be used in the server-side of these applications. Our designs offer various trade-offs and optimizations between performance and resource requirements and they are valuable for IoT applications.

We propose a lightweight coprocessor for 16-bit microcontrollers that implements high security elliptic curve cryptography. It uses a 283-bit Koblitz curve and offers 140-bit security. Koblitz curves offer fast point multiplications if the scalars are given as specific $$\tau $$ -adic expansions, which results in a need for conversions between integers and $$\tau $$ -adic expansions. We propose the first lightweight variant of the conversion algorithm and, by using it, introduce the first lightweight implementation of Koblitz curves that includes the scalar conversion. We also include countermeasures against side-channel attacks making the coprocessor the first lightweight coprocessor for Koblitz curves that includes a set of countermeasures against timing attacks, SPA, DPA and safe-error fault attacks. When the coprocessor is synthesized for 130 nm CMOS, it has an area of only 4,323 GE. When clocked at 16 MHz, it computes one 283-bit point multiplication in 98 ms with a power consumption of 97.70 $$\mu $$ W, thus, consuming 9.56 $$\mu $$ J of energy.

In this paper, we study a generalization of addition chains where$k$previous values are summed together on each step instead of only two values as in traditional addition chains. Such chains are called$k$-chains and we show that they have applications in finding efficient parallelizations in problems that are known to be difficult to parallelize. In particular, 3-chains improve computations of inversions in finite fields using hybrid-double multipliers. Recently, it was shown that this operation can be efficiently computed using a ternary algorithm but we show that 3-chains provide a significantly more efficient solution.

High performance implementation of single exponentiation in finite field is crucial for cryptographic applications such as those used in embedded systems and industrial networks. In this paper, we propose a new architecture for performing single exponentiations in binary finite fields. For the first time, we employ a digit-level hybrid-double multiplier proposed by Azarderakhsh and Reyhani-Masoleh for computing exponentiations based on square-and-multiply scheme. In our structure, the computations for squaring and multiplication are uniform and independent of the Hamming weight of the exponent; considered to have built-in resistance against simple power analysis attacks. The presented structure reduces the latency of exponentiation in binary finite field considerably and thus can be utilized in applications exhibiting high-performance computations including sensitive and constrained ones in embedded systems used in industrial setups and networks.

Fast inversion in finite fields is crucial for high-performance cryptography and codes. We present techniques to exploit the recently proposed hybrid-double multipliers for fast inversions in binary fields GF(2m) with normal bases. A hybrid-double multiplier computes a double multiplication, the product of three elements in GF(2m), with a latency comparable to the latency of single multiplication of two elements. Traditional approaches, such as Itoh-Tsujii, cannot utilize hybrid-double multipliers. We devise a new inversion algorithm based on ternary representations that exploits their potential. The algorithm reduces the latency of inversion significantly for the fields recommended by NIST if hybrid-double multipliers are employed. For example, the algorithm computes an inversion in GF(2163) with only five double multiplications whereas the Itoh-Tsujii algorithm requires nine single or double multiplications. We propose a new inverter architecture using this new algorithm and a hybrid-double multiplier. We show that it is faster than the existing techniques by providing ASIC synthesis results using 65-nm CMOS technology. For example, our inverter for GF(2163) achieves about 34 percent shorter computation time than an inverter using the Itoh-Tsujii algorithm and a single multiplier.

In this paper we offer new algorithms for one of the most common operations in public key cryptosystems: the inversion over binary Galois fields. The new algorithms are based on using double-base and triple-base representations. They are provably more economical-in terms of the average number of multiplications-than the popular Itoh-Tsujii algorithm. In addition to having fewer multiplications, the new inversion algorithms offer further implementation advantages because they allow more efficient computation of squarings and, in some cases, require fewer temporary variables. The new algorithms are straightforwardly usable in both software and hardware implementations.

This paper presents an extension of the byte-fault attack on signature schemes presented by Giraud et al. Our work extends their attack in a number of ways, but the main focus is an alternative fault model motivated by existing fault injection results. Instead of assuming faults are uniformly distributed (i.e., a given bit is flipped with probability 1/2), we consider the case where faults are biased (i.e., the probability differs from 1/2). Our results show that injecting biased faults allows an attacker to reveal security-critical data with significantly fewer faults and/or a significantly faster search through the remaining candidates.

Scalar multiplication in elliptic curve cryptography is the most computational intensive operation. Efficiency of this operation can be significantly improved in hardware implementations by using Frobenius endomorphisms which require integer toτ-adic nonadjacent form conversion. Because conversion is one of the limiting factors in some of Koblitz curve-based cryptosystems, it has become an interesting problem. In this paper, we propose two algorithms and a novel hardware architecture to double the speed of integer toτ-adic nonadjacent form conversion.

In this paper, we shall introduce several new algorithms for integer multiplication that are based on specific multiple-radix representation of one of the multiplicands. We provide extensive theoretical analysis and experimental results for multipliers based on the new representations on 0.18 μm CMOS technology. They provide a clear picture about the advantages of the new method in 64-bit hardware implementations compared to array-based classical multiplier and radix-8-based multiplier. The proposed multipliers have better area and power consumption compared to reference multipliers.

In this paper, we discuss conversions between integers and tau-adic expansions and we provide efficient algorithms and hardware architectures for these conversions. The results have significance in elliptic curve cryptography using Koblitz curves, a family of elliptic curves offering faster computation than general elliptic curves. However, in order to enable these faster computations, scalars need to be reduced and represented using a special base-tau expansion. Hence, efficient conversion algorithms and implementations are necessary. Existing conversion algorithms require several complicated operations, such as multiprecision multiplications and computations with large rationals, resulting in slow and large implementations in hardware and microcontrollers with limited instruction sets. Our algorithms are designed to utilize only simple operations, such as additions and shifts, which are easily implementable on practically all platforms. We demonstrate the practicability of the new algorithms by implementing them on Altera Stratix II FPGAs. The implementations considerably improve both computation speed and required area compared to the existing solutions.

We present an FPGA-based accelerator for elliptic curve cryptography on a Koblitz curve targeting for applications requiring very high speed. The accelerator supports fast computation of point multiplication by using window methods as well as multiple point multiplications with joint sparse form representations. Optimized operation-specific processing units are used in order to improve performance. Throughput is increased by pipelining operations. The accelerator was implemented in an Altera Stratix II FPGA and it computes point multiplication on average in 16.36 us and achieves a maximum of 161,290 operations per second. A 3-term multiple point multiplication requires 35.06 us with a maximum of 60,603 operations in second.

We describe algorithms for point multiplication on Koblitz curves using multiple-base expansions of the form $k = \sum \pm \tau^a (\tau-1)^b$ and $k= \sum \pm \tau^a (\tau-1)^b (\tau^2 - \tau - 1)^c.$ We prove that the number of terms in the second type is sublinear in the bit length of $k$, which leads to the first provably sublinear point multiplication algorithm on Koblitz curves. For the first type, we conjecture that the number of terms is sublinear and provide numerical evidence demonstrating that the number of terms is significantly less than that of $\tau$-adic non-adjacent form expansions. We present details of an innovative FPGA implementation of our algorithm and performance data demonstrating the efficiency of our method. We also show that implementations with very low computation latency are possible with the proposed method because parallel processing can be exploited efficiently.

This paper discusses parallelization of elliptic curve cryptography hardware accelerators using elliptic curves over binary fields F2m. Elliptic curve point multiplication, which is the operation used in every elliptic curve cryptosystem, is hierarchical in nature, and parallelism can be utilized in different hierarchy levels as shown in many publications. However, a comprehensive analysis on the effects of parallelization has not been previously presented. This paper provides tools for evaluating the use of parallelism and shows where it should be used in order to maximize efficiency. Special attention is given for a family of curves called Koblitz curves because they offer very efficient point multiplication. A new method where the latency of point multiplication is reduced with parallel field arithmetic processors is introduced. It is shown to outperform the previously presented multiple field multiplier techniques in the cases of Koblitz curves and generic curves with fixed base points. A highly efficient general elliptic curve cryptography processor architecture is presented and analyzed. Based on this architecture and analysis on the effects of parallelization, a few designs are implemented on an Altera Stratix II field-programmable gate array (FPGA).

An architecture for elliptic curve point multiplication, which is developed especially for FPGAs, is introduced. The point multiplication is the basic operation of any elliptic curve cryptosystem and, hence, it must be implemented efficiently. The architecture is designed to be flexible in terms of speed and logic requirements and it can be scaled to meet the demands of different applications. Implementations have proven to be very efficient in performance and they belong to the fastest published FPGA-based ECC designs for most elliptic curve parameters.

A fully pipelined implementation of the Advanced Encryption Standard encryption algorithm with 128-bit input and key length (AES-128) was implemented on Xilinx' Virtex-E and Virtex-II devices. The design is called SIG-AES-E and it implements the S-boxes combinatorially and thus requires no internal memory. It is concluded, that SIG-AES-E is faster than other published FPGA-based implementations of the AES-128 encryption algorithm.