In this work, we construct a second price (Vickrey) auction protocol (SPA), which does not require any auctioneers and ensures total privacy in the presence of rational parties participating in auction. In particular, the confidentiality of the highest bid and the identity of the second highest bidder are protected. We model the bidders participating in the second price auction as rational, computationally bounded and privacy-sensitive parties. These are self-interested agents who care about...

Power analysis of public-key algorithms is a well-known approach in the community of side-channel analysis. We usually classify operations based on the differences in power traces produced by different basic operations (such as modular exponentiation) to recover secret information like private keys. The more accurate the segmentation of power traces, the higher the efficiency of their classification. There exist two commonly used methods: one is equidistant segmentation, which requires a...

In this work we are interested in evaluating the possibility of extracting information from radio-enabled embedded-systems from a long distance. That is, our focus is capturing information from sources in the micrometer to tens of centimeters scale, such as intra- or inter- device busses, board-level routing traces etc. Moreover, we focus on distances in the range of millimeters to tens of centimeters from the (on-chip or on-board) embedded-system Tx Antenna to the signal source....

QC-MDPC (quasi cyclic moderate density parity check) code-based McEliece cryptosystems are considered to be one of the candidates for post-quantum cryptography. Decreasing DER (decoding error rate) is one of important factor for their security, since recent attacks to these cryptosystems effectively use DER information. In this paper, we pursue the possibility of optimization-base decoding, concretely we examine ADMM (alternating direction method of multipliers), a recent developing...

Security against side-channel assisted attacks remains a focus and concern in the ongoing standardization process of quantum-computer-resistant cryptography algorithms. Hiding and masking techniques are currently under investigation to protect the Post-Quantum Cryptography (PQC) algorithms in the NIST PQC standardization process against sophisticated side-channel attacks. Between hiding and masking, masking is emerging as a popular option due to its simplicity and minimized cost of...

The lattice-based CRYSTALS-Dilithium signature scheme has been selected for standardization by the NIST. As part of the selection process, a large number of implementations for platforms like x86, ARM Cortex-M4, or – on the hardware side – Xilinx Artix-7 have been presented and discussed by experts. While software implementations have been subject to side-channel analysis with several attacks being published, an analysis of Dilithium hardware implementations and their peculiarities has not...

Fault Injection (FI) attacks have become a practical threat to modern cryptographic implementations. Such attacks have recently focused more on exploitation of implementation-centric and device-specific properties of the faults. In this paper, we consider the parallel between SCA attacks and FI attacks; specifically, that many FI attacks rely on the data-dependency of activation and propagation of a fault, and SCA attacks similarly rely on data-dependent power usage. In fact, these are so...

Using a novel class of single bit one-way trapdoor functions we construct a theoretical probabilistic public key encryption scheme that has many interesting properties. These functions are constructed from binary quadratic forms and rational quartic reciprocity laws. They are not based on class group operations nor on universal one-way hash functions. Inverting these functions appears to be as difficult as factoring, and other than factoring, we know of no reductions between this new...

Embedded microprocessors are an important component of reconfigurable architectures. Fine-grain (e.g., cycle-accurate) power analysis of such processors has been used to improve power and energy efficiency, and detect implementation vulnerabilities, in embedded applications. However, such analysis is difficult to conduct; it requires either specialized and often expensive equipment, or construction of test architectures using disparate acquisition and analysis tools. In this research, we...

Passwords are the most widely used form of online user authentication. In a traditional setup, the user, who has a human-memorable low entropy password, wants to authenticate with a login server. Unfortunately, existing solutions in this setting are either non-portable or insecure against many attacks, including phishing, man-in-the-middle, honeypot, and offline dictionary attacks. Three previous studies (Acar et al. 2013, Bicakci et al. 2011, and Jarecki et al. 2016) provide solutions...

Single password authentication (SPA) schemes are introduced to overcome the challenges of traditional password authentications, which are vulnerable to offline dictionary, phishing, honeypot, and man-in-the-middle attacks. Unlike classical password-based authentication systems, in SPA schemes the user is required to remember only a single password (and a username) for all her accounts, while the password is protected against offline dictionary attacks in a provably secure manner. Several...

