International Association for Cryptologic Research

IACR News Central

Get an update on changes of the IACR web-page here. For questions, contact newsletter (at) iacr.org. You can also get this service via

To receive your credentials via mail again, please click here.

You can also access the full news archive.

Further sources to find out about changes are CryptoDB, ePrint RSS, ePrint Web, Event calender (iCal).

2012-08-18
06:17 [Pub][ePrint] Finding Lower Bounds on the Complexity of Secret Sharing Schemes by Linear Programming, by Carles Padro and Leonor Vazquez and An Yang

  Optimizing the maximum, or average, length of the shares in relation to the length of the secret for every given access structure is a difficult and long-standing open problem in cryptology. Most of the known lower bounds on these parameters have been obtained by implicitly or explicitly using that every secret sharing scheme defines a polymatroid related to the access structure. The best bounds that can be obtained by this combinatorial method can be determined by using linear programming, and this can be effectively done for access structures on a small number of participants.

By applying this linear programming approach, we improve some of the known lower bounds for the access structures on five participants and the graph access structures on six participants for which these parameters were still undetermined. Nevertheless, the lower bounds that are obtained by this combinatorial method are not tight in general. For some access structures, they can be improved by adding

to the linear program non-Shannon information inequalities as new constraints. We obtain in this way new separation results for some graph access structures on eight participants and for some ports of non-representable matroids. Finally, we prove that, for two access structures on five participants, the combinatorial lower bound cannot be attained by any linear secret sharing scheme.



06:17 [Pub][ePrint] T-MATCH: Privacy-Preserving Item Matching for Storage-Only RFID Tags, by Kaoutar Elkhiyaoui and Erik-Oliver Blass and Refik Molva

  RFID-based tag matching allows a reader Rk to determine whether two tags Ti and Tj store

some attributes that jointly fulfill a boolean constraint. The challenge in designing a matching mechanism

is tag privacy. While cheap tags are unable to perform any computation, matching has to be

achieved without revealing the tags\' attributes. In this paper, we present T-MATCH, a protocol for secure

and privacy preserving RFID tag matching. T-MATCH involves a pair of tags Ti and Tj , a reader

Rk, and a backend server S. To ensure tag privacy against Rk and S, T-MATCH employs a new technique

based on secure two-party computation that prevents Rk and S from disclosing tag attributes. For

tag privacy against eavesdroppers, each tag Ti in T-MATCH stores an IND-CPA encryption of its attribute.

Such an encryption allows Rk to update the state of Ti by merely re-encrypting Ti\'s ciphertext.

T-MATCH targets cheap tags that cannot perform any computation, but are only required to store 150

bytes.



06:17 [Pub][ePrint] Computational Entropy and Information Leakage, by Benjamin Fuller and Leonid Reyzin

  We investigate how information leakage reduces computational entropy of a random variable X. Recall that HILL and metric computational entropy are parameterized by quality (how distinguishable is X from a variable Z that has true entropy) and quantity (how much true entropy is there in Z).

We prove an intuitively natural result: conditioning on an event of probability p reduces the quality of metric entropy by a factor of p and the quantity of metric entropy by log 1/p note that this means that the reduction in quantity and quality is the same, because the quantity of entropy is measured on logarithmic scale). Our result improves previous bounds of Dziembowski and Pietrzak (FOCS 2008), where the loss in the \\emph{quantity} of entropy was related to its original quality. The use of metric entropy simplifies the analogous the result of Reingold et. al. (FOCS 2008) for HILL entropy.

Further, we simplify dealing with information leakage by investigating conditional metric entropy. We show that, conditioned on leakage of \\lambda bits, metric entropy gets reduced by a factor 2^\\lambda in quality and \\lambda in quantity.



06:17 [Pub][ePrint] New results on nonexistence of generalized bent functions, by Yupeng Jiang and Yingpu Deng

  We get two kinds of new results on nonexistence of generalized bent function. The first one is Based on Feng\'s results by using Schmidt\'s field descent method. For the second kind, considering special property of the field $\\mathbb{Q}(\\zeta_{23^e})$, We get new nonexistence results of generalized bent functions with type $[3,2\\cdot23^e]$.



