*15:17* [Pub][ePrint]
Dynamic Searchable Symmetric Encryption, by Seny Kamara and Charalampos Papamanthou and Tom Roeder
Searchable symmetric encryption (SSE) allows a client to encrypt its data in such a way that this data can still be searched. The most immediate application of SSE is to cloud storage, where it enables a client to securely outsource its data to an untrusted cloud provider without sacrificing the ability to search over it. SSE has been the focus of active research and a multitude of schemes that achieve various levels of security and efficiency have been proposed. Any practical SSE scheme, however, should (at a minimum) satisfy the following properties: sublinear search time, security against adaptive chosen-keyword attacks, compact indexes and the ability to add and delete files efficiently. Unfortunately, none of the previously-known SSE constructions achieve all these properties at the same time. This severely limits the practical value of SSE and decreases its chance of deployment in real-world cloud storage systems.

To address this, we propose the first SSE scheme to satisfy all the properties outlined above. Our construction extends the inverted index approach (Curtmola et al., CCS 2006) in several non-trivial ways and introduces new techniques for the design of SSE. In addition, we implement our scheme and conduct a performance evaluation, showing that our approach is highly efficient and ready for deployment.

*15:17* [Pub][ePrint]
Generic Construction of Trace and Revoke Schemes, by Murat Ak, Aggelos Kiayias, Serdar Pehlivanoglu, Ali AydÄ±n Selcuk
Broadcast encryption (BE) is a cryptographic primitive that allows a broadcaster to encrypt a content to a specific group of users called privileged users and prevent revoked users from decrypting the content. In BE schemes, a group of users, called traitor s may leak their keys and allow illegal reception of the content. Such malicious users can be detected through traitor tracing (TT) schemes. The ultimate goal in a content distribution system would be combining traitor tracing and broadcast encryption (trace and revoke mechanisms) so that any receiver key found to be compromised in a tracing process would be revoked in the future transmissions.In this paper, we propose a generic method to transform a broadcast encryption scheme into a trace and revoke scheme. This transformation involves imposing a fingerprinting code over the underlying BE transmissions. In conventional usage of fingerprinting codes, this will inflate the public key size with an additional data linear in the length of the code. To restrain from such increase in public key size, we introduce a new property, called public samplability, of a fingerprinting code. This property enables us to simulate the code independently from the actual code generated for tracing purposes. We have proved this property for the open fingerprinting code of [10].

We have instantiated our generic transformation with the BE schemes of [4, 12, 19]: we introduce (i) trace and revoke schemes with constant private key size and short ciphertext size, (ii) the first ID-based trace and revoke scheme, (iii) the first publicly traceable scheme with constant private key size and (iv) the first trace and revoke scheme against pirate rebroadcasting attack in the public key setting.

*21:17* [Pub][ePrint]
Invertible Polynomial Representation for Private Set Operations, by Hyung Tae Lee and Hyunsook Hong and Jung Hee Cheon
In many private set operations, a set is represented by a polynomial over a ring $\\Z_\\sigma$ for a composite integer $\\sigma$, where $\\Z_\\sigma$ is the message space of some additive homomorphic encryption. While it is useful for implementing set operations with polynomial additions and multiplications, a polynomial representation has a limitation due to the hardness of polynomial factorizations over $\\Z_\\sigma$. That is, it is hard to recover a corresponding set from a resulting polynomial over $\\Z_\\sigma$ if $\\sigma$ is not a prime. In this paper, we propose a new representation of a set by a polynomial over $\\Z_\\sigma$, in which $\\sigma$ is a composite integer with {\\em known factorization} but a corresponding set can be efficiently recovered from a polynomial except negligible probability. Note that $\\Z_\\sigma[x]$ is not a unique factorization domain, so a polynomial may be written as a product of linear factors in several ways. To exclude irrelevant linear factors, we introduce a special encoding function which supports early abort strategy. As a result, our representation can be efficiently inverted by computing all the linear factors of a polynomial in $\\Z_\\sigma[x]$ whose root locates in the image of encoding function.

When we consider group decryption as in most private set operation protocols, inverting polynomial representations should be done without a single party possessing a factorization of $\\sigma$. This is very hard for Paillier\'s encryption whose message space is $\\Z_N$ with unknown factorization of $N$. Instead, we detour this problem by using Naccache-Stern encryption with message space $\\Z_\\sigma$ where $\\sigma$ is a smooth integer with public factorization. As an application of our representation, we obtain a constant round privacy preserving set union protocol. Our construction improves the complexity than the previous without honest majority assumption. It can be also used for constant round multi-set union protocol and private set intersection protocol even when decryptors do not possess a superset of the resulting set.

*21:17* [Pub][ePrint]
Cryptanalysis of a recent two factor authentication scheme , by Michael Scott
Very recently a scheme has been proposed by Wang and Ma for a robust smart-card based password authentication scheme, which claimsto be secure against a Smart Card security breach. In this short note we attempt an initial cryptanalysis of this scheme.

*18:17* [Pub][ePrint]
Optimizing Segment Based Document Protection (Corrected Version), by Miroslaw Kutylowski and Maciej Gebala
In this paper we provide a corrected and generalized version of the scheme presented at SOFSEM\'2012 in our paper ``Optimizing Segment Based Document Protection\'\' (SOFSEM 2012: Theory and Practice of Computer Science, LNCS 7147, pp. 566-575).

We develop techniques for protecting documents with restricted access rights. In these documents so called \\emph{segments} are encrypted. Different segments may be encrypted with different keys so that different user may be given different \\emph{access rights}. Hierarchy of access rights is represented by means of a directed acyclic \\emph{access graph}. The segments are encrypted with keys - where each key corresponds to one node in the access graph. The main feature of the access graph is that if there is an arch $\\overrightarrow{AB}$ in the graph, then all segments labelled with $B$ can be decrypted with the key corresponding to node $A$.

We show how to minimize the space overhead necessary for auxiliary keying information stored in the document. We provide an algorithm based on node disjoint paths in the access graph and key derivation based on one-way functions. Our current solution, based on maximal weighted matchings, provides an optimal solution for creating subdocuments, in case when frequency of creating each subdocument is known.

*18:17* [Pub][ePrint]
Functional Encryption with Bounded Collusions via Multi-Party Computation, by Sergey Gorbunov and Vinod Vaikuntanathan and Hoeteck Wee
We construct a functional encryption scheme secure against an a priori bounded polynomial number of collusions for the class of all polynomial-size circuits. Our constructions require only semantically secure public-key encryption schemes and pseudo-random generators computable by small-depth circuits (known to be implied bymost concrete intractability assumptions). For certain special cases such as predicate encryption schemes with public index, the construction requires only semantically secure encryption schemes, which is clearly the minimal necessary assumption.

Our constructions rely heavily on techniques from secure multiparty computation and randomized encodings. All our constructions are secure under a strong, adaptive simulation-based definition of functional encryption.