Fully Homomorphic Encryption (FHE) enables computations on encrypted data, proving itself to be an essential building block for privacy-preserving applications. However, it involves computationally demanding operations such as polynomial multiplication, with the Number Theoretic Transform (NTT) being the state-of-the-art solution to perform it. Considering that most FHE schemes operate over the negacyclic ring of polynomials, we introduce a novel formulation of the hierarchical Four-Step NTT approach for the negacyclic ring, eliminating the need for pre- and post-processing steps found in the existing methods. To accelerate NTT operations, the Field-Programmable Gate Array (FPGA) devices offer flexible and powerful computing platforms. We propose an FPGA-based, high-speed, parametric and fully pipelined architecture that implements the improved Seven-Step NTT algorithm, which builds upon the four-step algorithm. Our design supports a wide range of parameters, including ring sizes up to 216 and modulus sizes up to 64-bit. We focus on achieving configurable throughput, as constrained by the bandwidth of High-Bandwidth Memory (HBM), which is an additional in-package memory common in high-end FGPA devices such as Alveo U280. We aim to maximize throughput through an IO parametric design on the Alveo U280 FPGA. The implementation results demonstrate that the average latency of our design for batch NTT operation is 8.32μs for the ring size 216 and 64-bit width; a speed-up of 7.96 × compared to the current state-of-the-art designs.

Lattice-based cryptographic schemes such as Crystals-Kyber and Dilithium are post-quantum algorithms selected to be standardized by NIST as they are considered to be secure against quantum computing attacks. The multiplication in polynomial rings is the most time-consuming operation in many lattice-based cryptographic schemes, which is also subject to side-channel attacks. While NTT-based polynomial multiplication is almost a norm in a wide range of implementations, a relatively new method, incomplete NTT is preferred to accelerate lattice-based cryptography, especially on some computing platforms that feature special instructions. In this paper, we present a novel, efficient and non-profiled power/EM side-channel attack targeting polynomial multiplication based on the incomplete NTT algorithm. We apply the attack on the Crystals-Dilithium signature algorithm and Crystals-Kyber KEM. We demonstrate that the method accelerates attack run-time when compared to the existing approaches. While a conventional non-profiled side-channel attack tests a much larger hypothesis set because it needs to predict two coefficients of secret polynomials together, we propose a much fasterzero-value filtering attack(ZV-FA), which reduces the size of the hypothesis set by targeting the coefficients individually. We also propose an effective and efficient validation and correction technique employing the inverse NTT to estimate and modify the mispredicted coefficients. Our experimental results show that we can achieve a speed-up of 1915×over brute-force.

This paper presents a design-time configurable hardware generator for hardware acceleration of the CKKS Fully Homomorphic Encryption (FHE) scheme. Our design aims to accelerate the multiplication and relinearization operations of the CKKS. It includes a design-time configurable Number Theoretic Transform (NTT) multiplication hardware for polynomial sizes between 210and 215. The NTT-based multiplication realizes modular multiplication using an efficient word-level Montgomery reduction algorithm.Polynomial multiplication is a bottleneck for the FHE operations. The NTT enables very fast polynomial multiplication by reducing its complexity to ${\mathcal{O}}\left({n{{\log }_2}n}\right)$ from ${\mathcal{O}}\left({{n^2}}\right)$. The fundamental arithmetic block of the NTT operation is the butterfly, which implements four different operations, namely, modular multiplication and modular addition/subtraction.The memory access pattern (MAP) of the NTT operation is complex, and it is crucial to design an efficient MAP for NTT for implementing a high-throughput NTT architecture. We designed and implemented an efficient algorithm for the MAP of NTT and generalized this approach for polynomial sizes, 210to 215.

In the past few years, Convolutional Neural Networks (CNN) have demonstrated promising performance in various real-world cybersecurity applications, such as network and multimedia security. However, the underlying fragility of CNN structures poses major security problems, making them inappropriate for use in security-oriented applications, including computer networks. Protecting these architectures from adversarial attacks necessitates using security-wise architectures that are challenging to attack. In this study, we present a novel architecture based on an ensemble classifier that combines the enhanced security of 1-Class classification (known as 1C) with the high performance of conventional 2-Class classification (known as 2C) in the absence of attacks. Our architecture is referred to as the 1.5-Class (cmb-classifier) classifier and is constructed using a final dense classifier, one 2C classifier (i.e., CNNs), and two parallel 1C classifiers (i.e., auto-encoders). In our experiments, we evaluated the robustness of our proposed architecture by considering eight possible adversarial attacks in various scenarios. We performed these attacks on the 2C and cmb-classifier architectures separately. The experimental results of our study showed that the Attack Success Rate (ASR) of the I-FGSM attack against a 2C classifier trained with the N-BaIoT dataset is 0.9900. In contrast, the ASR is 0.0000 for the cmb-classifier.

