friends [entries|archive|friends|userinfo]

## Arvind Narayanan's journal

Research Blog | Web page

Decentralized Traceable Attribute-Based Signatures, by Ali El Kaafarani and Essam Ghadafi and Dalia [Dec. 11th, 2013|01:18 pm]
 iacr_eprint

http://eprint.iacr.org/2013/828

Attribute-based signatures allow a signer owning a set of attributes to anonymously sign a message w.r.t.\ some signing policy. A recipient of the signature is convinced that a signer with a set of attributes satisfying the signing policy has indeed produced the signature without learning the identity of the signer or which set of attributes was used in the signing.

Traceable attribute-based signatures add anonymity revocation mechanisms to attribute-based signatures whereby a special tracing authority equipped with a secret key is capable of revealing the identity of the signer. Such a feature is important in settings where accountability and abuse prevention are required.

In this work, we first provide a formal security model for traceable attribute-based signatures. Our focus is on the more practical case where attribute management is distributed among different authorities rather than relying on a single central authority.
By specializing our model to the single attribute authority setting, we overcome some of the shortcomings of the existing model for the same setting.

Our second contribution is a generic construction for the primitive which achieves a strong notion of security. Namely, it achieves CCA anonymity and its security is w.r.t.\ adaptive adversaries. Moreover, our framework permits expressive signing polices.
Finally, we provide some instantiations of the primitive whose security reduces to falsifiable intractability assumptions and without relying on idealized assumptions.

cusp: Dictionary.com Word of the Day [Dec. 11th, 2013|12:00 am]
 dictionary_wotd

cusp: a point or pointed end.

Seyferts Sextet [Dec. 11th, 2013|06:05 am]
 apod

http://antwrp.gsfc.nasa.gov/apod/ap131210.html

What will survive this battle of the galaxies?

My First 1000000 Years [Dec. 10th, 2013|04:48 pm]
 brianhayes

http://bit-player.org/2013/my-first-1000000-years

http://bit-player.org/?p=1608

Limites
Hay una línea de Verlaine que no volveré a recordar,
Hay una calle próxima que está vedada a mis pasos,
Hay un espejo que me ha visto por última vez,
Hay una puerta que he cerrado hasta el fin del mundo.
Entre los libros de mi biblioteca (estoy viéndolos)
Hay alguna que ya nunca abriré.
Este verano cumpliré cincuenta años:
La muerte me desgasta, incesante.
—Jorge Luis Borges, 1923

Limits
There is a line of Verlaine I shall not recall again.
There is a nearby street forbidden to my steps.
There is a mirror that has seen me for the last time.
There is a door I have closed until the end of the world.
Among the books in my library (I am looking at them now)
There are some I'll never open again.
This summer I complete my fiftieth year.
Death wears me down, incessantly.
—Jorge Luis Borges, 1923


Passing half a century is a landmark for those who count on 10 fingers, but as a bit-player I celebrate powers of 2. Today I turn 26, which is a mega-milestone: 10000002 years. It’s a special occasion in several ways. Need I point out that it’s the last power of 2 I’ll ever see? Also, other than 0 and 1, it’s the only sixth power I’ll visit in my lifespan, and hence it is the only age that’s both a square and a cube.

As a young man—well shy of 50—I admired that poem by Borges, but as I grow older I find its mood of lugubrious foreboding less attractive. Yes, it’s true: There is a line of Borges I’ll never read again. But if my time is so limited, I shouldn’t be spending too much of it stuck in a tight loop, rereading the same lamentations over and over. Let the last time pass; I’ll move on to something new—something I haven’t yet done for the first time.

Life is all too full of never-to-be-repeated moments, right from the outset. Even the silly numerology of birthdays makes this apparent. Long before I reached my last power of 2, I celebrated my last Bell birthday (52), my last Catalan birthday (42), my last perfect birthday (28), my last factorial birthday (24), my last pair of birthdays satisfying $$x^m – y^n = 1$$ ($$2^3 = 8, 3^2 = 9$$). Never again will my age be an even prime number, a multiplicative identity, an additive identity. But I can live with that!

