International Association
for Cryptologic Research

Secure Multiparty Computation (MPC) protocols allow a set of distrusting participants to securely compute a joint function

of their private inputs without revealing anything but the output of the function to each other. In 1991 Ostrovsky

and Yung introduced the \\emph{proactive security model}, where faults spread throughout the network, analogous

to the spread of a virus or a worm. More specifically, in the proactive security model, the adversary is not limited in the number of

parties it can corrupt but rather in the {\\em rate} of corruption with respect to a ``rebooting\'\' rate. In the same

paper, Ostrovsky and Yung showed that constructing a general purpose MPC protocol in the proactive security model is indeed feasible

when the rate of corruption is a constant fraction of the parties. Their result, however, was shown

only for stand-alone security and incurred a large polynomial communication overhead for each gate of the

computation. In contrast, protocols for ``classical\'\' MPC models (where the adversary is limited to corrupt in total up to a fixed

fraction of the parties) have seen dramatic progress in reducing communication complexity in recent years.

The question that we consider in this paper is whether continuous improvements of communication overhead in

protocols for the ``classical\'\' stationary corruptions model in the MPC literature can lead to communication complexity reductions in the

proactive security model as well. It turns out that improving communication complexity of proactive MPC protocols using modern

techniques encounters two fundamental roadblocks due to the nature of the mobile faults model: First, in the

proactive security model there is the inherent impossibility of ``bulk pre-computation\'\' to generate cryptographic material

that can be slowly consumed during protocol computation in order to amortize communication cost (the adversary can easily

discover pre-computed values if they are not refreshed, and refreshing is expensive); second, there is an apparent need for

double-sharing (which requires high communication overhead) of data in order to achieve proactive security guarantees.

Thus, techniques that were used to speed up classical MPC do not work, and new ideas are needed. That is exactly what we do in this paper: we show

a novel MPC protocol in the proactive security model that can tolerate a $\\frac13-\\epsilon$ (resp. $\\frac12-\\epsilon$) fraction of moving faults, is perfectly (resp. statistically) UC-secure, and

achieves near-linear communication complexity for each step of the computation. Our results match the asymptotic communication complexity of the best known results in the ``classical\'\' model

of stationary faults \\cite{DIK10}. One of the important building blocks that we introduce is a new near-linear

``packed\'\' proactive secret sharing (PPSS) scheme, where the amortized communication and computational cost of maintaining

each individual secret share is just a constant. We believe that our PPSS scheme might be of independent interest.

Submission: 15 September 2013
Notification: 15 January 2014
From February 28 to February 28
More Information: http://cfc-crypt.weebly.com/index.html

Submission: 15 September 2013
Notification: 15 January 2014
From February 28 to February 28
More Information: http://cfc-crypt.weebly.com/index.html

Submission: 1 January 2014
Notification: 15 April 2014
From August 26 to October 1
More Information: http://www.di.ens.fr/~fouque/cfp-cc

Submission: 31 July 2014
From August 31 to July 31
More Information: http://www.ijiss.org

I'm looking for a volunteer to edit the videos from TCC 2013. The data consists of about 30 DVDs, or about 100GB of video data. There are two DVDs for each session (the stage and the presentation screen), and they need to be re-encoded for streaming distribution on youtube. If we decide that this is too much, we might opt for only the presentation screen videos from the invited talks, but ideally I'd like to do the following: 1. split the VOB files into one file per talk. The files should be named in such a way that they can be matched to cryptodb, e.g., 24520.mp4 for http://www.iacr.org/cryptodb/data/paper.php?pubkey=24520 2. encode each file as AAC-LC audio with H.264 video, as described on https://support.google.com/youtube/answer/1722171?hl=en. 3. upload the resulting files to www.iacr.org so that they can be archived and uploaded to the IACR youtube channel. If interested, contact [email protected].

Submission: 10 September 2013
Notification: 31 October 2013
From November 27 to November 29
Location: Berlin, Germany
More Information: http://cardis.sec.t-labs.tu-berlin.de/index.html

IACR 2013 Election

The 2013 election is being held to fill three of nine IACR Director positions and all four Officer positions. The election will again be run electronically and further information will be available on the IACR website.

Nominations Are Now Open

Nominations are due by September 24, 2013. A nomination form is available at the elections page.

Election of Directors

The directors and officers whose terms are expiring are

• Mitsuru Matsui (director)
• Christof Paar (director)
• David Pointcheval (director)
• Bart Preneel (president)
• Christian Cachin (vice president)
• Greg Rose (treasurer)
• Martijn Stam (secretary)

Election Committee

• Michel Abdalla (Returning Officer)
• Josh Benaloh (Chair)
• Tom Berson

Name: Daniel Wichs
Topic: Cryptographic Resilience to Continual Information Leakage
Category: foundations

Description: In this thesis, we study the question of achieving cryptographic security on\r\ndevices that leak information about their internal secret state to an external attacker. This study is motivated by the prevalence of side-channel attacks, where\r\nthe physical characteristics of a computation (e.g. timing, power-consumption,\r\ntemperature, radiation, acoustics, etc.) can be measured, and may reveal useful information about the internal state of a device. Since some such leakage is\r\ninevitably present in almost any physical implementation, we believe that this\r\nproblem cannot just be addressed by physical countermeasures alone. Instead, it\r\nshould already be taken into account when designing the mathematical specication of cryptographic primitives and included in the formal study of their security.\r\nIn this thesis, we propose a new formal framework for modeling the leakage\r\navailable to an attacker. This framework, called the continual leakage model, assumes that an attacker can continually learn arbitrary information about the internal secret state of a cryptographic scheme at any point in time, subject only to the\r\nconstraint that the rate of leakage is bounded. More precisely, our model assumes\r\nsome abstract notion of time periods. In each such period, the attacker can choose\r\nto learn arbitrary functions of the current secret state of the scheme, as long as\r\nthe number of output bits leaked is not too large. In our solutions, cryptographic\r\nschemes will continually update their internal secret state at the end of each time\r\nperiod. This will ensure that leakage observed in dierent time periods cannot be\r\nmeaningfully combined to break the security of the cryptosystem. Although these\r\nupdates modify the secret state of the cryptosystem, the desired functionality of\r\nthe scheme is preserved, and the users can remain oblivious to these updates. We\r\nconstruct signatures, encryption, and secret sharing/storage schemes in this model.[...]

Submission: 20 February 2014
Notification: 30 April 2014
From August 7 to August 11
Location: Gyeongju, Korea
More Information: http://ants2014.kookmin.ac.kr

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

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.

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}

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.

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.

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.

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.

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.

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.

HTML version