*00:17* [Pub][ePrint]
Accumulating Automata and Cascaded Equations Automata for Communicationless Information Theoretically Secure Multi-Party Computation, by Shlomi Dolev and Niv Giboa and Ximing Li
Information theoretically secure multi-party computation implies severe communication overhead among the computing participants, as there is a need to reduce the polynomial degree after each multiplication. In particular, when the input is (practically) unbounded, the number of multiplications and therefore the communication bandwidth among the participants may be practically unbounded. In some scenarios the communication among the participants should better be avoided altogether, avoiding linkage among the secret share holders. For example, when processes in clouds operate over streaming secret shares without communicating with each other, they can actually hide their linkage and activity in the crowd. An adversary that is able to compromise processes in the cloud may need to capture and analyze a very large number of possible shares.Consider a dealer that wants to repeatedly compute functions on a long file with the assistance of $m$ servers. The dealer does not wish to leak either the input file or the result of the computation to any of the servers. We investigate this setting given two constraints. The dealer is allowed to share each symbol of the input file among the servers and is allowed to halt the computation at any point. However, the dealer is otherwise stateless. Furthermore, each server is not allowed any communication beyond the shares of the inputs that it receives and the information it provides to the dealer during reconstruction.

We present a protocol in this setting for generalized string matching, including wildcards. We also present solutions for identifying other regular languages, as well as particular context free and context sensitive languages. The results can be described by a newly defined {\\em accumulating automata} and {\\em cascaded equations automata} which may be of an independent interest. As an application of {\\em accumulating automata} and {\\em cascaded equations automata}, secure and private repeated computations on a secret shared file among communicationless clouds are presented.

*00:17* [Pub][ePrint]
Attribute-Based Encryption Optimized for Cloud Computing, by Máté Horváth
In this work, we aim to make attribute-based encryption (ABE) more suitable for access control to data stored in the cloud. For this purpose, we concentrate on giving to the encryptor full control over the access rights, providing feasible key management even in case of multiple independent authorities, and enabling viable user revocation, which is essential in practice.Our main result is an extension of the decentralized CP-ABE scheme of Lewko and Waters with identity-based user revocation. Our revocation system is made feasible by removing the computational burden of a revocation event from the cloud service provider, at the expense of some permanent, yet acceptable overhead of the encryption and decryption algorithms run by the users. Thus, the computation overhead is distributed over a potentially large number of users, instead of putting it on a single party (e.g., a proxy server), which would easily lead to a performance bottleneck.

Besides describing our scheme, we also give a formal proof of its security in the generic bilinear group and random oracle models.

*00:17* [Pub][ePrint]
A Security Analysis of the Composition of ChaCha20 and Poly1305, by Gordon Procter
This note contains a security reduction to demonstrate that Langley\'s composition of Bernstein\'s ChaCha20 and Poly1305, as proposed for use in IETF protocols, is a secure authenticated encryption scheme.The reduction assumes that ChaCha20 is a PRF, that Poly1305 is epsilon-almost-Delta-universal, and that the adversary is nonce respecting.

*00:17* [Pub][ePrint]
Expressive and Secure Searchable Encryption in the Public Key Setting, by Zhiquan Lv and Cheng Hong and Min Zhang and Dengguo Feng
Searchable encryption allows an untrusted server to searchon encrypted data without knowing the underlying data contents. Traditional searchable encryption schemes focus only on single keyword or conjunctive keyword search. Several solutions have been recently proposed to design more expressive search criteria, but most of them are in the setting of symmetric key encryption. In this paper, based on the

composite-order groups, we present an expressive and secure asymmetric

searchable encryption (ESASE) scheme, which is the first that simultaneously supports conjunctive, disjunctive and negation search operations. We analyze the efficiency of ESASE and prove it is secure under the standard model. In addition, we show that how ESASE could be extended to support the range search and the multi-user setting.

