Biblio

As one of the most expensive computations in public-key cryptosystems, modular exponentiation is typically out-sourced to the cloud servers. Traditional cloud-based outsourcing algorithms depend on multiple untrusted servers to guarantee the security, which may lead to vulnerability to the collusion attack. Although recent single-server multiple-requests outsourcing algorithms are more secure, they have to perform multiple requests to the single untrusted server to guarantee the security and checkability of the data, which will incur unacceptable latency and local computational costs. In comparison, the edge computing paradigm enhances security since it has multiple computational nodes, including some highly secure local computational nodes. In this paper, we propose the secure outsourcing algorithm of modular exponentiation for the edge computing paradigm. To address the dilemma that the computational resources of different nodes vary significantly, we design two lightweight algorithms to adaptively separate the modular exponentiation to the nodes based on the computational resources. To guarantee the outsourcing checkability, we propose a protocol verify the result returned from each node. We formally prove the security and checkability of our algorithm and validate the efficiency of our algorithm based on experiments and case studies.

This paper discusses and demonstrates the construction of a quantum modular exponentiation circuit in the Qiskit simulator for use in Shor's Algorithm for integer factorization problem (IFP), which is deemed to be able to crack RSA cryptosystems when a large-qubit quantum computer exists. We base our implementation on Vedral, Barenco, and Ekert (VBE) proposal of quantum modular exponentiation, one of the firsts to explicitly provide the aforementioned circuit. Furthermore, we present an example simulation of how to construct a 7xmod 15 circuit in a step-by-step manner, giving clear and detailed information and consideration that currently not provided in the existing literature, and present the whole circuit for use in Shor's Algorithm. Our present simulation shows that the 4-bit VBE quantum modular exponentiation circuit can be constructed, simulated, and measured in Qiskit, while the Shor's Algorithm incorporating this VBE approach itself can be constructed but not yet simulated due to an overly large number of QASM instructions.

This paper presents the implementation of the ELGamal cryptoalgorithm for information flows encryption / decryption, which is based on the application of the vector-modular method of modular exponentiation and multiplication. This allows us to replace the complex operation of the modular exponentiation with multiplication and the last one with addition that increases the speed of the cryptosystem. In accordance with this, the application of the vector-modular method allows us to reduce the modular exponentiation and multiplication temporal complexity in comparison with the classical one.

This research aims to implement different modular exponentiation algorithms and evaluate the average complexity and compare it to the theoretical value. We use the library GMP to implement seven modular exponentiation algorithms. They are Left-to-right Square and Multiply, Right-to-left Square and Multiply, Left-to-right Signed Digit Square, and Multiply Left-to-right Square and Multiply Always Right-to-left Square and Multiply Always, Montgomery Ladder and Joye Ladder. For some exponent bit length, we choose 1024 bits and execute each algorithm on many exponent values and count the average numbers of squares and the average number of multiplications. Whenever relevant, our programs will check the consistency relations between the registers at the end of the exponentiation.

This paper presents an analysis of Rabin-P encryption scheme on microprocessor platform in term of runtime and energy consumption. A microprocessor is one of the devices utilized in the Internet of Things (IoT) structure. Therefore, in this work, the microprocessor selected is the Raspberry Pi that is powered with a smaller version of the Linux operating system for embedded devices, the Raspbian OS. A comparative analysis is then conducted for Rabin-p and RSA-OAEP cryptosystem in the Raspberry Pi setup. A conclusion can be made that Rabin-p performs faster in comparison to the RSA-OAEP cryptosystem in the microprocessor platform. Rabin-p can improve decryption efficiency by using only one modular exponentiation while produces a unique message after the decryption process.

Public key cryptographic primitive (e.g., the famous Diffie-Hellman key agreement, or public key encryption) has recently been used as a standard building block in authenticated key agreement (AKA) constructions for wireless sensor networks (WSNs) to provide perfect forward secrecy (PFS), where the expensive cryptographic operation (i.e., exponentiation calculation) is involved. However, realizing such complex computation on resource-constrained wireless sensors is inefficient and even impossible on some devices. In this work, we introduce a new AKA scheme with PFS for WSNs without using any public key cryptographic primitive. To achieve PFS, we rely on a new dynamic one-time authentication credential that is regularly updated in each session. In particular, each value of the authentication credential is wisely associated with at most one session key that enables us to fulfill the security goal of PFS. Furthermore, the proposed scheme enables the principals to identify whether they have been impersonated previously. We highlight that our scheme can be very efficiently implemented on sensors since only hash function and XOR operation are required.