This paper presents an accelerated and parallelized GPU implementation for homomorphic encryption operations of the Brakerski-Fan-Vercauteren (BFV) scheme. We improved the run-time performance by optimizing homomorphic multiplication, relinearization, rotation, and addition using Number Theoretic Transform (NTT) and Barrett Reduction and utilizing a Compute Unified Device Architecture (CUDA). To the best of our knowledge, this implementation performs the fastest homomorphic operations in the literature. We used the Simple Encrypted Arithmetic Library (SEAL) version 3.6.6 BFV scheme for implementation on a GPU. Our implementation achieved $13.39\times, 47.01\times, 39.6\times$, and $33.71\times$ speedup compared to SEAL running on CPU for addition, multiplication, relinearization, and rotation, respectively for a modulus size of 438-bits and ring degree of 16,384. For the same modulus size and ring degree, this implementation performed one homomorphic multiplication in 1 ms, a relinearization operation in 0.4 ms, a rotation in 0.5 ms, and an addition in 0.017 ms, which demonstrates significant performance improvement over state-of-the-art.

Efficient lattice-based cryptosystems operate with polynomial rings with the Number Theoretic Transform (NTT) to reduce the computational complexity of polynomial multiplication. NTT has therefore become a major arithmetic component (thus computational bottleneck) in various cryptographic constructions like hash functions, key-encapsulation mechanisms, digital signatures, and homomorphic encryption. Although there exist several hardware designs in prior work for NTT, they all are isolated design instances fixed for specific NTT parameters or parallelization level. This article provides an extensive study of flexible design methods for NTT implementation. To that end, we evaluate three cases: (1) parametric hardware design, (2) high-level synthesis (HLS) design approach, and (3) design for software implementation compiled on soft-core processors, where all are targeted on reconfigurable hardware devices. We evaluate the designs that implement multiple NTT parameters and/or processing elements, demonstrate the design details for each case, and provide a fair comparison with each other and prior work. On a Xilinx Virtex-7 FPGA, compared to HLS and processor-based methods, the results show that the parametric hardware design is on average$4.4\times$and$73.9\times$smaller and$22.5\times$and$19.3\times$faster, respectively. Surprisingly, HLS tools can yield less efficient solutions than processor-based approaches in some cases.

This article is an attempt in quest of the fastest hardware algorithms for the computation of the evaluation component of verifiable delay functions (VDFs),$a^{2^T} \bmod N$, proposed for use in various distributed protocols, in which no party is assumed to compute it significantly faster than other participants. To this end, we propose a class of modular squaring algorithms suitable for low-latency ASIC implementations. The proposed algorithms aim to achieve highest levels of parallelization that have not been explored in previous works in the literature, which usually pursue more balanced optimization of speed and area. For this, we utilize redundant representations of integers and introduce three modular squaring algorithms that work with integers in redundant forms: i) Montgomery algorithm, ii) memory-based algorithm and iii) direct reduction algorithm for fixed moduli. All algorithms enable$O(\log k)$depth circuit implementations, where$k$is the bit-size of the modulus$N$in the VDF function. We analyze and compare gate level-circuits of the proposed algorithms and provide estimates for their critical path delay and gate count.

Polynomial multiplication is one of the most time-consuming operations utilized in lattice-based post-quantum cryptography (PQC) schemes. CRYSTALS-KYBER is a lattice-based key encapsulation mechanism (KEM) and it was recently announced as one of the four finalists at round three in NIST's PQC Standardization. Therefore, efficient implementations of polynomial multiplication operation are crucial for highperformance CRYSTALS-KYBER applications. In this paper, we propose three different hardware architectures (lightweight, balanced, high-performance) that implement the NTT, Inverse NTT (INTT) and polynomial multiplication operations for the CRYSTALS-KYBER scheme. The proposed architectures include a unified butterfly structure for optimizing polynomial multiplication and can be utilized for accelerating the key generation, encryption and decryption operations of CRYSTALS-KYBER. Our high-performance hardware with 16 butterfly units shows up to 112×, 132× and 109× improved performance for NTT, INTT and polynomial multiplication, respectively, compared to the high-speed software implementations on Cortex-M4.

We tackle the problem where a server owns a trained Machine Learning (ML) model and a client/user has an unclassified query that he wishes to classify in secure and private fashion using the server’s model. During the process the server learns nothing, while the user learns only his final classification and nothing else. Since several ML classification algorithms, such as deep neural networks, support vector machines-SVM (and hyperplane decisions in general), Logistic Regression, Naïve Bayes, etc., can be expressed in terms of matrix operations, initially we propose novel secure matrix operations as our building blocks. On top of them we build our secure and private ML classification algorithms under strict security and privacy requirements. As our underlying cryptographic primitives are shown to be resilient to quantum computer attacks, our algorithms are also suitable for the post-quantum world. Our theoretical analysis and extensive experimental evaluations show that our secure matrix operations, hence our secure ML algorithms build on top of them as well, outperform the state of the art schemes in terms of computation and communication costs. This makes our algorithms suitable for devices with limited resources that are often found in Industrial IoT (Internet of Things)

