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

2013-08-22
08:51 [Event][New]

Submission: 20 February 2014
From August 7 to August 11
Location: Gyeongju, Korea

03:17 [Pub][ePrint]

We introduce the notion of locally updatable and locally decodable codes (LULDCs). While, intuitively, updatability and error-correction seem to be contrasting goals, we show that for a suitable, yet meaningful, metric (which we call the Prefix Hamming metric), one can construct such codes. Informally, the Prefix Hamming metric allows the adversary to corrupt an arbitrary (constant fraction of) bits of the codeword subject to the constraint that he does not corrupt more than a $\\delta$ fraction of the $t$ most-recently changed\" bits of the codeword (for all $1\\leq t\\leq n$, where $n$ is the length of the codeword).

We first construct binary LULDCs for messages in $\\{0,1\\}^{k}$ with constant rate, update locality of $\\bigo(\\log^2 k)$, and read locality of $\\bigo(k^\\epsilon)$ for any constant $\\epsilon 2013-08-21 03:17 [Pub][ePrint] The soundness of language-level reasoning about programs relies on program execution adhering to the language semantics. However, in a distributed computation, when a value is sent from one party to another, the receiver faces the question of whether the value is *well-traced*, i.e., could it have produced by a computation that respects the language semantics? Otherwise, accepting the value may lead to bugs or vulnerabilities. Proof-Carrying Data (PCD) is a recently-introduced cryptographic mechanism that allows messages in a distributed computation to be accompanied by proof that the message, and the history leading to it, complies with a specified predicate. Using PCD, a verifier can be convinced that the predicate held throughout the distributed computation, even in the presence of malicious parties, and at a verification cost that is independent of the size of the computation producing the value. With a suitable choice of predicate, a program may use PCD to check that values received from the network are well-traced. Unfortunately, previous approaches to using PCD required tailoring a specialized predicate for each application, using an inconvenient formalism and with little methodological support. This work introduces a novel, PCD-based approach to enforcing language semantics in a distributed computation. We show how to construct a runtime, for an object-oriented language, which ensures that objects received from potentially untrusted parties are well-traced with respect to any prescribed class definitions. This means programmers can analyze language-level properties of distributed programs in a trusted setting, and then use the runtime to generically enforce the same properties in the presence of malicious parties, without needing to be aware of the the underlying cryptographic techniques. 03:17 [Pub][ePrint] Client-side deduplication is a very effective mechanism to reduce both storage and communication cost in cloud storage service. Halevi~\\emph{et al.} (CCS \'11) discovered security vulnerability in existing implementation of client-side deduplication and proposed a cryptographic primitive called proofs of ownership\'\' (PoW) as a countermeasure. In a proof of ownership scheme, any owner of the same file can prove to the cloud storage server that he/she owns that file in an efficient and secure manner, even if a bounded amount of any efficiently extractable information of that file has been leaked. We revisit Halevi~\\emph{et al.}\'s formulation of PoW and significantly improve the understanding and construction of PoW. Our contribution is twofold: \\begin{itemize} \\item First, we propose a generic and conceptually simple approach to construct \\emph{Privacy-Preserving} Proofs of Ownership scheme, by leveraging on well-known primitives (i.e. Randomness Extractor and Proofs of Retrievability) and technique (i.e. sample-then-extract). Our approach can be roughly described as \\textsf{Privacy-Preserving PoW = Randomness Extractor$+\$ Proofs of Retrievability}.

Based on our PoW scheme, we also construct a secure client-side deduplication method which is leakage resilient against bot outside attack and inside attack.

\\item

Second, in order to provide a better instantiation of Privacy-Preserving-PoW, we propose a novel design of randomness extractor which improves the state of art by reducing both the random seed length and entropy loss (i.e. the difference between the entropy of input and output) simultaneously.

\\end{itemize}

03:17 [Pub][ePrint]

Large scale data processing brings new challenges to the design of privacy-preserving protocols: how to meet the increasing requirements of speed and throughput of modern applications, and how to scale up smoothly when data being protected is big. Efficiency and scalability become critical criteria for privacy preserving protocols in the age of Big Data. In this paper, we present a new Private Set Intersection (PSI) protocol that is extremely efficient and highly scalable compared with existing protocols. The protocol is based on a novel approach that we call oblivious Bloom intersection. It has linear complexity and relies mostly on efficient symmetric key operations. It has high scalability due to the fact that most operations can be parallelized easily. The protocol has two versions: a basic protocol and an enhanced protocol, the security of the two variants is analyzed and proved in the semi-honest model and the malicious model respectively. A prototype of the basic protocol has been built. We report the result of performance evaluation and compare it against the two previously fastest PSI protocols. Our protocol is orders of magnitude faster than these two protocols. To compute the intersection of two million-element sets, our protocol needs only 41 seconds (80-bit security) and 339 seconds (256-bit security) on moderate hardware in parallel mode.

03:17 [Pub][ePrint]

We consider the problem of constructing anonymous credentials for use in a setting where the issuer of credentials is also the verifier, or where the issuer and verifier have a shared key. In this setting we can use message authentication codes (MACs) instead of public key signatures as the basis of the credential system.

To this end, we construct two algebraic MAC schemes in prime order groups, along with efficient protocols for issuing credentials, asserting possession a credential, and proving statements about the attributes.Security of the first scheme is proven in the generic group model, and we show that the second is secure under the decisional Diffie-Hellman (DDH) assumption, using a dual system-based approach.

Finally, we compare the efficiency of our new systems to two traditional credential systems, U-Prove and Idemix. We show that performance of the new schemes are competitive with U-Prove, and many times faster than Idemix. This brings together the best aspects of these two existing systems: the efficiency of U-Prove combined with the multi-show unlinkability of Idemix.

03:17 [Pub][ePrint]

In 2011, the authors [8] presented an adaptive oblivious transfer (OT) scheme based on Decisional 3-Party Diffie-Hellman (3DDH) assumption. The encryption used in the scheme is a combination of the Boneh-Boyen IBE scheme and a variation of the Hohenberger-Waters signature. The scheme is somewhat inefficient since it combines the two underlying schemes in a simple way. In this paper, we present an improvement of the OT scheme and show its security under 3DDH assumption. The proposed skills are helpful for designing and analyzing other cryptographic schemes.

03:17 [Pub][ePrint]

K.Yoneyama et al. introduces the Leaky Random Oracle Model at ProvSec2008, which only considers the leakage of the hash list of a hash function used by a cryptosystem due to various attacks caused by implementation or sloppy usages. However, an important fact is that such attacks not only leak the hash list of a hash function, but also leak other secret states outside the hash list of a cryptosystem (e.g. the secret key). In most cases, an adversary may be more interesting in revealing these secret states. Therefore, the Leaky Random Oracle Model is very limited because it only considers the leakage of the hash list and does not consider the leakage of other secret states. In this paper, we present a new leakage model based on the Leaky Random Oracle Model. In our new model, both the secret states (secret key) and the hash list can be leaked. Furthermore, the secret key can be leaked continually. Hence, our new model is more universal and stronger than the Leaky Random Oracle Model and some other leakage models. Furthermore, we give a provable security public key encryption scheme which is IND-CCA secure in our new model.

03:17 [Pub][ePrint]

In this paper we present a parallel approach to compute interleaved Montgomery multiplication. This approach is particularly suitable to be computed on 2-way single instruction, multiple data platforms as can be found on most modern computer architectures in the form of vector instruction set extensions. We have implemented this approach for tablet devices which run the x86 architecture (Intel Atom Z2760) using SSE2 instructions as well as devices which run on the ARM platform (Qualcomm MSM8960, NVIDIA Tegra 3 and 4) using NEON instructions. When instantiating modular exponentiation with this parallel version of Montgomery multiplication we observed a performance increase of more than a factor of 1.5 compared to

the sequential implementation in OpenSSL for the classical arithmetic logic unit on the Atom platform for 2048-bit moduli.

2013-08-20
15:40 [Service]

IACR and Springer are pleased to offer you free access to the Journal of Cryptology and the IACR proceedings volumes for CRYPTO, EUROCRYPT, ASIACRYPT, FSE, CHES, PKC, and TCC. Simply use the links below to access these publications.