main-content

## Über dieses Buch

This book constitutes the refereed proceedings of the 9th International Conference on Provable Security, ProvSec 2015, held in Kanazawa, Japan, in November 2015.

The 19 full papers and 7 short papers presented together with 3 invited talks were carefully reviewed and selected from 60 submissions. The papers are grouped in topical sections on fundamental, protocol, authenticated encryption and key exchange, encryption and identification, privacy and cloud, leakage-resilient cryptography and lattice cryptography, signature and broadcast encryption.

## Inhaltsverzeichnis

### On Privacy for RFID

Abstract
Many wearable devices identify themselves in a pervasive way. But at the same time, people want to remain anonymous. Modeling anonymity and unlinkability in identification protocols is a delicate issue. In this paper, we revisit the privacy model from Asiacrypt 2007. We show how to achieve forward-privacy (in the V07 sense) using an IND-CCA secure cryptosystem with the PKC protocol. We review the impossibility result of strong privacy and the model extension from CANS 2012 to reach strong privacy (in the OV12 sense) using the PKC protocol with plaintext awareness. We also discuss on the simplified model from ESORICS 2011 and achieve strong-privacy (in the HPVP11 sense) using IND-CCA security only. Finally, we apply these results to add privacy protection in distance bounding protocols.
Serge Vaudenay

### From Stateful Hardware to Resettable Hardware Using Symmetric Assumptions

Abstract
Universally composable multi-party computation is impossible without setup assumptions. Motivated by the ubiquitous use of secure hardware in many real world security applications, Katz (EUROCRYPT 2007) proposed a model of tamper-proof hardware as a UC-setup assumption. An important aspect of this model is whether the hardware token is allowed to hold a state or not. Real world examples of tamper-proof hardware that can hold a state are expensive hardware security modules commonly used in mainframes. Stateless, or resettable hardware tokens model cheaper devices such as smartcards, where an adversarial user can cut off the power supply, thus resetting the card’s internal state.
A natural question is how the stateful and the resettable hardware model compare in their cryptographic power, given that either the receiver or the sender of the token (and thus the token itself) might be malicious. In this work we show that any UC-functionality that can be implemented by a protocol using a single untrusted stateful hardware token can likewise be implemented using a single untrusted resettable hardware token, assuming only the existence of one-way functions.
We present two compilers that transform UC-secure protocols in the stateful hardware model into UC-secure protocols in the resettable hardware model. The first compiler can be proven secure assuming merely the existence of one-way functions. However, it (necessarily) makes use of computationally rather expensive non-black-box techniques. We provide an alternative second compiler that replaces the expensive non-black-box component of the first compiler by few additional seed OTs. While this second compiler introduces the seed OTs as additional setup assumptions, it is computationally very efficient.
Nico Döttling, Daniel Kraschewski, Jörn Müller-Quade, Tobias Nilges

### Constrained Verifiable Random Functions from Indistinguishability Obfuscation

Abstract
Constrained verifiable random functions (VRFs) were first explicitly introduced by Fuchsbauer (SCN’14) as an extension of the standard concept of VRFs. In a standard VRF, there is a secret key sk that enables one to evaluate the function at any point of its domain, and enables generation of a proof that the function value is computed correctly. While, in a constrained VRF, it is allowed to derive constrained key $$sk_S$$ for subset S (of the domain) from sk, which enables evaluation of function and generation of proofs only at points in S and nowhere else. In fact, there are many open questions in the study of VRFs, especially constructing them from a wide variety of cryptographic assumptions.
In this work, we show how to construct constrained VRFs with respect to a set system, which can be described by a polynomial-size circuit C, from one-way functions together with indistinguishability obfuscation (iO). Our construction may be interesting for at least two reasons:
• Given the results of Brakerski et al. (TCC09) and Fiore et al. (TCC12), in which they proved that VRFs cannot be constructed from one-way permutations and trapdoor permutations in a black-box manner, it is interesting to study their construction from other stronger cryptographic primitives. Our construction shows that one-way functions plus iO are sufficient.
• Compared to the multilinear-map-based construction of constrained VRFs (SCN’14), our iO-based one has its particular advantage:
• In current multilinear-based constrained VRFs, since the level of their group is $$n+d_{C}$$ where n is the bit-length of input and $$d_{C}$$ is the depth of circuit C, public key is dependent on the depth of circuit. However, our iO-based construction does not have this limitation since our public key is an obfuscated program which is independent on the circuit.
Bei Liang, Hongda Li, Jinyong Chang

