*04:17* [Pub][ePrint]
Fixed Argument Pairing Inversion on Elliptic Curves, by Sungwook Kim and Jung Hee Cheon
Let $E$ be an elliptic curve over a finite field ${\\mathbb F}_q$ with a power of prime $q$, $r$ a prime dividing $\\#E({\\mathbb F}_q)$, and $k$ the smallest positive integer satisfying $r | \\Phi_k(p)$, called embedding degree. Then a bilinear map $t: E({\\mathbb F}_q)[r] \\times E({\\mathbb F}_{q^k})/rE({\\mathbb F}_{q^k}) \\rightarrow {\\mathbb F}_{q^k}^*$ is defined, called the Tate pairing. And the Ate pairing and other variants are obtained by reducing the domain for each argument and raising it to some power. In this paper we consider the {\\em Fixed Argument Pairing Inversion (FAPI)} problem for the Tate pairing and its variants. In 2012, considering FAPI for the Ate$_i$ pairing, Kanayama and Okamoto formulated the {\\em Exponentiation Inversion (EI)} problem. However the definition gives a somewhat vague description of the hardness of EI. We point out that the described EI can be easily solved, and hence clarify the description so that the problem does contain the actual hardness connection with the prescribed domain for given pairings.

Next we show that inverting the Ate pairing (including other variants of the Tate pairing) defined on the smaller domain is neither easier nor harder than inverting the Tate pairing defined on the lager domain. This is very interesting because it is commonly believed that the structure of the Ate pairing is so simple and good (that is, the Miller length is short, the solution domain is small and has an algebraic structure induced from the Frobenius map) that it may leak some information, thus there would be a chance for attackers to find further approach to solve FAPI for the Ate pairing, differently from the Tate pairing.

*04:17* [Pub][ePrint]
Digital Signatures with Minimal Overhead, by Eike Kiltz and Krzysztof Pietrzak and Mario Szegedy
In a digital signature scheme with message recovery, rather than transmitting the message $m$ and its signature $\\sigma$, a single enhanced signature $\\tau$ is transmitted. The verifier is able to recover $m$ from $\\tau$ and at the same timeverify its authenticity. The two most important parameters of such a scheme are its security and the overhead $|\\tau|-|m|$. A simple argument shows that for any scheme with ``$n$ bits security\" $|\\tau|-|m|\\ge n$, i.e., the overhead is at least the security. The best previous constructions required an overhead of $2n$. In this paper we show that the $n$ bit lower bound can basically be matched. Concretely, we propose a new simple RSA-based digital signature scheme that, for $n=80$ bits security in the random oracle model, has an overhead of $\\approx 90$ bits.

At the core of our security analysis is an almost tight upper bound for the expected number of edges of the densest ``small\'\' subgraph of a random Cayley graph, which may be of independent interest.

*04:17* [Pub][ePrint]
Does Counting Still Count? Revisiting the Security of Counting based User Authentication Protocols against Statistical Attacks, by Hassan Jameel Asghar and Shujun Li and Ron Steinfeld and Josef Pierpz
At NDSS 2012, Yan et al. analyzed the security of several challenge-response type user authentication protocols against passive observers, and proposed a generic counting based statistical attack to recover the secret of some counting based protocols given a number of observed authentication sessions. Roughly speaking, the attack is based on the fact that secret (pass) objects appear in challenges with a different probability from non-secret (decoy) objects when the responses are taken into account. Although they mentioned that a protocol susceptible to this attack should minimize this difference, they did not give details as to how this can be achieved barring a few suggestions. In this paper, we attempt to fill this gap by generalizing the attack with a much more comprehensive theoretical analysis. Our treatment is more quantitative which enables us to describe a method to theoretically estimate a lower bound on the number of sessions a protocol can be safely used against the attack. Our results include 1) two proposed fixes to make counting protocols practically safe against the attack at the cost of usability, 2) the observation that the attack can be used on non-counting based protocols too as long as challenge generation is contrived, 3) and two main design principles for user authentication protocols which can be considered as extensions of the principles from Yan et al. This detailed theoretical treatment can be used as a guideline during the design of counting based protocols to determine their susceptibility to this attack. The Foxtail protocol, one of the protocols analyzed by Yan et al., is used as a representative to illustrate our theoretical and experimental results.

*01:17* [Pub][JoC]
Concurrent Zero Knowledge, Revisited
Abstract We provide a more general and, in our eyes, simpler variant of Prabhakaran, Rosen and Sahai’s (FOCS ’02, pp. 366–375, 2002) analysis of the concurrent zero-knowledge simulation technique of Kilian and Petrank (STOC ’01, pp. 560–569, 2001).

- Content Type Journal Article
- Pages 1-22
- DOI 10.1007/s00145-012-9137-2
- Authors

