Public-Key Cryptography

Frontmatter

Blending FHE-NTRU Keys – The Excalibur Property

Abstract

Can Bob give Alice his decryption secret and be convinced that she will not give it to someone else? This is achieved by a proxy re-encryption scheme where Alice does not have Bob’s secret but instead she can transform ciphertexts in order to decrypt them with her own key. In this article, we answer this question in a different perspective, relying on a property that can be found in the well-known modified NTRU encryption scheme. We show how parties can collaborate to one-way-glue their secret-keys together, giving Alice’s secret-key the additional ability to decrypt Bob’s ciphertexts. The main advantage is that the protocols we propose can be plugged directly to the modified NTRU scheme with no post-key-generation space or time costs, nor any modification of ciphertexts. In addition, this property translates to the NTRU-based multikey homomorphic scheme, allowing to equip a hierarchic chain of users with automatic re-encryption of messages and supporting homomorphic operations of ciphertexts. To achieve this, we propose two-party computation protocols in cyclotomic polynomial rings. We base the security in presence of various types of adversaries on the RLWE and DSPR assumptions, and on two new problems in the modified NTRU ring.

Louis Goubin, Francisco José Vial Prado

Approximate-Deterministic Public Key Encryption from Hard Learning Problems

Abstract

We introduce the notion of approximate-deterministic public key encryption (A-DPKE), which extends the notion of deterministic public key encryption (DPKE) by allowing the encryption algorithm to be “slightly” randomized. However, a ciphertext convergence property is required for A-DPKE such that the ciphertexts of a message are gathering in a small metric space, while ciphertexts of different messages can be distinguished easily. Thus, A-DPKE maintains the convenience of DPKE in fast search and de-duplication on encrypted data, and encompasses new constructions. We present two simple constructions of A-DPKE, respectively from the learning parity with noise and the learning with errors assumptions.

Yamin Liu, Xianhui Lu, Bao Li, Wenpan Jing, Fuyang Fang

Adaptively Secure Strong Designated Signature

Abstract

Almost all the available strong designated verifier signature (SDVS) schemes are either insecure or inefficient for practical implementation. Hence, an efficient and secure SDVS algorithm is desired. In this paper, we propose an efficient strong designated verifier signature on identity-based setting, we call it ID-SDVS scheme. The proposed scheme is strong existentially unforgeable against adaptive chosen message and adaptive chosen identity attack under standard assumptions, the hardness of the decisional and computational Bilinear Diffie-Hellman Problem (BDHP). Though the unverifiability by a non-designated verifier and the strongness are essential security properties of a SDVS, the proofs for these properties are not provided in most of the literature on SDVS we reviewed. We provide the proofs of unverifiability and of strongness of the proposed scheme. Moreover, we show that the proposed scheme is significantly more efficient in the view of computation and operation time than the existing similar schemes.

Neetu Sharma, Rajeev Anand Sahu, Vishal Saraswat, Birendra Kumar Sharma

The Shortest Signatures Ever

Abstract

Multivariate Cryptography is one of the main candidates for creating post quantum public key cryptosystems. Especially in the area of digital signatures, there exist many practical and secure multivariate schemes. In this paper we present a general technique to reduce the signature size of multivariate schemes. Our technique enables us to reduce the signature size of nearly all multivariate signature schemes by 10 to 15% without slowing down the scheme significantly. We can prove that the security of the underlying scheme is not weakened by this modification. Furthermore, the technique enables a further reduction of the signature size when accepting a slightly more costly verification process. This trade off between signature size and complexity of the verification process can not be observed for any other class of digital signature schemes. By applying our technique to the Gui signature scheme, we obtain the shortest signatures of all existing digital signature schemes.

Mohamed Saied Emam Mohamed, Albrecht Petzoldt

Cryptographic Protocols

Frontmatter

CRT-Based Outsourcing Algorithms for Modular Exponentiations

Abstract