Homomorphic sorting is an operation that blindly sorts a given set of encrypted numbers without decrypting them (thus, there is no need for the secret key). In this article, we propose a new, efficient, and scalable method for homomorphic sorting of numbers: polynomial rank sort algorithm. To put the new algorithm in a comparative perspective, we provide an extensive survey of classical sorting algorithms and networks that are not directly suitable for homomorphic computation. We also include, in our discussions, two of our previous algorithms specifically designed for homomorphic sorting operation: direct and greedy sort, and explain how they evolve from classical sorting networks. We theoretically show that the new algorithm is superior in terms of multiplicative depth when compared with all other algorithms. When batched implementation is used, the number of comparisons is reduced from O(N2) to O(N) provided that the number of slots is larger than or equal to the number of elements in the set. Our software implementation results confirm that the new algorithm is several orders of magnitude faster than many methods in the literature. Also, the polynomial sort algorithm scales better than the fastest algorithm in the literature to the best our knowledge although for small sets the execution times are comparable. The proposed algorithm is amenable to parallel implementation as most time consuming operations in the algorithm can naturally be performed concurrently.

The Number Theoretic Transform (NTT) enables faster polynomial multiplication and is becoming a fundamental component of next-generation cryptographic systems. NTT hardware designs have two prevalent problems related to design-time flexibility. First, algorithms have different arithmetic structures causing the hardware designs to be manually tuned for each setting. Second, applications have diverse throughput/area needs but the hardware have been designed for a fixed, pre-defined number of processing elements. This paper proposes a parametric NTT hardware generator that takes arithmetic configurations and the number of processing elements as inputs to produce an efficient hardware with the desired parameters and throughput. We illustrate the employment of the proposed design in two applications with different needs: A homomorphically encrypted deep neural network inference (CryptoNets) and a post-quantum digital signature scheme (qTESLA). We propose the first NTT hardware acceleration for both applications on FPGAs. Compared to prior software and high-level synthesis solutions, the results show that our hardware can accelerate NTT up to 28× and 48×, respectively. Therefore, our work paves the way for high-level, automated, and modular design of next-generation cryptographic hardware solutions.

Abstract Effective protection against cyber-attacks requires constant monitoring and analysis of system data in an IT infrastructure, such as log files and network packets, which may contain private and sensitive information. Security operation centers (SOC), which are established to detect, analyze and respond to cyber-security incidents, often utilize detection models either for known types of attacks or for anomaly and applies them to the system data for detection. SOC are also motivated to keep their models private to capitalize on the models that are their propriety expertise, and to protect their detection strategies against adversarial machine learning. In this paper, we develop a protocol for privately evaluating detection models on the system data, in which privacy of both the system data and detection models is protected and information leakage is either prevented altogether or quantifiably decreased. Our main approach is to provide an end-to-end encryption for the system data and detection models utilizing lattice-based cryptography that allows homomorphic operations over ciphertext. We employ recent data sets in our experiments which demonstrate that the proposed privacy-preserving intrusion detection system is feasible in terms of execution times and bandwidth requirements and reliable in terms of accuracy.

Fully homomorphic encryption (FHE) is a technique that allows computations on encrypted data without the need for decryption and it provides privacy in various applications such as privacy-preserving cloud computing. In this article, we present two hardware architectures optimized for accelerating the encryption and decryption operations of the Brakerski/Fan-Vercauteren (BFV) homomorphic encryption scheme with high-performance polynomial multipliers. For proof of concept, we utilize our architectures in a hardware/software codesign accelerator framework, in which encryption and decryption operations are offloaded to an FPGA device, while the rest of operations in the BFV scheme are executed in software running on an off-the-shelf desktop computer. Specifically, our accelerator framework is optimized to accelerate Simple Encrypted Arithmetic Library (SEAL), developed by the Cryptography Research Group at Microsoft Research. The hardware part of the proposed framework targets the XILINX VIRTEX7 FPGA device, which communicates with its software part via a peripheral component interconnect express (PCIe) connection. For proof of concept, we implemented our designs targeting 1024degree polynomials with 8-bit and 32-bit coefficients for plaintext and ciphertext, respectively. The proposed framework achieves almost 12× and 7× latency speedups, including I/O operations for the offloaded encryption and decryption operations, respectively, compared to their pure software implementations.

In this paper, we present an optimized FPGA implementation of a novel, fast and highly parallelized NTT-based polynomial multiplier architecture, which proves to be effective as an accelerator for lattice-based homomorphic cryptographic schemes. As I/O operations are as time-consuming as NTT operations during homomorphic computations in a host processor/accelerator setting, instead of achieving the fastest NTT implementation possible on the target FPGA, we focus on a balanced time performance between the NTT and I/O operations. Even with this goal, we achieved the fastest NTT implementation in literature, to the best of our knowledge. For proof of concept, we utilize our architecture in a framework for Fan-Vercauteren (FV) homomorphic encryption scheme, utilizing a hardware/software co-design approach, in which polynomial multiplication operations are offloaded to the accelerator via PCIe bus while the rest of operations in the FV scheme are executed in software running on an off-the-shelf desktop computer. Specifically, our framework is optimized to accelerate Simple Encrypted Arithmetic Library (SEAL), developed by the Cryptography Research Group at Microsoft Research, for the FV encryption scheme, where large degree polynomial multiplications are utilized extensively. The hardware part of the proposed framework targets Xilinx Virtex-7 FPGA device and the proposed framework achieves almost 11x latency speedup for the offloaded operations compared to their pure software implementations. We achieved a throughput of almost 800K polynomial multiplications per second, for polynomials of degree 1024 with 32-bit coefficients.