To increase computation throughput, general purpose Graphics Processing Units (GPUs) have been leveraged to accelerate computationally intensive workloads. GPUs have been used as cryptographic engines, improving encryption/decryption throughput and leveraging the GPU's Single Instruction Multiple Thread (SIMT) model. RSA is a widely used public-key cipher and has been ported onto GPUs for signing and decrypting large files. Although performance has been significantly improved, the security of RSA on GPUs is vulnerable to side-channel timing attacks and is an exposure overlooked in previous studies. GPUs tend to be naturally resilient to side-channel attacks, given that they execute a large number of concurrent threads, performing many RSA operations on different data in parallel. Given the degree of parallel execution on a GPU, there will be a significant amount of noise introduced into the timing channel given the thousands of concurrent threads executing concurrently. In this work, we build a timing model to capture the parallel characteristics of an RSA public-key cipher implemented on a GPU. We consider optimizations that include using Montgomery multiplication and sliding-window exponentiation to implement cryptographic operations. Our timing model considers the challenges of parallel execution, complications that do not occur in single-threaded computing platforms. Based on our timing model, we launch successful timing attacks on RSA running on a GPU, extracting the private key of RSA. We also present an effective error detection and correction mechanism. Our results demonstrate that GPU acceleration of RSA is vulnerable to side-channel timing attacks. We propose several countermeasures to defend against this class of attacks.

Modular exponentiation of large number is widely applied in public-key cryptosystem, also the bottleneck in the computation of public-key algorithm. Modular multiplication is the key calculation in modular exponentiation. An improved Montgomery algorithm is utilized to achieve modular multiplication and converted into systolic array to increase the running frequency. A high efficiency fast modular exponentiation structure is developed to bring the best out of the modular multiplication module and enhance the ability of defending timing attacks and power attacks. For 1024-bit key operands, the design can be run at 170MHz and finish a modular exponentiation in 4,402,374 clock cycles.

Network coding has been proposed to be built into Named Data Networking (NDN) for achieving efficient simultaneous content delivery. Network coding allows intermediate nodes to perform arbitrary coding operations on Data packets. One salient feature of NDN is its content-based security by protecting each Data packet with a signature signed by its publisher. However, in the network coding-based NDN, it remains unclear how to securely and efficiently sign a recoded Data packet at an intermediate router. This work proposes a mechanism to enable linearly homomorphic signatures in network coding-based NDN so as to directly generate a signature for a recoded Data packet by combining the signatures of those Data packets on which the recoding operation is performed.

We study the problem of developing efficient approaches for proving worst-case bounds of non-deterministic recursive programs. Ranking functions are sound and complete for proving termination and worst-case bounds of non-recursive programs. First, we apply ranking functions to recursion, resulting in measure functions. We show that measure functions provide a sound and complete approach to prove worst-case bounds of non-deterministic recursive programs. Our second contribution is the synthesis of measure functions in non-polynomial forms. We show that non-polynomial measure functions with logarithm and exponentiation can be synthesized through abstraction of logarithmic or exponentiation terms, Farkas Lemma, and Handelman's Theorem using linear programming. While previous methods obtain polynomial worst-case bounds, our approach can synthesize bounds of various forms including O(n log n) and O(nr), where r is not an integer. We present experimental results to demonstrate that our approach can efficiently obtain worst-case bounds of classical recursive algorithms such as (i) Merge sort, Heap sort, and the divide-and-conquer algorithm for the Closest Pair problem, where we obtain O(n log n) worst-case bound, and (ii) Karatsuba's algorithm for polynomial multiplication and Strassen's algorithm for matrix multiplication, for which we obtain O(nr) bounds such that r is not an integer and is close to the best-known bound for the respective algorithm. Besides the ability to synthesize non-polynomial bounds, we also show that our approach is equally capable of obtaining polynomial worst-case bounds for classical programs such as Quick sort and the dynamic programming algorithm for computing Fibonacci numbers.