And I still have a few treats to look forward to. In a couple of years I come to my next triangular birthday—and that one may not be my last. Then of course there’s $$3^4 = 9^2$$. At the end of my eighties there’s a Fibonacci waiting for me, if I can make it. And, nearer at hand, I have marked my calendar for May 22, 2018, when I will celebrate my 25,000th spin around the earth’s axis. Maybe I should try to spend the day in orbit.

NSA Spying on Online Gaming Worlds [Dec. 10th, 2013|03:08 pm]
 bruce_schneier

https://www.schneier.com/blog/archives/2013/12/nsa_spying_on_o.html

The NSA is spying on chats in World of Warcraft and other games. There's lots of information -- and a good source document. While it's fun to joke about the NSA and elves and dwarves from World of Warcraft, this kind of surveillance makes perfect sense. If, as Dan Geer has pointed out, your assigned mission is to ensure that something never happens, the only way you can be sure that something never happens is to know everything that does happen. Which puts you in the impossible position of having to eavesdrop on every possible communications channel, including online gaming worlds.

One bit (on page 2) jumped out at me:

The NMDC engaged SNORT, an open source packet-sniffing software, which runs on all FORNSAT survey packet data, to filter out WoW packets. GCHQ provided several WoW protocol parsing scripts to process the traffic and produce Warcraft metadata from all NMDC FORNSAT survey.

NMDC is the New Mission Development Center, and FORNSAT stands for Foreign Satellite Collection. MHS, which also appears in the source document, stands for -- I think -- Menwith Hill Station, a satellite eavesdropping location in the UK.

Since the Snowden documents first started being released, I have been saying that while the US has a bigger intelligence budget than the rest of the world's countries combined, agencies like the NSA are not made of magic. They're constrained by the laws of mathematics, physics, and economics -- just like everyone else. Here's an example. The NSA is using Snort -- an open source product that anyone can download and use -- because that's a more cost-effective tool than anything they can develop in-house.

ochlophobia: Dictionary.com Word of the Day [Dec. 10th, 2013|12:00 am]
 dictionary_wotd

ochlophobia: an abnormal fear of crowds.

Comet Lovejoy over a Windmill [Dec. 10th, 2013|06:46 am]
 apod

http://antwrp.gsfc.nasa.gov/apod/ap131209.html

Lovejoy continues to be an impressive camera comet.

Bitcoin Explanation [Dec. 9th, 2013|05:33 pm]
 bruce_schneier

https://www.schneier.com/blog/archives/2013/12/bitcoin_explana.html

This is the best explanation of the Bitcoin protocol that I have read.

calorifacient: Dictionary.com Word of the Day [Dec. 9th, 2013|12:00 am]
 dictionary_wotd

calorifacient: (of foods) producing heat.

Everest Panorama from Mars [Dec. 9th, 2013|05:20 am]
 apod

http://antwrp.gsfc.nasa.gov/apod/ap131208.html

If you could stand on Mars -- what might you see? Scroll right to find out.

hardihood: Dictionary.com Word of the Day [Dec. 8th, 2013|12:00 am]
 dictionary_wotd

hardihood: boldness or daring; courage.

Naked Eye Nova Centauri 2013 [Dec. 8th, 2013|06:08 am]
 apod

http://antwrp.gsfc.nasa.gov/apod/ap131207.html

Brightest stellar beacons of the constellation Centaurus,

jocose: Dictionary.com Word of the Day [Dec. 7th, 2013|12:00 am]
 dictionary_wotd

jocose: given to or characterized by joking.

Gamma Ray Earth and Sky [Dec. 7th, 2013|05:48 am]
 apod

http://antwrp.gsfc.nasa.gov/apod/ap131206.html

For an Earth-orbiting gamma-ray telescope,

Friday Squid Blogging: Hoax Squid-Like Creature [Dec. 6th, 2013|10:33 pm]
 bruce_schneier

https://www.schneier.com/blog/archives/2013/12/friday_squid_bl_403.html

The weird squid-like creature floating around Bristol Harbour is a hoax.

As usual, you can also use this squid post to talk about the security stories in the news that I haven't covered.

Bruce Schneier Facts T-Shirts [Dec. 6th, 2013|08:16 pm]
 bruce_schneier

