*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.

*00:17* [Pub][ePrint]
Fully Secure Attribute Based Encryption from Multilinear Maps, by Sanjam Garg and Craig Gentry and Shai Halevi and Mark Zhandry
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]
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.

*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.