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

2014-09-29
09:17 [Pub][ePrint] Adaptively Secure Broadcast Encryption with Small System Parameters, by Mark Zhandry

  We build the first public-key broadcast encryption system that simultaneously achieves adaptive security against arbitrary number of colluders, has small system parameters, and has a security proof based on non-interactive falsifiable assumptions. Our scheme is built from composite order multilinear maps and enjoys a ciphertext overhead, private key size, and public key size that are are all poly-logarithmic in the total number of users. Previous broadcast schemes with similar parameters are either proven secure in a weaker static model, or rely on powerful tools such as program obfuscation and involve non-falsifiable assumptions.



09:17 [Pub][ePrint] Cryptographic Reverse Firewalls, by Ilya Mironov and Noah Stephens-Davidowitz

  Recent revelations by Edward Snowden show that a user\'s own hardware and software can be used against her in various ways (e.g., to leak her private information). And, a series of recent announcements has shown that widespread implementations of cryptographic software often contain serious bugs that cripple security. This motivates us to consider the following (seemingly absurd) question: How can we guarantee a user\'s security when she may be using a malfunctioning or arbitrarily compromised machine? To that end, we introduce the notion of a cryptographic reverse firewall (RF). Such a machine sits between the user\'s computer and the outside world, potentially modifying the messages that she sends and receives as she engages in a cryptographic protocol.

A good reverse firewall accomplishes three things: (1) it maintains functionality, so that if the user\'s computer is working correctly, the RF will not break the functionality of the underlying protocol; (2) it preserves security, so that regardless of how the user\'s machine behaves, the presence of the RF will provide the same security guarantees as the properly implemented protocol; and (3) it resists exfiltration, so that regardless of how the user\'s machine behaves, the presence of the RF will prevent the machine from leaking any information to the outside world. Importantly, we do not model the firewall as a trusted party. It does not share any secrets with the user, and the protocol should be both secure and functional without the firewall (when it is implemented correctly).

Our security definition for reverse firewalls depends on the security notion(s) of the underlying protocol. As such, our model generalizes much prior work and provides a general framework for building cryptographic schemes that remain secure when run on compromised machine. It is also a modern take on a line of work that received considerable attention in the 80s and 90s.

We show that our definition is achievable by constructing a private function evaluation protocol with a secure reverse firewall for each party. Along the way, we design an oblivious transfer protocol that also has a secure RF for each party, and a rerandomizable garbled circuit that is both more efficient and more secure than previous constructions. Finally, we show how to convert \\emph{any} protocol into a protocol with an exfiltration-resistant reverse firewall for all parties. (In other words, we provide a generic way to prevent a tampered machine from leaking information to an eavesdropper via any protocol.)



09:17 [Pub][ePrint] How to Efficiently Evaluate RAM Programs with Malicious Security, by Arash Afshar and Zhangxiang Hu and Payman Mohassel and Mike Rosulek

  Secure 2-party computation (2PC) is becoming practical for some applications. However, most approaches are limited by the fact that the desired functionality must be represented as a boolean circuit. In response, random-access machines (RAM programs) have recently been investigated as a promising alternative representation.

In this work, we present the first practical protocols for evaluating RAM programs with security against malicious adversaries. A useful efficiency measure is to divide the cost of malicious-secure evaluation of $f$ by the cost of semi-honest-secure evaluation of $f$. Our RAM protocols achieve ratios matching the state of the art for circuit-based 2PC. For statistical security $2^{-s}$, our protocol without preprocessing achieves a ratio of $s$; our online-offline protocol has a pre-processing phase and achieves online ratio $\\sim 2 s / \\log T$, where $T$ is the total execution time of the RAM program.

To summarize, our solutions show that the ``extra overhead\" of obtaining malicious security for RAM programs (beyond what is needed for circuits) is minimal and does not grow with the running time of the program.



09:17 [Pub][ePrint] Montgomery Modular Multiplication on ARM-NEON Revisited, by Hwajeong Seo, Zhe Liu, Johann Groschadl, Jongseok Choi, and Howon Kim

  Montgomery modular multiplication constitutes the \"arithmetic foundation\"

of modern public-key cryptography with applications ranging from RSA, DSA