https://www.schneier.com/blog/archives/2013/12/bruce_schneier_5.html

0-Day Clothing has taken 25 Bruce Schneier Facts and turned them into T-shirts just in time for Christmas.

New Book: Carry On [Dec. 6th, 2013|08:47 pm]
 bruce_schneier

https://www.schneier.com/blog/archives/2013/12/new_book_carry.html

I have a new book. It's Carry On: Sound Advice from Schneier on Security, and it's my second collection of essays. This book covers my writings from March 2008 to June 2013. (My first collection of essays, Schneier on Security, covered my writings from April 2002 to February 2008.)

There's nothing in this book that hasn't been published before, and nothing you can't get free off my website. But if you're looking for my recent writings in a convenient-to-carry hardcover-book format, this is the book for you.

I'm also happy with the cover.

The Kindle and Nook versions are available now, and they're 50% off for some limited amount of time.

Unfortunately, the paper book isn't due in stores -- either online or brick-and-mortar -- until 12/27, which makes it a pretty lousy Christmas gift, though Amazon and B&N both claim it'll be in stock there on December 16. And if you don't mind waiting until after the new year, I will sell you a signed copy of the book here.

Suggestions for a title of my third collection of essays, to be published in five-ish years, are appreciated.

Errorless Smooth Projective Hash Function based on LWE, by Olivier Blazy and Céline Chevalier and Lé [Dec. 6th, 2013|08:42 pm]
 iacr_eprint

http://eprint.iacr.org/2013/821

Smooth Projective Hash Functions are one of the base tools to build
interactive protocols; and this notion has lead to the construction of numerous protocols enjoying strong security notions, such as the security in the Bellare-Pointcheval-Rogaway (BPR) model or even Universal Composability (UC).

Yet, the construction of SPHF has been almost limited to discrete-logarithm or pairing type assumptions up to now. This stands in contrast with domains such as homomorphic encryption or functional encryption, where Lattice Based Cryptography has already caught up and overtook discrete-log/pairing based cryptography. So far, work in the direction of UC based on lattices is almost restricted to a paper from Peikert, Vaikuntanathan, and Waters (Crypto 2008) dealing with Oblivious Transfer in the UC framework, and work in the direction of password-authenticated key exchange protocols (PAKE) to one from
Katz and Vaikuntanathan (Asiacrypt 2009) on a 3-round Password-Authenticated Key Exchange, but restraining itself to the BPR model. It seems that dealing with errors in those contexts is not as easy as it is for encryption.
In this work, we identify the problem at its source, namely, the lattice version of Diffie-Hellman key exchange protocol: the key greement is only approximate. We explicit a simple folklore trick to obtain true, errorless, one-round key exchange from LWE. We then show that this trick can be adapted to various lattice encryption schemes, leading, with some technicalities, to errorless SPHF's. From there, we derive three new results, namely the first lattice-based following protocols: a one-round PAKE secure in the BPR model, a 3-round PAKE secure in the UC model, and a UC commitment scheme, all of them based on SIS and LWE assumptions.

Leakage Resilient Fully Homomorphic Encryption, by Alexandra Berkoff and Feng-Hao Liu [Dec. 6th, 2013|08:42 pm]
 iacr_eprint

http://eprint.iacr.org/2013/822

We construct the first leakage resilient variants of fully homomorphic encryption (FHE) schemes. Our leakage model is bounded adaptive leakage resilience. We first construct a leakage- resilient leveled FHE scheme, meaning the scheme is both leakage resilient and homomorphic for all circuits of depth less than some pre-established maximum set at the time of key generation. We do so by applying ideas from recent works analyzing the leakage resilience of public key encryption schemes based on the decision learning with errors (DLWE) assumption to the Gentry, Sahai and Waters ([17]) leveled FHE scheme. We then move beyond simply leveled FHE, removing the need for an a priori maximum circuit depth, by presenting a novel way to combine schemes. We show that by combining leakage resilient leveled FHE with multi-key FHE, it is possible to create a leakage resilient scheme capable of homomorphically evaluating circuits of arbitrary depth, with a bounded number of distinct input ciphertexts.

