nach oben

2016 | Buch

Kapitel lesen Erstes Kapitel lesen

Public-Key Cryptography – PKC 2016

19th IACR International Conference on Practice and Theory in Public-Key Cryptography, Taipei, Taiwan, March 6-9, 2016, Proceedings, Part I

herausgegeben von: Chen-Mou Cheng, Kai-Min Chung, Giuseppe Persiano, Bo-Yin Yang

Verlag: Springer Berlin Heidelberg

Buchreihe : Lecture Notes in Computer Science

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

The two-volume set LNCS 9614 and 9615 constitutes the refereed proceedings of the 19th IACR International Conference on the Practice and Theory in Public-Key Cryptography, PKC 2016, held in Taipei, Taiwan, in March 2016.
The 34 revised papers presented were carefully reviewed and selected from 143 submissions. They are organized in topical sections named: CCA security, functional encryption, identity-based encryption, signatures, cryptanalysis, leakage-resilient and circularly secure encryption, protocols, and primitives.

Inhaltsverzeichnis

Frontmatter

CCA Security

Frontmatter

Trading Plaintext-Awareness for Simulatability to Achieve Chosen Ciphertext Security

Abstract

In PKC 2014, Dachman-Soled showed a construction of a chosen ciphertext (CCA) secure public key encryption (PKE) scheme based on a PKE scheme which simultaneously satisfies a security property called weak simulatability and (standard model) plaintext awareness (sPA1) in the presence of multiple public keys. It is not well-known if plaintext awareness for the multiple keys setting is equivalent to the more familiar notion of that in the single key setting, and it is typically considered that plaintext awareness is a strong security assumption (because to achieve it we have to rely on a “knowledge”-type assumption). In Dachman-Soled’s construction, the underlying PKE scheme needs to be plaintext aware in the presence of \(2k+2\) public keys.

The main result in this work is to show that the strength of plaintext awareness required in the Dachman-Soled construction can be somehow “traded” with the strength of a “simulatability” property of other building blocks. Furthermore, we also show that we can “separate” the assumption that a single PKE scheme needs to be both weakly simulatable and plaintext aware in her construction. Specifically, in this paper we show two new constructions of CCA secure key encapsulation mechanisms (KEMs): Our first scheme is based on a KEM which is chosen plaintext (CPA) secure and plaintext aware only under the 2 keys setting, and a PKE scheme satisfying a “slightly stronger” simulatability than weak simulatability, called “trapdoor simulatability” (introduced by Choi et al. ASIACRYPT 2009). Our second scheme is based on a KEM which is 1-bounded CCA secure (Cramer et al. ASIACRYPT 2007) and plaintext aware only in the single key setting, and a trapdoor simulatable PKE scheme. Our results add new recipes for constructing CCA secure PKE/KEM from general assumptions (that are incomparable to those used by Dachman-Soled), and in particular show interesting trade-offs among building blocks with those used in Dachman-Soled’s construction.

Takahiro Matsuda, Goichiro Hanaoka

Chosen-Ciphertext Security from Subset Sum

Abstract

We construct a public-key encryption (PKE) scheme whose security is polynomial-time equivalent to the hardness of the Subset Sum problem. Our scheme achieves the standard notion of indistinguishability against chosen-ciphertext attacks (IND-CCA) and can be used to encrypt messages of arbitrary polynomial length, improving upon a previous construction by Lyubashevsky, Palacio, and Segev (TCC 2010) which achieved only the weaker notion of semantic security (IND-CPA) and whose concrete security decreases with the length of the message being encrypted.

At the core of our construction is a trapdoor technique which originates in the work of Micciancio and Peikert (Eurocrypt 2012).

Sebastian Faust, Daniel Masny, Daniele Venturi

On the Hardness of Proving CCA-Security of Signed ElGamal

Abstract