and Diffie-Hellman over elliptic curve schemes to pairing-based cryptosystems. The increased prevalence of SIMD-type instructions in commodity processors (e.g. Intel SSE, ARM NEON) has initiated a massive body of research on vector-parallel implementations of Montgomery modular multiplication. In this paper, we introduce the Cascade Operand Scanning (COS) method to speed up multi-precision multiplication on SIMD architectures. We developed the COS technique with the goal of reducing Read-After-Write (RAW) dependencies in the propagation of carries, which also reduces the number of pipeline stalls (i.e. bubbles). The COS method operates on 32-bit words in a row-wise fashion (similar to the operand-scanning method) and does not require a \"non-canonical\" representation of operands with a reduced radix. We show that two COS computations can be \"coarsely\" integrated into an efficient vectorized variant of Montgomery multiplication, which we call Coarsely Integrated Cascade Operand Scanning (CICOS) method. Due to our sophisticated instruction scheduling, the CICOS method reaches record-setting execution times for Montgomery modular multiplication on ARM-NEON platforms. Detailed benchmarking results obtained on an ARM Cortex-A9 and Cortex-A15 processors show that the proposed CICOS method outperforms Bos et al\'s implementation from SAC 2013 by up to 57% (A9) and 40% (A15), respectively. Furthermore, our COS multiplication is faster than lastest GMP 6.0.0 by up to 55% (A9) and 52% (A15), respectively.





2014-09-26
11:33 [Job][New] postdoc and PhD student, Ecole Polytechnique Federale de Lausanne, Lausanne, Switzerland

  A postdoc position is available at the laboratory for cryptologic algorithms at the Ecole Polytechnique Federale de Lausanne. The position is for at most 4 years.

Candidates with an interest and proven track record in computational aspects of asymmetric cryptosystems (such as RSA and (EC)DSA) and of the mathematical problems underlying their security are encouraged to apply.

We are also looking for PhD students interested in the same topics (see also phd.epfl.ch/edic).

09:17 [Pub][ePrint] Eliminating Leakage in Reverse Fuzzy Extractors, by André Schaller, Boris Skoric, Stefan Katzenbeisser

  In recent years Physically Unclonable Functions (PUFs) have been proposed as a promising building block for security related scenarios like key storage and authentication. PUFs are physical systems and as such their responses are inherently noisy, precluding a straightforward derivation of cryptographic key material from raw PUF measurements. To overcome this drawback, Fuzzy Extractors are used to eliminate the noise and guarantee robust outputs. A special type are Reverse Fuzzy Extractors, shifting the computational load of error correction towards a computationally powerful verifier. However, the Reverse Fuzzy Extractor reveals error patterns to any eavesdropper, which may cause privacy issues (if the PUF key is drifting, the error pattern is linkable to the identity) and even security problems (if the noise is data-dependent and multiple protocol transcripts can be linked to the same user). In this work we investigate this leakage and propose a modified protocol that eliminates the problem.



09:17 [Pub][ePrint] A survey of Fault Attacks in Pairing Based Cryptography, by Nadia El Mrabet and Jacques J.A. Fournier and Louis Goubin and Ronan Lashermes

  The latest implementations of pairings allow efficient schemes for Pairing Based Cryptography. These make the use of pairings suitable for small and constrained devices (smart phones, smart cards...) in addition to more powerful platforms. As for any cryptographic algorithm which may be deployed in insecure locations, these implementations must be secure against physical attacks, and in particular fault attacks. In this paper, we present the state-of-the-art of fault attacks against pairing algorithms, more precisely fault attacks against the Miller algorithm and the final exponentiation which are the two parts of a pairing calculation.



09:17 [Pub][ePrint] Concise Multi-Challenge CCA-Secure Encryption and Signatures with Almost Tight Security, by Benoit Libert and Marc Joye and Moti Yung and Thomas Peters

  To gain strong confidence in the security of a public-key scheme, it

is most desirable for the security proof to feature a \\emph{tight}

reduction between the adversary and the algorithm solving the

