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

2013-06-20
12:17 [Pub][ePrint] A quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic, by Razvan Barbulescu and Pierrick Gaudry and Antoine Joux and Emmanuel Thomé

  In the present work, we present a new discrete logarithm algorithm, in the same vein as in recent works by Joux, using an asymptotically more efficient descent approach. The main result gives a quasi-polynomial heuristic complexity for the discrete logarithm problem in finite field of small characteristic. By quasi-polynomial, we mean a complexity of type $n^{O(\\log n)}$ where $n$ is the bit-size of the cardinality of the finite field. Such a complexity is smaller than any $L(\\varepsilon)$ for $\\epsilon>0$. It remains super-polynomial in the size of the input, but offers a major asymptotic improvement compared to $L(1/4+o(1))$.



12:17 [Pub][ePrint] Functional Signatures and Pseudorandom Functions, by Elette Boyle and Shafi Goldwasser and Ioana Ivan

  In this paper, we introduce \\emph{functional digital signatures}, \\emph{functional pseudorandom functions} and \\emph{pseudorandom functions with selective access}.

In a functional signature scheme, in addition to a master signing key that can be used to sign any message, there are \\emph{signing keys for a function} $f$, which allow one to sign any message in the range of $f$. An immediate application of functional signature schemes is delegation of the ability to sign a restricted set of messages by a master authority to a third party. We also show applications of functional signatures in constructing succinct non-interactive arguments and delegation schemes. We give several general constructions for this primitive based on different computational hardness assumptions, and describe the trade-offs between them in terms of the assumptions they require and the size of the signatures.

In a functional pseudorandom function, in addition to a master secret key that can be used to evaluate the pseudorandom function $F$ on any point in the domain, there are additional \\emph{secret keys for a function} $f$, which allow one to evaluate $F$ on any $y$ for which there exists an $x$ such that $f(x)=y$. This implies the ability to delegate keys per function $f$ for computing a pseudorandom function $F$ on points $y$ for which $f(y)=1$. Such functions imply {\\it pseudo random functions with selective access} -- pseudorandom function families F for which one may delegate keys per function f for computing F on points y for which f(y) = 1. We provide an example of a construction of a functional pseudorandom function for prefix fixing functions.



12:17 [Pub][ePrint] Efficient Two-Pass Anonymous Identity Authentication Using Smart Card, by Jue-Sam Chou1*, Chun-Hui Huang2, Yu-Siang Huang3, Yalin Chen4

  Recently, Khan et al. proposed an enhancement on a remote authentication scheme designed by Wang et al. which emphasizes on using dynamic identity. They claim that their improvement can avoid insider attack. However, we found the scheme lacks the anonymity property. Moreover, R. Madhusudhan et al. indicate their scheme also suffers the insider attack. Due to these observations, in this paper we propose a novel one which not only anonymously authenticates the remote user by using only two passes but also satisfies the ten requirements of an authentication scheme using smart card mentioned by Liao et al..