- Rafael Pass, Cornell University, Ithaca, NY 14853, USA
- Wei-Lung Dustin Tseng, Google Inc., 747 6th street, Kirkland, WA, USA
- Muthuramakrishnan Venkitasubramaniam, University of Rochester, 621 Computer Sciences Building, Rochester, NY 14627-0226, USA

- Journal Journal of Cryptology
- Online ISSN 1432-1378
- Print ISSN 0933-2790

From: Mon, 19 Nov 2012 15:07:03 GMT
*19:17* [Pub][ePrint]
TAAC: Temporal Attribute-based Access Control for Multi-Authority Cloud Storage Systems, by Kan Yang and Zhen Liu and Zhenfu Cao and Xiaohua Jia and Duncan S. Wong and Kui Ren
Data access control is an effective way to ensure the data security in the cloud. Due to data outsourcing and untrusted cloud servers, the data access control becomes a challenging issue in cloud storage systems. Ciphertext-Policy Attribute-based Encryption (CP-ABE), as a promising technique for access control of encrypted data, is very suitable for access control in cloud storage systems due to its high efficiency and expressiveness.

However, the existing CP-ABE schemes cannot be directly applied to data access control for cloud storage systems because of the attribute revocation problem. In this paper, we consider the problem of attribute revocation in multi-authority cloud storage systems where the users\' attributes come from different domains each of which is managed by a different authority.

We propose TAAC (Temporal Attribute-based Access Control), an efficient data access control scheme for multi-authority cloud storage systems, where the authorities are independent from each other and no central authority is needed. TAAC can efficiently achieve temporal access control on attribute-level rather than on user-level. Moreover, different from the existing schemes with attribute revocation functionality, TAAC does not require re-encryption of any ciphertext when the attribute revocation happens, which means great improvement on the efficiency of attribute revocation. The analysis results show that TAAC is highly efficient, scalable, and flexible to applications in practice.

*19:17* [Pub][ePrint]
Round-Efficient Concurrently Composable Secure Computation via a Robust Extraction Lemma, by Vipul Goyal and Omkant Pandey and Amit Sahai
We consider the problem of constructing protocols for secure computation that achieve strong concurrent and composable notions of security in the plain model. Unfortunately UC-secure secure computation protocols are impossible in this setting, but the Angel-Based Composable Security notion offers a promising alternative. Until now, however, under standard (polynomial-time) assumptions, only protocols with polynomially many rounds were known to exist.In this work, we give the first $\\tilde{O}(\\log n)$-round secure computation protocol in the plain model that achieves angel-based composable security in the concurrent setting, under standard assumptions. We do so by constructing the first $\\tilde{O}(\\log n)$-round CCA-secure commitment protocol. Our CCA-secure commitment protocol is secure based on the minimal assumption that one-way functions exist.

A central tool in obtaining our result is a new \\emph{robust concurrent extraction lemma} that we introduce and prove, based on the minimal assumptions that one-way functions exist. This robust concurrent extraction lemma shows how to build concurrent extraction procedures that work even in the context of an ``external\'\' protocol that cannot be rewound by the extractor. We believe this lemma can be used to simplify many existing works on concurrent security, and is of independent interest. In fact, our lemma when used in conjunction with the concurrent-simulation schedule of Pass and Venkitasubramaniam (TCC\'08), also yields a constant round construction based additionally on the existence of quasi-polynomial time (\\pqt) secure one-way functions.

*19:17* [Pub][ePrint]
How powerful are the DDH hard groups?, by Periklis A. Papakonstantinou and Charles W. Rackoff and Yevgeniy Vahlis
The question whether Identity-Based Encryption (IBE) can be based on the Decisional Diffie-Hellman (DDH) assumption is one of the most prominent questions in Cryptography related to DDH. We study limitations on the use of the DDH assumption in cryptographic constructions, and show that it is impossible to construct a secure Identity-Based Encryption system using, in a black box way, only the DDH (or similar) assumption about a group. Our impossibility result is set in the generic groups model, where we describe an attack on any IBE construction that relies on oracle access to the group operation of randomly labelled group elements -- a model that formalizes naturally DDH hardness.The vast majority of existing separation results typically give separation from general primitives, whereas we separate a primitive from a class of number theoretic hardness assumptions. Accordingly, we face challenges in creating an attack algorithm that will work against constructions which leverage the underlying algebraic structure of the group. In fact, we know that this algebraic structure is powerful enough to provide generic constructions for several powerful primitives including oblivious transfer and chosen ciphertext secure public-key cryptosystems (note that an IBE generalizes such systems). Technically, we explore statistical properties of the group algebra associated with a DDH oracle, which can be of independent interest.