The problem of securely outsourcing cryptographic computations to the untrusted servers was formally addressed first by Hohenberger and Lysyanskaya in TCC 2005. They presented an algorithm which outsources computation of modular exponentiations securely to two non-interacting third-party servers but the checkability of third-party computations has probability 1 / 2. Chen et al. improved this algorithm for two non-colluding servers by increasing the checkability probability to 2/3. For real-world cryptographic applications it is desirable that the checkability probability is \(1-\epsilon \), where \(\epsilon \) becomes negligible for appropriate parameter choices. Towards a more practical use, we present an algorithm(s) for secure outsourcing of (simultaneous) modular exponentiation(s) which can be seen as another application of the Chinese remainder theorem (CRT). Interestingly the checkability probability of our algorithm is 1 in the presence of two non colluding servers. Our algorithm is superior in both efficiency and checkability compared to that of the previously known schemes of the same kind. Finally we discuss the potential practical applications for our outsourcing schemes, for example computing the final exponentiation in pairings.

Lakshmi Kuppusamy, Jothi Rangasamy

Verifiable Computation for Randomized Algorithm

Abstract

Verifiable computation enables a computationally weak client to delegate the difficult computation to a more powerful cloud server. When the client receives the returned result, it can verify the correctness of the result. As a new computing model, it has been widely studied. But, the previous works on verifiable computation was restricted to the case where the target function was deterministic.

In this paper, we present a novel definition for verifiable computation supporting randomized algorithms, which allows a resource constrained client to outsource the computation of a randomized algorithm to an untrusted server. We consider a new setting where the random string, as the random input of the randomized algorithm, is generated by the cloud server. In our security definition, it must guarantee that the server can not tamper with the randomness which means that the generated string is indistinguishable with a truly random string. Our construction is based on indistinguishability obfuscation, constrained verifiable random function and functional pseudorandom function.

Muhua Liu, Ying Wu, Rui Xue

UC-secure and Contributory Password-Authenticated Group Key Exchange

Abstract

The contributory property allows participants of group key exchange fairly to engage in the generation of the random session key rather than an entity or some part of members solely to determinate it or force it to lie in an undesired distribution. In this paper, we put forth a password-authenticated group key exchange (GPAKE) in which principals cooperate to agree a strong session key just in possession of a short password. The scheme realizes the optimality of contributory property—full-contributiveness—as long as there is one honest party, the uniform distribution of final session keys can be guaranteed. Moreover, it reaches the security definitions in the well-known universal composability (UC) framework under the random oracle model based on the one-more gap Diffie-Hellman assumption. In particular, our scheme that achieves these results with only two-round messages, has better performances on round complexity in comparison with the existing UC-secure schemes.

Lin Zhang, Zhenfeng Zhang

Side-Channel Attacks

Frontmatter

Score-Based vs. Probability-Based Enumeration – A Cautionary Note

Abstract

The fair evaluation of leaking devices generally requires to come with the best possible distinguishers to extract and exploit side-channel information. While the need of a sound model for the leakages is a well known issue, the risks of additional errors in the post-processing of the attack results (with key enumeration/key rank estimation) are less investigated. Namely, optimal post-processing is known to be possible with distinguishers outputting probabilities (e.g. template attacks), but the impact of a deviation from this context has not been quantified so far. We therefore provide a consolidating experimental analysis in this direction, based on simulated and actual measurements. Our main conclusions are twofold. We first show that the concrete impact of heuristic scores such as produced with a correlation power analysis can lead to non-negligible post-processing errors. We then show that such errors can be mitigated in practice, with Bayesian extensions or specialized distinguishers (e.g. on-the-fly linear regression).

Marios O. Choudary, Romain Poussier, François-Xavier Standaert

Analyzing the Shuffling Side-Channel Countermeasure for Lattice-Based Signatures

Abstract

Implementation security for lattice-based cryptography is still a vastly unexplored field. At CHES 2016, the very first side-channel attack on a lattice-based signature scheme was presented. Later, shuffling was proposed as an inexpensive means to protect the Gaussian sampling component against such attacks. However, the concrete effectiveness of this countermeasure has never been evaluated.

We change that by presenting an in-depth analysis of the shuffling countermeasure. Our analysis consists of two main parts. First, we perform a side-channel attack on a Gaussian sampler implementation. We combine templates with a recovery of data-dependent branches, which are inherent to samplers. We show that an adversary can realistically recover some samples with very high confidence.

Second, we present a new attack against the shuffling countermeasure in context of Gaussian sampling and lattice-based signatures. We do not attack the shuffling algorithm as such, but exploit differing distributions of certain variables. We give a broad analysis of our attack by considering multiple modeled SCA adversaries.