### An Improved Attack for Recovering Noisy RSA Secret Keys and Its Countermeasure

Abstract
This paper discusses how to recover RSA secret keys from their noisy version observed by side-channel attacks. At CRYPTO2009, Heninger and Shacham proposed a polynomial time algorithm which recovers an original secret key from some fraction of secret key bits. Then, at CRYPTO2010, Henecka et al. proposed a polynomial time algorithm recovering a correct secret key from the noisy secret key bits with some errors. Then they gave the bound such that the secret key can be recovered in polynomial time. At PKC2013, Kunihiro et al. presented a key-recovery algorithm from the erroneous version of secret key bits with erasures and errors. They also gave a condition for recovering the secret key and its theoretical bound. They pointed out that there is a small gap between their derived condition and the theoretical bound and closing the gap is an open problem. In this paper, we first improve the bound and reduce the computational cost by introducing tighter inequalities than the Hoeffding bound and choosing aggressive parameter settings. Our obtained bound is asymptotically optimal. Further, we show a practical countermeasure against the secret key extraction attack based on our analysis. In the countermeasure, some of the bits in the secret key are intentionally flipped and then the secret key with errors is stored in the memory. With the help of the intentionally added errors, the security is enhanced. For example, it results to be secure against the attacker extracting the secret key with an error rate 0.13 by intentionally adding a 0.15 fraction of errors. Finally, we revisit asymmetric error cases and give a provable bound for crossover probabilities.
Noboru Kunihiro

### Augmented Secure Channels and the Goal of the TLS 1.3 Record Layer

Abstract
Motivated by the wide adoption of authenticated encryption and TLS, we suggest a basic channel abstraction, an augmented secure channel (ASC), that allows a sender to send a receiver messages consisting of two parts, where one is privacy-protected and both are authenticity-protected. Working in the tradition of constructive cryptography, we formalize this idea and provide a construction of this kind of channel using the lower-level tool authenticated-encryption.
We look at recent proposals on TLS 1.3 and suggest that the criterion by which their security can be judged is quite simple: do they construct an ASC? Due to this precisely defined goal, we are able to give a natural construction that comes with a rigorous security proof and directly leads to a proposal on TLS 1.3 that is provably secure.
Christian Badertscher, Christian Matt, Ueli Maurer, Phillip Rogaway, Björn Tackmann

### Sound Proof of Proximity of Knowledge

Abstract
Public-key distance bounding schemes are needed to defeat relay attacks in payment systems. So far, only five such schemes exist, but fail to fully protect against malicious provers. In this paper, we solve this problem. We provide a full formalism to define the proof of proximity of knowledge (PoPoK). Protocols should succeed if and only if a prover holding a secret is within the proximity of the verifier. Like proofs of knowledge, these protocols must satisfy completeness, soundness (protection for the honest verifier), and security (protection for the honest prover). We construct ProProx, the very first sound PoPoK.
Serge Vaudenay

### Multi-party Computation with Small Shuffle Complexity Using Regular Polygon Cards