Resource constrained devices such as sensors and RFIDs are utilized in many application areas to sense, store and transmit the sensitive data. This data must be encrypted to achieve confidentiality. The implementation of traditional public key encryption (PKE) techniques by these devices is always challenging as they possess very limited computational resources. Various encryption schemes based on identity-based encryption (IBE) and certificate-less public key encryption (CL-PKE) have been proposed to overcome limitations of PKI. However, many of these schemes involve the computationally expensive exponentiation and bilinear pairing operations on elliptic curve group to encrypt the messages. In this context, we propose a lightweight optimized CL-PKE scheme in which exponentiation and pairing operations are completely eliminated during encryption and only involves computation of cheaper addition and multiplication operations on elliptic curve. Implementation of the proposed scheme confirms its lightweight nature as compared to original CL-PKE scheme.

From signal processing to emerging deep neural networks, a range of applications exhibit intrinsic error resilience. For such applications, approximate computing opens up new possibilities for energy-efficient computing by producing slightly inaccurate results using greatly simplified hardware. Adopting this approach, a variety of basic arithmetic units, such as adders and multipliers, have been effectively redesigned to generate approximate results for many error-resilient applications.In this work, we propose SECO, an approximate exponential function unit (EFU). Exponentiation is a key operation in many signal processing applications and more importantly in spiking neuron models, but its energy-efficient implementation has been inadequately explored. We also introduce a cross-layer design method for SECO to optimize the energy-accuracy trade-off. At the algorithm level, SECO offers runtime scaling between energy efficiency and accuracy based on approximate Taylor expansion, where the error is minimized by optimizing parameters using discrete gradient descent at design time. At the circuit level, our error analysis method efficiently explores the design space to select the energy-accuracy-optimal approximate multiplier at design time. In tandem, the cross-layer design and runtime optimization method are able to generate energy-efficient and accurate approximate EFU designs that are up to 99.7% accurate at a power consumption of 3.73 pJ per exponential operation. SECO is also evaluated on the adaptive exponential integrate-and-fire neuron model, yielding only 0.002% timing error and 0.067% value error compared to the precise neuron model.

The performance of many data security and reliability applications depends on computations in finite fields \$\textbackslashtextGF (2ˆm)\$. In finite field arithmetic, field multiplication is a complex operation and is also used in other operations such as inversion and exponentiation. By considering the application domain needs, a variety of efficient algorithms and architectures are proposed in the literature for field \$\textbackslashtextGF (2ˆm)\$ multiplier. With the rapid emergence of Internet of Things (IoT) and Wireless Sensor Networks (WSN), many resource-constrained devices such as IoT edge devices and WSN end nodes came into existence. The data bus width of these constrained devices is typically smaller. Digit-level architectures which can make use of the full data bus are suitable for these devices. In this paper, we propose a new fully digit-serial polynomial basis finite field \$\textbackslashtextGF (2ˆm)\$ multiplier where both the operands enter the architecture concurrently at digit-level. Though there are many digit-level multipliers available for polynomial basis multiplication in the literature, it is for the first time to propose a fully digit-serial polynomial basis multiplier. The proposed multiplication scheme is based on the multiplication scheme presented in the literature for a redundant basis multiplication. The proposed polynomial basis multiplication results in a high-throughput architecture. This multiplier is applicable for a class of trinomials, and this class of irreducible polynomials is highly desirable for IoT edge devices since it allows the least area and time complexities. The proposed multiplier achieves better throughput when compared with previous digit-level architectures.

A permissioned blockchain platform comes with numerous assurances such as transaction confidentiality and system scalability to several organizations. Most permissioned blockchains rely on a Public-Key Infrastructure (PKI)as cryptographic tools to provide security services such as identity authentication and data confidentiality. Using PKI to validate transactions includes validating digital certificates of endorsement peers which creates an overhead in the system. Because public-key operations are computationally intensive, they limit the scalability of blockchain applications. Due to a large modulus size and expensive modular exponentiation operations, public-key operations such as RSA become slower than polynomial-based schemes, which involve a smaller modulus size and a less smaller number of modular multiplications. For instance, the 2048-bit RSA is approximately 15,728 times slower than a polynomial with a degree of 50 and 128-bit modulus size. In this paper, we propose a lightweight polynomial-based key management scheme in the context of a permissioned blockchain. Our scheme involves computationally less intensive polynomial evaluation operations such as additions and multiplications that result in a faster processing compared with public-key schemes. In addition, our proposed solution reduces the overhead of processing transactions and improves the system scalability. Security and performance analysis are provided in the paper.