Randomized moduli in Residue Number System (RNS) generate effectively large noise and make quite difficult to attack a secret key $K$ from only few observations of Hamming distances $H=(H_0, ..., H_{d-1})$ that result from the changes on the state variable. Since Hamming distances have gaussian distribution and most of the statistic tests, like NIST's ones, evaluate discrete and uniform distribution, we choose to use side-channel attacks as a tool in order to evaluate randomisation of...

We present the first hardware implementations of Diffie-Hellman key exchange based on the Kummer surface of Gaudry and Schost’s genus-2 curve targeting a 128-bit security level. We describe a single-core architecture for low-latency applications and a multi-core architecture for high-throughput applications. Synthesized on a Xilinx Zynq-7020 FPGA, our architectures perform a key exchange with lower latency and higher throughput than any other reported implementation using prime-field...

This paper presents a series of Montgomery scalar multiplication algorithms on general short Weierstrass curves over odd characteristic fields, which need only 12 field multiplications plus 12 ~ 20 field additions per scalar bit using 8 ~ 10 field registers, thus significantly outperform the binary NAF method on average. Over binary fields, the Montgomery scalar multiplication algorithm which was presented at the first CHES workshop by L´opez and Dahab has been a favorite of ECC...

Although lattice-based cryptography has proven to be a particularly efficient approach to post-quantum cryptography, its security against side-channel attacks is still a very open topic. There already exist some first works that use masking to achieve DPA security. However, for public-key primitives SPA attacks that use just a single trace are also highly relevant. For lattice-based cryptography this implementation-security aspect is still unexplored. In this work, we present the first...

In this paper, we investigate the security of the BLISS lattice-based signature scheme, one of the most promising candidates for post-quantum-secure signatures, against side-channel attacks. Several works have been devoted to its efficient implementation on various platforms, from desktop CPUs to micro-controllers and FPGAs, and more recent papers have also considered its security against certain types of physical attacks, notably fault injection and cache attacks. We turn to more...

In this paper, we investigate the security of the BLISS lattice-based signature scheme, one of the most promising candidates for post-quantum-secure signatures, against side-channel attacks. Several works have been devoted to its efficient implementation on various platforms, from desktop CPUs to micro-controllers and FPGAs, and more recent papers have also considered its security against certain types of physical attacks, notably fault injection and cache attacks. We turn to more...

This paper introduces dudect: a tool to assess whether a piece of code runs in constant time or not on a given platform. We base our approach on leakage detection techniques, resulting in a very compact, easy to use and easy to maintain tool. Our methodology fits in around 300 lines of C and runs on the target platform. The approach is substantially different from previous solutions. Contrary to others, our solution requires no modeling of hardware behavior. Our solution can be used in...

One prominent countermeasure against side-channel attacks, especially differential power analysis (DPA), is fresh re-keying. In such schemes, the so-called re-keying function takes the burden of protecting a cryptographic primitive against DPA. To ensure the security of the scheme against side-channel analysis, the used re-keying function has to withstand both simple power analysis (SPA) and differential power analysis (DPA). Recently, at SAC 2016, Keymill---a side-channel resilient key...

ECDSA is one of the most important public-key signature scheme, however it is vulnerable to lattice attack once a few bits of the nonces are leaked. To protect Elliptic Curve Cryptography (ECC) against Simple Power Analysis, many countermeasures have been proposed. Doubling and Additions of points on the given elliptic curve require several additions and multiplications in the base field and this number is not the same for the two operations. The idea of the atomicity protection is to use a...

Recently, several research groups in cryptography have presented new elliptic curve model based on Edwards curves. These new curves were selected for their good performance and security perspectives. Cryptosystems based on elliptic curves in embedded devices can be vulnerable to Side-Channel Attacks (SCA), such as the Simple Power Analysis (SPA) or the Differential Power Analysis (DPA). In this paper, we analyze the existence of special points whose use in SCA is known as Same Value...

We propose a lightweight coprocessor for 16-bit microcontrollers that implements high security elliptic curve cryptography. It uses a 283-bit Koblitz curve and offers 140-bit security. Koblitz curves offer fast point multiplications if the scalars are given as specific $\tau$-adic expansions, which results in a need for conversions between integers and $\tau$-adic expansions. We propose the first lightweight variant of the conversion algorithm and, by using it, introduce the first...