12:17 [Pub][ePrint] Function-Private Subspace-Membership Encryption and Its Applications, by Dan Boneh and Ananth Raghunathan and Gil Segev

  Boneh, Raghunathan, and Segev (CRYPTO \'13) have recently put forward the notion of function privacy and applied it to identity-based encryption, motivated by the need for providing predicate privacy in public-key searchable encryption. Intuitively, their notion asks that decryption keys reveal essentially no information on their corresponding identities, beyond the absolute minimum necessary. While Boneh et al. showed how to construct function-private identity-based encryption (which implies predicate-private encrypted keyword search), searchable encryption typically requires a richer set of predicates.

In this paper we significantly extend the function privacy framework. First, we introduce the new notion of subspace-membership encryption, a generalization of inner-product encryption, and formalize a meaningful and realistic notion for capturing its function privacy. Then, we present a generic construction of a function-private subspace-membership encryption scheme based on any inner-product encryption scheme. This is the first generic construction that yields a function-private encryption scheme based on a non-function-private one.

Finally, we present various applications of function-private subspace-membership encryption. Among our applications, we significantly improve the function privacy of the identity-based encryption schemes of Boneh et al.: whereas their schemes are function private only for identities that are highly unpredictable (with min-entropy of at least

$\\lambda + \\omega(\\log \\lambda)$ bits, where $\\lambda$ is the security parameter), we obtain function-private schemes assuming only the minimal required unpredictability (i.e., min-entropy of only $\\omega(\\log \\lambda)$ bits). This improvement offers a much more realistic function privacy guarantee.



12:17 [Pub][ePrint] The SIMON and SPECK Families of Lightweight Block Ciphers, by Ray Beaulieu and Douglas Shors and Jason Smith and Stefan Treatman-Clark and Bryan Weeks and Louis Wingers

  In this paper we propose two families of block ciphers, SIMON and SPECK, each of which comes in a variety of widths and key sizes. While many lightweight block ciphers exist, most were designed to perform well on a single platform and were not meant to provide high performance across a range of devices. The aim of SIMON and SPECK is to fill the need for secure, flexible, and analyzable lightweight block ciphers. Each offers excellent performance on hardware and software platforms, is flexible enough to admit a variety of implementations on a given platform, and is amenable to analysis using existing techniques. Both perform exceptionally well across the full spectrum of lightweight applications, but SIMON is tuned for optimal performance in hardware, and SPECK for optimal performance in software.



12:17 [Pub][ePrint] New Quadratic Bent Functions in Polynomial Forms with Coefficients in Extension Fields, by Chunming Tang, Yanfeng Qi, Maozhi Xu

  In this paper, we first discuss the bentness of a large class of quadratic Boolean functions in polynomial form

$f(x)=\\sum_{i=1}^{\\frac{n}{2}-1}Tr^n_1(c_ix^{1+2^i})+ Tr_1^{n/2}(c_{n/2}x^{1+2^{n/2}})$, where

$c_i\\in GF(2^n)$ for $1\\leq i \\leq \\frac{n}{2}-1$ and $c_{n/2}\\in GF(2^{n/2})$.

The bentness of these functions can be connected with linearized permutation

polynomials. Hence, methods for constructing quadratic bent functions are given. Further, we consider a subclass of quadratic Boolean functions of the form

$f(x)=\\sum_{i=1}^{\\frac{m}{2}-1}Tr^n_1(c_ix^{1+2^{ei}})+

Tr_1^{n/2}(c_{m/2}x^{1+2^{n/2}})$ , where $c_i\\in GF(2^e)$, $n=em$ and $m$ is even. The bentness of these functions are characterized and some methods for constructing new quadratic bent functions are given. Finally, for a special case: $m=2^{v_0}p^r$ and

$gcd(e,p-1)=1$, we present the enumeration of quadratic bent functions.



12:17 [Pub][ePrint] Attribute-Based Server-Aided Verfication Signature, by Zhiwei Wang and Ruirui Xie and Wei Zhang and Liwen He and Guozi Sun and Wei Chen

  Attribute based signature (ABS) is a novel cryptographic primitive, which enables a party can sign messages for any predicate satisfy by their attributes. However, heavy computational cost is required during the verification procedure in most existing ABS schemes, which may needs many pairing operations. Pairing are costly operation when compared to exponentiation in the base group. As a result, this presents a greatly challenge for resource-limited users, such as smart cards and wireless sensor. In other words, verification can hardly be done in these devices if attribute based signature is employed. We solve this

problem by proposing a new notion called \\emph{Attribute-Based Server-Aided Verification Signature}. It is similar to normal ABS scheme, but it further enables the verifier to verify the signature with the assistance of an external server. In this paper, we provide the security definition of Attribute-Based Server-Aided Verification Signature, and design a concrete server-aided verification protocol for Li et al.\'s attribute based signature. We also prove that our protocol is secure with random oracles.



06:28 [PhD][New] Enrico Thomae: About the Security of Multivariate Quadratic Public Key Schemes

  Name: Enrico Thomae
Topic: About the Security of Multivariate Quadratic Public Key Schemes
Category: public-key cryptography

Description: The primary goal of this thesis is to evaluate the security of multivariate quadratic public key schemes. We investigate three main topics related to the security of MQ-schemes, namely the MQ-Problem, the IP-Problem and the MinRank-Problem.
\r\nSection 2 discusses the MQ-Problem, which relates to direct pre-image attacks using the\r\npublic key, i.e. finding x for a given y and P(x) = y, which is known to be difficult in\r\ngeneral. In section 2.1 we provide a brief survey on algorithms to solve such systems, like F4, F5, XL and MutantXL. We recap the complexity analysis of the first three algorithms and provide a detailed complexity analysis of the latter. Our contribution is a proof of theorem 2.7 which is hopefully simpler than that in [CKPS, Section 8]. Further we derived theorem 2.29 and thus confirmed results from Yang and Chen [YC04a] in a different way.
\r\nIn section 2.2 we present a new direct attack on the Unbalanced Oil and Vinegar signature scheme, which forces to raise parameters in order to obtain the same\r\nsecurity level again. More generally we present an algorithm to solve underdetermined\r\nsystems of MQ-equations faster than before.
\r\nSection 3 presents the main part of this work and is dedicated to algebraic key recovery\r\nattacks on MQ-schemes.\r\nUnfortunately naive algebraic attacks are usually far from being efficient due to the large number of variables. So we first formalize the underlying class of problems and introduce the Isomorphism of Polynomials with partial Knowledge (IPpK) Problem in section 3.3. We relate this new problem to known problems, like the Isomorphism of Polynomials Problem with one and two secrets. Our main contribution is to provide a general algebraic\r\nframework to tackle the IPpK-Problem. Therefore we generalize the notion of equivalent keys to so-called good keys. In a nutshell equivalent keys allow to reduce the number of variables of an algebraic attack. Good keys further reduce the number of vari[...]




2013-06-19
06:17 [Forum] [IACR Publication Reform] Automatic follow up by cbw

  Hello, In case you want to follow up this forum - but not to poll it every other day, there are several options: * RSS feed: http://eprint.iacr.org/forum/rss.php * IACR News system (eMail, Twitter) via "Forum": http://www.iacr.org/news/ Best, Christopher From: 2013-19-06 04:56:53 (UTC)

06:17 [Forum] [General] Re: RSS feeds by cbw

  Hello, Apart from the RSS feed at http://eprint.iacr.org/forum/rss.php there is also the IACR News system system (eMail, Twitter). Just use the tag / channel "Forum": http://www.iacr.org/news/ Best, Christopher www.christopher-wolf.de Ruhr-University Bochum Germany From: 2013-19-06 05:02:11 (UTC)



2013-06-18
15:17 [Pub][ePrint] Attack on Liao and Hsiao\'s Secure ECC-based RFID Authentication Scheme integrated with ID-Verifier Transfer Protocol, by Roel Peeters and Jens Hermans

  We show that the Liao and Hsiao\'s protocol achieves neither tag-authentication nor privacy.