The proliferation of cryptographic primitives in resource-constrained Internet of Things (IoT) devices has made them prime targets for Side-Channel Analysis (SCA). However, designing effective defenses against these attacks has become increasingly complex, as traditional deep learning approaches rely heavily on extensive profiling datasets that are difficult to obtain in the context of widely distributed and physically restricted IoT environments. This challenge is further exacerbated by countermeasures such as clock jitter and random delays. To overcome this limitation, this paper introduces a novel and data-efficient three-stage framework for generating high-fidelity synthetic side-channel traces. First, we employ a Supervised Variational Autoencoder (S-VAE) to map noisy, high-dimensional raw traces into a compact and denoised latent space, effectively creating an information-rich manifold. Second, a conditional Denoising Diffusion Implicit Model (DDIM), powered by an advanced attention-augmented U-Net, is trained exclusively on this computationally tractable latent space to learn the complex conditional data distribution. Finally, we empirically validate our framework on the public ASCAD benchmark and ChipWhisperer CW308T UFO platform. The results are compelling: an attack model trained solely on our synthetic data successfully recovers the secret key in the most challenging ASCAD_desync100 scenario using only 4107 traces and using only 2560 traces, 97.7% accuracy can be achieved on the Chipwhisphere platform. This work provides a practical and efficient pathway for the robust security evaluation of cryptographic implementations in data-scarce IoT environments, significantly lowering the barrier for thorough side-channel vulnerability analysis.

Accurate sleep staging is essential for assessing sleep quality and diagnosing sleep disorders, yet it heavily depends on large-scale, expertly labeled datasets, which are costly and time-consuming to produce. While existing methods aim to reduce this reliance, they often utilize data from a limited number of subjects, thereby restricting data diversity and hindering model generalization. To address these challenges, we propose SleepAC, a novel model designed to reduce the dependence on extensive manual annotations. It employs an adaptive sample selection strategy that prioritizes informative and diverse samples, starting with simpler ones and gradually adding more complex ones, while incorporating sleep-specific factors., enabling accurate classification with fewer labeled samples. Furthermore, SleepAC integrates a contrastive learning framework that generates hard negative samples across different sleep stages, effectively enhancing the classification of transitional stages, which are particularly difficult due to limited annotations. Experiments on four public datasets demonstrate that SleepAC achieves competitive accuracy and F1-scores, attaining approximately 95% of the fully supervised performance using only 20% of labeled data. These results underscore its effectiveness in low-resource settings, showcasing promising generalization across complex sleep dynamics while significantly reducing annotation costs.

Contactless palmprint recognition has recently emerged as a promising biometric technology. However, traditional methods that require sharing user data introduce substantial security risks. While federated learning offers privacy-preserving solutions, it often compromises recognition accuracy due to feature distribution drift caused by external factors such as lighting and devices. To address this issue, we propose an adaptive personalized federated learning framework (AdaptPFL). The central innovation lies in decomposing palmprint features into identity-related and contextual-related components using a feature decoupling mechanism. This design isolates the influence of external environmental factors on identity recognition through de-entanglement. Furthermore, two adaptive aggregation strategies are introduced to correct client drift: (1) Intra-Local Adaptive Aggregation (ILAA), which addresses intra-client drift by adaptively combining the two decoupled feature types; (2) Global-Local Adaptive Aggregation (GLAA), which corrects inter-client drift by adaptively aggregating model parameters. Experimental results demonstrate that AdaptPFL achieves superior performance compared to existing state-of-the-art methods.

People have a hard time using cloud computing because of rules concerning privacy and security in fields like healthcare and banking. Fully Homomorphic Encryption (FHE) lets computers work with encrypted data, but it puts a lot of burden on them. This paper introduces SMMHE (Secure Matrix Multiplication with FHE), a novel element-wise approach that enhances SIMD parallelism in contemporary FHE frameworks to mitigate costly rotation operations. SMMHE is 3.98× faster than the most common FHE-based multiplication techniques, according to thorough testing. This big speedup, which cuts the difference in performance between encrypted and plaintext computation by a lot, makes it much easier to use privacy-preserving cloud applications in real life, like classifying medical images. For encrypted MNIST classification, the amortized duration of 26 ms per image is an excellent example of this.

Graph Contrastive Learning (GCL) is a powerful self-supervised technique for learning node and graph representations. However, real-world graph data often exhibit imbalanced class distributions, which pose significant challenges to GCL’s effectiveness. Our experiments show that current state-of-the-art (SOTA) methods perform poorly under imbalanced settings. To address this, we propose a novel GCL framework called AIGCL for imbalanced node classification. This framework automatically and adaptively balances the node representations learned by GCL. Specifically, we introduce a new data augmentation method that retains more information from minority class nodes during graph augmentation. Additionally, we use an imbalance rate adaptive sampling strategy to balance the data. We also incorporate a Variational Graph Autoencoder (VGAE) with an encoder–decoder structure to pretrain the data and generate high-quality pseudo-labels. Our experiments demonstrate that under imbalanced settings, our model improves classification accuracy by 4 %-12 % compared to baseline models, significantly enhancing the performance of minority class nodes.