Lattice trapdoors are an important primitive used in a wide range of cryptographic protocols, such as identity-based encryption (IBE), attribute-based encryption, functional encryption, and program obfuscation. In this paper, we present software implementations of the Gentry-Peikert-Vaikuntanathan (GPV) digital signature, IBE and ciphertext-policy attribute-based encryption (CP-ABE) schemes based on an efficient Gaussian sampling algorithm for trapdoor lattices, and demonstrate that these three important cryptographic protocols are practical. One important aspect of our implementation is that it supports prime moduli, which are required in many cryptographic schemes. Also, our implementation uses bases larger than two for the gadget matrix whereas most previous implementations use the binary base. We show that the use of higher bases significantly decreases execution times and storage requirements. We adapt IBE and CP-ABE schemes originally based on learning with errors (LWE) hardness assumptions to a more efficient Ring LWE (RLWE) construction. To the best of our knowledge, ours are the first implementations employing the Gaussian sampling for non-binary bases of the gadget matrix. The experimental results demonstrate that our lattice-based signature, IBE and CP-ABE implementations, which are based on standard assumptions with post-quantum security, provide a performance comparable to the recent state-of-the-art implementation works based on stronger/non-post-quantum assumptions.

We address the practicality challenges of secure program obfuscation by implementing, optimizing, and experimentally assessing an approach to securely obfuscate conjunction programs proposed in [1]. Conjunction programs evaluate functionsf(x1,...,xL) = Λi∈Iyi, whereyiis eitherxior ¬xiandI⊆ [L], and can be used as classifiers. Our obfuscation approach satisfies distributional Virtual Black Box (VBB) security based on reasonable hardness assumptions, namely an entropic variant of the Ring Learning with Errors (Ring-LWE) assumption. Prior implementations of secure program obfuscation techniques support either trivial programs like point functions, or support the obfuscation of more general but less efficient branching programs to satisfy Indistinguishability Obfuscation (IO), a weaker security model. Further, the more general implemented techniques, rather than relying on standard assumptions, base their security on conjectures that have been shown to be theoretically vulnerable. Our work is the first implementation of non-trivial program obfuscation based on polynomial rings. Our contributions include multiple design and implementation advances resulting in reduced program size, obfuscation runtime, and evaluation runtime by many orders of magnitude. We implement our design in software and experimentally assess performance in a commercially available multi-core computing environment. Our implementation achieves runtimes of 6.7 hours to securely obfuscate a 64-bit conjunction program and 2.5 seconds to evaluate this program over an arbitrary input. We are also able to obfuscate a 32-bit conjunction program with 53 bits of security in 7 minutes and evaluate the obfuscated program in 43 milliseconds on a commodity desktop computer, which implies that 32-bit conjunction obfuscation is already practical. Our graph-induced (directed) encoding implementation runs up to 25 levels, which is higher than previously reported in the literature for this encoding. Our design and implementation advances are applicable to obfuscating more general compute-and-compare programs and can also be used for many cryptographic schemes based on lattice trapdoors.

Summary Private Information Retrieval (PIR) enables the data owners to share and/or retrieve data on remote repositories without leaking any information as to which a data item is requested. Although it is always possible to download the entire dataset, this is clearly a waste of bandwidth. A fundamental approach in the literature for PIR is exploiting homomorphic cryptosystems. In these approaches, not one but many modular exponentiations need to be computed and multiplied to obtain the desired result. This multi‐exponentiation operation can be implemented by exponentiating the bases to their corresponding exponents one‐by‐one. However, when the operation is considered as a whole, it can be performed in a more efficient way. Although individual exponentiations are pleasingly parallelizable, the combined multi‐exponentiation requires a careful parallel implementation. In this work, we propose a generic tensor‐based PIR scheme and efficient and novel techniques to parallelize multi‐exponentiations on multicore processors with perfect load balance. The experimental results show that our load balancing techniques make a parallel multi‐exponentiation up to %27 faster when the size of the bases and the exponents are 4096 bits and the number of threads is 16.

In this paper, we report on our implementation of a lattice-based key-policy attribute-based encryption (KP-ABE) scheme, which uses short secret keys. The particular KP-ABE scheme can be used directly for attribute-based access control applications, as well as a building block in more involved applications and cryptographic schemes, such as audit log encryption, targeted broadcast encryption, functional encryption, and program obfuscation. We adapt a recently proposed KP-ABE scheme based on the learning with errors (LWE) problem to a more efficient scheme based on the ring learning with errors (RLWE) problem, and demonstrate an implementation that can be used in practical applications. Our state-of-the-art implementation on graphics processing units shows that the homomorphic public key and ciphertext evaluation operations, which dominate the execution time of the KP-ABE scheme, can be performed in a reasonably short amount of time. Our practicality results also hold when scaled to a relatively large number of attributes. To the best of our knowledge, this is the first KP-ABE implementation that supports both ciphertext and public key homomorphism, and the only experimental practicality results reported in this paper.