In this article, we introduce a new method for computing fixed points of a class of iterated functions in a finite time, by exponentiating linear multivalued operators. To better illustrate this approach and show that our method can give fast and accurate results, we have chosen two well-known applications which are difficult to handle by usual techniques. First, we apply the exponentiation of linear operators to a digital filter in order to get a fine approximation of its behavior at an arbitrary time. Second, we consider a PID controller. To get a reliable estimate of its control function, we apply the exponentiation of a bundle of linear operators. Note that, our technique can be applied in a more general setting, i.e. for any multivalued linear map and that the general method is also introduced in this article.

Methods for implementing integer arithmetic operations of addition, subtraction, and multiplication in the system of residual classes are considered. It is shown that their practical use in computer systems can significantly improve the performance of the implementation of arithmetic operations. A new method has been developed for raising numbers represented in the system of residual classes to an arbitrary power of a natural number, both in positive and in negative number ranges. An example of the implementation of the proposed method for the construction of numbers represented in the system of residual classes for the value of degree k = 2 is given.

This paper shows that stochastic heuristic approach for implicitly solving addition chain problem (ACP) in public-key cryptosystem (PKC) enhances the efficiency of the PKC and improves the security by blinding the multiplications/squaring operations involved against side-channel attack (SCA). We show that while the current practical heuristic approaches being deterministic expose the fixed pattern of the operations, using stochastic method blinds the pattern by being unpredictable and generating diffident pattern of operation for the same exponent at a different time. Thus, if the addition chain (AC) is generated implicitly every time the exponentiation operation is being made, needless for such approaches as padding by insertion of dummy operations and the operation is still totally secured against the SCA. Furthermore, we also show that the stochastic approaches, when carefully designed, further reduces the length of the operation than state-of-the-art practical methods for improving the efficiency. We demonstrated our investigation by implementing RSA cryptosystem using the stochastic approach and the results benchmarked with the existing current methods.

Today's rapid progress in the physical implementation of quantum computers demands scalable synthesis methods to map practical logic designs to quantum architectures. There exist many quantum algorithms which use classical functions with superposition of states. Motivated by recent trends, in this paper, we show the design of quantum circuit to perform modular exponentiation functions using two different approaches. In the design phase, first we generate quantum circuit from a verilog implementation of exponentiation functions using synthesis tools and then apply two different Quantum Error Correction techniques. Finally the circuit is further optimized using the Linear Nearest Neighbor (LNN) Property. We demonstrate the effectiveness of our approach by generating a set of networks for the reversible modular exponentiation function for a set of input values. At the end of the work, we have summarized the obtained results, where a cost analysis over our developed approaches has been made. Experimental results show that depending on the choice of different QECC methods the performance figures can vary by up to 11%, 10%, 8% in T-count, number of qubits, number of gates respectively.

This article will consider the probability test of Solovey-Strassen, to determine the simplicity of the number and its possible modifications. This test allows for the shortest possible time to determine whether the number is prime or not. C\# programming language was used to implement the algorithm in practice.

We conduct formal verification of the divide and conquer key distribution scheme (DC DHKE)-a contributory group key agreement that uses a quasilinear amount of exponentiations with respect to the number of communicating parties. The verification is conducted using both ProVerif and TLA+ as tools. ProVerif is used to verify the protocol correctness as well as its security against passive attacker; while TLA+ is utilized to verify whether all participants in the protocol retrieve the mutual key simultaneously. We also verify the ING and GDH.3 protocol for comparative purposes. The verification results show that the ING, GDH.3, and DC DHKE protocols satisfy the pre-meditated correctness, security, and liveness properties. However, the GDH.3 protocol does not satisfy the liveness property stating that all participants obtain the mutual key at the same time.

