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

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.

22:17 [Pub][ePrint] Succinct Non-Interactive Arguments for a von Neumann Architecture, by Eli Ben-Sasson and Alessandro Chiesa and Eran Tromer and Madars Virza

  We design and build a system that enables clients to verify the outputs of programs executed by untrusted servers. A server provides a succinct non-interactive zero-knowledge proof (also known as a zk-SNARK), which the client verifies to ascertain correct execution.

The system has two components: a cryptographic proof system for verifying satisfiability of arithmetic circuits, and a circuit generator to translate program executions to such circuits. Our design of both components improves in functionality and efficiency over previous work, as follows.

Our circuit generator is the first to be universal: it does not need to know the program, but only a bound on its running time. It is also the first to support programs expressed as code for a von Neumann RISC random-access memory architecture, where programs may use just-in-time compilation and self-modifying code. Moreover, the dependence on program size is additive (instead of multiplicative as in prior works), allowing efficient verification of large programs.

The cryptographic proof system significantly improves proving and verification times, using a new pairing-based cryptographic library tailored to the protocol.

We evaluated our system for programs with up to 10,000 instructions, running for up to 32,000 machine steps, each of which can arbitrarily access random-access memory; and demonstrated it executing programs that use just-in-time compilation. Our proofs are 230 bytes long at 80 bits of security, or 288 bytes long at 128 bits of security. Typical verification time is 5 ms, regardless of the original program\'s running time.

22:17 [Pub][ePrint] Policy-Based Non-interactive Outsourcing of Computation using multikey FHE and CP-ABE, by Michael Clear and Ciaran McGoldrick

  We consider the problem of outsourced computation that operates on encrypted inputs supplied by multiple independent parties. To facilitate fine-grained access control, it would be desirable if each party could encrypt her input under an appropriate access policy. Moreover, a party should only be authorized to decrypt the result of a computation performed on a set of encrypted inputs if his credentials satisfy the composition of all input policies. There has been limited success so far achieving homomorphic encryption in the functional setting; that is, for primitives such as Ciphertext-Policy Attribute Based Encryption (CP-ABE) and Identity Based Encryption (IBE). We introduce a new primitive that captures homomorphic encryption with support for access policies and policy composition. We then present a generic construction using CP-ABE and multikey Fully-Homomorphic encryption (FHE). Furthermore, we show that a CP-ABE scheme that is homomorphic for circuits of polylogarithmic depth in some parameter $m$ implies a CP-ABE scheme that is homomorphic for circuits of arity $m$ and unbounded depth.

22:17 [Pub][ePrint] Public-Key Encryption with Lazy Parties, by Kenji Yasunaga

  In a public-key encryption scheme,

if a sender is not concerned about the security of a message and

is unwilling to generate costly randomness,

the security of the encrypted message can be compromised.

This is caused by the \\emph{laziness} of the sender.

In this work, we characterize \\emph{lazy parties} in cryptography.

Lazy parties are regarded as honest parties in a protocol,

but they are not concerned about the security of the protocol in

a certain situation.

In such a situation, they behave in an honest-looking way, and are unwilling to do a costly task.

We study, in particular, public-key encryption with lazy parties.

Specifically, as the first step toward understanding the behavior of lazy parties

in public-key encryption, we consider a rather simple setting in which

the costly task is to generate randomness used in algorithms,

and parties can choose either costly good randomness or cheap bad randomness.

We model lazy parties as rational players who behaves rationally to

maximize their utilities, and define a security game between lazy parties

and an adversary.

A secure encryption scheme requires that the game is conducted by

lazy parties in a secure way if they follow a prescribed strategy,

and the prescribed strategy is a good equilibrium solution for the game.

Since a standard secure encryption scheme does not work for lazy parties,

we present some public-key encryption schemes that are secure for lazy parties.

13:17 [Pub][ePrint] RSA Key Extraction via Low-Bandwidth Acoustic Cryptanalysis, by Daniel Genkin and Adi Shamir and Eran Tromer

  Many computers emit a high-pitched noise during operation, due to vibration in some of their electronic components. These acoustic emanations are more than a nuisance: they can convey information about the software running on the computer, and in particular leak sensitive information about security-related computations. In a preliminary presentation (Eurocrypt\'04 rump session), we have shown that different RSA keys induce different sound patterns, but it was not clear how to extract individual key bits. The main problem was that the acoustic side channel has a very low bandwidth (under 20 kHz using common microphones, and a few hundred kHz using ultrasound microphones), many orders of magnitude below the GHz-scale clock rates of the attacked computers.

In this paper we describe a new acoustic cryptanalysis key extraction attack, applicable to GnuPG\'s current implementation of RSA. The attack can extract full 4096-bit RSA decryption keys from laptop computers (of various models), within an hour, using the sound generated by the computer during the decryption of some chosen ciphertexts. We experimentally demonstrate that such attacks can be carried out, using either a plain mobile phone placed next to the computer, or a more sensitive microphone placed 4 meters away.

Beyond acoustics, we demonstrate that a similar low-bandwidth attack can be performed by measuring the electric potential of a computer chassis. A suitably-equipped attacker need merely touch the target computer with his bare hand, or get the required leakage information from the ground wires at the remote end of VGA, USB or Ethernet cables.

13:17 [Pub][ePrint] Practical Dual-Receiver Encryption---Soundness, Complete Non-Malleability, and Applications, by Sherman S.M. Chow and Matthew Franklin and Haibin Zhang

  We reformalize and recast dual-receiver encryption (DRE) proposed in CCS \'04, a public-key encryption (PKE) scheme for encrypting to two independent recipients in one shot. We start by defining the crucial soundness property for DRE, which ensures that two recipients will get the same decryption result. While conceptually simple, DRE with soundness turns out to be a powerful primitive for various goals for PKE, such as complete non-malleability (CNM) and plaintext-awareness (PA). We then construct practical DRE schemes without random oracles under the Bilinear Decisional Diffie-Hellman assumption, while prior approaches rely on random oracles or inefficient non-interactive zero-knowledge proofs. Finally, we investigate further applications or extensions of DRE, including DRE with CNM, combined use of DRE and PKE, strengthening two types of PKE schemes with plaintext equality test, off-the-record messaging with a stronger notion of deniability, etc.