Unified formula for computing elliptic curve point addition and doubling are considered to be resistant against simple power-analysis attack. A new elliptic curve formula known as unified binary Huff curve in this regard has appeared into the literature in 2011. This paper is devoted to analyzing the applicability of this elliptic curve in practice. Our paper has two contributions.We provide an efficient implementation of the unified Huff formula in projective coordinates on FPGA....

In the paper, we study whether it is possible to construct an efficient leakage-resilient symmetric scheme using the AES block cipher. We aim at bridging the gap between the theoretical leakage-resilient symmetric primitives used to build encryption schemes and the practical schemes that do not have any security proof against side-channel adversaries. Our goal is to construct an as efficient as possible leakage-resilient encryption scheme, but we do not want to change the cryptographic...

Side-channel attacks using only a single trace crucially rely on the capability of reliably extracting side-channel information (e.g. Hamming weights of intermediate target values) from traces. In particular, in original versions of simple power analysis (SPA) or algebraic side channel attacks (ASCA) it was assumed that an adversary can correctly extract the Hamming weight values for all the intermediates used in an attack. Recent developments in error tolerant SPA style attacks relax...

Simple side-channel attacks trade off data complexity (i.e. the number of side-channel observations needed for a successful attack) with computational complexity (i.e. the number of operations applied to the side-channel traces). In the specific example of Simple Power Analysis (SPA) attacks on the Advanced Encryption Standard (AES), two approaches can be found in the literature, one which is a pragmatic approach that involves basic techniques such as efficient enumeration of key candidates,...