Time Series Classification (TSC) is a fundamental task in data mining and often suffers from class imbalance, particularly in real-world applications. Traditional methods often fail to capture high-order intrinsic dependencies among time series, especially when minority class samples are scarce. Effectively mining such associations to improve minority-class representation remains a significant challenge. To address this issue, we propose ITS2Graph, a graph-based generative adversarial learning framework that exploits high-order associations for imbalanced time series classification. An auto-encoder is employed to extract latent representations of time series, based on which pairwise similarities are computed to construct a graph, thereby reformulating TSC as a node classification task. To mitigate class imbalance, a graph generator synthesizes minority-class node features and their topological connections, while a Graph Convolutional Network (GCN) discriminator is trained to distinguish real from generated nodes. Experimental results on 22 real-world time series datasets demonstrate that ITS2Graph outperforms existing algorithms in imbalanced time series classification tasks.

Cloud computing offers inexpensive and scalable solutions for data processing, however privacy concerns often hinder the outsourcing of sensitive information. Homomorphic encryption provides a promising approach for secure computations over encrypted data. However, existing models often rely on restrictive assumptions, such as semi-honest adversaries and inaccessible public data. To address these limitations, we introduce the Secure Outsourcing Computation Toolkit (SOCT), which is a novel framework based on the threshold ElGamal cryptosystem. The toolkit employs a dual-server decryption architecture using a (2,2) threshold additively homomorphic ElGamal (TAHEG) algorithm. This architecture ensures that ciphertexts can be decrypted only with the cooperation of both servers, mitigating the risk of data breaches. The TAHEG algorithm requires the input of a secret key for every decryption operation, preventing unauthorized access to plaintext data. Moreover, the key generation process does not burden users with generating or distributing partial secret keys. We provide rigorous security proofs for our threshold ElGamal cryptosystem and associated secure computation functions. Experimental results demonstrate that SOCT achieves significant efficiency gains compared to existing toolkits, making it a practical choice for privacy-preserving data outsourcing.

Increasing attention has been paid to code-based post-quantum cryptography (PQC) schemes, e.g., HQC (Hamming Quasi-Cyclic) and BIKE (Bit Flipping Key Encapsulation), since they’ve been selected as the fourth-round National Institute of Standards and Technology (NIST) PQC standardization candidates. Though sparse polynomial multiplication is one of the critical components for HQC and BIKE, hardware-implemented high-performance sparse polynomial multiplier is rarely reported in the literature (due to its high-dimension and sparsity of polynomials involved in the computation). Based on this consideration, in this article, we propose two novel H igh-throughput S parse P olynomial multiplication A ccelerators (HSPA) for the mentioned two code-based PQC schemes. Specifically, we have designed the two accelerators based on two different implementation strategies targeting potential applications with different resource availability, i.e., one accelerator deploys a memory-based structure for computation while the other does not need memory usage. We have proposed three layers of coherent interdependent efforts to obtain the proposed accelerators. First, we have proposed two implementation strategies to execute the targeted sparse polynomial multiplication, i.e., a new parallel segment based accumulation (PSA) approach and a novel permutating-with-power (PWP)-based method. Then, the proposed two hardware accelerators are presented with detailed structural descriptions. Finally, field-programmable gate array (FPGA)-based implementation is presented to showcase the superior performance of the proposed accelerators. A proper comparison is also carried out to confirm the efficiency of the proposed designs. For instance, the proposed accelerator (using memory-based structure) has 56.84% and 80.25% less area-delay product (ADP) than the existing memory-based design (an extended high-speed version) on the UltraScale+ device, respectively, for n =17,669 and ω =75 (HQC) and n = 12,323 and ω =142 (BIKE). The proposed design strategy fits well with the two targeted code-based PQC schemes, which can be extended further to construct high-performance hardware cryptoprocessors. We hope the results of this work will be useful for the ongoing NIST PQC standardization process.

