International Association for Cryptologic Research

IACR News Central

Get an update on changes of the IACR web-page here. For questions, contact newsletter (at) You can also receive updates via:

To receive your credentials via mail again, please click here.

You can also access the full news archive.

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

00:17 [Pub][ePrint] Privacy and Imperfect Randomness, by Yevgeniy Dodis and Yanqing Yao

  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] KT-ORAM: A Bandwidth-efficient ORAM Built on K-ary Tree of PIR Nodes, by Jinsheng Zhang and Qiumao Ma and Wensheng Zhang and Daji Qiao

  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.

21:17 [Pub][ePrint] Private Web Search with Constant Round Efficiency, by Heeyeon Joo and Myungsun Kim

  Web search is increasingly becoming an essential activity as it is frequently the most effective and convenient way of finding information. However, it can be a threat for the privacy of users because their queries may reveal their sensitive information. Private web search (PWS) solutions allow users to find information in the Internet while preserving their privacy. In particular, cryptography-based PWS (CB-PWS) systems provide strong privacy guarantees.

This paper introduces a constant-round CB-PWS protocol which remains computationally efficient, compared to known CB-PWS systems. Our construction is comparable to similar solutions regarding users\' privacy.

21:17 [Pub][ePrint] On the Limits of Computational Fuzzy Extractors, by Kenji Yasunaga and Kosuke Yuzawa

  Fuller et.~al (Asiacrypt 2013) studied on computational fuzzy extractors,

and showed, as a negative result, that the existence of a computational ``secure sketch\'\'

implies the existence of an information-theoretically secure sketch with slightly weaker parameters.

In this work, we show a similar negative result such that, under some computational assumption,

the existence of a computational fuzzy extractor also implies the existence of

an information-theoretic fuzzy extractor with slightly weaker parameters.

The assumption is that the generation procedure of the fuzzy extractor can be efficiently invertible.

This result implies that to circumvent the limitations of information-theoretic fuzzy extractors,

we need to employ computational fuzzy extractors in which the generation procedure cannot be efficiently invertible.

21:17 [Pub][ePrint] A Multi-Function Provable Data Possession Scheme in Cloud Computing, by Xiaojun Yu and Qiaoyan Wen

  In order to satisfy the different requirements of provable data possession in cloud computing, a multi-function provable data possession (MF-PDP) is proposed, which supports public verification, data dynamic, unlimited times verification, sampling verification. Besides, it is security in RO model and it is verification privacy under half trust model and can prevent from replacing attack and replay attack. The detail design is provided and the theory analysis

about the correct, security and performance are also described. The experiment emulation and compare analysis suggest the feasibility and advantage.

21:17 [Pub][ePrint] Adding Controllable Linkability to Pairing-Based Group Signatures For Free, by Daniel Slamanig and Raphael Spreitzer and Thomas Unterluggauer

  Group signatures, which allow users of a group to anonymously produce signatures on behalf of the group, are an important cryptographic primitive for privacy-enhancing applications. Over the years, various approaches to enhanced anonymity management mechanisms, which extend the standard feature of opening of group signatures, have been proposed.

In this paper we show how pairing-based group signature schemes (PB-GSSs) based on the sign-and-encrypt-and-prove (SEP) paradigm can be generically transformed in order to support one particular enhanced anonymity management mechanism, i.e., we propose a transformation that turns every such PB-GSS into a PB-GSS with controllable linkability. Basically, this transformation replaces the public key encryption scheme used for identity escrow within a group signature scheme with a modified all-or-nothing public key encryption with equality tests scheme (denoted AoN-PKEET$^*$) instantiated from the respective public key encryption scheme. Thereby, the respective trapdoor is given to the linking authority as a linking key. The appealing benefit of this approach in contrast to other anonymity management mechanisms (such as those provided by traceable signatures) is that controllable linkability can be added to PB-GSSs based on the SEP paradigm for free, i.e., it neither influences the signature size nor the computational costs for signers and verifiers in comparison to the scheme without this feature.

21:17 [Pub][ePrint] Key-policy Attribute-based Encryption for Boolean Circuits from Bilinear Maps, by Ferucio Laurentiu Tiplea and Constantin Catalin Dragan

  We propose the first Key-policy Attribute-based Encryption (KP-ABE) scheme for (monotone) Boolean circuits based on bilinear maps. The construction is based on secret sharing and just one bilinear map, and can be viewed as an extension of the KP-ABE scheme in [7]. Selective security of the proposed scheme in the standard model is proved, and comparisons with the scheme in [5] based on leveled multilinear maps, are provided. Thus, for Boolean circuits representing multilevel access structures, our KP-ABE scheme is more efficient than the one in [5].