Modular multiplication of large integers is a performance-critical arithmetic operation of many public-key cryptosystems such as RSA, DSA, Diffie-Hellman (DH) and their elliptic curve-based variants ECDSA and ECDH. The computational cost of modular multiplication and related operations (e.g. exponentiation) poses a practical challenge to the widespread deployment of public-key cryptography, especially on embedded devices equipped with 8-bit processors (smart cards, wireless sensor nodes,...

In order to prevent the SPA (Simple Power Analysis) attack against modular exponentiation algorithms, a multiply-always implementation is generally used. Witteman et al. introduced in \cite{WI} a new cross-correlation power analysis attack against the multiply-always implementation. We suggest two new algorithms, resistant to this attack and also to other known attacks. The first algorithm is an alternative approach to exponentiation algorithms used in cryptography, which usually receive...

Power Analysis has been widely studied since Kocher et al. presented in 1998 the initial Simple and Differential Power Analysis (SPA and DPA). Correlation Power Analysis (CPA) is nowadays one of the most powerful techniques which requires, as classical DPA, many execu- tion curves for recovering secrets. We introduce in this paper a technique in which we apply correlation analysis using only one execution power curve during an exponentiation to recover the whole secret exponent manipulated...

The design of embedded processors demands a careful trade-off between many conflicting objectives such as performance, silicon area and power consumption. Finding such a trade-off can often ignore the issue of security, which can cause, otherwise secure, software to leak information through so-called micro-architectural side channels. In this paper we show that early-terminating integer multipliers found in many embedded processors (e.g., ARM7TDMI) represent an instance of this problem. The...

We describe an SPA attack on an 8-bit smart card implementation of the Serpent block cipher. Our attack uses measurements taken during an on-the-fly key expansion together with linearity in the cipher's key schedule algorithm to drastically reduce the search time for an initial key. An implementation finds 256-bit keys in 3.736 ms on average. Our work shows that linearity in key schedule design and other cryptographic applications should be carefully evaluated for susceptibility to...

This paper introduces fast algorithms for performing group operations on twisted Edwards curves, pushing the recent speed limits of Elliptic Curve Cryptography (ECC) forward in a wide range of applications. Notably, the new addition algorithm uses 8M for suitably selected curve constants. In comparison, the fastest point addition algorithms for (twisted) Edwards curves stated in the literature use 9M 1S. It is also shown that the new addition algorithm can be implemented with four processors...

Template attacks have been considered exclusively in the context of implementations of symmetric cryptographic algorithms on 8-bit devices. Within these scenarios, they have proven to be the most powerful attacks. This is not surprising because they assume the most powerful adversaries. In this article we investigate how template attacks can be applied to implementations of an asymmetric cryptographic algorithm on a 32-bit platform. The asymmetric cryptosystem under scrutiny is the elliptic...

This paper improves implementation techniques of Elliptic Curve Cryptography. We introduce new formulae and algorithms for the group law on Jacobi quartic, Jacobi intersection, Edwards, and Hessian curves. The proposed formulae and algorithms can save time in suitable point representations. To support our claims, a cost comparison is made with classic scalar multiplication algorithms using previous and current operation counts. Most notably, the best speedup is obtained in the case of Jacobi...

Public-key cryptosystem (PKC) is one of inevitable key technologies in order to accomplish fruitful security applications in ubiquitous computing systems. The ubiquitous computer only has scarce computational resources (like Smart cards, RFID, Sensor Network), however, so that the light weight PKC is necessary for those miniaturized low-power devices. Recently, XTR is considered as one of good candidates for more energy efficient cryptosystems. Among XTR exponentiation algorithms, the most...

Elliptic Curve Cryptography (ECC) has found wide applications in smart cards and embedded systems. Point multiplication plays a critical role in ECC. Many efficient point multiplication methods have been proposed. One of them is the comb method which is much more efficient than other methods if precomputation points are calculated in advance or elsewhere. Unfortunately, Many efficient point multiplication methods including the comb method are vulnerable to power-analysis attacks. Various...

We introduce two new left-to-right integer recodings which can be used to perform scalar multiplication with a fixed sequence of operations. These recodings make it possible to have a simple power analysis resistant implementation of a group-based cryptosystem without using unified formulas or introducing dummy operations. This approach is very useful for groups in which the doubling step are less expensive than the addition step, for example with hyperelliptic curves over binary fields or...

Recently new types of differential power analysis attacks (DPA) against elliptic curve cryptosystems (ECC) and RSA systems have been introduced. Most existing countermeasures against classical DPA attacks are vulnerable to these new DPA attacks which include refined power analysis attacks (RPA), zero-value point attacks (ZPA), and doubling attacks. The new attacks are different from classical DPA in that RPA uses a special point with a zero-value coordinate, while ZPA uses auxiliary...

Side Channel Attacks may exploit leakage information to break cryptosystems on smard card devices. In this paper we present a new SCA-resistant elliptic curve scalar multiplication algorithm, based on the Lim and Lee technique. The proposed algorithm builds a sequence of bit-strings representing the scalar $k$, characterized by the fact that all bit-strings are different from zero; this property will ensure a uniform computation behaviour for the algorithm, and thus will make it secure...

This note describes an SPA-based side channel attack against a CRT implementation of an RSA function. In contrast with Novak’s attack [8], it concentrates on the initial modular reduction. With the help of lattice reduction it applies even to implementations which use a common randomising technique to ensure resistance against certain side channel attacks.

The pipelining scheme proposed in~\cite{PKM04} is an efficient and secure scheme for computing scalar multiplication in Elliptic Curve Cryptosystems (ECC). The scheme proposed in~\cite{PKM04} does not assume any pre-computation. In this work we extend the scheme to the situation where the system allows some pre-computation and is capable of storing some precomputed values. Like the scheme proposed in~\cite{PKM04} our scheme uses an extra multiplier. On the performance front, it outperforms...

In this paper, we present a new parallel architecture to avoid side-channel analyses such as: timing attack, simple/differential power analysis, fault induction attack and simple/differential electromagnetic analysis. We use a Montgomery Multiplication based on Residue Number Systems. Thanks to RNS, we develop a design able to perform an RSA signature in parallel on a set of identical and independent coprocessors. Of independent interest, we propose a new DPA countermeasure in the framework...

The XTR public key system was introduced at Crypto 2000. Application of XTR in cryptographic protocols leads to substantial savings both in communication and computational overhead without compromising security. It is regarded that XTR is suitable for a variety of environments, including low-end smart cards, and XTR is the excellent alternative to either RSA or ECC. In \cite{LV00a,SL01}, authors remarked that XTR single exponentiation (XTR-SE) is less susceptible than usual exponentiation...

A way for preventing SPA-like attacks on elliptic curve systems is to use the same formula for the doubling and the general addition of points on the curve. Various proposals have been made in this direction with different results. This paper re-investigates the Jacobi form suggested by Liardet and Smart (CHES 2001). Rather than considering the Jacobi form as the intersection of two quadrics, the addition law is directly derived from the underlying quartic. As a result, this leads to...