Lipmaa's Computational Private Information Retrieval (CPIR) protocol is probably the most bandwidth efficient method in the literature, although its computational complexity is a limiting factor for practical applications as it is based on expensive public key operations. Utilizing binary decision diagrams (Bdd) and the Damgård–Jurik cryptosystem, Lipmaa's CPIR performs three modular exponentiation operations per internal node in Bdd. In this paper, we present a new CPIR protocol, which reduces the number of exponentiation operations to 1 per first-level internal nodes and 2 per other internal nodes of the Bdd. For 1024-bit exponents (i.e. 80-bit security level) and 32 768 items, when compared with the fastest parallel implementation in the literature on four cores, reducing the number of exponentiations yields a 1.22× speedup and the multi-exponentiation technique adds 2.23× more on top of that. Overall, when combined, reducing the number of exponentiations, multi-exponentiation, parallelization on four cores and the hybrid approach can provide more than 300× speedup compared to the sequential implementation of the original method.

After the introduction of first fully homomorphic encryption scheme in 2009, numerous research work has been published aiming at making fully homomorphic encryption practical for daily use. The first fully functional scheme and a few others that have been introduced has been proven difficult to be utilized in practical applications, due to efficiency reasons. Here, we propose a custom hardware accelerator, which is optimized for a class of reconfigurable logic, for Lopez-Alt, Tromer and Vaikuntanathan's somewhat homomorphic encryption based schemes. Our design is working as a co-processor which enables the operating system to offload the most compute-heavy operations to this specialized hardware. The core of our design is an efficient hardware implementation of a polynomial multiplier as it is the most compute-heavy operation of our target scheme. The presented architecture can compute the product of very-large polynomials in under 6.25 ms which is 102 times faster than its software implementation. In case of accelerating homomorphic applications; we estimate the per block homomorphic AES as 442 ms which is 28.5 and 17 times faster than the CPU and GPU implementations, respectively. In evaluation of Prince block cipher homomorphically, we estimate the performance as 52 ms which is 66 times faster than the CPU implementation.

We present scalable and parallel versions of Lipmaa's computationally-private information retrieval (CPIR) scheme [20], which provides log-squared communication complexity. In the proposed schemes, instead of binary decision diagrams utilized in the original CPIR, we employ an octal tree based approach, in which non-sink nodes have eight child nodes. Using octal trees offers two advantages: i) a serial implementation of the proposed scheme in software is faster than the original scheme and ii) its bandwidth usage becomes less than the original scheme when the number of items in the data set is moderately high (e.g., 4,096 for 80-bit security level using Damgard-Jurik cryptosystem). In addition, we present a highly-optimized parallel algorithm for shared-memory multi-core/processor architectures, which minimizes the number of synchronization points between the cores. We show that the parallel implementation is about 50 times faster than the serial implementation for a data set with 4,096 items on an eight-core machine. Finally, we propose a hybrid algorithm that scales the CPIR scheme to larger data sets with small overhead in bandwidth complexity. We demonstrate that the hybrid scheme based on octal trees can lead to more than two orders of magnitude faster parallel implementations than serial implementations based on binary trees. Comparison with the original as well as the other schemes in the literature reveals that our scheme is the best in terms of bandwidth requirement.

In this paper, we present a methodology to evaluate the feasibility, effectiveness and complexity of a class of cache-based side-channel attacks. The methodology provides estimates on the lower bound of the required number of observations on the side channel and the number of trials for a successful attack. As a case study, a weak implementation of the Advanced Encryption Standard algorithm is selected to apply the proposed methodology to three different categories of cache-based attacks; namely, access-driven, trace-driven and time-driven attacks. The approach, however, is generic in the sense that it can be utilized in other algorithms that are subject to the micro-architectural side-channel attacks. The adopted approach bases its analysis method partially on the conditional entropy of secret keys given the observations of the intermediate variables in software implementations of cryptographic algorithms via the side channel and explores the extent to which the observations can be exploited in a successful attack. Provided that the intermediate variables are relatively simple functions of the key material and the known inputs or outputs of cryptographic algorithms, a successful attack is theoretically feasible. Our methodology emphasizes the need for an analysis of this leakage through such intermediate variables and demonstrates a systematic way to measure it. The method allows us to explore every attack possibility, estimate the feasibility of an attack, and compare the efficiency and the costs of different attack strategies to determine an optimal level of effective countermeasures.

