International Association for Cryptologic Research

# IACR News Central

You can also access the full news archive.

Further sources to find out about changes are CryptoDB, ePrint RSS, ePrint Web, Event calender (iCal).

2015-02-24
04:17 [Pub][ePrint]

Resource constraints in smart devices demand an efficient cryptosystem that allows for low power and memory consumption. This has led to popularity of comparatively efficient Elliptic curve cryptog-raphy (ECC). Prior to this paper, much of ECC is implemented on re-configurable hardware i.e. FPGAs, which are costly and unfavorable as low-cost solutions.

We present comprehensive yet efficient implementations of ECC on fixed-point TMS54xx series of digital signal processors (DSP). 160-bit prime field GF(p) ECC is implemented over a wide range of coordinate choices. This paper also implements windowed recoding technique to provide better execution times. Stalls in the programming are mini-mized by utilization of loop unrolling and by avoiding data dependence. Complete scalar multiplication is achieved within 50 msec in coordinate implementations, which is further reduced till 25 msec for windowed-recoding method. These are the best known results for fixed-point low power digital signal processor to date.

04:17 [Pub][ePrint]

This paper is devoted to the design of a 258-bit multiplier for computing pairings over Barreto-Naehrig (BN) curves at 128-bit security level. The proposed design is optimized for Xilinx ﬁeld programmable gate array (FPGA). Each 258-bit integer is represented as a polynomial with ﬁve, 65 bit signed integer, coefficients. Exploiting this splitting we designed a pipelined 65-bit multiplier based on new Karatsuba- Ofman variant using non-standard splitting to ﬁt to the Xilinx embedded digital signal processor (DSP) blocks. We prototype the coprocessor in two architectures pipelined and serial on a Xilinx Virtex-6 FPGA using around 17000 slices and 11 DSPs in the pipelined design and 7 DSPs in the serial. The pipelined 128-bit pairing is computed in 1. 8 ms running at 225MHz and the serial is performed in 2.2 ms running at 185MHz. To the best of our knowledge, this implementation outperforms all reported hardware designs in term of DSP use.

Keywords-

04:17 [Pub][ePrint]

Hardcore lemmas are results in complexity theory which state that average-case hardness must have a very hard kernel\'\', that is a subset of instances where the given problem is extremely hard. They find important applications in hardness amplification. In this paper we revisit the following two fundamental results:

\\begin{enumerate}[(a)]