Abstract
It is well-known that a protocol for any function can be constructed using only cards and various shuffling techniques (this is referred to as a card-based protocol). In this paper, we propose a new type of cards called regular polygon cards. These cards enable a new encoding for multi-valued inputs while the previous works can only handle binary inputs. We furthermore propose a new technique for constructing a card-based protocol for any n-ary function with small shuffle complexity. This is the first general construction in which the shuffle complexity is independent of the complexity (size/depth) of the desired functionality, although being directly proportional to the number of inputs. The construction furthermore supports a wide range of cards and encodings, including previously proposed types of cards. Our techniques provide a method for reducing the number of shuffles in card-based protocols.
Kazumasa Shinagawa, Takaaki Mizuki, Jacob C. N. Schuldt, Koji Nuida, Naoki Kanayama, Takashi Nishide, Goichiro Hanaoka, Eiji Okamoto

### Forward-Secure Authenticated Symmetric Key Exchange Protocol: New Security Model and Secure Construction

Abstract
While a lot of work has been done on the design and security analysis of PKI-based authenticated key exchange (AKE) protocols, very few exist in the symmetric key setting. The first provably secure symmetric AKE was proposed by Bellare and Rogaway (BR) in CRYPTO 1994 and so far this stands out as the most prominent one for symmetric key setting. In line with the significant progress done for PKI based system, we propose a stronger model than the BR model for symmetric key based system. We assume that the adversary can launch active attacks. In addition, the adversary can also obtain long term secret keys of the parties and the internal states of parties by getting access to their ephemeral secrets (or internal randomness) by means of appropriate oracle queries. The salient feature of our model is the way we handle active adversaries even in the test session.
We also design a symmetric key AKE construction that is provably secure against active adversaries in our new model using weak primitives. Dodis et al. (EUROCRYPT 2012) used weak Pseudo Random Functions (wPRF) and weak Almost-XOR Universal hash function family (wAXU) to design a three-pass one-sided authentication protocol in the symmetric key paradigm. A direct application of their techniques yields a four-pass (two-round) symmetric key AKE protocol with mutual authentication. Our construction uses particular instances of these weak primitives and introduces a novel technique called input-swapping to achieve a three-pass symmetric key AKE protocol with mutual authentication resisting active attacks (even in the test session). Our construction is proven secure in the Random oracle Model under the DDH assumption.
Suvradip Chakraborty, Goutam Paul, C. Pandu Rangan

### Full PRF-Secure Message Authentication Code Based on Tweakable Block Cipher

Abstract
We propose a new message authentication code (MAC) based on a tweakable block cipher (TBC). We prove that the new MAC is a pseudo-random function (PRF) up to $$O(2^n)$$ queries, that is, full PRF-security, where the output length of the TBC is n bits. We note that although Yasuda proposed a full PRF-secure MAC based on a compression function (CF), that does not offer a full PRF-secure TBC-based MAC due to the PRF/PRF switch. Hence our MAC is the first full PRF-secure one based on a TBC.
Yusuke Naito

### Efficient Key Authentication Service for Secure End-to-End Communications

Abstract
After four decades of public key cryptography, both the industry and academia seek better solutions for the public key infrastructure. A recent proposal, the certificate transparency concept, tries to enable untrusted servers act as public key servers, such that any key owner can verify that her key is kept properly at those servers. Unfortunately, due to high computation and communication requirements, existing certificate transparency proposals fail to address the problem as a whole.
We propose a new efficient key authentication service (KAS). It uses server-side gossiping as the source of trust, and assumes servers are not all colluding. KAS stores all keys of each user in a separate hash chain, and always shares the last ring of the chain among the servers, ensuring the users that all servers provide the same view about them (i.e., no equivocation takes place). Storing users’ keys separately reduces the server and client computation and communication dramatically, making our KAS a very efficient way of public key authentication. The KAS handles a key registration/change operation in O(1) time using only O(1) proof size; independent of the number of users. While the previous best proposal, CONIKS, requires the client to download 100 KB of proof per day, our proposal needs less than 1 KB of proof per key lifetime, while obtaining the same probabilistic guarantees as CONIKS.

### PPAE: Practical Parazoa Authenticated Encryption Family