Post-quantum cryptography (PQC) has drawn significant attention from the hardware design research community. In particular, efficient implementation for major components of PQC algorithms like polynomial multiplication has been a hot topic recently. Following this trend, in this paper, we propose a novel hardware-implemented Lightweight Accelerator for the large integer polynomial MultiPlication (LAMP) used in PQC schemes. Specifically, we target the polynomial multiplications not bound by fixed fast algorithms like Number Theoretic Transform (NTT), i.e., Falcon (one of the National Institute of Standards and Technology (NIST) selected PQC algorithms) and Ring Binary Learning-with-Errors based encryption scheme (RBLWE-ENC, a promising lightweight PQC scheme). Overall, we have carried out three layers of innovative efforts. (i) A new lightweight computation strategy for the targeted polynomial multiplication is proposed; (ii) The new accelerator is then designed based on the proposed algorithm (applicable for both targeted schemes); (iii) A thorough evaluation process is carried out to showcase the superior performance of the proposed accelerator over the competing designs, e.g., at least 21.2% less area-delay product (ADP) when LAMP is used for RBLWE-ENC (on Virtex-7 device). The proposed work is efficient and interesting, and we hope this outcome can facilitate PQC development.

In 2022, the National Institute of Standards and Technology (NIST) made an announcement regarding the standardization of Post-Quantum Cryptography (PQC) candidates. Out of all the Key Encapsulation Mechanism (KEM) schemes, the CRYSTAL-Kyber emerged as the sole winner. This paper presents another improved version of Plantard arithmetic that could speed up Kyber implementations on two low-end 32-bit IoT platforms (ARM Cortex-M3 and RISC-V) without SIMD extensions. Specifically, we further enlarge the input range of the Plantard arithmetic without modifying its computation steps. After tailoring the Plantard arithmetic for Kyber’s modulus, we show that the input range of the Plantard multiplication by a constant is at least 2.14× larger than the original design in TCHES2022. Then, two optimization techniques for efficient Plantard arithmetic on Cortex-M3 and RISC-V are presented.We show that the Plantard arithmetic supersedes both Montgomery and Barrett arithmetic on low-end 32-bit platforms. With the enlarged input range and the efficient implementation of the Plantard arithmetic on these platforms, we propose various optimization strategies for NTT/INTT. We minimize or entirely eliminate the modular reduction of coefficients in NTT/INTT by taking advantage of the larger input range of the proposed Plantard arithmetic on low-end 32-bit platforms. Furthermore, we propose two memory optimization strategies that reduce 23.50%~28.31% stack usage for the speed-version Kyber implementation when compared to its counterpart on Cortex-M4. The proposed optimizations make the speed-version implementation more feasible on low-end IoT devices. Thanks to the aforementioned optimizations, our NTT/INTT implementation shows considerable speedups compared to the state-of-the-art work. Overall, we demonstrate the applicability of the speed-version Kyber implementation on memory-constrained IoT platforms and set new speed records for Kyber on these platforms.

CRYSTALS-Dilithium is a lattice-based post-quantum digital signature scheme that is resistant to attacks by quantum computers and has been selected to be standardized in the NIST post-quantum cryptography (PQC) standardization process. However, the speed performance and design flexibility of the Dilithium still need to be evaluated. This article presents a high-performance software/hardware co-design of CRYSTALS-Dilithium based on the NIST PQC round-3 parameters. High-speed pipelined hardware modules for NTT/INTT, point-wise multiplication/addition, and for SHAKE are included in the design to accelerate the time-consuming operations in Dilithium. All hardware modules are parameterized, thus allowing full support of runtime configuration to increase versatility. Moreover, the proposed software/hardware architecture and tight operating workflows reduce the data transmission overhead between the processor and other hardware modules. The hardware accelerator is implemented with a reconfigurable logic on FPGA and is integrated with the high-performance ARM Cortex-A9 processor in the Xilinx Zynq Architecture. We measure the performance of the software/hardware system for Dilithium in NIST security levels 2, 3, and 5. Compared to pure software implementations, we achieve 8.7–12.5 times speedup in Key generation, 6.3–7.3 times speedup in Sign, and 9.1–12.2 times speedup in Verify operations.

The Hamming quasi-cyclic (HQC) code-based encryption scheme is one of the fourth-round algorithms selected by the National Institute of Standards and Technology (NIST) postquantum cryptography (PQC) standardization process. However, very few hardware implementations have been reported for HQC to date. In this brief, we propose a novel Lightweight and Efficient Accelerator for sparse Polynomial multiplication (LEAP) of HQC, compatible with different parameters, on the field-programmable gate array (FPGA) platform. First, we give a mathematical derivation process for the sparse polynomial multiplication deployed in HQC. Then, we explain the proposed hardware structure in detail. Finally, we present the FPGA implementation results to confirm the efficiency of the proposed LEAP, for example, the proposed design for hqc-192 has at least 31.03% less area-delay product (ADP) than the existing design. LEAP can be extended further to construct efficient HQC cryptoprocessors.

