International Association for Cryptologic Research

# IACR News Central

You can also access the full news archive.

Further sources to find out about changes are CryptoDB, ePrint RSS, ePrint Web, Event calender (iCal).

2014-08-14
00:17 [Pub][ePrint]

Searchable encryption allows an untrusted server to search

on 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]

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]

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]

We study the problem of privacy-preserving proofs on authenticated data in which a party receives data from a trusted source and is requested to prove statements over the data to third parties in a correct and private way, i.e., the third party learns no information on the data but is still assured that the claimed proof is valid. Our work particularly focuses on the challenging requirement that the third party should be able to verify the validity with respect to the specific data authenticated by the source -- even without having access to that source. This problem is motivated by various scenarios emerging from several application areas such as wearable computing, smart metering, or general business-to-business interactions. Furthermore, these applications also demand any meaningful solution to satisfy additional properties related to usability and scalability. First, third parties should be able to check proofs very efficiently. Second, the trusted source should be independent of the data processor: it simply (and possibly continuously) provides data, e.g., without knowing which statements will be proven. This paper formalizes the above three-party model, discusses concrete application scenarios, and introduces a new cryptographic primitive for proving NP relations where statements are authenticated by trusted sources. After discussing a generic approach to construct this primitive, we present a more direct and efficient realization that supports general-purpose NP relations. Our realization significantly improves over state-of-the-art solutions for this model, such as those based on Pinocchio (Oakland\'13), by at least three orders of magnitude.

00:17 [Pub][ePrint]

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]

SNOW 2.0 is a word oriented stream cipher that has been selected as a standard stream cipher on ISO/IEC 18033-4. One of the general attacks on the stream ciphers is Guess and Determine attack. Heuristic GD attack is GD attack that represents an algorithmic method to analysis the stream cipher with the variables of the same size. The results of HGD attack on TIPSY, SNOW 1.0 and SNOW 2.0 stream ciphers led to less complexity rather than previously known GD attacks. In this paper, the authors use of two auxiliary polynomials to improve HGD attack on SNOW 2.0. This attack reduces the complexity and the size of the guessed basis from O (2265) to O (2192) and 8 to 6, respectively, compared with previous ad-hoc and heuristic GD attacks.

00:17 [Pub][ePrint]

vanced Ecryption Standard (AES) and the arcfour pseudorandom func-

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

00:17 [Pub][ePrint]

In this paper we present MATor: a framework for rigorously assessing the degree of anonymity in the Tor network. The framework explicitly addresses how user anonymity is impacted by real-life characteristics of actually deployed Tor, such as its path selection algorithm, Tor consensus data, and the preferences and the connections of the user. The anonymity assessment is based on rigorous anonymity bounds that are derived in an extension of the AnoA framework (IEEE CSF 2013). We show how to apply MATor on Tor\'s publicly available consensus and server descriptor data, thereby realizing the first real-time anonymity monitor. Based on experimental evaluations of this anonymity monitor on Tor Metrics data, we propose an alternative path selection algorithm that provides stronger anonymity guarantees without decreasing the overall performance of the Tor network.

00:17 [Pub][ePrint]

We construct the first fully secure attribute based encryption (ABE) scheme that can handle access control policies expressible as polynomial-size circuits. Previous ABE schemes for general circuits were proved secure only in an unrealistic selective security model, where the adversary is forced to specify its target before seeing the public parameters, and full security could be obtained only by complexity leveraging, where the reduction succeeds only if correctly guesses the adversary\'s target string x*, incurring a 2^{|x^*|} loss factor in the tightness of the reduction.

At a very high level, our basic ABE scheme is reminiscent of Yao\'s garbled circuits, with 4 gadgets per gate of the circuit, but where the decrypter in our scheme puts together the appropriate subset of gate gadgets like puzzle pieces by using a cryptographic multilinear map to multiply the pieces together. We use a novel twist of Waters\' dual encryption methodology to prove the full security of our scheme. Most importantly, we show how to preserve the delicate information-theoretic argument at the heart of Waters\' dual system by enfolding it in an information-theoretic argument similar to that used in Yao\'s garbled circuits.

00:17 [Pub][ePrint]

We revisit the impossibility of a variety of cryptographic tasks including privacy and differential privacy with imperfect randomness. For traditional notions of privacy, such as security of encryption, commitment or secret sharing schemes, dramatic impossibility results are known [MP90,DOPS04]. In fact, they are true even if the imperfect source is modeled as a seemingly very \"nice and friendly\" Santha-Vazirani (SV) source. The SV source outputs a sequence of bits r_1,r_2,..., where each r_i has almost 1 full bit of fresh entropy conditioned on the previous bits r_1,...,r_{i-1}. Moreover, Bosley and Dodis [BD07] gave strong evidence that many traditional privacy tasks (e.g., encryption) inherently require an \"extractable\" source of randomness.

The common interpretation of these negative results is that traditional privacy is impossible even with \"very structured\" imperfect sources. Somewhat surprisingly, Dodis et al. [DLMV12] put a slight dent in this belief, by showing that non-trivial *differential* privacy is possible with SV sources. This suggested a qualitative gap between traditional and differential privacy, and left open the question if differential privacy is possible with more realistic (i.e., less structured) sources than the SV sources. Motivated by solving this question, we abstract and generalize prior techniques for showing impossibility results for achieving privacy with various imperfect sources of randomness. In particular, we introduce the concepts of separability and expressivity of a given imperfect source as a measure of its \"imperfectness\", and show the

following results:

(1) Separability implies expressivity;

(2) Low levels of expressivity (and, thus, separability) generically imply strong impossibility results for both traditional and *differential* privacy;

(3) Existing (and quantitatively improved!) impossibility results for traditional privacy with respect to known imperfect sources easily follow as corollaries of our unified framework; New results follow equally easily.

(4) Although, unsurprisingly, our new impossibility results for differential privacy (barely) miss the highly structured SV sources, they come back *extremely quickly* once the source becomes slightly more realistic. E.g., if a small number of bits r_i can be fully determined by the previous bits;

(5) Any imperfect source allowing (either traditional or differential) privacy admits a certain type of deterministic bit extraction. (This result is incomparable to the result of [BD07].)

Overall, our results unify and strengthen the belief that, for the most part, privacy with imperfect randomness is impossible, unless the source is (almost) deterministically extractable.

00:17 [Pub][ePrint]

This paper proposes KT-ORAM, a new hybrid ORAM-PIR construction, to preserve a client\'s access pattern to his/her outsourced data. The construction organizes the server storage as a $k$-ary tree with each node acting as a fully-functional PIR storage, and adopts a novel \\emph{delayed eviction} technique to optimize the eviction process. KT-ORAM is proved to preserve the data access pattern privacy with a negligibly-small failure probability of $O(N^{-\\log N})$. KT-ORAM requires only a constant-size local storage at the client side, and has an asymptotical communication cost of $O(\\frac{\\log^2 N}{\\log\\log N})$ (the best known asymptotical result of ORAM~\\cite{Kush12}) when $k=\\log N$. The communication cost of KT-ORAM is also compared with two state-of-the-art ORAM constructions, B-ORAM~\\cite{Kush12} and P-PIR~\\cite{MaBl14}, which share the same assumption of constant-size client-side storage as KT-ORAM, in practical scenarios. The results show that, KT-ORAM outperforms these constructions.