Abstract
The CAESAR competition for standardization of schemes for authenticated encryption has received 49 entries. Constructions such as Keyak, ICEPOLE, Artemia, NORX and Ascon use DuplexWrap and JHAE modes. DuplexWrap is based on the sponge construction and JHAE is based on the JH hash function. Andreeva et al. have recently defined a generalized sponge like construction called Parazoa hash family and provided indifferentiability security bound for the same. They had shown that the sponge as well as the JH hash function are instances of the parazoa construction with suitable choices of parameters. In our work, we define PPAE as an Authenticated Encryption family based on Parazoa construction. The proposed AE mode supports feed-forward operation which is lacking in sponge based AE constructions. We also provide security analysis of the PPAE family.
Donghoon Chang, Sumesh Manjunath R., Somitra Kumar Sanadhya

### Lightweight Anonymous Authentication for Ad Hoc Group: A Ring Signature Approach

Abstract
Anonymous authentication protocol allows the system to authenticate a user anonymously. That is, the system knows that the requester is eligible to access, yet does not know his/her actual identity. Anonymous authentication is useful in many privacy-preserving applications such as wireless sensor networks and roaming. However, most of the anonymous authentication protocols are not lightweight. They all require a number of exponentiations or pairings which cannot be executed by lightweight devices such as sensors or RFID. In this paper, we propose a lightweight anonymous authentication protocol for Ad Hoc group. Our protocol contains only lightweight calculations such as hashing or modulus square but not exponentiation or pairing in both prover and verifier sides. The core primitive of our mechanism is a lightweight ring signature scheme. The security of our scheme can be reduced to the classic integer factorization assumption in the random oracle model.
Xu Yang, Wei Wu, Joseph K. Liu, Xiaofeng Chen

### Reset-Secure Identity-Based Identification Schemes Without Pairings

Abstract
Identity-based identification (IBI) schemes are generally insecure against reset attacks since they are commonly constructed from three-move $$\varSigma$$-protocols similar those of traditional public-key identification schemes. In 2009, Thorncharoensri et al. proposed the first IBI scheme secure against impersonators who are able to perform concurrent-reset attacks and is the only scheme that satisfies this notion of security in literature to date. However, their scheme suffers from correctness issues and is also constructed using pairings, which are known to be costly operationally. In this paper, we utilize one of Bellare et al’s methods to reinforce the Schnorr-IBI scheme (and also its more-secure variant: the Twin-Schnorr-IBI scheme) against reset attacks, therefore achieving reset-secure IBI schemes without pairings.
Ji-Jian Chin, Hiroaki Anada, Syh-Yuan Tan

### Attribute-Based Encryption for Finite Automata from LWE

Abstract
We propose a construction of Attribute-Based Encryption for deterministic finite automata with bounded input length from lattices. The security of our construction can be reduced to the hardness of learning with errors (LWE) problem in the selective security model.
The main technique in our scheme is a novel way to securely encode the deterministic finite automata and the input string as a “matrix ribbon” that closely mimics the structure of the tape and supports simple operations that rely only on traditional preimage sampling on lattices.
Our result is the first direct construction of key-policy attribute-based encryption for deterministic finite automata. Comparing with the existing indirect constructions from lattices, our scheme is conceptually simpler and also more efficient.
Xavier Boyen, Qinyi Li

### Functional Signcryption: Notion, Construction, and Applications

Abstract
Functional encryption (FE) enables sophisticated control over decryption rights in a multi-user scenario, while functional signature (FS) allows to enforce complex constraints on signing capabilities. This paper introduces the concept of functional signcryption (FSC) that aims to provide the functionalities of both FE and FS in an unified cost-effective primitive. FSC provides a solution to the problem of achieving confidentiality and authenticity simultaneously in digital communication and storage systems involving multiple users with better efficiency compared to a sequential implementation of FE and FS. We begin by providing formal definition of FSC and formulating its security requirements. Next, we present a generic construction of this challenging primitive that supports arbitrary polynomial-size signing and decryption functions from known cryptographic building blocks, namely, indistinguishability obfuscation (IO) and statistically simulation-sound non-interactive zero-knowledge proof of knowledge (SSS-NIZKPoK). Finally, we exhibit a number of representative applications of FSC: (I) We develop the first construction of attribute-based signcryption (ABSC) supporting signing and decryption policies representable by general polynomial-size circuits from FSC. (II) We show how FSC can serve as a tool for building SSS-NIZKPoK system and IO, a result which in conjunction with our generic FSC construction can also be interpreted as establishing an equivalence between FSC and the other two fundamental cryptographic primitives.
Pratish Datta, Ratna Dutta, Sourav Mukhopadhyay