Early neural network architectures were designed by so-called "grad student descent". Since then, the field of Neural Architecture Search (NAS) has developed with the goal of algorithmically designing architectures tailored for a dataset of interest. Recently, gradient-based NAS approaches have been created to rapidly perform the search. Gradient-based approaches impose more structure on the search, compared to alternative NAS methods, enabling faster search phase optimization. In the real-world, neural architecture performance is measured by more than just high accuracy. There is increasing need for efficient neural architectures, where resources such as model size or latency must also be considered. Gradient-based NAS is also suitable for such multi-objective optimization. In this work, we extend a popular gradient-based NAS method to support one or more resource costs. We then perform in-depth analysis on the discovery of architectures satisfying single-resource constraints for classification of CIFAR-10.

Deep neural networks (DNN) now outperform competing methods in many academic and industrial domains. These high-capacity universal function approximators have recently been leveraged by deep reinforcement learning (RL) algorithms to obtain impressive results for many control and decision making problems. During the past three years, research toward pruning, quantization, and compression of DNNs has reduced the mathematical, and therefore time and energy, requirements of DNN-based inference. For example, DNN optimization techniques have been developed which reduce storage requirements of VGG-16 from 552MB to 11.3MB, while maintaining the full-model accuracy for image classification. Building from DNN optimization results, the computer architecture community is taking increasing interest in exploring DNN hardware accelerator designs. Based on recent deep RL performance, we expect hardware designers to begin considering architectures appropriate for accelerating these algorithms too. However, it is currently unknown how, when, or if the “noise” introduced by DNN optimization techniques will degrade deep RL performance. This work measures these impacts, using standard OpenAI Gym benchmarks. Our results show that mathematically optimized RL policies can perform equally to full-precision RL, while requiring substantially less computation. We also observe that different optimizations are better suited than others for different problem domains. By beginning to understand the impacts of mathematical optimizations on RL policy performance, this work serves as a starting point toward the development of low power or high performance deep RL accelerators.

Modular multiplication forms the basis of many cryptographic functions such as RSA, Diffie-Hellman key exchange, and ElGamal encryption. For large RSA moduli, combining the fast Fourier transform (FFT) with McLaughlin's Montgomery modular multiplication (MLM) has been validated to offer cost-effective implementation results. However, the conditional selections in McLaughlin's algorithm are considered to be inefficient and vulnerable to timing attacks, since extra long additions or subtractions may take place and the running time of MLM varies. In this work, we restrict the parameters of MLM by a set of new bounds and present a modified MLM algorithm involving no conditional selection. Compared to the original MLM algorithm, we inhibit extra operations caused by the conditional selections and accomplish constant running time for modular multiplications with different inputs. As a result, we improve both area-time efficiency and security against timing attacks. Based on the proposed algorithm, efficient FFT-based modular multiplication and exponentiation are derived. Exponentiation architectures with dual FFT-based multipliers are designed obtaining area-latency efficient solutions. The results show that our work offers a better efficiency compared to the state-of-the-art works from and above 2048-bit operand sizes. For single FFT-based modular multiplication, we have achieved constant running time and obtained area-latency efficiency improvements up to 24.3 percent for 1,024-bit and 35.5 percent for 4,096-bit operands, respectively.

The papers in this special section examine the impact of cryptographic engineering in a post-quantum world. The vast majority of public-key cryptosystems currently in use is based on integer factorization and (elliptic curve) discrete logarithm problems, which are believed to be intractable with current computing technology. However, these hard problems can be solved in polynomial time by using Shor’s algorithm (or one of its variants) on a quantum computer. Recent progress towards the development of a largescale, fault-tolerant quantum computer has motivated the interest for post-quantum cryptography (a.k.a. quantum-safe or quantum-resistant cryptography) by governments, enterprises and the cryptography community.

The modular multiplication operation is the most time-consuming operation for number-theoretic cryptographic algorithms involving large integers, such as RSA and Diffie-Hellman. Implementations reveal that more than 75 percent of the time is spent in the modular multiplication function within the RSA for more than 1,024-bit moduli. There are fast multiplier architectures to minimize the delay and increase the throughput using parallelism and pipelining. However such designs are large in terms of area and low in efficiency. In this paper, we integrate the fast Fourier transform (FFT) method into the McLaughlin's framework, and present an improved FFT-based Montgomery modular multiplication (MMM) algorithm achieving high area-time efficiency. Compared to the previous FFT-based designs, we inhibit the zero-padding operation by computing the modular multiplication steps directly using cyclic and nega-cyclic convolutions. Thus, we reduce the convolution length by half. Furthermore, supported by the number-theoretic weighted transform, the FFT algorithm is used to provide fast convolution computation. We also introduce a general method for efficient parameter selection for the proposed algorithm. Architectures with single and double butterfly structures are designed obtaining low area-latency solutions, which we implemented on Xilinx Virtex-6 FPGAs. The results show that our work offers a better area-latency efficiency compared to the state-of-the-art FFT-based MMM architectures from and above 1,024-bit operand sizes. We have obtained area-latency efficiency improvements up to 50.9 percent for 1,024-bit, 41.9 percent for 2,048-bit, 37.8 percent for 4,096-bit and 103.2 percent for 7,680-bit operands. Furthermore, the operating latency is also outperformed with high clock frequency for length-64 transform and above.