We show that a simple version of shuffling is not an effective countermeasure. With our attack, a profiled SCA adversary can recover the key by observing only 7 000 signatures. A second version of this countermeasure, which uses Gaussian convolution in conjunction with shuffling twice, can increase side-channel security and the number of required signatures significantly. Here, roughly 285 000 observations are needed for a successful attack. Yet, this number is still practical.

Peter Pessl

Implementation of Cryptographic Schemes

Frontmatter

Atomic-AES: A Compact Implementation of the AES Encryption/Decryption Core

Abstract

The implementation of the AES encryption core by Moradi et al. at Eurocrypt 2011 is one of the smallest in terms of gate area. The circuit takes around 2400 gates and operates on an 8 bit datapath. However this is an encryption only core and unable to cater to block cipher modes like CBC and ELmD that require access to both the AES encryption and decryption modules. In this paper we look to investigate whether the basic circuit of Moradi et al. can be tweaked to provide dual functionality of encryption and decryption (ENC/DEC) while keeping the hardware overhead as low as possible. As a result, we report an 8-bit serialized AES circuit that provides the functionality of both encryption and decryption and occupies around 2645 GE with a latency of 226 cycles. This is a substantial improvement over the next smallest AES ENC/DEC circuit (Grain of Sand) by Feldhofer et al. which takes around 3400 gates but has a latency of over 1000 cycles for both the encryption and decryption cycles.

Subhadeep Banik, Andrey Bogdanov, Francesco Regazzoni

Fast Hardware Architectures for Supersingular Isogeny Diffie-Hellman Key Exchange on FPGA

Abstract

In this paper, we present a constant-time hardware implementation that achieves new speed records for the supersingular isogeny Diffie-Hellman (SIDH), even when compared to highly optimized Haswell computer architectures. We employ inversion-free projective isogeny formulas presented by Costello et al. at CRYPTO 2016 on an FPGA. Modern FPGA’s can take advantage of heavily parallelized arithmetic in \(\mathbb {F}_{p^{2}}\), which lies at the foundation of supersingular isogeny arithmetic. Further, by utilizing many arithmetic units, we parallelize isogeny evaluations to accelerate the computations of large-degree isogenies by approximately 57%. On a constant-time implementation of 124-bit quantum security SIDH on a Virtex-7, we generate ephemeral public keys in 10.6 and 11.6 ms and generate the shared secret key in 9.5 and 10.8 ms for Alice and Bob, respectively. This improves upon the previous best time in the literature for 768-bit implementations by a factor of 1.48. Our 83-bit quantum security implementation improves upon the only other implementation in the literature by a speedup of 1.74 featuring fewer resources and constant-time.

Brian Koziel, Reza Azarderakhsh, Mehran Mozaffari-Kermani

AEZ: Anything-But EaZy in Hardware

Abstract

We provide the first hardware implementation of AEZ, a third-round candidate to the CAESAR competition for authenticated encryption. Complex, optimized for software, and impossible to implement in a single pass, AEZ poses significant obstacles for any hardware realization. Still, we find that a hardware implementation of AEZ is quite feasible. On Xilinx Virtex-6 FPGAs, our single-core design has a throughput exceeding 3.4 Gbit/s, and uses about 4600 LUTs and about 1250 CLB slices. In terms of the throughput to area ratio, this performance places it on the 12th position among 28 CAESAR candidate families benchmarked during Round 2 of the competition (assuming the key size of at least 96 bits, and the limit on the message size equal to \(2^{11}-1\) bytes). At the same time, AEZ targets a stronger notion of security against the cipher misuse than all other algorithms implemented and ranked ahead of it in the Round 2 hardware benchmarking study.

Ekawat Homsirikamol, Kris Gaj

Functional Encryption

Frontmatter

Private Functional Encryption: Indistinguishability-Based Definitions and Constructions from Obfuscation

Abstract