### BetterTimes

Privacy-Assured Outsourced Multiplications for Additively Homomorphic Encryption on Finite Fields
Abstract
We present a privacy-assured multiplication protocol using which an arbitrary arithmetic formula with inputs from two parties over a finite field $$\mathbb {F}_p$$ can be jointly computed on encrypted data using an additively homomorphic encryption scheme. Our protocol is secure against malicious adversaries. To motivate and illustrate applications of this technique, we demonstrate an attack on a class of known protocols showing how to compromise location privacy of honest users by manipulating messages in protocols with additively homomorphic encryption. We evaluate our approach using a prototypical implementation. The results show that the added overhead of our approach is small compared to insecure outsourced multiplication.
Per Hallgren, Martín Ochoa, Andrei Sabelfeld

### Provably Secure Identity Based Provable Data Possession

Abstract
Provable Data Possession (PDP), which enables cloud users to verify the integrity of their outsourced data without retrieving the entire file from cloud servers, is highly essential in secure cloud storage. A majority of the existing PDP schemes rely on the expensive Public Key Infrastructure (PKI). In this paper, we eliminate the complex certificate management of PDP by presenting a generic construction of identity-based PDP (ID-PDP) protocol, derived from identity-based signatures (IBS) and traditional PDP protocols. We formalize the security model of ID-PDP and prove that the soundness of the generic construction depends on the security of the underlying PDP protocols and the IBS. Then, a concrete ID-PDP protocol is described as an instance of the generic construction to a state-of-the-art PDP protocol due to Shacham and Waters. The implementation shows that our ID-PDP protocol is efficient and practical.
Yong Yu, Yafang Zhang, Yi Mu, Willy Susilo, Hongyu Liu

### Efficient Private Set Intersection Cardinality in the Presence of Malicious Adversaries

Abstract
In this paper, we study Private Set Intersection Cardinality (PSI-CA) protocols and propose two new constructions of PSI-CA. While one of these constructions is secure in the standard model, the other one is secure in the random oracle model (ROM). The security is under the Decisional Diffie-Hellman (DDH) assumption against malicious adversaries. Our proposed PSI-CA protocols are the first to achieve linear communication and computation complexities and secure against malicious adversaries. Furthermore, each of our PSI-CA constructions can be converted to PSI without losing any of the above stated properties.
Sumit Kumar Debnath, Ratna Dutta

### A Formal Dynamic Verification of Choreographed Web Services Conversations

Abstract
Performing runtime verification of composite web services is one of the actual main research challenges. This paper presents a formal approach for dynamically enforcing security policies on web services choreographies. We define a security framework for monitoring choreographed web services by inlining a monitor that checks whether a choreography adheres to some constraints dictated by a security policy. Therefore, this monitor prohibits the execution of undesirable behaviors during runtime and does not change the original behavior of the choreography until an action is about to violate the security policy.
Karim Dahmani, Mahjoub Langar, Riadh Robbana

### Efficient Unconditionally Secure Comparison and Privacy Preserving Machine Learning Classification Protocols

Abstract
We propose an efficient unconditionally secure protocol for privacy preserving comparison of $$\ell$$-bit integers when both integers are shared between two semi-honest parties. Using our comparison protocol as a building block, we construct two-party generic private machine learning classifiers. In this scenario, one party holds an input while the other holds a model and they wish to classify the input according to the model without revealing their private information to each other. Our constructions are based on the setup assumption that there exists pre-distributed correlated randomness available to the computing parties, the so-called commodity-based model. The protocols are storage and computationally efficient, consisting only of additions and multiplications of integers.
Bernardo David, Rafael Dowsley, Raj Katti, Anderson C. A. Nascimento