On-chip bus implementations must be bug-free and secure to provide the functionality and performance required by modern system-on-a-chip (SoC) designs. Regardless of the specific topology and protocol, bus behavior is never fully specified, meaning there exist cycles/conditions where some bus signals are irrelevant, and ignored by the verification effort. We highlight the susceptibility of current bus implementations to Hardware Trojans hiding in this partially specified behavior, and present a model for creating a covert Trojan communication channel between SoC components for any bus topology and protocol. By only altering existing bus signals during the period where their behaviors are unspecified, the Trojan channel is very difficult to detect. We give Trojan channel circuitry specifics for AMBA AXI4 and advanced peripheral bus (APB), then create a simple system comprised of several master and slave units connected by an AXI4-Lite interconnect to quantify the overhead of the Trojan channel and illustrate the ability of our Trojans to evade a suite of protocol compliance checking assertions from ARM. We also create an SoC design running a multiuser Linux OS to demonstrate how a Trojan communication channel can allow an unprivileged user access to root-user data. We then outline several detection strategies for this class of Hardware Trojan.

A wide variety of mixed digital-physical (cyber-physical) systems with complex and often loosely defined components are now deployed, whose behavior affect our daily lives in significant and sometimes critical ways. Cyber-physical systems (CPS) can provide much richer functionality, efficiency, autonomy, and reliability than manually controlled and loosely coupled systems. However, they also create inherent vulnerability related to privacy, security, robustness, and reliability of the underlying components and as a whole system. The mixed digital-physical aspect of such systems opens new and, as-of-yet, lightly explored opportunities for hybrid design, modeling, and analysis. Robust and safe systems must be designed and deployed to meet operational and security challenges. Additionally, the continuous-time nature of the physical components of these systems implies a fit for certain high-performance, low-power analog computing solutions. Here we survey existing efforts related to such risks and opportunities. We also tie the topics together and provide guidance to other researchers interested in exploring the hybrid aspects of mixed digital-physical systems.

Reconfigurable platforms such as FPGAs and CPLDs are used to implement flexible and lightweight embedded systems often using soft-processors and a fixed instruction sequence stored in block memories. The bitstream format is proprietary for most vendors, however, in this work we demonstrate how to identify and extract block memory contents within the bitstream, allowing an adversary to learn and possibly modify the fixed instruction sequence. Manipulating the instruction sequence by inserting a Trojan in the bitstream as opposed to in the RTL code allows an adversary to bypass many verification steps. Moreover, the proposed Trojans only add extra instructions to the sequence to leak secret information, and do not change the original program behavior, making them virtually impossible to detect using functional tests. We present a case study where a Trojan is injected into a MIPS AES encryption program to leak internal state information by adding extra instructions from the available ones without changing the original program behavior.

Modular multiplication is the core operation in public-key cryptographic algorithms such as RSA and the Diffie-Hellman algorithm. The efficiency of the modular multiplier plays a crucial role in the performance of these cryptographic methods. In this paper, improvements to FFT-based Montgomery Modular Multiplication (FFTM3) using carry-save arithmetic and pre-computation techniques are presented. Moreover, pseudo-Fermat number transform is used to enrich the supported operand sizes for the FFTM3. The asymptotic complexity of our method is O(l log l log log l), which is the same as the Schonhage-Strassen multiplication algorithm (SSA). A systematic procedure to select suitable parameter set for the FFTM3is provided. Prototypes of the improved FFTM3multiplier with appropriate parameter sets are implemented on Xilinx Virtex-6 FPGA. Our method can perform 3,100-bit and 4,124-bit modular multiplications in 6.74 and 7.78 μs, respectively. It offers better computation latency and area-latency product compared to the state-of-the-art methods for operand size of 3,072-bit and above.

We introduce a matrix decomposition method and prove that multiplication in GF$(2^k)$with a Type 1 optimal normal basis for can be performed using$k^2-1$XOR gates irrespective of the choice of the irreducible polynomial generating the field. The previous results achieved this bound only with special irreducible polynomials. Furthermore, the decomposition method performs the multiplication operation using$1.5k(k-1)$XOR gates for Type 2a and 2b optimal normal bases, which matches previous bounds.