Another Look at XCB, by {Debrup Chakraborty and Vicente Hernandez-Jimenez and Palash Sarkar [Dec. 6th, 2013|08:42 pm]
 iacr_eprint

http://eprint.iacr.org/2013/823

XCB is a tweakable enciphering scheme (TES) which was first proposed in 2004. The scheme was modified in 2007. We call these
two versions of XCB as XCBv1 and XCBv2 respectively. XCBv2 was later proposed as a standard for encryption of sector oriented
storage media in IEEE-std 1619.2 2010. There is no known proof of security for XCBv1 but the authors provided a concrete security bound for XCBv2 and
a "proof" for justifying the bound. In this paper we show that XCBv2 is not secure as a TES by showing an easy distinguishing attack on it.
For XCBv2 to be secure, the message space should contain only messages whose lengths are multiples of the block length of the block cipher.
For such restricted message spaces also the bound that the authors claim is not justified. We show this by pointing out some errors in the proof.
We provide a new security bound for XCBv2, and this bound is much worse than that has been claimed by the authors. We also for the first time
provide a concrete security bound for XCBv1. The new bounds shows that both XCBv1 and XCBv2 are worse in terms of security compared
to all TES for which a concrete security bound is known.

Fair and Efficient Secure Multiparty Computation with Reputation Systems, by Gilad Asharov and Yehud [Dec. 6th, 2013|08:42 pm]
 iacr_eprint

http://eprint.iacr.org/2013/824

A reputation system for a set of entities is essentially a list of scores that provides a measure of the reliability of each entity in the set. The score given to an entity can be interpreted (and in the reputation system literature it often is~\cite{FRS}) as the probability that an entity will behave honestly. In this paper, we ask whether or not it is possible to utilize reputation systems for carrying out secure multiparty computation. We provide formal definitions of secure computation in this setting, and carry out a theoretical study of feasibility. We present almost tight results showing when it is and is not possible to achieve \emph{fair} secure computation in our model. We suggest applications for our model in settings where some information about the honesty of other parties is given. This can be preferable to the current situation where either an honest majority is arbitrarily assumed, or a protocol that is secure for a dishonest majority is used and the efficiency and security guarantees (including fairness) of an honest majority are not obtained.

EPCGen2 Pseudorandom Number Generators: Analysis of J3Gen, by Alberto Peinado and Jorge Munilla and [Dec. 6th, 2013|08:42 pm]
 iacr_eprint

http://eprint.iacr.org/2013/825

This paper analyzes the cryptographic security of J3Gen, a
promising pseudo random number generator for low-cost passive RFID
tags. Although J3Gen has been shown to fulfill the randomness
criteria set by the EPCglobal Gen2 standard and is intended for
security applications, we describe here two cryptanalytic attacks
which question its security claims: i) a probabilistic attack
based on solving linear equation systems, and ii) a
deterministic attack based on the output sequence decimation.
Numerical results, supported by simulations, show that for the
specific recommended values of the configurable parameters, a low
number of intercepted output bits are enough to crytanalyze J3Gen.
We then make some recommendations which address these issues.

Secure multi-party data analysis: end user validation and practical experiments, by Dan Bogdanov and [Dec. 6th, 2013|08:42 pm]
 iacr_eprint

http://eprint.iacr.org/2013/826

Research papers on new secure multi-party computation protocols
rarely confirm the need for the developed protocol with its end users.
One challenge in the way of such validation is that it is hard to explain
the benefits of secure multi-party computation to non-experts.
We present a method that we used to explain the application
models of secure multi-party computation to a diverse group of end users
in several professional areas. In these interviews, we learned that
the potential users were curious about the possibility of using
secure multi-party computation to share and statistically analyse
private data. However, they also had concerns on how the new
technology will change the data analysis processes.
Inspired by this, we implemented a secure multi-party
computation prototype that calculates statistical functions in the same way as
popular data analysis packages like R, SAS, SPSS and Stata.
Finally, we validated the practical feasibility of this application by conducting
an experimental study that combined tax records with education records.

Lower Bounds in the Hardware Token Model, by Shashank Agrawal and Prabhanjan Ananth and Vipul Goyal [Dec. 6th, 2013|08:42 pm]
 iacr_eprint