21:17 [Pub][ePrint] SPOKE: Simple Password-Only Key Exchange in the Standard Model, by Michel Abdalla and Fabrice Benhamouda and David Pointcheval

  In this paper, we propose a simple and efficient password-only authenticated key exchange (PAKE) protocol with a proof of security in the standard model. In its most efficient instantiation, the new protocol has only two flows of communication and a total of 7 group elements and its proof of security is based on the plain DDH assumption. To achieve this goal, we first propose a variant of the Gennaro-Lindell/Katz-Ostrovsky-Yung (GL/KOY) PAKE protocol, in which the encryption schemes used to generate the first- and second-flow messages are only required to be semantically secure against plaintext-checking attacks (IND-PCA) and chosen-plaintext attacks (IND-CPA), respectively. Unlike semantic security against chosen-ciphertext attacks (IND-CCA), an IND-PCA adversary is only given access to an oracle which says whether or not a given ciphertext encrypts a given message. Next, we design a more efficient variant of the Cramer-Shoup encryption scheme with shorter ciphertexts together with an associated hash proof system and we prove its IND-PCA security under the plain DDH assumption. We believe that the new IND-PCA scheme is of independent interest, since it yields, in particular, the most efficient IND-CCA encryption scheme under plain DDH for small messages.

15:17 [Pub][ePrint] Recursive Trees for Practical ORAM, by Tarik Moataz and Erik-Oliver Blass and Guevara Noubir

  We present a general construction to reduce the communication cost of recent tree-based ORAMs. Contrary to trees with constant height and path lengths, our new construction r-ORAM provides varying, shorter path lengths. Accessing an element in the ORAM tree will have different communication cost depending on the location of the element. The main idea behind r-ORAM is a recursive ORAM tree structure, where nodes in the tree are roots of other trees. While this approach results in a worst-case access cost (tree height) at most as any recent tree-based ORAM, we demonstrate that the expected cost saving is around 35% for binary tree ORAMs. For a k-ary tree-based ORAM, we still can reduce cost with r-ORAM, e.g., 20% for k =4. Besides reducing communication cost, r-ORAM also reduces storage overhead on the server by 20%. To prove r-ORAM\'s soundness, we conduct a detailed overflow analysis. We stress that r-ORAM is general and can be applied to all recent tree ORAMs, both constant memory or poly-log client memory ORAMs.

06:17 [Pub][ePrint] DTKI: a new formalized PKI with no trusted parties, by Jiangshan Yu and Vincent Cheval and Mark Ryan

  The security of public key validation protocols for web-based applications has recently attracted attention because of weaknesses in the certificate authority model, and consequent attacks.

Recent proposals using public logs have succeeded in making certificate management more transparent and verifiable. How- ever, those proposals involve a fixed set of authorities which create a monopoly, and they have heavy reliance on trusted parties that monitor the logs.

We propose a distributed transparent key infrastructure (DTKI), which greatly reduces the monopoly of service providers and removes the reliance on trusted parties. In addition, this paper formalises the public log data structure and provides a formal analysis of the security that DTKI guarantees.

06:17 [Pub][ePrint] Adaptive versus Static Security in the UC Model, by Ivan Damgård and Jesper Buus Nielsen

  We show that for certain class of unconditionally secure protocols and

target functionalities, static security implies adaptive security in the UC

model. Similar results were previously only known for models with

weaker security and/or composition guarantees. The result is, for

instance, applicable to a wide range of protocols based on secret

sharing. It ``explains\'\' why an often used proof technique for such

protocols works, namely where the simulator runs in its head a copy of

the honest players using dummy inputs and generates a protocol

execution by letting the dummy players interact with the

adversary. When a new player $P_i$ is corrupted, the simulator

adjusts the state of its dummy copy of $P_i$ to be consistent with

the real inputs and outputs of $P_i$ and gives the state to the

adversary. Our result gives a characterisation of the cases where this

idea will work to prove adaptive security. As a special case,

we use our framework to give the first proof of adaptive security

of the seminal BGW protocol in the UC framework.