The well-known Signed ElGamal scheme consists of ElGamal encryption with a non-interactive Schnorr proof of knowledge. While this scheme should be intuitively secure against chosen-ciphertext attacks in the random oracle model, its security has not yet been proven nor disproven so far, without relying on further non-standard assumptions like the generic group model. Currently, the best known positive result is that Signed ElGamal is non-malleable under chosen-plaintext attacks. In this paper we provide some evidence that proving Signed ElGamal to be CCA secure in the random oracle model is hard. That is, building on previous work of Shoup and Gennaro (Eurocrypt’98), Seurin and Treger (CT-RSA 2013), and Bernhard et al. (PKC 2015), we exclude a large class of potential reductions that could be used to establish CCA security of the scheme.

David Bernhard, Marc Fischlin, Bogdan Warinschi

CCA-Secure Keyed-Fully Homomorphic Encryption

Abstract

To simultaneously achieve CCA security and homomorphic property for encryption, Emura et al. introduced a new cryptographic primitive named keyed-homomorphic encryption, in which homomorphic ciphertext manipulations can only be performed by someone holding a devoted evaluation key which, by itself, does not enable decryption. A keyed-homomorphic encryption scheme should provide CCA2 security when the evaluation key is unavailable to the adversary and remain CCA1-secure when the evaluation key is exposed. While existing keyed-homomorphic encryption schemes only allow simple computations on encrypted data, our goal is to construct CCA-secure keyed-fully homomorphic encryption (keyed-FHE) capable of evaluating any functions on encrypted data with an evaluation key.

In this paper, we first introduce a new primitive called convertible identity-based fully homomorphic encryption (IBFHE), which is an IBFHE with an additional transformation functionality, and define its security notions. Then, we present a generic construction of CCA-secure keyed-FHE from IND-sID-CPA-secure convertible IBFHE and strongly EUF-CMA-secure signature. Finally, we propose a concrete construction of IND-sID-CPA-secure convertible IBFHE, resulting in the first CCA-secure keyed-FHE scheme in the standard model.

Junzuo Lai, Robert H. Deng, Changshe Ma, Kouichi Sakurai, Jian Weng

On the Key Dependent Message Security of the Fujisaki-Okamoto Constructions

Abstract

In PKC 1999, Fujisaki and Okamoto showed how to convert any public key encryption (PKE) scheme secure against chosen plaintext attacks (CPA) to a PKE scheme which is secure against chosen ciphertext attacks (CCA) in the random oracle model. Surprisingly, the resulting CCA secure scheme has almost the same efficiency as the underlying CPA secure scheme. Moreover, in J. Cryptology 2013, they proposed more efficient conversion by using the hybrid encryption framework.

In this work, we clarify whether these two constructions are also secure in the sense of key dependent message security against chosen ciphertext attacks (KDM-CCA security), under exactly the same assumptions on the building blocks as those used by Fujisaki and Okamoto. Specifically, we show two results: Firstly, we show that the construction proposed in PKC 1999 does not satisfy \(\text {KDM}\text {-}\text {CCA}\) security generally. Secondly, on the other hand, we show that the construction proposed in J. Cryptology 2013 satisfies \(\text {KDM}\text {-}\text {CCA}\) security.

Fuyuki Kitagawa, Takahiro Matsuda, Goichiro Hanaoka, Keisuke Tanaka

Functional Encryption

Frontmatter

Extended Nested Dual System Groups, Revisited

Abstract

The notion of extended nested dual system groups (ENDSG) was recently proposed by Hofheinz et al. [PKC 2015] for constructing almost-tight identity based encryptions (IBE) in the multi-instance, multi-ciphertext (MIMC) setting. However only a composite-order instantiation was proposed and more efficient prime-order instantiations are absent. The paper fills the blank by presenting two constructions.

We revise the definition of ENDSG and realize it using prime-order bilinear groups based on Chen and Wee’s prime-order instantiation of nested dual system groups [CRYPTO 2013]. This yields the first almost-tight IBE in the prime-order setting achieving weak adaptive security in MIMC scenario under the d-linear (d-Lin) assumption. We further enhanced the revised ENDSG to capture stronger security notions for IBE, including B -weak adaptive security and full adaptive security. We show that our prime-order instantiation is readily B-weak adaptive secure and full adaptive secure without introducing extra assumption.