The Schönhage-Strassen Algorithm (SSA) is an asymptotically fast multiplication algorithm with the complexity of O(l log l log log l) where l is the operand size. It outperforms other multiplication algorithms when l is large enough. One possible usage of such long integer multiplication is for cryptography. Innovated from SSA, the Interleaved Spectral Montgomery Modular Multiplication (ISM3) algorithm is proposed to accelerate the modular multiplication. ISM3 algorithm primarily interleaves the Montgomery modular multiplication algorithm between time and spectral (frequency) domain. We show that the tasks in each step of the proposed algorithm have little data dependency, and hence, extremely suitable for hardware implementation. We present the parallel ISM3architecture and implement it on Xilinx Virtex-II and Virtex-6 FPGAs. Experimental results show that our 3838-bit ISM3 is faster than the previous Montgomery multiplier. Moreover, our design can complete a 7678-bit modular multiplication in 3398 cycles in 17.98 μs on a Virtex-6 device.

As an important component of Spectral Modular Arithmetic (SMA) cryptographic co-processor, the efficient architectures of Number Theoretic Transforms (NTTs) on FPGA are discussed in this paper. We analyze characteristics of the NTTs for cryptographic applications, compare different arithmetic approaches, introduce an optimized solution for FPGA implementation, and developed several different architectures. Qualitative and quantitative analyses are provided to show the effectiveness of our proposed architectures.

A method for polynomial multiplication over finite fields using field extensions and polynomial interpolation is introduced. The proposed method uses polynomial interpolation as Toom-Cook method together with field extensions. Furthermore, the proposed method can be used when Toom-Cook method cannot be applied directly. Explicit formulae improving the previous results in many cases are obtained.

The spectral hash algorithm is one of the round 1 candidates for the SHA-3 family, and is based on spectral arithmetic over a finite field, involving multidimensional discrete Fourier transformations over a finite field, data dependent permutations, rubic-type rotations, and affine and nonlinear functions. The underlying mathematical structures and operations pose interesting and challenging tasks for computer architects and hardware designers to create fast, efficient, and compact ASIC and FPGA realizations. In this paper, we present an efficient hardware architecture for the full 512-bit hash computation using the spectral hash algorithm. We have created a pipelined implementation on a Xilinx Virtex-4 XC4VLX200-11 FPGA which yields 100 MHz and occupies 38,328 slices, generating a throughput of 51.2 Gbps. Our fully parallel synthesized implementation shows that the spectral hash algorithm is about 100 times faster than the fastest SHA-1 implementation, while requiring only about 13 times as many logic slices.

We describe a new method to perform the modular exponentiation operation, i.e., the computation of c = memod n, where c, m, e and n are large integers. The new method uses the discrete Fourier transform over a finite ring, and relies on new techniques to perform multiplication and reduction operations. The method yields efficient and highly parallel architectures for hardware realizations of public-key cryptosystems requiring the modular exponentiation as the core computation, such as the RSA and Diffie-Hellman algorithms.

Since the remarkable work of Kocher [7], several papers considering different types of timing attacks have been published. In 2003, Brumley and Boneh presented a timing attack on unprotected OpenSSL implementations [2]. In this paper, we improve the efficiency of their attack by a factor of more than 10. We exploit the timing behavior of Montgomery multiplications in the table initialization phase, which allows us to increase the number of multiplications that provide useful information to reveal one of the prime factors of RSA moduli. We also present other improvements, which can be applied to the attack in [2].

It is widely recognized that data security will play a central role in future IT systems. Providing public-key cryptographic primitives, which are the core tools for security, is often difficult on embedded processor due to computational, memory, and power constraints. This contribution appears to be the first thorough comparison of two public-key families, namely elliptic curve (ECC) and hyperelliptic curve cryptosystems on a wide range of embedded processor types (ARM, ColdFire, PowerPC). We investigated the influence of the processor type, resources, and architecture regarding throughput. Further, we improved previously known HECC algorithms resulting in a more efficient arithmetic.

Certification is a common mechanism for authentic public key distribution. In order to obtain a public key, verifiers need to extract a certificate path from a network of certificates, which is called public key infrastructure (PKI), and verify the certificates on this path recursively. This is classical methodology. Nested certification is a novel methodology for efficient certificate path verification. Basic idea is to issue special certificates (called nested certificates) for other certificates. Nested certificates can be used together with classical certificates in PKIs. Such a PKI, which is called nested certificate-based PKI (NPKI), is proposed in this paper as an alternative to classical PKI. The concept of "certificates for other certificates" results in nested certificate paths in which the first certificate is verified cryptographically while others are verified by just fast hash computations. Thus, we can employ efficiently verifiable nested certificate paths instead of classical certificate paths. NPKI is a dynamic system and involves several authorities in order to add a new user to the system. This uses the authorities' idle time to the benefit of the verifiers. We formulate the trade-off between the nested certification overhead and the time improvement on certificate path verification. This trade-off is numerically analyzed for a 4-level 20-ary balanced tree-shaped PKI and it has been shown that the extra cost of nested certification is in acceptable limits in order to generate quickly verifiable certificate paths for certain applications. Moreover, PKI-to-NPKI transition preserves the existing hierarchy and trust relationships in the PKI, so that it can be used for PKIs with fixed topology. Although there are many certificates in NPKI, certificate revocation is no more of a problem than with classical PKIs. NPKI even has an advantage on the number of certificate revocation controls: at most two certificate revocation controls are sufficient independent of the path length. Nested certificates can be easily adopted into X.509 standard certificate structure. Both verification efficiency and revocation advantage of NPKI and nested certificates make them suitable for hierarchical PKIs of wireless applications where wireless end users have limited processing power.

