*13:17* [Pub][ePrint]
Practical UC security with a Global Random Oracle, by Ran Canetti and Abhishek Jain and Alessandra Scafuro
We show that there exist commitment, zero-knowledge and general function evaluation protocols with universally composable security, in a model where all parties and all protocols have access to a single, global, random oracle and no other trusted setup. This model provides significantly stronger composable security guarantees than the traditional random oracle model of Bellare and Rogaway [CCS\'93] or even the common reference string model. Indeed, these latter models provide no security guarantees in the presence of arbitrary protocols that use the same random oracle (or reference string or hash function).Furthermore, our protocols are highly efficient. Specifically, in the interactive setting, our commitment and general computation protocols are much more efficient than the best known ones due to Lindell [Crypto\'11,\'13] which are secure in the common reference string model. In the non-interactive setting, our protocols are slightly less efficient than the best known ones presented by Afshar et al. [Eurocrypt \'14] but do away with the need to rely on a non-global (programmable) reference string.

*13:17* [Pub][ePrint]
Robust Secret Sharing Schemes Against Local Adversaries, by Allison Bishop Lewko and Valerio Pastro
We study robust secret sharing schemes in which between one third and one half of the players are corrupted. In this scenario, robust secret sharing is possible only with a share size larger than the secrets, and allowing a positive probability of reconstructing the wrong secret. In the standard model, it is known that at least $m+k$ bits per share are needed to robustly share a secret of bit-length $m$ with an error probability of $2^{-k}$; however, to the best of our knowledge, the efficient scheme that gets closest to this lower bound has share size $m+\\widetilde O (n+k)$, where $n$ is the number of players in the scheme.We show that it is possible to obtain schemes with close to minimal share size in a model of local adversaries, i.e. in which corrupt players cannot communicate between receiving their respective honest shares and submitting corrupted shares to the reconstruction procedure, but may coordinate before the execution of the protocol and can also gather information afterwards.

In this limited adversarial model, we prove a lower bound of roughly $m+k$ bits on the minimal share size, which is (somewhat surprisingly) similar to the lower bound in the standard model, where much stronger adversaries are allowed.

We then present an efficient secret sharing scheme that essentially meets our lower bound, therefore improving upon the best known constructions in the standard model by removing a linear dependence on the number of players. For our construction, we introduce a novel procedure that compiles an error correcting code into a new randomized one, with the following two properties: a single local portion of a codeword leaks no information on the encoded message itself, and any set of portions of a codeword reconstructs the message with error probability exponentially low in the set size.

*13:17* [Pub][ePrint]
Adaptive Multiparty Non-interactive Key Exchange Without Setup In The Standard Model, by Vanishree Rao
Non-interactive key exchange (NIKE) is a fundamental notion in Cryptography. This notion was introduced by Diffie and Hellman in 1976. They proposed the celebrated 2-party NIKE protocol and left open as a fascinating question, whether NIKE could be realized in the multiparty setting. NIKE has since then been an active area of research with an ultimate goal of obtaining best possible security in the multiparty setting. Although this has evaded researchers for many decades, advancements have been made through relaxations in multiple directions such as restricting to 3-parties, static/semi-static model (where the adversary needs to commit to the set of parties he wishes to be challenged upon ahead of time), random-oracle model, allowing initial setup, etc.In this work, we settle the longstanding open question: we present the first multiparty NIKE protocol that is adaptively secure with no setup and in the standard model.

Our construction is based on indistinguishability obfuscation and obliviously-patchable puncturable pseudorandom functions, a new notion that we introduce.

We employ novel techniques of using indistinguishability obfuscation, which are interesting in their own right and which we believe would find wider applications in other settings. One such technique pertains overcoming, the somewhat inherent, drawback of non-adaptivity of the puncturing technique introduced by Sahai and Waters [STOC\'14]. Central to this technique is our new notion of obliviously-patchable puncturable pseudorandom functions. We present a concrete construction of these pseudorandom functions using multilinear maps.

Note that pseudorandom functions amounts to an interactive assumption. We shall establish via a meta-reduction technique that, in natural settings, an interactive assumption is necessary (even with setup).

*13:17* [Pub][ePrint]
A Denial of Service Attack against Fair Computations using Bitcoin Deposits, by Jethro Beekman
Bitcoin supports complex transactions where the recipient of a transaction can be programmatically determined.Using these transactions, multi-party computation protocols that aim to ensure fairness among participants have been designed.

We present a Denial of Service attack against these protocols that results in a net loss for some or all of the honest parties involved, violating those fairness goals.

*13:17* [Pub][ePrint]
Low-Cost Concurrent Error Detection for GCM and CCM, by Xiaofei Guo and Ramesh Karri
In many applications, encryption alone does not provide enough security. To enhance security, dedicated authenticated encryption (AE) mode are invented. Galios Counter Mode (GCM) and Counter with CBC-MAC mode (CCM) are the AE modes recommended by the National Institute of Standards and Technology. To support high data rates, AE modes are usually implemented in hardware. However, natural faults reduce its reliability and may undermine both its encryption andauthentication capability. We present a low-cost concurrent error detection (CED) scheme for 7 AE architectures. The proposed technique explores idle cycles of the AE mode architectures. Experimental results shows that the performance overhead can be lower than 100% for all architectures depending on the workload. FPGA implementation results show that the hardware overhead in the 0.1-23.3% range and

the power overhead is in the 0.2-23.2% range. ASIC implementation results show that the hardware overhead in the 0.1-22.8% range and the power overhead is in the 0.3-12.6% range. The underlying block cipher and hash module need not have CED built in. Thus, it allows system designers to integrate block cipher and hash function intellectual property from different vendors.

*01:17* [Pub][ePrint]
Primary-Secondary-Resolver Membership Proof Systems, by Moni Naor and Asaf Ziv
We consider Primary-Secondary-Resolver Membership Proof Systems (PSR for short) and show different constructions of that primitive. A PSR system is a 3-party protocol, where we have a primary, which is a trusted party which commits to a set of members and their values, then generates a public and secret keys in order for secondaries (provers with knowledge of both keys) and resolvers (verifiers who only know the public key) to engage in interactive proof sessions regarding elements in the universe and their values. The motivation for such systems is for constructing a secure Domain Name System (DNSSEC) that does not reveal any unnecessary information to its clients.We require our systems to be complete, so honest executions will result in correct conclusions by the resolvers, sound, so malicious secondaries cannot cheat resolvers, and zero-knowledge, so resolvers will not learn additional information about elements they did not query explicitly. Providing proofs of membership is easy, as the primary can simply precompute signatures over all

the members of the set. Providing proofs of non-membership, i.e. a

denial-of-existence mechanism, is trickier and is the main issue in constructing PSR systems.

We provide three different strategies to construct a denial of existence mechanism. The first uses a set of cryptographic keys for all elements of the universe which are not members, which we implement using hierarchical identity based encryption and a tree based signature scheme. The second construction uses cuckoo hashing with a stash, where in order to prove non-membership, a

secondary must prove that a search for it will fail, i.e. that it is not in the tables or the stash of the cuckoo hashing scheme. The third uses a verifiable ``random looking\'\' function which the primary evaluates over the set of members, then signs the values lexicographically and secondaries then use those signatures to prove to resolvers that the value of the non-member was not

signed by the primary. We implement this function using a weaker variant of verifiable random/unpredictable functions and pseudorandom functions with interactive zero knowledge proofs.

For all three constructions we suggest fairly efficient implementations, of order comparable to other public-key operations such as signatures and encryption. The first approach offers perfect ZK and does not reveal the size of the set in question, the second can be implemented based on very solid cryptographic assumptions and uses the unique structure of cuckoo hashing, while the last technique has the potential to be highly efficient, if one could construct an efficient and secure VRF/VUF or if one is willing to live in the random oracle model.

*03:17* [Pub][ePrint]
How Secure is TextSecure?, by Tilman Frosch and Christian Mainka and Christoph Bader and Florian Bergsma and Joerg Schwenk and Thorsten Holz
Instant Messaging has attracted a lot of attention by users for both private and business communication and has especially gained popularity as low-cost short message replacement on mobile devices. However, most popular mobile messaging apps do not provide end-to-end security. Press releases about mass surveillance performed by intelligence services such as NSA and GCHQ lead many people looking for means that allow them to preserve the security and privacy of their communication on the Internet. Additionally fueled by Facebook\'s acquisition of the hugely popular messaging app WhatsApp, alternatives that claim to provide secure communication experienced a significant increase of new users.A messaging app that has attracted a lot of attention lately is TextSecure, an app that claims to provide secure instant messaging and has a large number of installations via Google\'s Play Store. It\'s protocol is part of Android\'s most popular aftermarket firmware CyanogenMod. In this paper, we present the first complete description of TextSecure\'s complex cryptographic protocol and are the first to provide a thorough security analysis of TextSecure. Among other findings, we present an Unknown Key-Share Attack on the protocol, along with a mitigation strategy, which has been acknowledged by TextSecure\'s developers. Furthermore, we formally prove that---if our mitigation is applied---TextSecure\'s push messaging can indeed achieve the goals of authenticity and confidentiality.