We propose enhancing a reconfigurable and extensible embedded reduced instruction set computer (RISC) processor core with a protected zone for isolated execution of cryptographic algorithms. The protected zone is a collection of processor subsystems such as functional units optimized for high-speed execution of integer operations, a small amount of local memory for storing sensitive data during cryptographic computations, and special-purpose and cryptographic registers to execute instructions securely. We outline the principles for secure software implementations of cryptographic algorithms in a processor equipped with the proposed protected zone. We demonstrate the efficiency and effectiveness of our proposed zone by implementing the most-commonly used cryptographic algorithms in the protected zone; namely RSA, elliptic curve cryptography, pairing-based cryptography, Advanced Encryption Standard (AES) block cipher, and secure hash algorithm (SHA)-1 and SHA-256 cryptographic hash functions. In terms of time efficiency, our software implementations of cryptographic algorithms running on the enhanced core compare favorably with equivalent software implementations on similar processors reported in the literature. The protected zone is designed in such a modular fashion that it can easily be integrated into any RISC processor. The proposed enhancements for the protected zone are realized on an field programmabel gate array (FPGA) device. The implementation results on the FPGA confirm that its area overhead is relatively moderate in the sense that it can be used in many embedded processors. Finally, the protected zone is useful against cold-boot and micro-architectural side-channel attacks such as cache-based and branch prediction attacks.

We present improved and parallel versions of Lipmaa's computationally-private information retrieval (CPIR) protocol based on a additively-homomorphic cryptosystem. Lipmaa's original CPIR utilizes binary decision diagrams, in which non-sink nodes have two children nodes and the data items to be retrieved are placed in the sink nodes. In our scheme, we employ, instead, quadratic and octal trees, where non-sink nodes have four and eight child nodes, respectively. Using other tree forms, which does not change the asymptotic complexity, results in shallow trees by which we can obtain an implementation that is an order of magnitude faster than the original scheme. We also present a non-trivial parallel algorithm that takes advantage of shared-memory multi-core architectures. Finally, our scheme proves to be highly efficient in terms of bandwidth requirement, the amount of data being exchanged in a run of the CPIR protocol.

In this paper, we design, implement, and realize a cryptographic unit (CU) that can easily be integrated to any reduced instruction set computing (RISC)-type processor for the safe and efficient execution of cryptographic algorithms. Design of the CU takes a novel approach in the execution of cryptographic algorithms when compared with cryptographic accelerators and architectural enhancements. Although it is integrated to a pipeline of an embedded RISC processor, it is partially an autonomous unit with its own resources, which is analogous to the floating point unit in this sense. It provides new instructions to accelerate cryptographic algorithms, and its associated cost in terms of area is acceptable and justified by the improvement in the performance and efficiency. The CU can also be instrumental in protecting the cryptographic computation against active and passive attacks and other malicious processes running simultaneously. We demonstrate that the execution of Advanced Encryption Standart (AES) encryption can be performed inside the CU, which prevents secret and/or sensitive information from leaving the CU during the cryptographic computation.

Quadratic residue codes are introduced as an effective and efficient fault detection technique to protect cryptographic devices against fault attacks. In this paper, we re-consider these codes in an adversarial model, where a powerful attacker can introduce faults with high precision and accuracy. We present two analysis techniques that can lead to successful attacks against quadratic codes if the modulus is not chosen carefully. We provide in-depth theoretical analysis that covers wide range of attacks and present results of practical concerns such as exact number of undetected faults and effective countermeasures. Our analysis is generic in the sense that it can be extended to other residue codes.

Cloud computing technologies become more and more popular every year, as many organizations tend to outsource their data utilizing robust and fast services of clouds while lowering the cost of hardware ownership. Although its benefits are welcomed, privacy is still a remaining concern that needs to be addressed. We propose an efficient privacy-preserving search method over encrypted cloud data that utilizes minhash functions. Most of the work in literature can only support a single feature search in queries which reduces the effectiveness. One of the main advantages of our proposed method is the capability of multi-keyword search in a single query. The proposed method is proved to satisfy adaptive semantic security definition. We also combine an effective ranking capability that is based on term frequency-inverse document frequency (tf-idf) values of keyword document pairs. Our analysis demonstrates that the proposed scheme is proved to be privacy-preserving, efficient and effective.

Location-Based Services (LBS) are becoming more prevalent. While there are many benefits, there are also real privacy risks. People are unwilling to give up the benefits - but can we reduce privacy risks without giving up on LBS entirely? This paper explores the possibility of introducing uncertainty into location information when using an LBS, so as to reduce privacy risk while maintaining good quality of service. This paper also explores the current uses of uncertainty information in a selection of mobile applications.

Cryptographic algorithms, which withstand cryptanalysis after years of rigorous theoretical study and detailed scrutiny have been shown to succumb to attacks that exploit the vulnerabilities in their implementations. Therefore, there has been a vast amount of research effort to find potential vulnerabilities in the implementation of cryptographic algorithms, and efficient and effective countermeasures if such vulnerabilities exist. In this paper, we survey side-channel and fault attacks, which are two powerful methods that have been demonstrated to render many implementations effectively broken. While we categorically analyze the attack techniques, possible countermeasures will also be discussed.