http://eprint.iacr.org/2013/827

We study the complexity of secure computation in the tamper-proof hardware token model. Our main focus is on non-interactive unconditional two-party computation using bit-OT tokens, but we also study computational security with stateless tokens that have more complex functionality. Our results can be summarized as follows:

- There exists a class of functions such that the number of bit-OT tokens required to securely implement them is at least the size of the sender's input. The same applies for receiver's input size (with a different class of functionalities).

- Non-adaptive protocols in the hardware token model imply efficient (decomposable) randomized encodings. This can be interpreted as evidence to the impossibility of non-adaptive protocols for a large class of functions.

- There exists a functionality for which there is no protocol in the stateless hardware token model accessing the tokens at most a constant number of times, even when the adversary is computationally bounded.

En route to proving our results, we make interesting connections between the hardware token model and well studied notions such as OT hybrid model, randomized encodings, and obfuscation.

On the Security of Recently Proposed RFID Protocols, by Mete Akg\"{u}n, M. Ufuk \c{C}a\v{g}layan [Dec. 6th, 2013|08:42 pm]
 iacr_eprint

http://eprint.iacr.org/2013/820

RFID authentication protocols should have a secret updating phase in order to protect the privacy of RFID tags against tag tracing attacks. In the literature, there are many lightweight RFID authentication protocols that try to provide key updating with lightweight cryptographic primitives. In this paper, we analyse the security of two recently proposed lightweight RFID authentication protocol against de-synchronization attacks. We show that secret values shared between the back-end server and any given tag can be easily desynchronised. This weakness stems from the insufficient design of these protocols.

Interactive Encryption, Message Authentication, and Anonymous Key Exchange, by Yevgeniy Dodis and Da [Dec. 6th, 2013|08:42 pm]
 iacr_eprint

http://eprint.iacr.org/2013/817

Public-Key Encryption (PKE) and Message Authentication (PKMA, aka as digital signatures) are fundamental cryptographic primitives. Traditionally, both notions are defined as non-interactive (i.e., single-message). In this work, we initiate rigorous study of (possibly) {\em interactive} PKE and PKMA schemes. We obtain the following results demonstrating the power of interaction to resolve questions which are either open or impossible in the non-interactive setting.

Efficiency/Assumptions.
One of the most well known open questions in the area of PKE is to build, in a black-box way'', so called chosen ciphertext attack (CCA-) secure PKE from chosen plaintext attack (CPA-) secure PKE. In contrast, we show a simple $2$-round CCA-secure PKE from any (non-interactive) CPA-secure PKE (in fact, these primitives turn out to be equivalent). Similarly, although non-interactive PKMA schemes can be inefficiently built from any one-way function, no efficient signature schemes are known from many popular number-theoretic assumptions, such as factoring, CDH or DDH. In contrast, we show an efficient $2$-round PKMA from most popular assumptions, including factoring, CDH and DDH.

It is well known that no non-interactive signature (resp. encryption) scheme can be {\em deniable} (resp. {\em forward-secure}), since the signature (resp. ciphertext) can later serve as an evidence of the sender's consent'' (resp. be decrypted if the receiver's key is compromised''). We also formalize a related notion of {\em replay-secure} (necessarily) interactive PKMA (resp. PKE) schemes, where the verifier (resp. encryptor) is assured that the current'' message can only be authenticated (resp. decrypted) by the secret key owner {\em now}, as opposed to some time in the past (resp. future). We observe that our 2-round PKMA scheme is both replay-secure and (passively) deniable, and our 2-round PKE scheme is both replay- and forward-secure. We also define and construct stronger forms of necessarily interactive PKE/PKMA schemes, called {\em confirmed encryption} and {\em confidential authentication}.

Anonymous Key Exchange.
We extend our definitional framework for interactive PKE and PKMA schemes to give definitions and constructions of (necessarily interactive) {\em anonymous key exchange} (1-KE), where an anonymous (unkeyed) party establishes a key with an authenticated (keyed) party. Unlike the prior work, defining 1-KE by downgrading'' the hairy and complex definition of {\em mutually authenticated} key exchange (2-KE), our definition is very short'' and easy to understand. We also show simple and general connections between anonymous KE and (interactive) confirmed PKE/confidential PKMA schemes. As a result, we obtain old and new schemes for anonymous KE in a clean and modular manner. For example, we obtain the first $2$-round anonymous KE which is both (passively) deniable and forward-secure.