We propose a new algorithm for fast multiplication of large integers having a precision of 1k computer words, where k is an integer. The algorithm is derived from the Karatsuba-Ofman Algorithm and has the same asymptotic complexity. However, the running time of the new algorithm is slightly better, and it makes one third as many recursive calls.

The state-of-the-art Galois field GF(2/sup m/) multipliers offer advantageous space and time complexities when the field is generated by so special irreducible polynomial. To date, the best complexity results have been obtained when the irreducible polynomial is either a trinomial or an equally spaced polynomial (ESP). Unfortunately, there exist only a few irreducible ESPs in the range of interest for most of the applications, e.g., error-correcting codes, computer algebra, and elliptic curve cryptography. Furthermore, it is not always possible to find an irreducible trinomial of degree m in this range. For those cases where neither an irreducible trinomial nor an irreducible ESP exists, the use of irreducible pentanomials has been suggested. Irreducible pentanomials are abundant, and there are several eligible candidates for a given m. We promote the use of two special types of irreducible pentanomials. We propose new Mastrovito and dual basis multiplier architectures based on these special irreducible pentanomials and give rigorous analyses of their space and time complexity.

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.

This paper presents a scalable architecture for the computation of modular multiplication, based on the Montgomery multiplication (MM) algorithm. A word-based version of MM is presented and used to explain the main concepts in the hardware design. The proposed multiplier is able to work with any precision of the input operands, limited only by memory or control constraints. Its architecture gives enough freedom to select the word size and the degree of parallelism to be used, according to the available area and/or desired performance. Design trade offs are analyzed in order to identify adequate hardware configurations for a given area or bandwidth requirement.

The security of electronic payment protocols is of interest to researchers in academia and industry. While the ultimate objective is the safest and most secure protocol, convenience and usability should not be ignored, or the protocol may not be suitable for large-scale deployment. Our aim is to design a practical electronic payment protocol which is both secure and convenient. ANSI X9.59 standard describes secure payment objects to be used in electronic payment in a convenient and secure way. It has many useful convenience features for large-scale consumer market deployment, the best being the elimination of consumer certificates. Consumer public keys are stored in account records at financial institutions; the digital signatures issued by consumers are verified by financial institutions. Encryption is deliberately not provided by X9.59. We propose a new Internet e-payment protocol, namely CONSEPP (CONvenient and Secure E-Payment Protocol), based on the account authority model of ANSI X9.59 standard. CONSEPP is the specialized version of X9.59 for Internet transactions (X9.59 is multi-purpose). It has some extra features on top of the X9.59 standard. X9.59 requires merchant certificates; in CONSEPP we propose a lightweight method to avoid the need for merchant certificates. Moreover, we propose a simple method for secure shopping experience between merchant and consumer. Merchant authentication is embedded in the payment cycle. CONSEPP aims to use current financial transaction networks, like VisaNet, BankNet and ACH networks, for communications among financial institutions. No certificates (in the classical sense) or certificate authorities exist in CONSEPP. Convenience is not traded for security; basic security requirements are fulfilled in the payment authorization cycle without extra messaging and significant overhead.

This paper presents a new parallel multiplier for the Galois field GF(2/sup m/) whose elements are represented using the optimal normal basis of type II. The proposed multiplier requires 1.5(m/sup 2/-m) XOR gates, as compared to 2(m/sup 2/-m) XOR gates required by the Massey-Omura multiplier. The time complexities of the proposed and the Massey-Omura multipliers are similar.

We present the results of our implementation of elliptic curve cryptography (ECC) over the field GF(p) on an 80-MHz, 32-bit ARM microprocessor. We have produced a practical software library which supports variable length implementation of the elliptic curve digital signature algorithm (ECDSA). We implemented the ECDSA and a recently proposed ECC-based wireless authentication protocol using the library. Our timing results show that the 160-bit ECDSA signature generation and verification operations take around 46 ms and 94 ms, respectively. With these timings, the execution of the ECC-based wireless authentication protocol takes around 140 ms on the ARM7TDMI processor, which is a widely, used, low-power core processor for wireless applications.

