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

10:17 [Pub][ePrint] MaxMinMax problem and sparse equations over finite fields, by Igor Semaev

  Asymptotical complexity of sparse equation systems over finite field $F_q$ is studied.

Let the variable sets belong to a fixed family $\\mathcal{X}=\\{X_1,\\ldots,X_m\\}$ while

the polynomials $f_i(X_i)$ are taken independently and uniformly at random from the set of all polynomials

of degree $\\leq q-1$ in each of the

variables in $X_i$. In particular, for $|X_i|\\le3$, $m=n$, we prove

the average complexity of finding all solutions to $f_i(X_i)=0, i=1,\\ldots,m$ by Gluing algorithm ( Semaev, Des. Codes Cryptogr., vol. 49 (2008), pp.47--60) is at most $

q^{\\frac{n}{5.7883}+O(\\log n)}$ for arbitrary $\\mathcal{X}$ and $q$. The proof results from a detailed analysis of 3-MaxMinMax problem, a novel problem for hyper-graphs.

10:17 [Pub][ePrint] Pseudorandom Generator Based on Hard Lattice Problem, by Kuan Cheng

  This paper studies how to construct a pseudorandom generator using hard lattice problems.

We use a variation of the classical hard problem \\emph{Inhomogeneous Small Integer Solution} ISIS of lattice, say \\emph{Inhomogeneous Subset Sum Solution} ISSS. ISSS itself is a hash function. Proving the preimage sizes ISSS hash function images are almost the same, we construct a pseudorandom generator using the method in \\cite{GKL93}. Also, we construct a pseudoentropy generator using the method in \\cite{HILL99}. Most theoretical PRG constructions are not feasible in fact as they require rather long random bits as seeds. Our PRG construction only requires seed length to be $O(n^{2}\\log_{2} n)$ which is feasible practically.

10:17 [Pub][ePrint] $GF(2^n)$ Bit-Parallel Squarer Using Generalized Polynomial Basis For a New Class of Irreducible Pentanomials, by Xi Xiong and Haining Fan

  We present explicit formulae and complexities of bit-parallel $GF(2^{n})$ squarers for a new class of irreducible pentanomials

$x^{n}+x^{n-1}+x^{k}+x+1$, where $n$ is odd and $1

23:37 [Event][New] YACC 2014: Yet Another Conference on Cryptography

  Submission: 8 January 2014
Notification: 28 February 2014
From June 9 to June 13
Location: ´┐Żle de Porquerolles, France
More Information:

22:17 [Pub][ePrint] Comments on: EIBAS - an efficient identity broadcast authentication scheme in wireless sensor networks, by Yalin Chen and Jue-Sam Chou

  Recently, Shm et al. Proposed an efficient identity-based broadcast authentication scheme based on Tso et al.\'s IBS scheme with message recovery to achieve security requirements in wireless sensor networks. They claim that their scheme can achieve security requirements and mitigated DOS attack by limiting the times of signature verification failures in wireless sensor networks (WSN). However, we found that the scheme cannot attain the security level as they claimed. We will demonstrate it in this article.

16:17 [Pub][ePrint] New Constructions of Revocable Identity-Based Encryption from Multilinear Maps, by Seunghwan Park and Kwangsu Lee and Dong Hoon Lee

  A revocation mechanism in cryptosystems for a large number of users is absolutely necessary to maintain the security of whole systems. A revocable identity-based encryption (RIBE) provides an efficient revocation method in IBE that a trusted authority periodically broadcasts an update key for non-revoked users and a user can decrypt a ciphertext if he is not revoked in the update key. Boldyreva, Goyal, and Kumar (CCS 2008) defined RIBE and proposed an RIBE scheme that uses a tree-based revocation encryption scheme to revoke users. However, this approach has an inherent limitation that the number of private key elements and update key elements cannot be constant. In this paper, to overcome the previous limitation, we devise a new technique for RIBE and propose RIBE schemes with a constant number of private key elements. We achieve the following results:

- We first devise a new technique for RIBE that combines hierarchical IBE (HIBE) scheme and a public-key broadcast encryption (PKBE) scheme by using multilinear maps. In contrast to the previous technique for RIBE, our technique uses a PKBE scheme in bilinear maps for revocation to achieve short private keys and update keys.

- Following our new technique for RIBE, we propose an RIBE scheme in 3-leveled multilinear maps that combines the HIBE scheme of Boneh and Boyen and the PKBE scheme of Boneh, Gentry, and Waters. The private key and update key of our scheme have a constant number of group elements. To prove the security of our scheme, we introduce a new complexity assumption in multilinear maps, and prove its security in the selective revocation list model.

- Next, we propose another RIBE scheme that reduces the number of public parameters by using the parallel construction technique of PKBE. We could reduce the number of public parameters by using the fact that only the trusted authority in RIBE can broadcast an update key.

16:17 [Pub][ePrint] Can Bitcoin Scale? Secure High-Rate Transaction Processing in The Bitcoin Network, by Yonatan Sompolinsky and Aviv Zohar

  Bitcoin is a potentially disruptive new crypto-currency based on a decentralized open-source protocol which is gradually gaining popularity. Perhaps the most important question that will affect Bitcoin\'s success, is whether or not it will be able to scale to support the high volume of transactions required from a global currency system.

We investigate the restrictions on the rate of transaction processing in Bitcoin as a function of both the bandwidth available to nodes and the network delay, both of which lower the efficiency of Bitcoin\'s transaction processing.