*00:17* [Pub][ePrint]
Optimally Resilient and Adaptively Secure Multi-Party Computation with Low Communication Locality, by Nishanth Chandran and Wutichai Chongchitmate and Juan A. Garay and Shafi Goldwasser and Rafail Ost
Secure multi-party computation (MPC) has been thoroughly studied over the past decades. The vast majority of works assume a full communication pattern: every party exchanges messages with all the network participants over a complete network of point-to-point channels. This can be problematic in modern large scale networks, where the number of parties can be of the order of millions, as for example when computing on large distributed data.Motivated by the above observation, Boyle, Goldwasser, and Tessaro [TCC 2013] recently put forward the notion of communication locality, namely, the total number of point-to-point channels that each party uses in the protocol, as a quality metric of MPC protocols. They proved that assuming a public-key infrastructure (PKI) and a common reference string (CRS), an MPC protocol can be constructed for computing any n-party function, with communication locality O(log^c n) and round complexity O(log^{c\'} n), for appropriate constants c and c\'. Their protocol tolerates a static (i.e., non-adaptive) adversary corrupting up to t < (1/3- e) n parties for any given constant 0 < e < 1/3 . These results leave open the following questions:

(1) Can we achieve low communication locality and round complexity while tolerating adaptive adversaries? (2) Can we achieve low communication locality with optimal resiliency t < n/2?

In this work we answer both questions affirmatively. First, we consider the model from [TCC 2013], where we replace the CRS with a symmetric-key infrastructure (SKI). In this model we give a protocol with communication locality and round complexity polylog(n) (as in the [TCC 2013] work) which tolerates up to t < n/2 adaptive corruptions, under a standard intractability assumption for adaptively secure protocols, namely, the existence of trapdoor permutations whose domain has invertible sampling. This is done by using the SKI to derive a sequence of random hidden communication graphs among players. A central new technique then shows how to use these graphs to emulate a complete network in polylog(n) rounds while preserving the polylog(n) locality. Second, we show how we can even remove the SKI setup assumption at the cost, however, of increasing the communication locality (but not the round complexity) by a factor of \\sqrt{n}.

*00:17* [Pub][ePrint]
Practical Attribute Based Encryption: Traitor Tracing, Revocation, and Large Universe, by zhen Liu and Duncan S. Wong
In Ciphertext-Policy Attribute-Based Encryption (CP-ABE), a user\'s decryption key is associated with attributes which in general are not related to the user\'s identity, and the same set of attributes could be shared between multiple users. From the decryption key, if the user created a decryption blackbox for sale, this malicious user could be difficult to identify from the blackbox. Hence in practice, a useful CP-ABE scheme should have some tracing mechanism to identify this `traitor\' from the blackbox. In addition, being able to revoke compromised keys is also an important step towards practicality, and for scalability, the scheme should support an exponentially large number of attributes. However, none of the existing traceable CP-ABE schemes supports revocation or large attribute universe. In this paper, we construct the first practical CP-ABE which possesses these three important properties: (1) blackbox traceability, (2) revocation, and (3) supporting large universe.When compared with the latest traceable CP-ABE schemes, this new scheme achieves the same efficiency level, enjoying the sub-linear overhead of $O(\\sqrt{N})$, where $N$ is the number of users in the system, and attains the same security level, namely, the fully collusion-resistant traceability against policy-specific decryption blackbox, which is proven against selective adversaries in the standard model.

The scheme also supports large attribute universe, and attributes do not need to be pre-specified during the system setup. It is highly expressive and can take any monotonic access structures as ciphertext policies.

We also present the analogous results in the Key-Policy Attribute-Based Encryption (KP-ABE) setting, where users\' description keys are described by access policies and ciphertexts are associated with attributes.

We construct the first practical KP-ABE which possesses the three important properties: (1) blackbox traceability, (2) revocation, and (3) supporting large universe.

The scheme is highly expressive and can take any monotonic access structures as key policies,

and is efficient, namely, enjoys the sub-linear overhead of $O(\\sqrt{N})$ while supporting fully collusion-resistant blackbox traceability and revocation, and does not need to pre-specify the attributes during the system setup.

The scheme is proven selectively secure in the standard model.

*00:17* [Pub][ePrint]
Proving Correctness and Security of Two-Party Computation Implemented in Java in Presence of a Semi-Honest Sender, by Florian Böhl and Simon Greiner and Patrik Scheidecker
We provide a proof of correctness and security of a two-party-computation protocol based on garbled circuits and oblivious transfer in the presence of a semi-honest sender. To achieve this we are the first to combine a machine-assisted proof of correctness with advanced cryptographic primitives to prove security properties of Java code. The machine-assisted part of the proof is conducted with KeY, an interactive theorem prover.The proof includes a correctness result for the construction and evaluation of garbled circuits. This is particularly interesting since checking such an implementation by hand would be very tedious and error-prone. Although we stick to the secure two-party-computation of an n-bit AND in this paper, our approach is modular, and we explain how our techniques can be applied to other functions.

To prove the security of the protocol for an honest-but-curious sender and an honest receiver, we use the framework presented by Kuesters et al. for the cryptographic verification of Java programs. As part of our work, we add oblivious transfer to the set of cryptographic primitives supported by the framework. This is a general contribution beyond our results for concrete Java code.

*00:17* [Pub][ePrint]
The M3dcrypt Password Scheme, by Isaiah Makwakwa
M3dcrypt is a password authentication scheme built around the ad-vanced Ecryption Standard (AES) and the arcfour pseudorandom func-

tion. It uses up to 256-bit pseudorandom salt values and supports 48-byte passwords.