Private functional encryption guarantees that not only the information in ciphertexts is hidden but also the circuits in decryption tokens are protected. A notable use case of this notion is query privacy in searchable encryption. Prior privacy models in the literature were fine-tuned for specific functionalities (namely, identity-based encryption and inner-product encryption), did not model correlations between ciphertexts and decryption tokens, or fell under strong uninstantiability results. We develop a new indistinguishability-based privacy notion that overcomes these limitations and give constructions supporting different circuit classes and meeting varying degrees of security. Obfuscation is a common building block that these constructions share, albeit the obfuscators necessary for each construction are based on different assumptions. In particular, we develop a composable and distributionally secure hyperplane membership obfuscator and use it to build an inner-product encryption scheme that achieves an unprecedented level of privacy, positively answering a question left open by Boneh, Raghunathan and Segev (ASIACRYPT 2013) concerning the extension and realization of enhanced security for schemes supporting this functionality.

Afonso Arriaga, Manuel Barbosa, Pooya Farshim

Revocable Decentralized Multi-Authority Functional Encryption

Abstract

Attribute-Based Encryption (ABE) is regarded as one of the most desirable cryptosystems realizing data security in the cloud storage systems. Functional Encryption (FE) which includes ABE and the ABE system with multiple authorities are studied actively today. However, ABE has the attribute revocation problem. In this paper, we propose a new revocation scheme using update information, i.e., revocation patch (not update key), in which an encryptor does not need to care about the revocation list. We propose an FE scheme with multiple authorities and no central authority supporting revocation by using revocation patch. Our proposal realizes the revocation on the attribute level. More precisely, we introduce the new concept, i.e., the revocation on the category level that is a generalization of attribute level. We prove that our construction is adaptively secure against chosen plaintext attacks and static corruption of authorities based on the decisional linear (DLIN) assumption.

Hikaru Tsuchida, Takashi Nishide, Eiji Okamoto, Kwangjo Kim

Symmetric-Key Cryptanalysis

Frontmatter

On Linear Hulls and Trails

Abstract

This paper improves the understanding of linear cryptanalysis by highlighting some previously overlooked aspects. It shows that linear hulls are sometimes formed already in a single round, and that overlooking such hulls may lead to a wrong estimation of the linear correlation, and thus of the data complexity. It shows how correlation matrices can be used to avoid this, and provides a tutorial on how to use them properly. By separating the input and output masks from the key mask it refines the formulas for computing the expected correlation and the expected linear potential. Finally, it shows that when the correlation of a hull is not properly estimated (e.g., by using the correlation of a single trail as the correlation of the hull), the success probability of Matsui’s Algorithm 1 drops, sometimes drastically. It also shows that when the trails composing the hull are properly accounted for, more than a single key bit can be recovered using Algorithm 1. All the ideas presented in this paper are followed by examples comparing previous methods to the corrected ones, and verified experimentally with reduced-round versions of Simon32/64.

Tomer Ashur, Vincent Rijmen

Related-Key Cryptanalysis of Midori

Abstract

Midori64 and Midori128 [2] are lightweight block ciphers, which respectively cipher 64-bit and 128-bit blocks. While several attack models are discussed by the authors of Midori, the authors made no claims concerning the security of Midori against related-key differential attacks. In this attack model, the attacker uses related-key differential characteristics, i.e., tuples \((\delta _P, \delta _K, \delta _C)\) such that a difference (generally computed as a XOR) of \(\delta _P\) in the plaintext coupled with a difference \(\delta _K\) in the key yields a difference \(\delta _C\) after r rounds with a good probability. In this paper, we propose a constraint programming model to automate the search for optimal (in terms of probability) related-key differential characteristics on Midori. Using it, we build related-key distinguishers on the full-round Midori64 and Midori128, and mount key recovery attacks on both versions of the cipher with practical time complexity, respectively \(2^{35.8}\) and \(2^{43.7}\).

David Gérault, Pascal Lafourcade

Some Proofs of Joint Distributions of Keystream Biases in RC4

Abstract

In Usenix Security symposium 2015, Vanhoef and Piessens published a number of results regarding weaknesses of the RC4 stream cipher when used in the TLS protocol. The authors unearthed a number of new biases in the keystream bytes that helped to reliably recover the plaintext using a limited number of TLS sessions. Most of these biases were based on the joint distribution successive/non-successive keystream bytes. Moreover, the biases were reported after experimental observations and no theoretical explanations were proffered. In this paper, we provide detailed proofs of most of these biases, and provide certain generalizations of the results reported in the above paper. We also unearth new biases based on the joint distributions of three consecutive bytes.

