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

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.

13:17 [Pub][ePrint] Using the Joint Distributions of a Cryptographic Function in Side Channel Analysis, by Yanis Linge and Cecile Dumas and Sophie Lambert-Lacroix

  The Side Channel Analysis is now a classic way to retrieve a secret key in the smart-card world. Unfortunately, most of the ensuing attacks require the plaintext or the ciphertext used by the embedded algorithm. In this article, we present a new method for exploiting the leakage of a device without this constraint. Our attack is based on a study of the leakage distribution of internal data of a cryptographic function and can be performed not only at the beginning or the end of the algorithm, but also at every instant that involves the secret key. This paper focuses on the distribution study and the resulting attack. We also propose a way to proceed in a noisy context using smart distances. We validate our proposition by practical results on an AES128 software implemented on a ATMega2561 and on the DPA contest v4.

13:17 [Pub][ePrint] On the Implausibility of Differing-Inputs Obfuscation and Extractable Witness Encryption with Auxiliary Input , by Sanjam Garg and Craig Gentry and Shai Halevi and Daniel Wichs

  The notion of differing-inputs obfuscation (diO) was introduced by Barak et al. (CRYPTO 2001). It guarantees that for any two circuits $C_0, C_1$, for which it is difficult to use their description and come up with an input $x$ on which they differ $C_0(x) \\neq C_1(x)$, it should also be difficult to distinguish the obfuscation of $C_0$ from that of $C_1$. This is a strengthening of indistinguishability obfuscation, where the above is only guaranteed for circuits that agree on all inputs: $C_0(x) = C_1(x)$ for all $x$. Two recent works of Ananth et al. (ePrint 2013) and Boyle et al. (TCC 2014) study the notion of diO in the setting where the attacker is also given some auxiliary information related to the circuits, showing that this notion leads to many interesting applications. One of these applications is extractable witness encryption, defined by Goldwasswer et al. (CRYPTO \'13), which in turn leads to constructions of functional encryption and reusable garbling schemes that work directly on Turing Machines rather than circuits.

In this work, we show that the existence of general-purpose diO with general auxiliary input leads to a surprising ``implausible\'\' consequence: in particular, it would show the impossibility of obfuscating a specific circuit $C^*$ with specific auxiliary input $\\aux^*$ in a way that hides some specific information. In particular, we put forth the assumption that such special-purpose obfuscation exists, and under this assumption, we show that general-purpose diO does not exist. This special-purpose obfuscation assumption isn\'t implied by diO itself and hence we do not get an unconditional impossibility result. However, the special-purpose obfuscation assumption is a falsifiable assumption which we do not know how to break for candidate obfuscation schemes. Showing the existence of general-purpose diO with general auxiliary input would necessitate showing how to break this assumption. We also give a similar result showing the impossibility of extractable witness encryption under the same special-purpose obfuscation assumption.

13:17 [Pub][ePrint] Privacy Preserving Enforcement of Sensitive Policies in Outsourced and Distributed Environments, by Muhammad Rizwan Asghar

  The enforcement of sensitive policies in untrusted environments is still an open challenge for policy-based systems. On the one hand, taking any appropriate security decision requires access to these policies. On the other hand, if such access is allowed in an untrusted environment then confidential information might be leaked by the policies. The key challenge is how to enforce sensitive policies and protect content in untrusted environments. In the context of untrusted environments, we mainly distinguish between outsourced and distributed environments. The most attractive paradigms concerning outsourced and distributed environments are cloud computing and opportunistic networks, respectively.

In this dissertation, we present the design, technical and implementation details of our proposed policy-based access control mechanisms for untrusted environments. First of all, we provide full confidentiality of access policies in outsourced environments, where service providers do not learn private information about policies during the policy deployment and evaluation phases. Our proposed architecture is such that we are able to support expressive policies and take into account contextual information before making any access decision. The system entities do not share any encryption keys and even if a user is deleted, the system is still able to perform its operations without requiring any action. For complex user management, we have implemented a policy-based Role-Based Access Control (RBAC) mechanism, where users are assigned roles, roles are assigned permissions and users execute permissions if their roles are active in the session maintained by service providers. Finally, we offer the full-fledged RBAC policies by incorporating role hierarchies and dynamic security constraints.

In opportunistic networks, we protect content by specifying expressive access control policies. In our proposed approach, brokers match subscriptions against policies associated with content without compromising privacy of subscribers. As a result, an unauthorised broker neither gains access to content nor learns policies and authorised nodes gain access only if they satisfy fine-grained policies specified by publishers. Our proposed system provides scalable key management in which loosely-coupled publishers and subscribers communicate without any prior contact. Finally, we have developed a prototype of the system that runs on real smartphones and analysed its performance.

13:17 [Pub][ePrint] How to Delegate Computations: The Power of No-Signaling Proofs, by Yael Tauman Kalai and Ran Raz and Ron Rothblum

  We construct a 1-round delegation scheme (i.e., argument-system)

for every language computable in time t=t(n), where the running

time of the prover is poly(t) and the running time of the

verifier is n*polylog(t). In particular, for every language in P

we obtain a delegation scheme with almost linear time

verification. Our construction relies on the existence of a

computational sub-exponentially secure private information

retrieval (PIR) scheme.

The proof exploits a curious connection between the problem of

computation delegation and the model of multi-prover interactive

proofs that are sound against no-signaling (cheating) strategies,

a model that was studied in the context of multi-prover

interactive proofs with provers that share quantum entanglement,

and is motivated by the physical principle that information

cannot travel faster than light.

For any language computable in time t=t(n), we construct a

multi-prover interactive proof (MIP) that is sound against

no-signaling strategies, where the running time of the provers is

poly(t), the number of provers is polylog(t), and the running

time of the verifier is n*polylog(t).

In particular, this shows that the class of languages that have

polynomial-time MIPs that are sound against no-signaling

strategies, is exactly EXP. Previously, this class was only known

to contain PSPACE.

To convert our MIP into a 1-round delegation scheme, we use the

method suggested by Aiello et-al (ICALP, 2000), which makes use

of a PIR scheme. This method lacked a proof of security. We prove

that this method is secure assuming the underlying MIP is secure

against no-signaling provers.