On the Relation of Random Grid, Probabilistic and Deterministic Visual Cryptography, by Roberto De P [Dec. 6th, 2013|08:42 pm]
 iacr_eprint

http://eprint.iacr.org/2013/818

Visual cryptography is a special type of secret sharing. Two models of visual cryptography have been independently studied: deterministic visual cryptography, introduced by Naor and Shamir, and random grid visual cryptography, introduced by Kafri and Keren. In the context of the deterministic model, Yang has introduced a third model, the probabilistic visual cryptography model. The connection between the probabilistic and the deterministic models have been explored.
In this paper we show that there is a strict relation between the random grid model and the deterministic model. More specically we show that to any random grid scheme corresponds a deterministic scheme and viceversa. This allows us to use results known in a model also in the other model. In fact, the random grid model is equivalent to the probabilistic model with no pixel expansion. Exploiting the (many) results known in the deterministic model we are able to improve several schemes and to provide many upper bounds for the random grid model. Exploiting some results known for the random grid model, we are also able to provide new schemes for the deterministic model. A side eect of this paper is that future new results for any one of the two models (random grid and deterministic) should not ignore, and in fact be compared to, the results known in the other model.

Safe enclosures: towards cryptographic techniques for server protection, by Sergiu Bursuc and Julian [Dec. 6th, 2013|08:42 pm]
 iacr_eprint

http://eprint.iacr.org/2013/819

Cryptography is generally used to protect sensitive data from an untrusted server. In this paper, we investigate the converse question: can we use cryptography to protect a trusted server from untrusted data?
As a first step in this direction, we propose the notion of safe enclosures. Intuitively, a safe enclosure is a cryptographic primitive that encapsulates data in a way that allows to perform some computation on it, while at the same time protecting the server from malicious data. Furthermore, a safe enclosure should come equipped with a dedicated protocol that implements the enclosing function with unconditional integrity. Otherwise, unguarded data may reach the server. We discuss the novelty of these concepts, propose their formal definition and show several realizations.

Riding the Saddle Point: asymptotics of the capacity-achieving simple decoder for bias-based traitor [Dec. 6th, 2013|08:42 pm]
 iacr_eprint

http://eprint.iacr.org/2013/809

We study the asymptotic-capacity-achieving score function that was recently proposed by Oosterwijk et al. for bias-based traitor tracing codes. For the bias function we choose the Dirichlet distribution with a cutoff. Using Bernstein's inequality and Bennett's inequality, we upper bound the false positive and false negative error probabilities. From these bounds we derive sufficient conditions for the scheme parameters. We solve these conditions in the limit of large coalition size $c_0$ and obtain asymptotic solutions for the cutoff, the sufficient code length and the corresponding accusation threshold.
The code length converges to its asymptote approximately as $c_0^{-1/2}$, which is faster than the $c_0^{-1/3}$ of Tardos' score function.

Formal Analysis of CRT-RSA Vigilant's Countermeasure Against the BellCoRe Attack, by Pablo Rauzy and [Dec. 6th, 2013|08:42 pm]
 iacr_eprint

http://eprint.iacr.org/2013/810

In our paper at PROOFS 2013, we formally studied a few known countermeasures to protect CRT-RSA against the BellCoRe fault injection attack. However, we left Vigilant's countermeasure and its alleged repaired version by Coron et al. as future work, because the arithmetical framework of our tool was not sufficiently powerful. In this paper we bridge this gap and then use the same methodology to formally study both versions of the countermeasure. We obtain surprising results, which we believe demonstrate the importance of formal analysis in the field of implementation security. Indeed, the original version of Vigilant's countermeasure is actually broken, but not as much as Coron et al. thought it was. As a consequence, the repaired version they proposed can be simplified. It can actually be simplified even further as two of the nine modular verifications happen to be unnecessary. Fortunately, we could formally prove the simplified repaired version to be resistant to the BellCoRe attack, which was considered a "challenging issue" by the authors of the countermeasure themselves.