06:17 [Pub][ePrint] Functional Encryption: New Perspectives and Lower Bounds, by Shweta Agrawal and Sergey Gorbunov and Vinod Vaikuntanathan and Hoeteck Wee

  Functional encryption is an emerging paradigm for public-key encryption that enables fine-grained control of access to encrypted data. In this work, we present new perspectives on security definitions for functional encryption, as well as new lower bounds on what can be achieved. Our main contributions are as follows:

* We show a lower bound for functional encryption that satisfies a weak (non-adaptive) simulation-based security notion, via pseudo-random functions. This is the first lower bound that exploits unbounded collusions in an essential way.

* We put forth and discuss a simulation-based notion of security for functional encryption, with an unbounded simulator (called USIM). We show that this notion interpolates indistinguishability and simulation-based security notions, and has strong correlations to results and barriers in the zero-knowledge and multi-party computation literature.



06:17 [Pub][ePrint] Perfect Keyword Privacy in PEKS Systems, by Mototsugu Nishioka

  This paper presents a new security notion, called \\emph{perfect keyword privacy (PKP)}, for non-interactive public-key encryption with keyword search (PEKS) \\cite{bcop04}. Although the conventional security notion for PEKS guarantees that a searchable ciphertext leaks no information about keywords, it gives no guarantee concerning leakage of a keyword from the trapdoor. PKP is a notion for overcoming this fatal deficiency. Since the trapdoor has verification functionality, the popular concept of ``indistinguishability\'\' is inadequate for capturing the notion of keyword privacy from the trapdoor. Hence, our formalization of PKP depends on the idea of formalizing a perfectly one-way hash function \\cite{can97,cmr98}. We also present \\emph{IND-PKP security} as a useful notion for showing that a given PEKS scheme has PKP. Furthermore, we present PKP+ and IND-PKP+ as enhanced notions of PKP and IND-PKP, respectively. Finally, we present several instances of an IND-PKP or IND-PKP+ secure PEKS scheme, in either the random oracle model or the standard model.



06:17 [Pub][ePrint] Some Connections Between Primitive Roots and Quadratic Non-Residues Modulo a Prime, by Sorin Iftene

  In this paper we present some interesting connections between primitive roots and quadratic non-residues modulo a prime. Using these correlations, we improve the existing randomized algorithm for generating primitive roots and we propose a polynomial deterministic algorithm for generating primitive roots for primes

with special forms (for example, for safe primes). The key point of our improvement is the fact that the evaluation of Legendre-Jacobi symbol is much faster than an exponentiation.



06:17 [Pub][ePrint] A Quasigroup Based Random Number Generator for Resource Constrained Environments, by Matthew Battey and Abhishek Parakh

  This paper proposes a pseudo random number generator (PRNG) based on quasigroups. The proposed PRNG has low memory requirements, is autonomous and the quality of the output stream of random numbers is better than other available standard PRNG implementations (commercial and open source) in majority of the tests. Comparisons are done using the benchmark NIST Statistical Test Suite and compression tools. Results are presented for quality of raw stream of random numbers and for encryption results using these random numbers.



06:17 [Pub][ePrint] Glitches and Static Power Hand in Hand, by Amir Moradi and Oliver Mischke

  Several masking schemes to protect cryptographic implementations against side-channel attacks have been proposed. A few considered the glitches, and provided security proofs in presence of such inherent phenomena happening in logic circuits. One which is based on multi-party computation protocols and utilizes Shamir\'s secret sharing scheme was presented at CHES 2011. It aims at providing security for hardware implementations - mainly of AES - against those sophisticated side-channel attacks that also take glitches into account. One part of this article deals with the practical issues and relevance of the aforementioned masking scheme. We first provide a guideline on how to implement the scheme for the simplest settings, and address some pitfalls in the scheme which prevent it to be practically realized. Solving the problems and constructing an exemplary design of the scheme, we provide practical side-channel evaluations based on a 65nm-technology Virtex-5 FPGA. We still observe univariate side-channel leakage, which is not expected according to the proven security of the scheme. We believe that the leakage is due to a combination of static power consumption and glitches in the circuit which is observed for the first time in practice. Dependency of static power consumption of nano-scale devices on processed data - which was warned before to be problematic - becomes now critical. Our result does not invalidate the given security proof of the scheme itself, but instead shows that the underlying model to obtain the proofs no longer fits to the reality. This is true not only for the scheme showcased here, but also for most other known masking schemes. As a result, due to the still ongoing technology shrinkage most of the available data-randomizing side-channel countermeasures will not be able to completely prevent univariate side-channel leakage of hardware implementations. Our work shows that new models must be created under which the security of new schemes can be proven considering leakages through both dynamic and static power consumption.



