International Association for Cryptologic Research

IACR News Central

Get an update on changes of the IACR web-page here. For questions, contact newsletter (at) You can also receive updates 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).

18:17 [Pub][ePrint] Sequential Aggregate Signatures with Short Public Keys: Design, Analysis and Implementation Studies, by Kwangsu Lee and Dong Hoon Lee and Moti Yung

  The notion of aggregate signature has been motivated by applications and it enables any user to compress different signatures signed by different signers on different messages into a short signature. Sequential aggregate signature, in turn, is a special kind of aggregate signature that only allows a signer to add his signature into an aggregate signature in sequential order. This latter scheme has applications in diversified settings, such as in reducing bandwidth of a certificate chains, and in secure routing protocols. Lu, Ostrovsky, Sahai, Shacham, and Waters presented the first sequential aggregate signature scheme in the standard (non idealized ROM) model. The size of their public key, however, is quite large (i.e., the number of group elements is proportional to the security parameter), and therefore they suggested as an open problem the construction of such a scheme with short keys. Schr\\\"oder recently proposed a sequential aggregate signature (SAS) with short public keys using the Camenisch-Lysyanskaya signature scheme, but the security is only proven under an interactive assumption (which is considered a relaxed notion of security).

In this paper, we propose the first sequential aggregate signature scheme with short public keys (i.e., a constant number of group elements) in prime order (asymmetric) bilinear groups which is secure under static assumptions in the standard model. Further, our scheme employs constant number of pairing operation per message signing and message verification operation. Technically, we start with a public key signature scheme based on the recent dual system encryption technique of Lewko and Waters. This technique cannot give directly an aggregate signature scheme since, as we observed, additional elements should be published in the public key to support aggregation (and these may, in fact, invalidate the security arguments). Thus, our construction is a careful augmentation technique for the dual system technique to allow it to support a sequential aggregate signature scheme via randomized verification. We further implemented our scheme and conducted a performance study and implementation optimization.

18:17 [Pub][ePrint] Faster implementation of scalar multiplication on Koblitz curves, by Diego F. Aranha and Armando Faz-Hernández and Julio López and Francisco Rodríguez-Henríquez

  We design a state-of-the-art software implementation of field and elliptic curve arithmetic in standard Koblitz curves at the 128-bit security level. Field arithmetic is carefully crafted by using the best formulae and implementation strategies available, and the increasingly common native support to binary field arithmetic in modern desktop computing platforms. The i-th power of the Frobenius automorphism on Koblitz curves is exploited to obtain new and faster interleaved versions of the well-known $\\tau$NAF scalar multiplication algorithm. The usage of the $\\tau^{\\lfloor m/3 \\rfloor}$ and

$\\tau^{\\lfloor m/4 \\rfloor}$ maps are employed to create analogues of the 3-and 4-dimensional GLV decompositions and in general, the $\\lfloor m/s \\rfloor$-th power of the Frobenius automorphism is applied as an analogue of an $s$-dimensional GLV decomposition. The effectiveness of these techniques is illustrated by timing the scalar multiplication operation for fixed, random and multiple points. To our knowledge, our library was the first to compute a random point scalar multiplication in less than 10^5 clock cycles among all curves with or without endomorphisms defined over binary or prime fields. The results of our optimized implementation suggest a trade-off between speed, compliance with the published standards and side-channel protection. Finally, we estimate the performance of curve-based cryptographic protocols instantiated using the proposed techniques and compare our results to related work.

06:10 [Job][New] Research Scientist / Senior Research Scientist, Palo Alto Research Center (PARC, a Xerox Company)

  We invite applications for outstanding researchers to strengthen and broaden our research activities in security research. Our expertise ranges from applied cryptography and privacy to network, system, and usable security. Both recent Ph.D. graduates and well-established scientists are encouraged to apply.

A premier center for commercial innovation, PARC, a Xerox company, is in the business of breakthroughs. We work closely with global enterprises, entrepreneurs, government agencies and partners, and other clients to invent, co-develop, and bring to market game-changing innovations by combining imagination, investigation, and return on investment for our clients. For 40 years, we have lived at the leading edge of innovation, merging inquiry and strategy to pioneer technological change. PARC was incorporated in 2002 as a wholly owned independent subsidiary of Xerox Corporation – enabling us to continue pioneering technological change but across a broader set of industries and clients today.

