*18:17* [Pub][ePrint]
Dual System Groups and its Applications --- Compact HIBE and More, by Jie Chen and Hoeteck Wee
We introduce the notion of *dual system groups*.- We show how to derive compact HIBE by instantiating the dual system framework in Waters (Crypto \'09) and Lewko and Waters (TCC \'10) with dual system groups. Our construction provides a unified treatment of the prior compact HIBE schemes from static assumptions.

- We show how to instantiate dual system groups under the decisional subgroup assumption in composite-order groups and the decisional linear assumption ($d$-LIN) in prime-order groups. Along the way, we provide new tools for simulating properties of composite-order bilinear groups in prime-order groups. In particular, we present new randomization and parameter-hiding techniques in prime-order groups.

Combining the two, we obtain a number of new encryption schemes, notably

- a new construction of IBE in prime-order groups with shorter parameters;

- a new construction of compact HIBE in prime-order

groups whose structure closely mirrors the selectively secure HIBE

scheme of Boneh, Boyen and Goh (Eurocrypt \'05);

- a new construction of compact spatial encryption in prime-order groups.

*15:17* [Pub][ePrint]
Introducing Fault Tolerance into Threshold Password-Authenticated Key Exchange, by Ivan Pryvalov and Aniket Kate
A threshold password-authenticated key exchange (T-PAKE) protocol allows a set of n servers to collectively authenticate a client with a human-memorizable password such that any subset of size greater than a threshold t can authenticate the client, while smaller subsets of servers learn no information about the password. With its protection against offline dictionary attacks, T-PAKE provides a practical solution for an important real-life problem with password authentication. However, the proposed T-PAKE constructions cannot tolerate any misbehavior---not even a crash---by a participating server during a protocol execution; the protocol has to be re-executed until all participating servers behave correctly. This not only presents a fault management challenge for the servers, but more importantly also can leave the clients frustrated.In this work, we present a novel T-PAKE protocol which solves the above fault management problem by employing a batched and offline phase of distributed key generation (DKG). Our protocol is secure against any malicious behavior from up to any t < n servers under the decisional Diffie-Hellman assumption in the random oracle model, and it ensures protocol completion for t < n/2. Moreover, it is efficient (16n + 7 exponentiations per client, 20n + 14 per server), performs explicit authentication in three communication rounds, and requires a significantly lesser number of broadcast rounds compared to previous secure T-PAKE constructions. We have implemented our protocol, and have verified its efficiency using micro-benchmark experiments. Our experimental results show that the protocol only introduces a computation overhead of few milliseconds at both the client and the server ends, and it is practical for use in real-life authentication scenarios.

*06:17* [Pub][ePrint]
Zero-Knowledge Password Policy Checks and Verifier-Based PAKE, by Franziskus Kiefer and Mark Manulis
We propose the concept of Zero-Knowledge Password Policy Checks (ZKPPC) to enable remote registration of client passwords without their actual transmission to the server. The ZKPPC protocol executed as part of the client registration process allows the client to prove compliance of the chosen password with the password policy defined by the server. The main benefit of ZKPPC-based password registration is that it guarantees that passwords can never be processed nor stored in clear on the server side. At the end of the registration phase the server only receives and stores some verification information that can later be used for authentication in suitable Verifier-based Password Authenticated Key Exchange (VPAKE) protocols.To this end, we first formalize the requirements of ZKPPC protocols and propose a general framework for their construction in the standard model using randomised password hashing and set membership proofs. We design a suitable encoding scheme for password characters and show how to express password policies to allow the adoption of set membership proofs. Finally, we present a concrete ZKPPC-based registration protocol that is based on efficient Pedersen commitments and corresponding proofs, and analyse its performance.

To complete the ZKPPC-based registration and authentication framework we propose a concrete VPAKE protocol, where the server can use the obtained verification information from the ZKPPC-based registration phase to subsequently setup secure communication sessions with the client. Our VPAKE protocol follows the recent framework for the construction of such protocols and is secure in the standard model.

*06:17* [Pub][ePrint]
Key Derivation From Noisy Sources With More Errors Than Entropy, by Ran Canetti and Benjamin Fuller and Omer Paneth and Leonid Reyzin
Fuzzy extractors convert a noisy source of entropy into a consistent uniformly-distributed key. In the process of eliminating noise, they lose some of the entropy of the original source---in the worst case, as much as the logarithm of the number of correctable error patterns. We call what is left after this worst-case loss the minimum usable entropy. Unfortunately, this quantity is negative for some sources that are important in practice. Most known approaches for building fuzzy extractors work in the worst case and cannot be used when the minimum usable entropy is negative.We construct the first fuzzy extractors that work for a large class of distributions that have negative minimum usable entropy. Their security is computational. They correct Hamming errors over a large alphabet. In order to avoid the worst-case loss, they necessarily restrict distributions for which they work.

Our first construction requires high individual entropy of a constant fraction of symbols, but permits symbols to be dependent. Our second construction requires a constant fraction of symbols to have a constant amount of entropy conditioned on prior symbols. The constructions can be implemented efficiently based on number-theoretic assumptions or assumptions on cryptographic hash functions.