\\item The hardcore lemma for unpredictability, due to Impagliazzo (FOCS \'95). It states that if a boolean function $f$ is moderately\'\' hard to predict on average, then there must be a set of noticeable size on which $f$ is extremely\'\' hard to predict.

\\item The hardcore lemma for indistinguishability, proved by Maurer and Tessaro (TCC\'10), states that for two random variables $X$ and $Y$ which are $\\epsilon$-computationally close, there are events $A$ and $B$ of probability $1-\\epsilon$ such that the distributions of $X|A$ and $Y|B$ are computationally\'\' identical.

\\end{enumerate}

Using only the standard min-max theorem and some basic facts about convex approximations in $L_p$ spaces, we provide alternative modular proofs and some generalizations of these results in the nonuniform setting, achieving best possible bounds for (a) and slightly improving the known bounds for (b). As an interesting application, we show a strengthening of the transformation between two most popular pseudoentropy variants: HILL and Metric Entropy, and apply it to show how to extract pseudorandomness from a sequence of metric-entropy sources of poor quality. In this case we significantly improve security parameters, comparing to the best known techniques.

04:17 [Pub][ePrint]

In this paper, we introduce and study a new cryptographic primitive that we call \"puncturable key encapsulation mechanism\" (PKEM), which is a special class of KEMs that satisfy some functional and security requirements that, combined together, imply chosen ciphertext security (CCA security). The purpose of introducing this primitive is to capture certain common patterns in the security proofs of the several existing CCA secure public key encryption (PKE) schemes and KEMs based on general cryptographic primitives which (explicitly or implicitly) use the ideas and techniques of the Dolev-Dwork-Naor (DDN) construction (STOC\'91), and \"break down\" the proofs into smaller steps, so that each small step is easier to work with/verify/understand than directly tackling CCA security.

To see the usefulness of PKEM, we show (1) how several existing constructions of CCA secure PKE/KEM constructed based on general cryptographic primitives can be captured as a PKEM, which enables us to understand these constructions via a unified framework, (2) its connection to detectable CCA security (Hohenberger et al. EUROCRYPT\'12), and (3) a new security proof for a KEM-analogue of the DDN construction from a set of assumptions: \"sender non-committing encryption\" (SNCE) and non-interactive witness indistinguishable proofs.

Then, as our main technical result, we show how to construct a PKEM satisfying our requirements (and thus a CCA secure KEM) from a new set of general cryptographic primitives: \"SNCE\" and \"symmetric key encryption secure for key-dependent messages\" (KDM secure SKE). Our construction realizes the \"decrypt-then-re-encrypt\"-style validity check of a ciphertext which is powerful but in general has a problem of the circularity between a plaintext and a randomness.We show how SNCE and KDM secure SKE can be used together to overcome the circularity. We believe that the connection among three seemingly unrelated notions of encryption primitives, i.e. CCA security, the sender non-committing property, and KDM security, to be of theoretical interest.

2015-02-23
22:17 [Pub][ePrint]

Secure transmission of message was the concern of early men. Several techniques have been developed ever since to assure that the message is understandable only by the sender and the receiver while it would be meaningless to others. In this century, cryptography has gained much significance. This paper proposes a scheme to generate a Dynamic Key-dependent S-Box for the SubBytes Transformation used in Cryptographic Techniques.

22:17 [Pub][ePrint]

Linear and differential cryptanalysis and their generalizations are the most important tools in ststistical analysis of symmetric ciphers.

These attacks make use of linear and differential properties of Sboxes and component functions of symmetric ciphers. In this

article, we investigate generalized statistical properties for Sboxes. We justify the application of linear, differential and differential-linear

cryptanalysis from the mathematical viewpoint. We verify some well-known Sboxes and vectotial Boolean functions by the proposed

criteria and show that these functions have larger biases compared with previous criteria presentesd up to now.

22:17 [Pub][ePrint]

This paper presents several methods for reducing the number of bit operations for multiplication of polynomials over the binary field. First, a modified Bernstein\'s 3-way algorithm is introduced, followed by a new 5-way algorithm. Next, a new 3-way algorithm that improves asymptotic arithmetic complexity compared to Bernstein\'s 3-way algorithm is introduced. This new algorithm uses three multiplications of one-third size polynomials over the binary field and one multiplication of one-third size polynomials over the finite field with four elements. Unlike Bernstein\'s algorithm, which has a linear delay complexity with respect to input size, the delay complexity of the new algorithm is logarithmic. The number of bit operations for the multiplication of polynomials over the finite field with four elements is also computed. Finally, all these new results are combined to obtain improved complexities.

22:17 [Pub][ePrint]

Rotational cryptanalysis is a probabilistic attack applicable to word oriented designs that use (almost) rotation-invariant constants. It is believed that the success probability of rotational cryptanalysis against ciphers and functions based on modular additions, rotations and XORs, can be computed only by counting the number of additions. We show that this simple formula is incorrect due to the invalid Markov cipher assumption used for computing the probability. More precisely, we show that chained modular additions used in ARX ciphers do not form a Markov chain with regards to rotational analysis, thus the rotational probability cannot be computed as a simple product of rotational probabilities of individual modular additions. We provide a precise value of the probability of such chains and give a new algorithm for computing the rotational probability of ARX ciphers. We use the algorithm to correct the rotational attacks on BLAKE2 and to provide valid rotational attacks against the simplified version of Skein.

22:17 [Pub][ePrint]

Kuznyechik is an SPN block cipher that has been recently chosen to be standardized by the Russian federation as a new GOST cipher. The algorithm updates a 128-bit state for nine rounds using a 256-bit key. In this paper, we present meet-in-the-middle attacks on the 4 and 5 round reduced cipher. Our attacks are based on the differential enumeration approach, where we propose a distinguisher for the middle rounds and match a sequence of state differences at its output. However, the application of the exact approach is not successful on Kuznyechik due to its optimal round diffusion. Accordingly, we adopt an equivalent representation for the last round where we can efficiently filter ciphertext pairs and launch the attack in the chosen ciphertext setting. We also utilize partial sequence matching which further reduces the memory and time complexities through relaxing the error probability. The adopted partial sequence matching approach enables successful key recovery by matching parts of the generated sequence instead of the full sequence matching used in the traditional settings of this attack. For the 4 and 5 round reduced cipher, the 256-bit master key is recovered with a time complexity of $2^{139.6}$ and $2^{140.3}$, and a memory complexity of $2^{24.6}$ and $2^{153.3}$, respectively. Both attacks have similar data complexity of $2^{113}$

22:17 [Pub][ePrint]

Revelations over the past couple of years highlight the importance of understanding malicious and surreptitious weakening of cryptographic systems. We provide an overview of this domain, using a number of historical examples to drive development of a weaknesses taxonomy. This allows comparing different approaches to sabotage. We categorize a broader set of potential avenues for weakening systems using this taxonomy, and discuss what future research is needed to provide sabotage-resilient cryptography.

22:17 [Pub][ePrint]

In view of the expiration or reveal of user\'s private credential (or private key) in a realistic scenario, identity-based encryption (IBE) schemes with an efficient key revocation mechanism, or for short, revocable identity-based encryption (RIBE) schemes, become prominently significant. In this paper, we present an RIBE scheme from lattices by combining two Agrawal et al.\'s IBE schemes with the subset difference (SD) method. Our scheme is secure against adaptive identity-time attacks in the standard model under the learning with errors (LWE) assumption. In particular, our scheme serves as one solution to the challenge posed by Chen et al.(ACISP \'12).