We then try to find better solutions by fine-tuning ENDSG again and realizing it using the technique of Chen, Gay, and Wee [EUROCRYPT 2015]. This leads to an almost-tight secure IBE in the same setting with better performance than our first result, but the security relies on a non-standard assumption, d-linear assumption with auxiliary input (d-LinAI) for an even positive integer d. However we note that, the 2-LinAI assumption is implied by the external decisional linear (XDLIN) assumption. This concrete instantiation could also be realized using symmetric bilinear groups under standard decisional linear assumption.

Junqing Gong, Jie Chen, Xiaolei Dong, Zhenfu Cao, Shaohua Tang

Functional Encryption for Inner Product with Full Function Privacy

Abstract

Functional encryption (FE) supports constrained decryption keys that allow decrypters to learn specific functions of encrypted messages. In numerous practical applications of FE, confidentiality must be assured not only for the encrypted data but also for the functions for which functional keys are provided. This paper presents a non-generic simple private key FE scheme for the inner product functionality, also known as inner product encryption (IPE). In contrast to the existing similar schemes, our construction achieves the strongest indistinguishability-based notion of function privacy in the private key setting without employing any computationally expensive cryptographic tool or non-standard complexity assumption. Our construction is built in the asymmetric bilinear pairing group setting of prime order. The security of our scheme is based on the well-studied Symmetric External Diffie-Hellman (SXDH) assumption.

Pratish Datta, Ratna Dutta, Sourav Mukhopadhyay

Deniable Functional Encryption

Abstract

Deniable encryption, first introduced by Canetti et al. [14], allows a sender and/or receiver of encrypted communication to produce fake but authentic-looking coins and/or secret keys that “open” the communication to a different message. Here we initiate its study for the more general case of functional encryption (FE), as introduced by Boneh et al. [12], wherein a receiver in possession of a key k can compute from any encryption of a message x the value F(k, x) according to the scheme’s functionality F. Our results are summarized as follows: We put forth and motivate the concept of deniable FE, for which we consider two models. In the first model, as previously considered by O’Neill et al. [31] in the case of identity-based encryption, a receiver gets assistance from the master authority to generate a fake secret key. In the second model, there are “normal” and “deniable” secret keys, and a receiver in possession of a deniable secret key can produce a fake but authentic-looking normal key on its own. This parallels the “multi-distributional” model of deniability previously considered for public-key encryption.

In the first model, we show that any FE scheme for the general circuit functionality (as several recent candidate construction achieve) can be converted into an FE scheme having receiver deniability, without introducing any additional assumptions. In addition we show an efficient receiver deniable FE for Boolean Formulae from bilinear maps. In the second (multi-distributional) model, we show a specific FE scheme for the general circuit functionality having receiver deniability. This result additionally assumes differing-inputs obfuscation and relies on a new technique we call delayed trapdoor circuits. To our knowledge, a scheme in the multi-distributional model was not previously known even in the simpler case of identity-based encryption.

Finally, we show that receiver deniability for FE implies some form of simulation security, further motivating study of the latter and implying optimality of our results.

Angelo De Caro, Vincenzo Iovino, Adam O’Neill

Identity-Based Encryption

Frontmatter

Identity-Based Cryptosystems and Quadratic Residuosity

Abstract

Three approaches are currently used for devising identity-based encryption schemes. They respectively build on pairings, quadratic residues (\(\mathsf {QR}\)), and lattices. Among them, the \(\mathsf {QR}\)-based scheme proposed by Cocks in 2001 is notable in that it works in standard RSA groups: its security relies on the standard quadratic residuosity assumption. But it has also a number of deficiencies, some of them have been subsequently addressed in follow-up works. Currently, one of the main limitations of Cocks’ scheme resides in its apparent lack of structure. This considerably restricts the range of possible applications. For example, given two Cocks ciphertexts, it is unknown how to evaluate of a function thereof.