Sonu Jha, Subhadeep Banik, Takanori Isobe, Toshihiro Ohigashi

Practical Low Data-Complexity Subspace-Trail Cryptanalysis of Round-Reduced PRINCE

Abstract

Subspace trail cryptanalysis is a very recent new cryptanalysis technique, and includes differential, truncated differential, impossible differential, and integral attacks as special cases.

In this paper, we consider PRINCE, a widely analyzed block cipher proposed in 2012. After the identification of a 2.5 rounds subspace trail of PRINCE, we present several (truncated differential) attacks up to 6 rounds of PRINCE. This includes a very practical attack with the lowest data complexity of only 8 plaintexts for 4 rounds, which co-won the final round of the PRINCE challenge in the 4-round chosen-plaintext category. The attacks have been verified using a C implementation.

Of independent interest, we consider a variant of PRINCE in which ShiftRows and MixLayer operations are exchanged in position. In particular, our result shows that the position of ShiftRows and MixLayer operations influences the security of PRINCE. The same analysis applies to follow-up designs inspired by PRINCE.

Lorenzo Grassi, Christian Rechberger

Foundations

Frontmatter

On Negation Complexity of Injections, Surjections and Collision-Resistance in Cryptography

Abstract

Goldreich and Izsak (Theory of Computing, 2012) initiated the research on understanding the role of negations in circuits implementing cryptographic primitives, notably, considering one-way functions and pseudo-random generators. More recently, Guo, Malkin, Oliveira and Rosen (TCC, 2015) determined tight bounds on the minimum number of negations gates (i.e., negation complexity) of a wide variety of cryptographic primitives including pseudo-random functions, error-correcting codes, hardcore-predicates and randomness extractors.

We continue this line of work to establish the following results:

1.

First, we determine tight lower bounds on the negation complexity of collision-resistant and target collision-resistant hash-function families.

2.

Next, we examine the role of injectivity and surjectivity on the negation complexity of one-way functions. Here we show that,

(a)

Assuming the existence of one-way injections, there exists a monotone one-way injection. Furthermore, we complement our result by showing that, even in the worst-case, there cannot exist a monotone one-way injection with constant stretch.

(b)

Assuming the existence of one-way permutations, there exists a monotone one-way surjection.

3.

Finally, we show that there exists list-decodable codes with monotone decoders.

In addition, we observe some interesting corollaries to our results.

Douglas Miller, Adam Scrivener, Jesse Stern, Muthuramakrishnan Venkitasubramaniam

Implicit Quadratic Property of Differentially 4-Uniform Permutations

Abstract

Substitution box (S-box) is an important component of block ciphers for providing nonlinearity. It is often constructed from differentially 4-uniform permutation. In this paper, we examine all (to the best of our knowledge) the differentially 4-uniform permutations that are known in the literature and determine whether they are implicitly quadratic. We found that all of them are implicitly quadratic, making them vulnerable to algebraic attack [10, 12‐14]. This leads to an open question of whether there exists a differentially 4-uniform permutation over \(\mathbb {F}_{2^n}\) that is not implicitly quadratic. We provide a partial answer to this question by solving it for the special cases of \(n=11\) and \(n=13\).

Theo Fanuela Prabowo, Chik How Tan

Secret Sharing for mNP: Completeness Results

Abstract

We show completeness results for secret sharing schemes realizing \(\mathsf {mNP}\) access structures. We begin by proposing a new, Euclidean-type, division technique for access structures. Using this new technique we obtain several results in characterizing access structures for efficient (unconditionally secure) secret sharing schemes:

We show a useful transformation that achieves efficient schemes for complex access structures using schemes realizing simple access structures.
We show that, assuming every access structure in \(\mathsf {P} \cap \mathsf {mono}\) admits efficient secret sharing, the existence of an efficient secret sharing for an access structure in \(\mathsf {mNP}\) that is also complete for \(\mathsf {mNP}\) under Karp/Levin monotone-reductions implies secret sharing schemes for all of \(\mathsf {mNP}\).
We finally improve upon the above completeness result by obtaining the same under ordinary Karp/Levin reductions.

Mahabir Prasad Jhanwar, Kannan Srinathan

New Cryptographic Constructions

Frontmatter

Receiver Selective Opening Security from Indistinguishability Obfuscation