We propose a new class of error detection codes, {\em quadratic dual residue codes}, to protect cryptographic computations running on general-purpose processor cores against fault attacks. The assumed adversary model is a powerful one, whereby the attacker can inject errors anywhere in the data path of a general-purpose microprocessor by bit flipping. We demonstrate that quadratic dual residue codes provide a much better protection under this powerful adversary model compared to similar codes previously proposed for the same purpose in the literature. The adopted strategy aims to protect the single-precision arithmetic operations, such as addition and multiplication, which usually dominate the execution time of many public key cryptography algorithms in general-purpose microprocessors. Two so called {\em robust} units for addition and multiplication operations, which provide a protection against faults attacks, are designed and tightly integrated into the data path of a simple, embedded re-configurable processor. We report the implementation results that compare the proposed error detection codes favorably with previous proposals of similar type in the literature. In addition, we present performance evaluations of the software implementations of Montgomery multiplication algorithm using the robust execution units. Implementation results clearly show that it is feasible to implement robust arithmetic units with relatively low overhead even for a simple embedded processor.

In wireless sensor networks (WSNs), sensor nodes eventually die due to battery depletion. WSNs in which new nodes are periodically redeployed with certain intervals, called generations, to replace the dead nodes are called multi-phase WSNs. In the literature, there are several key predistribution schemes proposed for secure operation of WSNs. However, these schemes are designed for single-phase networks which are not resilient against continuous node capture attacks; even under temporary attacks on the network, the harm caused by the attacker does not heal in time. However, the periodic deployments in multi-phase sensor networks could be utilized to improve the resiliency of the WSNs by deploying nodes with fresh keys. In the literature, there is limited work done in this area. In this paper, we propose a key predistribution scheme for multi-phase WSNs which is resilient under node capture attacks. In our scheme, called random generation material (RGM) key predistribution scheme, each generation of deployment has its own random keying material and pairwise keys are established between node pairs of particular generations. These keys are specific to these generations. Therefore, a captured node cannot be abused to obtain keys of other generations. We compare the performance of our RGM scheme with a well-known multi-phase key predistribution scheme and show that RGM achieves up to 3-fold more resiliency. Even under heavy attacks, our scheme's resiliency performance is 35 % better in steady state.

Digital identity and trust management mechanisms play an important role on the Internet. They help users make decisions on trustworthiness of digital identities in online communities or e-commerce environments, which have significant security consequences. This work aims to contribute to construction of an analytical foundation for digital identity and trust by adopting a quantitative approach. A game theoretic model is developed to quantify community effects and other factors in trust decisions. The model captures factors such as peer pressure and personality traits. The existence and uniqueness of a Nash equilibrium solution is studied and shown for the trust game defined. In addition, synchronous and asynchronous update algorithms are shown to converge to the Nash equilibrium solution. A numerical analysis is provided for a number of scenarios that illustrate the interplay between user behavior and community effects.

In November 2007 NIST announced that it would organize the SHA-3 competition to select a new cryptographic hash function family by 2012. In the selection process, hardware performances of the candidates will play an important role. Our analysis of previously proposed hardware implementations shows that three SHA-3 candidate algorithms can provide superior performance in hardware: Keccak, Luffa and Blue Midnight Wish (BMW). In this paper, we provide efficient and fast hardware implementations of these three algorithms. Considering both single- and multi-message hashing applications with an emphasis on both speed and efficiency, our work presents more comprehensive analysis of their hardware performances by providing different performance figures for different target devices. To our best knowledge, this is the first work that provides a comparative analysis of SHA-3 candidates in multi-message applications. We discover that BMW algorithm can provide much higher throughput than previously reported if used in multi-message hashing. We also show that better utilization of resources can increase speed via different configurations. We implement our designs using Verilog HDL, and map to both ASIC and FPGA devices (Spartan3, Virtex2, and Virtex 4) to give a better comparison with those in the literature. We report total area, maximum frequency, maximum throughput and throughput/area of the designs for all target devices. Given that the selection process for SHA3 is still open; our results will be instrumental to evaluate the hardware performance of the candidates.

Practical implementations of cryptographic algorithms are vulnerable to side-channel analysis and fault attacks. Thus, some masking and fault detection algorithms must be incorporated into these implementations. These additions further increase the complexity of the cryptographic devices which already need to perform computationally-intensive operations. Therefore, the general-purpose processors are usually supported by coprocessors/hardware accelerators to protect as well as to accelerate cryptographic applications. Using a configurable processor is just another solution. This work designs and implements robust execution units as an extension to a configurable processor, which detect the data faults (adversarial or otherwise) while performing the arithmetic operations. Assuming a capable adversary who can injects faults to the cryptographic computation with high precision, a nonlinear error detection code with high error detection capability is used. The designed units are tightly integrated to the datapath of the configurable processor using its tool chain. For different configurations, we report the increase in the space and time complexities of the configurable processor. Also, we present performance evaluations of the software implementations using the robust execution units. Implementation results show that it is feasible to implement robust arithmetic units with relatively low overhead in an embedded processor.