Cocks’ scheme is believed to be non-homomorphic. This paper disproves this conjecture and proposes a constructive method for computing over Cocks ciphertexts. The discovery of the hidden algebraic structure behind Cocks encryption is at the core of the method. It offers a better understanding of Cocks’ scheme. As a further illustration of the importance of the knowledge of the underlying structure, this paper shows how to anonymize Cocks ciphertexts without increasing their size or sacrificing the security.

Finally and of independent interest, this paper presents a simplified version of the abstract identity-based cryptosystem with short ciphertexts of Boneh, Gentry, and Hamburg.

Marc Joye

Identity-Based Hierarchical Key-Insulated Encryption Without Random Oracles

Abstract

Key-insulated encryption is one of the effective solutions to a key exposure problem. Recently, identity-based encryption (IBE) has been used as one of fundamental cryptographic primitives in a wide range of various applications, and it is considered that the identity-based key-insulated security has a huge influence on the resulting applications. At Asiacrypt’05, Hanaoka et al. proposed an identity-based hierarchical key-insulated encryption (hierarchical IKE) scheme. Although their scheme is secure in the random oracle model, it has a “hierarchical key-updating structure,” which is attractive functionality that enhances key exposure resistance.

In this paper, we first propose the hierarchical IKE scheme without random oracles. Our hierarchical IKE scheme is secure under the symmetric external Diffie–Hellman (SXDH) assumption, which is known as the simple and static one. Furthermore, when the hierarchy depth is one (i.e. not hierarchical case), our scheme is the first IKE scheme that achieves constant-size parameters including public parameters, secret keys, and ciphertexts.

Yohei Watanabe, Junji Shikata

Signatures

Frontmatter

Attribute-Based Signatures for Circuits from Bilinear Map

Abstract

In attribute-based signatures, each signer receives a signing key from the authority, which is associated with the signer’s attribute, and using the signing key, the signer can issue a signature on any message under a predicate, if his attribute satisfies the predicate. One of the ultimate goals in this area is to support a wide class of predicates, such as the class of arbitrary circuits, with practical efficiency from a simple assumption, since these three aspects determine the usefulness of the scheme. We present an attribute-based signature scheme which allows us to use an arbitrary circuit as the predicate with practical efficiency from the symmetric external Diffie-Hellman assumption. We achieve this by combining the efficiency of Groth-Sahai proofs, which allow us to prove algebraic equations efficiently, and the expressiveness of Groth-Ostrovsky-Sahai proofs, which allow us to prove any NP relation via circuit satisfiability.

Yusuke Sakai, Nuttapong Attrapadung, Goichiro Hanaoka

Efficient Unlinkable Sanitizable Signatures from Signatures with Re-randomizable Keys

Abstract

In a sanitizable signature scheme the signer allows a designated third party, called the sanitizer, to modify certain parts of the message and adapt the signature accordingly. Ateniese et al. (ESORICS 2005) introduced this primitive and proposed five security properties which were formalized by Brzuska et al. (PKC 2009). Subsequently, Brzuska et al. (PKC 2010) suggested an additional security notion, called unlinkability which says that one cannot link sanitized message-signature pairs of the same document. Moreover, the authors gave a generic construction based on group signatures that have a certain structure. However, the special structure required from the group signature scheme only allows for inefficient instantiations.

Here, we present the first efficient instantiation of unlinkable sanitizable signatures. Our construction is based on a novel type of signature schemes with re-randomizable keys. Intuitively, this property allows to re-randomize both the signing and the verification key separately but consistently. This allows us to sign the message with a re-randomized key and to prove in zero-knowledge that the derived key originates from either the signer or the sanitizer. We instantiate this generic idea with Schnorr signatures and efficient \(\varSigma \)-protocols, which we convert into non-interactive zero-knowledge proofs via the Fiat-Shamir transformation. Our construction is at least one order of magnitude faster than instantiating the generic scheme of Brzuska et al. with the most efficient group signature schemes.