The security analysis done by Bitcoin\'s creator Satoshi Nakamoto~\\cite{nakamoto2008bitcoin} assumes that block propagation delays are negligible compared to the time between blocks---an assumption that does not hold when the protocol is required to process transactions at high rates. We improve upon the original analysis and remove this assumption.

Using our results, we are able to give bounds on the number of transactions per second the protocol can handle securely. Building on previously published measurements by Decker and Wattenhofer~\\cite{Decker2013Information}, we show these bounds are currently more restrictive by an order of magnitude than the bandwidth needed to stream all transactions. We additionally show how currently planned improvements to the protocol, namely the use of transaction hashes in blocks (instead of complete transaction records), will dramatically alleviate these restrictions.

Finally, we present an easily implementable modification to the way Bitcoin constructs its main data structure, the blockchain, that immensely improves security from attackers, especially when the network operates at high rates. This improvement allows for further increases in the number of transactions processed per second. We show that with our proposed modification, significant speedups can be gained in confirmation time of transactions as well. The block generation rate can be securely increased to more than one block per second -- a 600 fold speedup compared to today\'s rate, while still allowing the network to processes many transactions per second.

16:17 [Pub][ePrint] New Speed Records for Montgomery Modular Multiplication on 8-bit AVR Microcontrollers, by Zhe Liu and Johann Gro{\\ss}sch{\\\"a}dl

  Modular multiplication of large integers is a performance-critical arithmetic operation of many public-key cryptosystems such as RSA, DSA, Diffie-Hellman (DH) and their elliptic curve-based variants ECDSA and ECDH. The computational cost of modular multiplication and related operations (e.g. exponentiation) poses a practical challenge to the widespread deployment of public-key cryptography, especially on embedded devices equipped with 8-bit processors (smart cards, wireless sensor nodes, etc.). In this paper, we describe basic software techniques to improve the performance of Montgomery modular multiplication on 8-bit AVR-based microcontrollers. First, we present a new variant of the widely-used hybrid method for multiple precision multiplication that is 10.6% faster than the original hybrid technique of Gura et al. Then, we discuss different hybrid Montgomery multiplication algorithms, including Hybrid Finely Integrated Product Scanning (HFIPS), and introduce a novel approach for Montgomery multiplication, which we call Hybrid Separated Product Scanning (HSPS). Finally, we show how to perform the modular subtraction of Montgomery reduction in a regular fashion without execution of conditional statements so as to counteract Simple Power Analysis (SPA) attacks. Our AVR implementation of the HFIPS and HSPS method outperforms the Montgomery multiplication of the MIRACL Crypto SDK by 21.6% and 14.3%, respectively, and is twice as fast as the modular multiplication of the TinyECC library.

06:37 [Job][New] Computer Engineering, Ariel University, Israel, Mediterranean

  The Department of Electrical and Electronic Engineering at Ariel University (Israel) invites applications for a tenure-track Lecturer or Senior Lecturer (Assistant Professor) position to begin in 2014.

The position is full-time, tenure-track, with eligible benefits. The candidate will teach undergraduate and graduate courses in the computer engineering track, including required courses such as Introduction to programming in C, Introduction to microprocessors, and elective courses such as Computer networking laboratory and Assembly language.

The candidate\\\'s areas of research should be in one of the following areas:

Coding, cryptography, information protection, cyber security

Computer network design and analysis

Computer architecture and parallel distributed processing

Data storage

Compilers and operating systems

Wireless sensor networks

Cloud computing

Quantum computers

22:17 [Pub][ePrint] MQ Signature and Proxy Signature Schemes with Exact Security Based on UOV Signature, by Shaohua Tang, Jiahui Chen, Lingling Xu, Xiaoyu Li

  Multivariate public key cryptography which relies on MQ (Multivariate Quadratic) problems is one of the main approaches to guarantee the security of communication in the post-quantum world. In this paper, we propose a combined MQ signature scheme based on the yet unbroken UOV (Unbalanced Oil and Vinegar) signature if parameters are properly chosen. Our scheme can not only reduce the public key size of the UOV signature, but also provide more tighter bound of security against chosen-message attack in the random oracle model. On the other hand, we propose a proxy signature scheme based on our proposed combined signature scheme. Additionally, we give a strict security proof for our proxy signature scheme. Finally, we present experiments for all of our proposed schemes and the baseline schemes. Comparisons with related schemes show that our work has some advantages on performance along

with more strict security.

22:17 [Pub][ePrint] Efficient Hardware Implementation of MQ Asymmetric Cipher PMI+ on FPGAs, by Shaohua Tang and Bo Lv and Guomin Chen and Zhiniang Peng

  PMI+ is a Multivariate Quadratic (MQ) public key algorithm used for encryption and decryption operations, and belongs to post quantum cryptography.We designs a hardware on FPGAs to efficiently implement PMI+ in this paper.Our main contributions are that,firstly, a hardware architecture of encryption and decryption of PMI+ is developed, and description of corresponding hardware algorithm is proposed;secondly, basic arithmetic units are implemented with higher efficiency that multiplication, squaring, vector dot product and power operation are implemented in full parallel;and thirdly, an optimized implementation for core module, including optimized large power operation, is achieved. The encryption and decryption hardware of PMI+ is efficiently realized on FPGA by the above optimization and improvement.It is verified by experiments that the designed hardware can complete an encryption operation within 497 clock cycles, and the clock frequency can be up to 145.6MHz,and the designed hardware can complete a decryption operation within 438 clock cycles wherein the clock frequency can be up to 37.04MHz.