Cryptographic algorithms handle sensitive information and their safe execution plays an essential role in many security applications. When implemented in software on general-purpose computers, cryptographic algorithms are vulnerable to a variety of attacks such as side-channel and cold-boot attacks since they either share hardware resources with other simultaneously executing processes or store sensitive information in easily accessible places (e.g. main memory). In this paper, we demonstrate that secure and isolated execution of cryptographic algorithms is possible on a cryptographic unit that can easily be integrated to all RISC processors. The cryptographic unit is capable of physically isolating the execution of cryptographic algorithms from all other simultaneously executing processes. By specifically providing an AES implementation running in this isolated execution environment we demonstrate that it is possible to provide physical process isolation for cryptographic algorithms without any significant overhead in execution time. Furthermore, the proposed technique protects the cryptographic applications against cold-boot and cache attacks as well as any other threats originated from other processes since the sensitive material never leave the cryptographic unit. We realized a RISC-based embedded processor with five-stage pipeline featuring the cryptographic unit on an FPGA device. We included the implementation results both for FPGA and ASIC realizations.

Identity-based encryption (IBE) systems are relatively recently proposed; yet they are highly popular for messaging applications since they offer new features such as certificateless infrastructure and anonymous communication. However, recent studies also reveal that the infrastructure needed for IBE systems may be as complicated as the conventional public key cryptosytems and not sufficient research has been conducted in relevant issues concerning the infrastructure. In this paper, we intended to propose an IBE infrastructure for messaging applications. The proposed infrastructure requires one registration authority and at least one public key generator and they secret share the master secret key. In addition, the PKG also shares the same master secret with each user in the system in a different way. Therefore, the PKG will never be able to learn the private keys of users under non-collusion assumption. Users can also select meaningful pseudonyms and communicate anonymously using them with other users in the system. We discuss different aspects of the proposed infrastructure such as security, key revocation, uniqueness of the identities, and non-repudiation that constitute the main drawbacks of other IBE schemes. We demonstrate that our infrastructure solves many of these drawbacks under certain assumptions. We also provide some implementation results to show the feasibility of the proposed infrastructure.

In the relatively young field of fault tolerant cryptography the main research effort has focused exclusively on the protection of the data-path of cryptographic circuits. To date, however, we have not found any work that aims at protecting the control logic of these circuits against fault attacks, which thus remained as Achilles' proverbial heel. Motivated by an example of a hypothetical attack on an otherwise protected modular exponentiation engine we set out to close this remaining gap. In this paper we present guidelines for the design of t-fault resilient sequential control logic based on Error Detecting Codes (EDC). Our method allows to trade area overhead against fault resilience, and has the added benefit that the detection circuit does not add to the critical path.

A new carry-free Montgomery inversion algorithm which is suitable for hardware implementation is presented. The algorithm utilizes a new redundant sign digit (RSD) representation and arithmetic to avoid carry propagation in addition and subtraction, which are the atomic operations in the Montgomery inversion algorithm. The proposed algorithm is described in such a way that its hardware realization is straightforward. The algorithm enables very fast computation of multiplicative inversion in GF(p), which is the most time-consuming operation in elliptic and hyperelliptic curve cryptography. Complexity analysis and a gate level implementation of the algorithm reveal that the proposed algorithm provides a speedup of at least 1.95 over the original Montgomery inversion algorithm.

WTLS (wireless transport layer security) is an important standard protocol for secure wireless access to Internet services. WTLS employs public-key cryptosystems during the handshake between mobile client and WAP gateway (server). Several cryptosystems at different key strengths can be used in WTLS. The trade-off is security versus processing and transmission time. In this paper, an analytical performance model for public-key cryptosystem operations in WTLS protocol is developed. Different handshake protocols, different cryptosystems and key sizes are considered. Public-key cryptosystems are implemented using state-of-the-art performance improvement techniques, yielding actual performance figures for individual cryptosystems. These figures and the analytical model are used to calculate the cost of using public-key cryptosystems in WTLS. Results for different cryptosystems and handshake protocols are comparatively depicted and interpreted. It has been observed that ECC (elliptic curve cryptography) performs better than its rival RSA cryptosystem in WTLS. Performance of some stronger ECC curves, which are not considered in WTLS standard, is also analyzed. Results showed that some of those curves could be used in WTLS for high security applications with an acceptable degradation in performance.

We describe a method of construction of a composite field representation from a given binary field representation. We derive the conversion (change of basis) matrix. The special case of when the degree of the ground field is relatively prime to the extension degree, where the irreducible polynomial generating the composite field has its coefficients from the binary prime field rather than the ground field, is also treated. Furthermore, certain generalizations of the proposed construction method, e.g., the use of nonprimitive elements and the construction of composite fields with special irreducible polynomials, are also discussed. Finally, we give storage-efficient conversion algorithms between the binary and composite fields when the degree of the ground field is relatively prime to the extension degree.

We modify an algorithm given by Kaliski to compute the Montgomery inverse of an integer modulo a prime number. We also give a new definition of the Montgomery inverse, and introduce efficient algorithms for computing the classical modular inverse, the Kaliski-Montgomery inverse, and the new Montgomery inverse. The proposed algorithms are suitable for software implementations on general-purpose microprocessors.