Abstract

In this paper we study public key encryptions secure against RSO (receiver selective opening) attacks. To do so, we exploit the puncturable property of several existing CCA secure schemes that employs the “all-but-one” technique, use an indistinguishability obfuscator to wrap up the decryption circuit and set the obfuscated circuit as the secret key. Concretely, our first construction is from lossy trapdoor functions; our second construction is a bit encryption from puncturable pseudo-random functions and is secure against chosen ciphertext attacks simultaneously.

Dingding Jia, Xianhui Lu, Bao Li

Format Preserving Sets: On Diffusion Layers of Format Preserving Encryption Schemes

Abstract

Format preserving encryption refers to a set of techniques for encrypting data such that the ciphertext has the same format as the plaintext. Here, we consider the design of diffusion layers only which can be defined by, in general, a linear transformation. In this paper, we study and explore the format preserving diffusion layers, in particular, the relationship between the \(n \times n\) diffusion matrix M over the field \(\mathbb {F}_{q}\) and the format preserving set \(\mathbb {S} \subseteq \mathbb {F}_{q}\) such that whenever \(\mathbf {v} \in \mathbb {S}^n\), \(M\mathbf {v} \in \mathbb {S}^n\). It is proved in this paper that if such a set \(\mathbb {S}\) with respect to a certain type of matrix M contains \(\bar{0} \in \mathbb {F}_q\), then it is always a vector space over the smallest field containing entries of M. Moreover, some more interesting results are found when this condition, \(\bar{0} \in \mathbb {S}\), is relaxed. We illustrate our results by a credit card example where plaintext and ciphertext both come from the set \(\{0,\cdots ,9\}\). We further show that only certain type of \(4 \times 4\) matrices over the field \(\mathbb {F}_{2^4}\) can be constructed which yield a format preserving set of cardinality 10 which is suited for our credit card example. However, to the best of our knowledge, such matrices do not have any cryptographic significance. Thus, it is impossible to construct any cryptographically significant \(4 \times 4\) matrices over the field \(\mathbb {F}_{2^4}\) in the diffusion layer which yields a format preserving set of cardinality 10.

Kishan Chand Gupta, Sumit Kumar Pandey, Indranil Ghosh Ray

Springer Professional

Über dieses Buch

Inhaltsverzeichnis

Frontmatter

Public-Key Cryptography

Frontmatter

Blending FHE-NTRU Keys – The Excalibur Property

Approximate-Deterministic Public Key Encryption from Hard Learning Problems

Adaptively Secure Strong Designated Signature

The Shortest Signatures Ever

Cryptographic Protocols

Frontmatter

CRT-Based Outsourcing Algorithms for Modular Exponentiations

Verifiable Computation for Randomized Algorithm

UC-secure and Contributory Password-Authenticated Group Key Exchange

Side-Channel Attacks

Frontmatter

Score-Based vs. Probability-Based Enumeration – A Cautionary Note

Analyzing the Shuffling Side-Channel Countermeasure for Lattice-Based Signatures

Implementation of Cryptographic Schemes

Frontmatter

Atomic-AES: A Compact Implementation of the AES Encryption/Decryption Core

Fast Hardware Architectures for Supersingular Isogeny Diffie-Hellman Key Exchange on FPGA

AEZ: Anything-But EaZy in Hardware

Functional Encryption

Frontmatter

Private Functional Encryption: Indistinguishability-Based Definitions and Constructions from Obfuscation

Revocable Decentralized Multi-Authority Functional Encryption

Symmetric-Key Cryptanalysis

Frontmatter

On Linear Hulls and Trails

Related-Key Cryptanalysis of Midori

Some Proofs of Joint Distributions of Keystream Biases in RC4

Practical Low Data-Complexity Subspace-Trail Cryptanalysis of Round-Reduced PRINCE

Foundations

Frontmatter

On Negation Complexity of Injections, Surjections and Collision-Resistance in Cryptography

Implicit Quadratic Property of Differentially 4-Uniform Permutations

Secret Sharing for mNP: Completeness Results

New Cryptographic Constructions

Frontmatter

Receiver Selective Opening Security from Indistinguishability Obfuscation

Format Preserving Sets: On Diffusion Layers of Format Preserving Encryption Schemes

Backmatter