Depending on seniority, the successful candidate will be responsible for one or more of the following roles:

. Formulating research problems based on real-world needs and independently conducting high-quality research

. Working with existing research and development staff on a broad range of research topics

. Working with business development team in identifying important business opportunities with industry and government agencies.

. Identifying new promising research directions and contributing them to the group’s long-term research agenda.

Candidates in all areas of cyber security will be considered, however, the following areas are of particular interest:

. Systems & network security

. Security in cloud computing

. Data mining and machine learning applied to security and privacy

. Security and privacy in ubiquitous and mobile computing environments

06:10 [Job][New] Lecturer or Senior Lecturer, University of Cape Town, South Africa

  Applications are sought for a position at the level of Lecturer or Senior Lecturer in the Department of Mathematics and Applied Mathematics at the University of Cape Town. This is a large, dynamic department and a leading research centre in mathematical sciences in the country. It has over thirty faculty members, ten administrative staff members and more than 50 postgraduate students.

Candidates must be in possession of a PhD in the Mathematical Sciences and are expected to have a research track record, which must show some evidence of independence for Senior Lecturer level.

Applications in all areas in Mathematics and Applied Mathematics will be considered. We are particularly seeking active researchers whose research field complements or strengthens existing research areas in our department. For further details on the Department please see our website at

The successful applicants would be expected to teach not only in their areas of research, but also service courses offered to other Faculties such as Engineering and Commerce, to contribute to the administration of the department and its courses, and to supervise students.

Candidates should indicate for which level of position they are applying and the level of appointment will be commensurate with experience and standing of applicants.

The annual remuneration packages, including benefits, for the following levels are:

· Senior Lecturer : R526 873

· Lecturer : R427 311

00:07 [News] Videos from Crypto 2012

  Videos from Crypto 2012 are now online at YouTube and cryptodb.

15:17 [Pub][ePrint] Desynchronization Attack on RAPP Ultralightweight Authentication Protocol, by Zahra Ahmadian, Mahmoud Salmasizadeh, and Mohammad Reza Aref

  RAPP (RFID Authentication Protocol with Permutation) is a recently proposed efficient ultralightweight authentication protocol. The operation used in this protocol is totally different from the other existing ultralightweight protocols due to the use of new introduced data dependent permutations and avoidances of modular arithmetic operations and biased logical operations such as AND and OR. The designers of RAPP claimed that this protocol resists against desynchronization attacks since the last messages of the protocol is sent by the reader and not by the tag. This letter challenges this assumption and shows that RAPP is vulnerable against desynchronization attack. This attack has a remarkable probability of success and is effective whether Hamming weight-based or modular-based rotations are used by the protocol.

15:17 [Pub][ePrint] On the Multiple Fault Attack on RSA Signatures with LSBs of Messages Unknown, by Lidong Han and Wei Wei and Mingjie Liu

  In CHES 2009, Coron, Joux, Kizhvatov, Naccache and

Paillier(CJKNP) introduced a fault attack on

RSA signatures with partially unknown messages. They

factored RSA modulus $N$ using a single faulty signature and

increased the bound of unknown messages by multiple fault attack,

however, the complexity multiple fault attack is exponential in the

number of faulty signatures. At RSA 2010, it was improved which run

in polynomial time in number of faults.

Both previous multiple fault attacks deal with the general case that

the unknown part of message is in the middle. This paper handles a

special situation that some least significant bits of messages are

unknown. First, we describe a sample attack by utilizing the

technique of solving simultaneous diophantine approximation problem,

and the bound of unknown message is $N^{\\frac1{2}-\\frac1{2\\ell}}$

where $\\ell$ is the number of faulty signatures. Our attacks are

heuristic but very efficient in practice. Furthermore, the new bound

can be extended up to $N^{\\frac1{2}^{1+\\frac1{\\ell}}}$ by the

Cohn-Heninger technique. Comparison between previous attacks and new

attacks with LSBs of message unknown will be given by simulation