Nils Fleischhacker, Johannes Krupp, Giulio Malavolta, Jonas Schneider, Dominique Schröder, Mark Simkin

Fault-Tolerant Aggregate Signatures

Abstract

Aggregate signature schemes allow for the creation of a short aggregate of multiple signatures. This feature leads to significant reductions of bandwidth and storage space in sensor networks, secure routing protocols, certificate chains, software authentication, and secure logging mechanisms. Unfortunately, in all prior schemes, adding a single invalid signature to a valid aggregate renders the whole aggregate invalid. Verifying such an invalid aggregate provides no information on the validity of any individual signature. Hence, adding a single faulty signature destroys the proof of integrity and authenticity for a possibly large amount of data. This is largely impractical in a range of scenarios, e.g. secure logging, where a single tampered log entry would render the aggregate signature of all log entries invalid.

In this paper, we introduce the notion of fault-tolerant aggregate signature schemes. In such a scheme, the verification algorithm is able to determine the subset of all messages belonging to an aggregate that were signed correctly, provided that the number of aggregated faulty signatures does not exceed a certain bound.

We give a generic construction of fault-tolerant aggregate signatures from ordinary aggregate signatures based on cover-free families. A signature in our scheme is a small vector of aggregated signatures of the underlying scheme. Our scheme is bounded, i.e. the number of signatures that can be aggregated into one signature must be fixed in advance. However the length of an aggregate signature is logarithmic in this number. We also present an unbounded construction, where the size of the aggregate signature grows linearly in the number of aggregated messages, but the factor in this linear function can be made arbitrarily small.

The additional information encoded in our signatures can also be used to speed up verification (compared to ordinary aggregate signatures) in cases where one is only interested in verifying the validity of a single message in an aggregate, a feature beyond fault-tolerance that might be of independent interest. For concreteness, we give an instantiation using a suitable cover-free family.

Gunnar Hartung, Björn Kaidel, Alexander Koch, Jessica Koch, Andy Rupp

Delegatable Functional Signatures

Abstract

We introduce delegatable functional signatures (DFS) which support the delegation of signing capabilities to another party, called the evaluator, with respect to a functionality \(\mathcal {F} \). In a DFS, the signer of a message can choose an evaluator, specify how the evaluator can modify the signature without voiding its validity, allow additional input, and decide how the evaluator can further delegate its capabilities. Technically, DFS unify several seemingly different signature primitives, including functional signatures and policy-based signatures (PKC’14), sanitizable signatures, identity based signatures, and blind signatures. We characterize the instantiability of DFS with respect to the corresponding security notions of unforgeability and privacy. On the positive side we show that privacy-free DFS can be constructed from one-way functions. Furthermore, we show that unforgeable and private DFS can be constructed from doubly-enhanced trapdoor permutations. On the negative side we show that the previous result is optimal regarding its underlying assumptions presenting an impossibility result for unforgeable private DFS from one-way permutations.

Michael Backes, Sebastian Meiser, Dominique Schröder

Mitigating Multi-target Attacks in Hash-Based Signatures

Abstract

This work introduces XMSS-T, a new stateful hash-based signature scheme with tight security. Previous hash-based signatures are facing a loss of security, linear in performance parameters such as the total tree height. Our new scheme can achieve the same security level but using hash functions with a smaller output length, which immediately leads to a smaller signature size. The same techniques also apply directly to the recent stateless hash-based signature scheme SPHINCS (Eurocrypt 2015), and the signature size is reduced as well.

Being a little more specific and technical, the tight security stems from new multi-target notions of hash-function properties which we define and analyze. We show precise complexity for breaking these security properties under both classical and quantum generic attacks, thus establishing a reliable estimate for the quantum security of XMSS-T. Especially, we prove quantum query complexity tailored for cryptographic applications, which overcome some limitations of standard techniques in quantum query complexity such as they usually only consider worst-case complexity. Our proof techniques may be useful elsewhere.

