Get an update on changes of the IACR web-page here. For questions, contact newsletter (at) iacr.org. You can also receive updates via:
To receive your credentials via mail again, please click here.
You can also access the full news archive.
Motivated by advances in multi-core architectures, we present a new method for constructing sub-linear SSE schemes. Our approach is highly parallelizable and dynamic. With roughly a logarithmic number of cores in place, searches for a keyword w in our scheme execute in o(r) parallel time, where r is the number of documents containing keyword w (with more cores, this bound can go down to O(log n), i.e., independent of the result size r). Such time complexity outperforms the optimal \\theta(r) sequential search time--a similar bound holds for the updates.
Our scheme also achieves the following important properties: (a) it enjoys a strong notion of security, namely security against adaptive chosen-keyword attacks; (b) compared to existing sub-linear dynamic SSE schemes (e.g., Kamara, Papamanthou, Roeder, CCS \'12), updates in our scheme do not leak any information, apart from information that can be inferred from previous search tokens; (c) it can be implemented efficiently in external memory (with logarithmic I/O overhead). Our technique is simple and uses a red-black tree data structure; its security is proven in the random oracle model.
an L-bit public index IND and a message m, and
a secret key
is associated with a
Boolean predicate P. The secret key allows to decrypt the ciphertext and learn m iff P(IND)=1. Moreover, the scheme should be secure against collusions of users, namely,
given secret keys for polynomially many predicates, an adversary
learns nothing about the message
if none of the secret keys can individually decrypt the ciphertext.
attribute-based encryption schemes for circuits
of any arbitrary polynomial size, where the public parameters and
the ciphertext grow linearly with the depth of the circuit. Our construction
is secure under the standard learning with errors (LWE) assumption. Previous
constructions of attribute-based encryption were for Boolean formulas, captured
by the complexity class NC1.
In the course of our construction, we
present a new framework for constructing ABE schemes.
As a by-product of our framework, we obtain ABE schemes
for polynomial-size branching programs,
corresponding to the complexity class LOGSPACE, under
quantitatively better assumptions.
Unfortunately, we show that neither the model nor the specific PRNG construction proposed by Barak and Halevi meet this new property, despite meeting a weaker robustness notion introduced by BH. From a practical side, we also give a precise assessment of the security of the two Linux PRNGs, /dev/random and /dev/urandom. In particular, we show several attacks proving that these PRNGs are not robust according to our definition, and do not accumulate entropy properly. These attacks are due to the vulnerabilities of the entropy estimator and the internal mixing function of the Linux PRNGs. These attacks against the Linux PRNG show that it does not satisfy the \"robustness\" notion of security, but it remains unclear if these attacks lead to actual exploitable vulnerabilities in practice. Finally, we propose a simple and very efficient PRNG construction that is provably robust in our new and stronger adversarial model.
We therefore recommend to use this construction whenever a PRNG with input is used for cryptography.
We find that a central tension in an anonymous subscription service is the service provider\'s desire for a long epoch (to reduce server-side computation) versus users\' desire for a short epoch (so they can repeatedly \"re-anonymize\" their sessions). We balance this tension by having short epochs, but adding an efficient operation for clients who do not need unlinkability to cheaply re-authenticate themselves for the next time period.
We measure performance of a research prototype of our pro- tocol that allows an independent service to offer anonymous access to existing services. We implement a music service, an Android-based subway-pass application, and a web proxy, and show that adding anonymity adds minimal client latency and only requires 33 KB of server memory per active user.