15:17 [Pub][ePrint] A Method for Generating Full Cycles by a Composition of NLFSRs, by Elena Dubrova

  Non-Linear Feedback Shift Registers (NLFSR) are a generalization of Linear Feedback Shift Registers (LFSRs) in which a current state is a non-linear function of the previous state. The interest in NLFSRs is motivated by their ability to generate pseudo-random sequences which are usually hard to break with existing cryptanalytic methods. However, it is still not known how to construct large $n$-stage NLFSRs which generate full cycles of $2^n$ possible states. This paper presents a method for generating full cycles by a composition of NLFSRs. First, we show that an $n*k$-stage register with period $O(2^{2n})$ can be constructed from $k$ $n$-stage NLFSRs by adding to their feedback functions a logic block of size $O(n*k)$. This logic block implements Boolean functions representing the set of pairs of states whose successors have to be exchanged in order to join cycles. Then, we show how to join all cycles into one by using one more logic block of size $O(n*k^2)$ and an extra time step. The presented method is feasible for generating very large full cycles.

15:17 [Pub][ePrint] Efficient Query Integrity for Outsourced Dynamic Databases, by Qingji Zheng, Shouhuai Xu, Giuseppe Ateniese

  As databases are increasingly outsourced to the cloud, data owners

require various security assurances. This paper investigates one

particular assurance, query integrity, by which a database querier

(either the data owner or a third party) can verify that its queries

were faithfully executed by the cloud server with respect to the outsourced database. Query integrity is investigated in the setting of

dynamic databases, where the outsourced databases can be updated

by the data owners as needed. We present a formal security definition

of query integrity and a provably-secure efficient construction.

Our solution improves upon the state-of-the-art solutions by additionally allowing aggregate queries and more flexible join queries. In addition, we provide better performance by eliminating a linear factor in the extra storage complexity for security purpose. Our solution also achieves a trade-off between computational and communication complexities.

15:17 [Pub][ePrint] Format-Transforming Encryption: More than Meets the DPI, by Kevin P. Dyer and Scott E. Coull and Thomas Ristenpart and Thomas Shrimpton

  Nation-states and other organizations are increasingly deploying deep-packet inspection (DPI) technologies to censor Internet traffic based on application-layer content. We introduce a new DPI circumvention approach, format-transforming encryption (FTE), that cryptographically transforms the format of arbitrary plaintext data (e.g. packet contents) into specified formats that are designed to bypass DPI tests. We show how to build a general-purpose FTE system, in which these formats are defined compactly by families of regular expressions. Moreover, we specify and implement a full FTE record-layer protocol.

We exhibit formats that are guaranteed to avoid known filters, and give a framework for learning formats from non-censored HTTP traffic. These formats are put to use in our FTE record layer, to explore trade-offs between performance and steganographic capabilities. As one example, we visit the top 100 Alexa webpages through an FTE tunnel, incurring an average overhead of roughly 5%.

15:17 [Pub][ePrint] \"Metaproofs\" (and their Cryptographic Applications), by Alfredo De Santis and Moti Yung

  We develop a non-interactive proof-system which we call \"Metaproof\"

(mu-NIZK proof system); it provides a proof of \"the existence of a proof to a statement\". This meta-mathematical notion indeed seems redundant when we deal with proving NP statements, but in

the context of zero-knowledge theory and cryptography it has a large variety of applications.

Combined with another tool we develop which we call \"on-line simulatable NIZK proof system\", it is the key tool used to solve the open problem of the existence of a many prover non-interactive zero-knowledge system (MP-NIZK proof system). This problem was presented

by Micali when the important notion of non-interactive zero-knowledge proofs (NIZK) was rst suggested and implemented for a sole prover.

The solution immensely enlarges the domain of applications of the NIZK model. The work also provides a new connection between bounded (single-theorem) non-interactive zero-knowledge proofs and the unbounded (multi-theorem) one. This may help in reducing

the complexity assumption upon which to base NIZK systems.

Remark: This is a full version (with more details, more material, and with new proofs) of the Crypto 1990 paper on Metaproof. Over the years, the concept has been used and reinvented for specic settings beyond the original ones, by others; (which has made it more useful). Recently, we were asked about this paper and about details, so here they are! For historical reasons, except for this remark, this version is presented as it was in the above mentioned date under the above

aliations, though we did not pursue publication before!