06:17 [Pub][ePrint] Sender Equivocable Encryption Schemes Secure against Chosen-Ciphertext Attacks Revisited, by Zhengan Huang and Shengli Liu and Baodong Qin

  The first sender equivocable encryption scheme secure against chosen-ciphertext attack (NC-CCA) was proposed by Fehr et al. in Eurocrypt 2010. The scheme was also secure against selective opening chosen-ciphertext attack (SO-CCA), since NC-CCA security implies SO-CCA security.

The NC-CCA security proof of the scheme relies on security against substitution attack of a new primitive, ``cross-authentication code\'\'. However, the security of cross-authentication code can not guarantee anything when all the keys used in the code are exposed. The key observation is that in the NC-CCA game, the randomness used in the generation of the challenge ciphertext is exposed to the adversary. This random information can be used to recover all the keys involved in cross-authentication code, and forge a ciphertext (like a substitution attack of cross-authentication code) that is different from but related to the challenge ciphertext. And the response of decryption oracle leaks information. This leaked information is employed by an attack to spoil the NC-CCA security proof of the sender equivocable encryption scheme encrypting multi-bits. We also propose a new scheme encrypting single-bit plaintext, free of cross-authentication code, and prove its NC-CCA security.



06:17 [Pub][ePrint] Semantically Secure Functional Encryption, Revisited, by Manuel Barbosa and Pooya Farshim

  Functional encryption (FE) is a powerful cryptographic primitive that generalizes many asymmetric encryption systems proposed in recent years. Syntax and security definitions for general FE were recently proposed by Boneh, Sahai, and Waters (BSW) (TCC 2011) and independently by O\'Neill (ePrint 2010/556). In this paper we revisit these definitions, identify a number of shortcomings in them, and propose a new definitional approach that overcomes these limitations. Our definitions display good compositionality properties and allow us to obtain new feasibility and impossibility results for adaptive token extraction attack scenarios that shed further light on the potential reach of general FE for practical applications. The main contributions of the paper are the following:

- We show that the BSW definition of semantic security fails to reject intuitively insecure FE schemes where a ciphertext leaks more about an encrypted message than that which can be recovered from an image under the supported functionality. Our definition (as O\'Neill\'s) does not suffer from this problem.

- We introduce an orthogonal notion of {\\em setup security} that rejects all FE schemes where the master secret key may give unwanted power to the TA, allowing the recovery of extra information from images under the supported functionality. We prove FE schemes supporting {\\em all-or-nothing} functionalities are intrinsically setup-secure and further show that many well-known functionalities {\\em are} all-or-nothing.

- We extend the equivalence result of O\'Neill between indistinguishability and semantic security to restricted {\\em adaptive} token extraction attacks (the standard notion of security for, e.g., IBEs and ABEs). We establish that this equivalence holds for the large class of all-or-nothing functionalities. Conversely, we show that the proof technique used to establish this equivalence cannot be applied to schemes supporting a one-way function.

- We show that the notable {\\em inner-product} functionality introduced by Katz, Sahai, and Waters (EUROCRYPT 2008) can be used to encode a one-way function under the small integer solution problem, and hence natural approaches to prove its (restricted) adaptive security fail. This complements the equivalence result of O\'Neill for the non-adaptive case, and leaves open the question of proving the semantic security of existing inner-product encryption schemes.