underlying hard problem. Recently, Chen and Wee (Crypto\\,\'13) described the first Identity-Based Encryption scheme with almost

tight security under a standard assumption. Here, ``almost tight\'\'

means that the security reduction only loses a factor $O(\\lambda)$

-- where $\\lambda$ is the security parameter -- instead of a factor

proportional to the number of adversarial queries. Chen and Wee

also gave the shortest signatures whose security almost tightly

relates to a simple assumption in the standard model. Also recently,

Hofheinz and Jager (Crypto\\,\'12) constructed the first CCA-secure

public-key encryption scheme in the multi-user setting with tight

security. These constructions give schemes that are significantly

less efficient in length (and thus, processing) when compared with

the earlier schemes with loose reductions in their proof of

security. Hofheinz and Jager\'s scheme has a ciphertext of a few

hundreds of group elements, and they left open the problem of

finding truly efficient constructions. Likewise, Chen and Wee\'s

signatures and IBE schemes are somewhat less efficient than previous

constructions with loose reductions from the same assumptions. In

this paper, we consider space-efficient schemes with security almost

tightly related to standard assumptions. As a step in solving the

open question by Hofheinz and Jager, we construct an efficient

CCA-secure public-key encryption scheme whose chosen-ciphertext

security in the multi-challenge, multi-user setting almost tightly

relates to the DLIN assumption (in the standard model). Quite

remarkably, the ciphertext size decreases to $69$ group elements

under the DLIN assumption whereas the best previous solution required about $400$ group elements. Our scheme is obtained by taking advantage of a new almost tightly secure signature scheme (in the standard model) we develop here and which is based on the recent concise proofs of linear subspace membership in the quasi-adaptive

non-interactive zero-knowledge setting (QA-NIZK) defined by Jutla

and Roy (Asiacrypt\\,\'13). Our signature scheme reduces the length of the previous such signatures (by Chen and Wee) by $37\\%$ under the Decision Linear assumption, by almost $50\\%$ under the $K$-LIN assumption, and it becomes only $3$ group elements long under the Symmetric eXternal Diffie-Hellman assumption. Our signatures are obtained by carefully combining the proof technique of Chen and Wee and the above mentioned QA-NIZK proofs.



09:17 [Pub][ePrint] Sieving for shortest vectors in lattices using angular locality-sensitive hashing, by Thijs Laarhoven

  By replacing the brute-force list search in sieving algorithms with angular locality-sensitive hashing, we get both theoretical and practical speed-ups for finding shortest vectors in lattices. Optimizing for time, we obtain a heuristic time and space complexity for solving SVP of 2^(0.3366n). Preliminary experiments show that the proposed HashSieve algorithm already outperforms the GaussSieve in low dimensions, and that the practical increase in the space complexity is much smaller than the asymptotic bounds suggest. Using probing we show how we can further reduce the space complexity at the cost of slightly increasing the time complexity.



09:17 [Pub][ePrint] Universal Signature Aggregators, by Susan Hohenberger and Venkata Koppula and Brent Waters

  We introduce the concept of universal signature aggregators. In a universal signature aggregator system, a third party, using a set of common reference parameters, can aggregate a collection of signatures produced from any set of signing algorithms (subject to a chosen length constraint) into one short signature whose length is independent of the number of signatures aggregated. In prior aggregation works, signatures can only be aggregated if all signers use the same signing algorithm (e.g., BLS) and shared parameters. A universal aggregator can aggregate across schemes even in various algebraic settings (e.g., BLS, RSA, ECDSA), thus creating novel opportunities for compressing authentication overhead. It is especially compelling that existing public key infrastructures can be used and that the signers do not have to alter their behavior to enable aggregation of their signatures.

We provide multiple constructions and proofs of universal signature aggregators based on indistinguishability obfuscation and other supporting primitives. We detail our techniques as well as the tradeoffs in features and security of our solutions.



09:17 [Pub][ePrint] Decoy-based information security, by Vladimir Shpilrain

  In this survey, we discuss an emerging concept of decoy-based information security, or security without computational assumptions.

In particular, we show how this concept can be implemented to

provide security against (passive) computationally unbounded adversary in some public-key encryption protocols. In the world of symmetric cryptography, decoy-based security finds a wide range of applications, notably to secure delegation of computation to another party. We single out the scenario where a computationally limited party wants to send an encrypted message to a computationally superior party using the RSA protocol, thereby providing another kind of application of decoy ideas in a public-key setting. With typical RSA parameters, decoy-based method of delegation of computation improves the efficiency for the sender by several orders of magnitude.