We also implement XMSS-T and compare its performance to that of XMSS (PQCrypto 2011), the most recent stateful hash-based signature scheme before our work.

Andreas Hülsing, Joost Rijneveld, Fang Song

Nearly Optimal Verifiable Data Streaming

Abstract

The problem of verifiable data streaming (VDS) considers the setting in which a client outsources a large dataset to an untrusted server and the integrity of this dataset is publicly verifiable. A special property of VDS is that the client can append additional elements to the dataset without changing the public verification key. Furthermore, the client may also update elements in the dataset. All previous VDS constructions follow a hash-tree-based approach, but either have an upper bound on the size of the database or are only provably secure in the random oracle model. In this work, we give the first unbounded VDS constructions in the standard model. We give two constructions with different trade-offs. The first scheme follows the line of hash-tree-constructions and is based on a new cryptographic primitive called Chameleon Vector Commitment (CVC), that may be of independent interest. A CVC is a trapdoor commitment scheme to a vector of messages where both commitments and openings have constant size. Due to the tree-based approach, integrity proofs are logarithmic in the size of the dataset. The second scheme achieves constant size proofs by combining a signature scheme with cryptographic accumulators, but requires computational costs on the server-side linear in the number of update-operations.

Johannes Krupp, Dominique Schröder, Mark Simkin, Dario Fiore, Giuseppe Ateniese, Stefan Nuernberger

ARMed SPHINCS

Computing a 41 KB Signature in 16 KB of RAM

Abstract

This paper shows that it is feasible to implement the stateless hash-based signature scheme SPHINCS-256 on an embedded microprocessor with memory even smaller than a signature and limited computing power. We demonstrate that it is possible to generate and verify the 41 KB signature on an ARM Cortex M3 that only has 16 KB of memory available. We provide benchmarks for our implementation which show that this can be used in practice. To analyze the costs of using the stateless SPHINCS scheme instead of its stateful alternatives, we also implement XMSS\(^{MT}\) on this platform and give a comparison.

Andreas Hülsing, Joost Rijneveld, Peter Schwabe

Backmatter

Titel: Public-Key Cryptography – PKC 2016
herausgegeben von: Chen-Mou Cheng
Kai-Min Chung
Giuseppe Persiano
Bo-Yin Yang
Verlag: Springer Berlin Heidelberg
Electronic ISBN: 978-3-662-49384-7
Print ISBN: 978-3-662-49383-0
DOI: https://doi.org/10.1007/978-3-662-49384-7

Springer Professional

Über dieses Buch

Inhaltsverzeichnis

Frontmatter

CCA Security

Frontmatter

Trading Plaintext-Awareness for Simulatability to Achieve Chosen Ciphertext Security

Chosen-Ciphertext Security from Subset Sum

On the Hardness of Proving CCA-Security of Signed ElGamal

CCA-Secure Keyed-Fully Homomorphic Encryption

On the Key Dependent Message Security of the Fujisaki-Okamoto Constructions

Functional Encryption

Frontmatter

Extended Nested Dual System Groups, Revisited

Functional Encryption for Inner Product with Full Function Privacy

Deniable Functional Encryption

Identity-Based Encryption

Frontmatter

Identity-Based Cryptosystems and Quadratic Residuosity

Identity-Based Hierarchical Key-Insulated Encryption Without Random Oracles

Signatures

Frontmatter

Attribute-Based Signatures for Circuits from Bilinear Map

Efficient Unlinkable Sanitizable Signatures from Signatures with Re-randomizable Keys

Fault-Tolerant Aggregate Signatures

Delegatable Functional Signatures

Mitigating Multi-target Attacks in Hash-Based Signatures

Nearly Optimal Verifiable Data Streaming

ARMed SPHINCS

Backmatter

Premium Partner