### Attribute-Based Encryption Resilient to Auxiliary Input

Abstract
The auxiliary input model defines a class of computationally uninvertible function families $$\mathcal {F}$$ to simulate a large class of leakage. Such a function $$f\in \mathcal {F}$$ can information-theoretically reveal the entire secret key SK, but it is still computationally infeasible to recover SK from f(SK). That means SK can be used for multiple tasks, since SK doesn’t need to be continually refreshed. We propose the first CP-ABE scheme based on linear secret sharing schemes, that can tolerate leakage on master key and attribute-based secret keys with auxiliary input(AI). For the security proof of our scheme, we present three modified assumptions in composite order bilinear groups, and prove their hardness. Under these modified assumptions, our scheme can be proved AI-CPA secure in the standard model. Finally, we devise a key-policy ABE scheme also resilient to auxiliary input.
Zhiwei Wang, Siu Ming Yiu

### On Provable Security of wPRF-Based Leakage-Resilient Stream Ciphers

Abstract
Weak pseudorandom functions (wPRFs) found an important application as main building blocks for leakage-resilient ciphers (EUROCRYPT’09 and later works). Several security bounds, based on different techniques and different assumptions, were given to those stream ciphers. The aim of this paper is twofold. First, we present a clear comparison of quantitatively different security bounds in the literature, obtained by means of time-to-success ratio analysis. Second, we revisit the current proof techniques and answer the natural question of how far we are from meaningful and provable security guarantees, when instantiating weak PRFs with standard primitives (block ciphers or hash functions). In particular, we attempt to fix some flaws in the recent analysis of the EUROCRYPT’09 stream cipher (TCC’14), applying new proof techniques to the problem of simulating auxiliary inputs. For one bit of leakage, for the first time, we achieve meaningful security of 60 bits when the cipher is build on the AES.
Maciej Skórski

### Tighter Security for Efficient Lattice Cryptography via the Rényi Divergence of Optimized Orders

Abstract
In security proofs of lattice based cryptography, to bound the closeness of two probability distributions is an important procedure. To measure the closeness, the Rényi divergence has been used instead of the classical statistical distance. Recent results have shown that the Rényi divergence offers security reductions with better parameters, e.g. smaller deviations for discrete Gaussian distributions. However, since previous analyses used a fixed order Rényi divergence, i.e., order two, they lost tightness of reductions. To overcome the deficiency, we adaptively optimize the orders based on the advantages of the adversary for several lattice-based schemes. The optimizations enable us to prove the security with both improved efficiency and tighter reductions. Indeed, our analysis offers security reductions with smaller parameters than the statistical distance based analysis and the reductions are tighter than that of previous Rényi divergence based analysis. As applications, we show tighter security reductions for sampling discrete Gaussian distributions with smaller precomputed tables for BLISS signatures, and variants of learning with errors (LWE) problem and small integer solution (SIS) problem called k-LWE and k-SIS.
Katsuyuki Takashima, Atsushi Takayasu

### Black-Box Separations of Hash-and-Sign Signatures in the Non-Programmable Random Oracle Model