Constant-Round Black-Box Construction of Composable Multi-Party Computation Protocol, by Susumu Kiyo [Dec. 6th, 2013|08:42 pm]
 iacr_eprint

http://eprint.iacr.org/2013/811

We present the first general MPC protocol that satisfies the following: (1) the construction is black-box, (2) the protocol is universally composable in the plain model, and (3) the number of rounds is constant. The security of our protocol is proven in angel-based UC security under the assumption of the existence of one-way functions that are secure against sub-exponential-time adversaries and constant-round semi-honest oblivious transfer protocols that are secure against quasi-polynomial-time adversaries. We obtain the MPC protocol by constructing a constant-round CCA-secure commitment scheme in a black-box way under the assumption of the existence of one-way functions that are secure against sub-exponential-time adversaries. To justify the use of such a sub-exponential hardness assumption in obtaining our constant-round CCA-secure commitment scheme, we show that if black-box reductions are used, there does not exist any constant-round CCA-secure commitment scheme under any falsifiable polynomial-time hardness assumptions.

A Note on Bilinear Groups of a Large Composite Order, by Zhengjun Cao and Lihua Liu [Dec. 6th, 2013|08:42 pm]
 iacr_eprint

http://eprint.iacr.org/2013/812

We remark that the structure of bilinear groups of a large composite order(at least 1024 bits) could make group operation inefficient and lose the advantages of elliptic curve cryptography which gained mainly from smaller parameter size. As of 2013, the longest parameter recommended by NIST for elliptic curves has 571 bits.
From the practical point of view, such an algebraic structure is unlikely applicable to cryptographic schemes.

Multi-ciphersuite security and the SSH protocol, by Benjamin Dowling and Florian Giesen and Florian [Dec. 6th, 2013|08:42 pm]
 iacr_eprint

http://eprint.iacr.org/2013/813

Real-world cryptographic protocols, such as the Transport Layer Security (TLS) and Secure Shell (SSH) protocols, support the negotiation of different combinations of cryptographic algorithms, often known as ciphersuites. An individual ciphersuite can be modelled as an authenticated and confidential channel establishment (ACCE) protocol, and recently all widely deployed TLS ciphersuites have been individually proven ACCE-secure. In practice, users often re-use long-term keys across ciphersuites, for example using the same digital signature key in two different signed Diffie--Hellman (DH) ciphersuites. Recently, a cross-ciphersuite attack on TLS was discovered in which a signed elliptic curve DH structure can be interpreted as a signed finite-field DH structure, breaking authentication. Thus, ACCE security of individual ciphersuites does not generically imply collective security when long-term keys are re-used across ciphersuites.

We investigate the security of multi-ciphersuite protocols with re-used long-term keys. We show how to "open" the ACCE definition slightly so that, after each ciphersuites has been proven secure individually, they can then be used together in a secure multi-ciphersuite protocol, even when long-term keys are re-used across ciphersuites, provided the ciphersuites' messages satisfy an independence property. We apply our definitions and composition theorem to the SSH protocol, showing that signed Diffie--Hellman SSH ciphersuites are individually ACCE-secure; they also satisfy the preconditions of our composition theorem, and thus SSH is multi-ciphersuite-secure even with re-use of long-term keys.

RDAS: A Symmetric Key Scheme for Authenticated Query Processing in Outsourced Databases, by Lil Mari [Dec. 6th, 2013|08:42 pm]
 iacr_eprint

http://eprint.iacr.org/2013/814

In this paper we address the problem of authenticated query processing in outsourced databases.
An authenticated query processing mechanism allows a client to verify the validity of the query responses that it gets from an untrusted and remote server, who stores the client's database
on its behalf.
We introduce a general framework called RDAS for the problem of authenticated query processing, and define the
security goals for this task in line with concrete provable security. We propose several schemes which enable
a client to verify both the completeness and correctness of the query responses of a server. All the schemes follow
the proposed framework and are provably secure in terms of the proposed security definition. The novelty of the proposed schemes
is that they use bitmap indexes as a main component for providing authentication. Bitmap indexes have recently seen
lot of applications for accelerated query processing and many commercial databases implement such indexes. Bitmaps have not been
previously used for a security goal. We show that the proposed schemes can match in both
functionality and efficiency compared to the existing schemes. We also implement the schemes on a real database and provide extensive
experimental studies on the schemes