We present a new formulation of the Mastrovito multiplication matrix for the field GF(2/sup m/) generated by an arbitrary irreducible polynomial. We study in detail several specific types of irreducible polynomials, e.g., trinomials, all-one-polynomials, and equally-spaced-polynomials, and obtain the time and space complexity of these designs. Particular examples illustrating the properties of the proposed architecture are also given. The complexity results established in this paper match the best complexity results known to date. The most important new result is the space complexity of the Mastrovito multiplier for an equally-spaced-polynomial, which is found as (m/sup 2/-/spl Delta/) XOR gates and m/sup 2/ AND gates, where /spl Delta/ is the spacing factor.

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.

An efficient algorithm for the multiplication in GF(2/sup m/) was introduced by Mastrovito. The space complexity of the Mastrovito multiplier for the irreducible trinomial x/sup m/+x+1 was given as m/sup 2/-1 XOR and m/sup 2/ AND gales. In this paper, we describe an architecture based on a new formulation of the multiplication matrix and show that the Mastrovito multiplier for the generating trinomial x/sup m/+x/sup n/+1, where m/spl ne/2n, also requires m/sup 2/-1 XOR and m/sup 2/ AND gates, However, m/sup 2/-x/sup m/2/ XOR gates are sufficient when the generating trinomial is of the form x/sup m/+x/sup m/2/+1 for an even m. We also calculate the time complexity of the proposed Mastrovito multiplier and give design examples for the irreducible trinomials x/sup 7/+x/sup 4/+1 and x/sup 6/+x/sup 3/+1.

We present a new low-complexity bit-parallel canonical basis multiplier for the field GF(2m) generated by an all-one-polynomial. The proposed canonical basis multiplier requires m/sup 2/-1 XOR gates and m/sup 2/ AND gates. We also extend this canonical basis multiplier to obtain a new bit-parallel normal basis multiplier.

The authors present a new algorithm for computing a/sup e/ where a/spl isin/GF(2/sup k/) and e is a positive integer. The proposed algorithm is more suitable for implementation in software, and relies on the Montgomery multiplication in GF(2/sup k/). The speed of the exponentiation algorithm largely depends on the availability of a fast method for multiplying two polynomials of length w defined over GF(2). The theoretical analysis and experiments indicate that the proposed exponentiation method is at least 6 times faster than the exponentiation method using the standard multiplication when w=8. Furthermore, the availability of a 32-bit GF(2) polynomial multiplication instruction on the underlying processor would make the new exponentiation algorithm up to 37 times faster.

The commenter indicates that in the above-mentioned paper (see ibid., vol.5, no.5, p.569-82 (1989)) the proposed pipelined array architecture for the mixed-radix conversion problem is not as efficient and suitable for VLSI implementation as claimed. The commenter identifies the shortcomings of the design and then gives an efficient systolic/wavefront array that requires fewer hardware resources. The authors reply that this is another valid design for the mixed-radix conversion problem that avoids broadcasting; however, the triangular array of buffers is still required in the design for the data-format conversion, and this problem is not addressed. Since a semisystolic design was not given, the comparison between the original design and the semisystolic design in terms of buffers is premature.>

The authors present several time-optimal and space-time-optimal systolic arrays for computing a process dependence graph corresponding to the mixed-radix conversion algorithm. The arrays are particularly suitable for software implementations of algorithms from the applications of residue number systems on a programmable systolic/wavefront array. Examples of such applications are the exact solution of linear systems and matrix problems over integral domains. The authors also describe a decomposition strategy for treating a mixed-radix conversion problem whose size exceeds the array size.>

An algorithm based on a partitioning of the coefficient matrix when the mixed-radix conversion problem is cast as a set of linear congruent equations is presented. The algorithm partitions the moduli set into disjoint subsets such that the product of the moduli in each subset is less than the largest integer representable by the computer. It is shown that, with this partitioning strategy, mixed-radix representation of a residue number can be computed using less than O(n/sup 2/) arithmetic steps where n is the cardinality of the moduli set. It is also shown that if a good partitioning exists, then the algorithm requires only O(n/sup 1.5/) arithmetic steps. The algorithm is particularly suitable for single processor implementation of algorithms from the residue number system applications.>

An inherent problem in the use of simulators for the determination of capacitance in VLSI circuits is the verification of the reliability of the simulation. The problem is due to the numerical approximations made in order to achieve a versatile simulation. The Schwarz-Christoffel transformation provides theoretically exact simulation of a limited class of problems consisting of two odd shaped conductors embedded in a uniform dielectric. It is proposed that the Schwarz-Christoffel technique can be used to calibrate simulators designed for more general problems.>

The architecture and implementation of a novel VLSI bit-level systolic Vector Quantization processor is described. This architecture offers very high data throughput for real-time processing applications. Given a codebook of sizeNand dimensionk, an input vector can be quantized everyNclock cycles, compared to O(kN) cycles for a Single-Instruction, Single-Data (SISD) machine. Any distortion measure which can be expressed as a Euclidean vector inner product can be computed with this array.