Abstract
A popular methodology of designing cryptosystems with practical efficiency is to give a security proof in the random oracle (RO) model. The work of Fischlin and Fleischhacker (Eurocrypt ’13) investigated the case of Schnorr signature (and generally, Fiat-Shamir signatures) and showed the reliance of RO model is inherent.
We generalize their results to a large class of “malleable” hash-and-sign signatures, where one can efficiently “maul”any two valid signatures between two signature instances with different public keys if it can get the difference between the secret keys. We follow the technique of Fischlin and Fleischhacker to show that the security of malleable hash-and-sign signature cannot be reduced to its related hard cryptographic problem without programming the RO. Our proof assumes the hardness of a one-more cryptographic problem (depending on the signature instantiation). Our result applies to single-instance black-box reductions, subsuming those reductions used in existing proofs.
Our framework not only encompasses Fiat-Shamir signatures as special cases, but also covers $$\Gamma$$-signature (Yao and Zhao, IEEE Transactions on Information Forensics and Security ’13), and other schemes which implicitly used malleable hash-and-sign signatures, including Boneh-Franklin identity-based encryption, and Sakai-Ohgishi-Kasahara non-interactive identity-based key exchange.
Zongyang Zhang, Yu Chen, Sherman S. M. Chow, Goichiro Hanaoka, Zhenfu Cao, Yunlei Zhao

### Rethinking Privacy for Extended Sanitizable Signatures and a Black-Box Construction of Strongly Private Schemes

Abstract
Sanitizable signatures, introduced by Ateniese et al. at ESORICS’05, allow to issue a signature on a message where certain predefined message blocks may later be changed (sanitized) by some dedicated party (the sanitizer) without invalidating the original signature. With sanitizable signatures, replacements for modifiable (admissible) message blocks can be chosen arbitrarily by the sanitizer. However, in various scenarios this makes sanitizers too powerful. To reduce the sanitizers power, Klonowski and Lauks at ICISC’06 proposed (among others) an extension that enables the signer to limit the allowed modifications per admissible block to a well defined set each. At CT-RSA’10 Canard and Jambert then extended the formal model of Brzuska et al. from PKC’09 to additionally include the aforementioned and other extensions. We, however, observe that the privacy guarantees of their model do not capture privacy in the sense of the original definition of sanitizable signatures. That is, if a scheme is private in this model it is not guaranteed that the sets of allowed modifications remain concealed. To this end, we review a stronger notion of privacy, i.e., (strong) unlinkability (defined by Brzuska et al. at EuroPKI’13), in this context. While unlinkability fixes this problem, no efficient unlinkable scheme supporting the aforementioned extensions exists and it seems to be hard to construct such schemes. As a remedy, in this paper, we propose a notion stronger than privacy, but weaker than unlinkability, which captures privacy in the original sense. Moreover, it allows to easily construct efficient schemes satisfying our notion from secure existing schemes in a black-box fashion.
David Derler, Daniel Slamanig

### Unique Signature with Short Output from CDH Assumption

Abstract
We give a simple and efficient construction of unique signature on groups equipped with bilinear map. In contrast to prior works, our proof of security is based on computational Diffie-Hellman problem in the random oracle model. Meanwhile, the resulting signature consists of only one group element. Due to its simplicity, security and efficiency, our scheme is suitable for those situations that require to overcome communication bottlenecks. Moreover, the unique signature is a building block for designing chosen-ciphertext secure cryptosystems and verifiable random functions, which have found many interesting applications in cryptographic protocol design.
Shiuan-Tzuo Shen, Amir Rezapour, Wen-Guey Tzeng

### Constructions of Unconditionally Secure Broadcast Encryption from Key Predistribution Systems with Trade-Offs Between Communication and Storage

Abstract
An $$(\le n,\le \omega )$$-one-time secure broadcast encryption schemes (BESs) allows a sender to specify any subset of receivers so that only the specified recievers can decrypt a ciphertext. In this paper, we first show an efficient construction of a BES with general ciphertext sizes. Specifically, we propose a generic construction of a BES from key predistribution systems (KPSs) when its ciphertext size is equal to integer multiple of the plaintext size, and our construction includes all known constructions. However, there are many possible combinations of the KPSs to realize the BES in our construction methodology, and therefore, we show that which combination is the best one in the sense that secret-key size can be minimized.
Deriving a tight bound on the secret-key size required for $$(\le n,\le \omega )$$-one-time secure BES with any ciphertext size still remains an open problem.Our result also means that we first show an upper bound on the size of secret keys for general ciphertext sizes.
Yohei Watanabe, Junji Shikata

### Backmatter

Weitere Informationen