Iterated group products and leakage resilience against NC^1, by Eric Miles [Dec. 6th, 2013|08:42 pm]
 iacr_eprint

http://eprint.iacr.org/2013/815

We show that if NC^1 \neq L, then for every element g of the alternating group A_t, circuits of depth O(log t) cannot distinguish between a uniform vector over (A_t)^t with product = g and one with product = identity. Combined with a recent construction by the author and Viola in the setting of leakage-resilient cryptography [STOC '13], this gives a compiler that produces circuits withstanding leakage from NC^1 (assuming NC^1 \neq L). For context, leakage from NC^1 breaks nearly all previous constructions, and security against leakage from P is impossible.

We build on work by Cook and McKenzie [J.\ Algorithms '87] establishing the relationship between L = logarithmic space and the symmetric group S_t. Our techniques include a novel algorithmic use of commutators to manipulate the cycle structure of permutations in A_t.

Fast Prime Field Elliptic Curve Cryptography with 256 Bit Primes, by Shay Gueron and Vlad Krasnov [Dec. 6th, 2013|08:42 pm]
 iacr_eprint

http://eprint.iacr.org/2013/816

This paper studies software optimization of Elliptic Curve Cryptography with 256-bit prime fields. We propose a constant-time implementation of the NIST and SECG standardized curve P-256, that can be seamlessly integrated into OpenSSL. This accelerates Perfect Forward Secrecy TLS handshakes that use ECDSA and/or ECDHE, and can help improving the efficiency of TLS servers. We report significant performance improvements for ECDSA and ECDH, on several architectures. For example, on the latest Intel Haswell microarchitecture, our ECDSA sign is 2.33x faster than OpenSSL's implementation.

Differential Indistinguishability for Cryptographic Primitives with Imperfect Randomness, by Michael [Dec. 6th, 2013|08:42 pm]
 iacr_eprint

http://eprint.iacr.org/2013/808

Indistinguishability-based definitions of cryptographic primitives such as encryption, commitments, and zero-knowledge proofs are proven to be impossible to realize in scenarios where parties only have access to non-extractable sources of randomness (Dodis et al., FOCS 2004). In this work we demonstrate that it is, nevertheless, possible to quantify this secrecy loss for non-extractable sources such as the (well-studied) Santha-Vazirani (SV) sources. In particular, to establish meaningful security guarantees in scenarios where such imperfect randomness sources are used, we define and study differential indistinguishability, a generalization of indistinguishability inspired by the notion of differential privacy.
We analyze strengths and weaknesses of differential indistinguishability both individually as well as under composition, and we interpret the resulting differential security guarantees for encryption, commitments, and zero-knowledge proofs.
Surprisingly, indistinguishability with uniform randomness carries over to differential indistinguishability with SV randomness: We show that all primitives that are secure under a traditional indistinguishibility-based definition are differentially secure when they use (a bounded amount of) SV randomness instead of uniform randomness.

Telepathwords: A New Password Strength Estimator [Dec. 6th, 2013|12:19 pm]
 bruce_schneier

https://www.schneier.com/blog/archives/2013/12/telepathwords_a.html

Telepathwords is a pretty clever research project that tries to evaluate password strength. It's different from normal strength meters, and I think better.

Telepathwords tries to predict the next character of your passwords by using knowledge of:
• common passwords, such as those made public as a result of security breaches
• common phrases, such as those that appear frequently on web pages or in common search queries
• common password-selection behaviors, such as the use of sequences of adjacent keys

Password-strength evaluators have generally been pretty poor, regularly assessing weak passwords as strong (and vice versa). I like seeing new research in this area.

abiogenesis: Dictionary.com Word of the Day [Dec. 6th, 2013|12:00 am]
 dictionary_wotd

abiogenesis: the now discredited theory that living organisms can arise spontaneously.