In Diffie-Hellman Key Exchange (DHKE), two parties need to communicate to each other by sharing their secret key (cipher text) over an unsecure communication channel. An adversary or cryptanalyst can easily get their secret keys but cannot get the information (plaintext). Brute force is one the common tools used to obtain the secret key, but when the key is too large (etc. 1024 bits and 2048 bits) this tool is no longer suitable. Thus timing attacks have become more attractive in the new cryptographic era where networked embedded systems security present several vulnerabilities such as lower processing power and high deployment scale. Experiments on timing attacks are useful in helping cryptographers make security schemes more resistant. In this work, we timed the computations of the Discrete Log Hard Problem of the Diffie Hellman Key Exchange (DHKE) protocol implemented on an embedded system network and analyzed the timing patterns of 1024-bit and 2048-bit keys that was obtained during the attacks. We have chosen to implement the protocol on the Raspberry-pi board over U-BOOT Bare Metal and we used the GMP bignum library to compute numbers greater than 64 bits on the embedded system.

Now-a-days, the security of data becomes more and more important, people store many personal information in their phones. However, stored information require security and maintain privacy. Encryption algorithm has become the main force of maintaining the security of data. Thus, the algorithm complexity and encryption efficiency have become the main measurement of whether the encryption algorithm is save or not. With the development of hardware, we have many tools to improve the algorithm at present. Because modular exponentiation in RSA algorithm can be divided into several parts mathematically. In this paper, we introduce a conception by dividing the process of encryption and add the model into graphics process unit (GPU). By using GPU's capacity in parallel computing, the core of RSA can be accelerated by using central process unit (CPU) and GPU. Compute unified device architecture (CUDA) is a platform which can combine CPU and GPU together to realize GPU parallel programming and this is the tool we use to perform experience of accelerating RSA algorithm. This paper will also build up a mathematical model to help understand the mechanism of RSA encryption algorithm.

The improvement of the implementation of the RSA cryptographic algorithm for encrypting / decoding information flows based on the use of the vector-modular method of modular exponential is presented in this paper. This makes it possible to replace the complex operation of modular multiplication with the addition operation, which increases the speed of the RSA cryptosystem. The scheme of algorithms of modular multiplication and modular exponentiation is presented. The analytical and graphical comparison of the time complexities of the proposed and known approaches shows that the use of the vector-modular method reduces the temporal complexity of the modular exponential compared to the classical one.

In cloud computing application scenarios involving computationally weak clients, the natural need for applied cryptography solutions requires the delegation of the most expensive cryptography algorithms to a computationally stronger cloud server. Group exponentiation is an important operation used in many public-key cryptosystems and, more generally, cryptographic protocols. Solving the problem of delegating group exponentiation in the case of a single, possibly malicious, server, was left open since early papers in the area. Only recently, we have solved this problem for a large class of cyclic groups, including those commonly used in cryptosystems proved secure under the intractability of the discrete logarithm problem. In this paper we solve this problem for an important class of non-cyclic groups, which includes RSA groups when the modulus is the product of two safe primes, a common setting in applications using RSA-based cryptosystems. We show a delegation protocol for fixed-exponent exponentiation in such groups, satisfying natural correctness, security, privacy and efficiency requirements, where security holds with exponentially small probability. In our protocol, with very limited offline computation and server computation, a client can delegate an exponentiation to an exponent of the same length as a group element by only performing two exponentiations to an exponent of much shorter length (i.e., the length of a statistical parameter). We obtain our protocol by a non-trivial adaptation to the RSA group of our previous protocol for cyclic groups.

Diffie-Hellman and RSA encryption/decryption involve computationally intensive cryptographic operations such as modular exponentiation. Computing modular exponentiation using appropriate pre-computed pairs of bases and exponents was first proposed by Boyko et al. In this paper, we present a reconfigurable architecture for pre-computation methods to compute modular exponentiation and thereby speeding up RSA and Diffie-Hellman like protocols. We choose Diffie-Hellman key pair (a, ga mod p) to illustrate the efficiency of Boyko et al's scheme in hardware architecture that stores pre-computed values ai and corresponding gai in individual block RAM. We use a Pseudo-random number generator (PRNG) to randomly choose ai values that are added and corresponding gai values are multiplied using modular multiplier to arrive at a new pair (a, ga mod p). Further, we present the advantage of using Montgomery and interleaved methods for batch multiplication to optimise time and area. We show that a 1024-bit modular exponentiation can be performed in less than 73$μ$s at a clock rate of 200MHz on a Xilinx Virtex 7 FPGA.