International Association
for Cryptologic Research

Known methods for obfuscating a circuit need to represent the circuit as a branching program and then use a multilinear map to encrypt the branching program. Multilinear maps are, however, too inefficient for encrypting the branching program. We found a dynamic encoding method which effectively singles out different inputs in the context of the matrix randomization technique of Kilian and Gentry et al., so that multilinear maps are no longer needed. To make the method work, we need the branching programs to be regular. For such branching programs, we also give most efficient constructions for NC1 circuits. This results in a much more efficient core obfuscator for NC1 circuits.

Event date: 16 December to 18 December 2016
Submission deadline: 30 June 2016
Notification: 5 August 2016

The list of papers accepted to FSE 2016 is now online at http://fse.rub.de/accepted.html

Dear IACR members,

The past year has again seen vibrant research activity in cryptology and many successful IACR events. For example, the IACR Cryptology Schools program has gained momentum with four schools sponsored in 2015. Another significant change was the introduction of parallel sessions at Eurocrypt, Crypto, and Asiacrypt to cope with the increased number of high-quality papers (more on that later). Last but not least, Alexandra Boldyreva has joined as co-editor of the Cryptology ePrint Archive, replacing Tal Rabin.

Board of Directors

As it happens every year, the composition of the Board has changed for 2016. I'd like to thank the leaving Board members, Svetla Petkova-Nikova, Steven Galbraith, Thomas Ristenpart, and Tom Berson, for their contributions to the IACR and to cryptology research.

A very special *thank you* from my side goes to Tom Berson, Fellow of the IACR, former president, secretary and much more: He was among the founding members of this association and has held almost every position since 1983; though his work in building the IACR he helped the individuals in the field make careers in research and technology; his dedication to the organization positioned cryptology to become an independent and vibrant domain today. We are sure he will enjoy board-meeting-free Sundays at the conferences in the future!

Joining the Board are three colleagues: Phil Rogaway has been newly elected to the Board in 2015, Steven Myers and SM Yiu join in their roles as General Chairs of Crypto and Asiacrypt in 2017 -- welcome!

Conference attendance

As many members have asked about attendance at our conferences I am including here the attendee counts at the 2015 events:

Asiacrypt 2015: 200
CHES 2015: 448
Crypto 2015: 322
Eurocrypt 2015: 324
FSE 2015: 136
PKC 2015: 144
TCC 2015: 145


Referendum on parallel sessions and bylaws modifications

The Board had suggested for many years that Program Chairs find a way to accommodate the increased number of submitted papers, including organizing parallel sessions. In 2014 the Board asked the Program Chairs of the 2015 general conferences (Eurocrypt, Crypto, Asiacrypt) directly to introduce parallel sessions in the program. The echo at the conferences was positive. As promised before we will now organize a formal membership vote on the question of continuing with parallel sessions like this.

With the same referendum we also propose to change the bylaws in minor ways. The document currently distinguishes between "IACR conferences" (Eurocrypt, Crypto, Asiacrypt) and "IACR workshops" (CHES, FSE, PKC, TCC). Since the latter have by far surpassed the common notion of a workshop in scope and attendance, we will rename them to "IACR Area Conferences". Some further small changes are also proposed.

You will receive email form the Helios voting system with your credential to vote. The full text of the referendums appears at iacr.org/elections/2016-vote/announcement.html.

Conferences

The first IACR conference in 2016 has already taken place (TCC 2016-A in Tel Aviv). Our next conferences are:

• Public Key Cryptography, March 6-March 9, 2016, Taipei, Taiwan.
  http://troll.iis.sinica.edu.tw/pkc16/
• Fast Software Encryption, March 20-March 23, 2016, Bochum, Germany.
  http://fse.rub.de/
• Eurocrypt 2016, May 8-May 12, 2016, Vienna, Austria
  http://ist.ac.at/eurocrypt2016/

I am looking forward to seeing many of you at the IACR events this year.

Closing

This is *your* IACR: Please share your feedback and suggestions for improving IACR's services. Contact me, other Board members, the conference chairs, and feel free to use other communication channels.

Best regards,

Christian Cachin
President, IACR

Event date: 31 August to 2 September 2016
Submission deadline: 29 February 2016

Event date: 31 August to 2 September 2016
Submission deadline: 13 March 2016
Notification: 13 May 2016

We present the first CCA-secure public-key encryption scheme based on DDH where the security loss is independent of the number of challenge ciphertexts and the number of decryption queries. Our construction extends also to the standard k-Lin assumption in pairing-free groups, whereas all prior constructions starting with Hofheinz and Jager (Crypto ’12) rely on the use of pairings. Moreover, our construction improves upon the concrete efficiency of existing schemes, reducing the ciphertext overhead by about half (to only 3 group elements under DDH), in addition to eliminating the use of pairings. We also show how to use our techniques in the NIZK setting. Specifically, we construct the first tightly simulation-sound designated-verifier NIZK for linear languages without pairings. Using pairings, we can turn our construction into a highly optimized publicly verifiable NIZK with tight simulation-soundness.

Universal circuits (UCs) can be programmed to evaluate any circuit of a given size $k$. They provide elegant solutions in various application scenarios, e.g. for private function evaluation (PFE) and for improving the flexibility of attribute-based encryption (ABE) schemes. The optimal size of a universal circuit is proven to be $\Omega(k\log k)$. Valiant (STOC'76) proposed a size-optimized UC construction, which has not been put in practice ever since. The only implementation of universal circuits was provided by Kolesnikov and Schneider (FC'08), with size $\mathcal{O}(k\log^2 k)$.

In this paper, we refine the size of Valiant's UC and further improve the construction by (at least) $2k$. We show that due to recent optimizations and our improvements, it is the best solution to apply in the case for circuits with a constant number of inputs and outputs. When the number of inputs or outputs is linear in the number of gates, we propose a more efficient hybrid solution based on the two existing constructions. We validate the practicality of Valiant's UC, by giving an example implementation for PFE using these size-optimized UCs.

Spritz is a stream cipher proposed by Rivest and Schuldt at the rump session of CRYPTO 2014. It is intended to be a replacement of the popular RC4 stream cipher. In this paper we propose distinguishing attacks on the full Spritz, based on {\it a short-term bias} in the first two bytes of a keystream and {\it a long-term bias} in the first two bytes of every cycle of $N$ keystream bytes, where $N$ is the size of the internal permutation. Our attacks are able to distinguish a keystream of the {\it full} Spritz from a random sequence with samples of first two bytes produced by $2^{44.8}$ multiple key-IV pairs or $2^{60.8}$ keystream bytes produced by a single key-IV pair. These biases are also useful in the event of plaintext recovery in a broadcast attack. In the second part of the paper, we look at a state recovery attack on Spritz, in a special situation when the cipher enters a class of weak states. We determine the probability of encountering such a state, and demonstrate a state recovery algorithm that betters the $2^{1400}$ step algorithm of Ankele et al. at Latincrypt 2015.

The Algebraic Eraser has been gaining prominence as SecureRF, the company commercializing the algorithm, increases its marketing reach. The scheme is claimed to be well-suited to IoT applications but a lack of detail in available documentation has hampered peer-review. Recently more details of the system have emerged after a tag authentication protocol built using the Algebraic Eraser was proposed for standardization in ISO/IEC SC31 and SecureRF provided an open public description of the protocol. In this paper we describe a range of attacks on this protocol that include very efficient and practical tag impersonation as well as partial, and total, tag secret key recovery. Most of these results have been practically verified, they contrast with the 80-bit security that is claimed for the protocol, and they emphasize the importance of independent public review for any cryptographic proposal.

In this paper we study what happens to sets when we iteratively apply lossy (round) mappings to them. We describe the information loss as imbalances of parities of intermediate distributions and show that their evolution is governed by the correlation matrices of the mappings. At the macroscopic level we show that iterating lossy mappings results in an increase of a quantity we call "total imbalance". We quantify the increase in total imbalance as a function of the number of iterations and of round mapping characteristics. At the microscopic level we show that the imbalance of a parity located in some round, dubbed "final", is the sum of distinct terms. Each of these terms consists of the imbalance of a parity located at the output of a round, multiplied by the sum of the correlation contributions of all linear trails between that parity and the final parity. We illustrate our theory with experimental data. The developed theory can be applied whenever lossy mappings are repeatedly applied to a state. This is the case in many modes of block ciphers and permutations for, e.g., iterated hashing or self-synchronizing stream encryption. The main reason why we have developed it however, is for applying it to study the security implications of using non-uniform threshold schemes as countermeasure against differential power and electromagnetic analysis.

The security of many cryptographic schemes has been based on special instances of the Learning with Errors (LWE) problem, e.g., Ring-LWE, LWE with binary secret, or LWE with ternary error. However, recent results show that some subclasses are weaker than expected. In this work we show that LWE with binary error, introduced by Micciancio and Peikert, is one such subclass. We achieve this by applying the Howgrave-Graham attack on NTRU, which is a combination of lattice techniques and a Meet-in-the-Middle approach, to this setting. We show that the attack outperforms all other currently existing algorithms for several natural parameter sets. For instance, for the parameter set n = 256, m = 512, q = 256, this attack on LWE with binary error only requires 2^85 operations, while the previously best attack requires 2^117 operations. We additionally present a complete and improved analysis of the attack, using analytic techniques. Finally, based on the attack, we give concrete hardness estimations that can be used to select secure parameters for schemes based on LWE with binary error

The block cipher Simon has a very simple round function. This simplicity allows us to compute the correlation matrix of the round function. Despite its simplicity, Simon exhibits some very interesting phenomena with respect to linear cryptanalysis. The combination of an expanding linear function and a compressing nonlinear function creates one-round hulls. These hulls complicate the estimation of the correlation contribution of trails as well as the potential of linear hulls. They cause difficulties in the commonly used methods to estimate the cipher's security against linear cryptanalysis. Finally, because most hulls contain many trails with similar correlation contributions, we can demonstrate erratical behaviour of Matsui's Algorithm 1 when applied in the default way. We also show how Algorithm 1 can be adapted to this situation and recover multiple key bits.

We investigate how to safely export additional cryptographic keys from secure channel protocols, modelled with the authenticated and confidential channel establishment (ACCE) security notion. For example, the EAP-TLS protocol uses the Transport Layer Security (TLS) handshake to output an additional shared secret which can be used for purposes outside of TLS, and the RFC 5705 standard specifies a general mechanism for exporting keying material from TLS. We show that, for a class of ACCE protocols we call “TLS-like” protocols, the EAP-TLS transformation can be used to export an additional key, and that the result is a secure AKE protocol in the Bellare–Rogaway model. Interestingly, we are able to carry out the proof without looking at the specifics of the TLS protocol itself (beyond the notion that it is “TLS-like”), but rather are able to use the ACCE property in a semi black-box way. To facilitate our modular proof, we develop a novel technique, notably an encryption-based key checking mechanism that is used by the security reduction. Our results imply that EAP-TLS using secure TLS 1.2 cipher-suites is a secure authenticated key exchange protocol.

Intel's Software Guard Extensions (SGX) is a set of extensions to the Intel architecture that aims to provide integrity and privacy guarantees to security-sensitive computation performed on a computer where all the privileged software (kernel, hypervisor, etc) is potentially malicious.

This paper analyzes Intel SGX, based on the 3 papers that introduced it, on the Intel Software Developer's Manual (which supersedes the SGX manuals), on an ISCA 2015 tutorial, and on two patents. We use the papers, reference manuals, and tutorial as primary data sources, and only draw on the patents to fill in missing information.

This paper's contributions are a summary of the Intel-specific architectural and micro-architectural details needed to understand SGX, a detailed and structured presentation of the publicly available information on SGX, a series of intelligent guesses about some important but undocumented aspects of SGX, and an analysis of SGX's security properties.

This paper shows how several ring-LWE based key exchange protocols can be broken, under the assumption that the same key share is used for multiple exchanges. This indicates that, if these key exchange protocols are used, then it will be necessary for a fresh key share be generated for each exchange, and that these key exchange protocols cannot be used as a drop in replacement for designs which use Diffie-Hellman static key shares.

RoadRunneR is a small and fast bitslice lightweight block cipher for low cost 8-bit processors proposed by Adnan Baysal and Sa ̈hap S ̧ahin in the LightSec 2015 conference. While most software efficient lightweight block ciphers lacking a security proof, RoadRunneR’s security is provable against differential and linear attacks. RoadRunneR is a Feistel structure block cipher with 64-bit block size. RoadRunneR-80 is a vision with 80-bit key and 10 rounds, and RoadRunneR-128 is a vision with 128-bit key and 12 rounds. In this paper, we obtain 5-round truncated differentials of RoadRunneR-80 and RoadRunneR-128 with probability 2^{−56}. Using the truncated differentials, we give a truncated differential attack on 7-round RoadRunneR-128 without whitening keys with data complexity of 2^{55} chosen plaintexts, time complexity of 2^{121} encryptions and memory complexity of 2^{68}. This is first known attack on RoadRunneR block cipher.

While DNSSEC securely provides authenticity and integrity to the domain name system (DNS), it also creates a new security vulnerability called zone enumeration that allows an adversary that asks a small number of targeted DNS queries to learn the IP addresses of all domain names in a zone. An enumerated zone can be used as ''a source of probable e-mail addresses for spam, or as a key for multiple WHOIS queries to reveal registrant data that many registries may have legal obligations to protect'' [RFC 5155] (e.g., per EU data protection laws), or to create a toehold for more complex attacks. As the Internet of things becomes increasingly ubiquitous, it also becomes increasingly important to keep the names and addresses of these ''things'' (e.g., thermostats, fridges, baby monitors) away from remote attackers.

In previous work we solved DNSSEC's zone enumeration problem by introducing NSEC5, a cryptographic construction based on RSA digital signatures. NSEC5 provides authenticated denial of existence, i.e., it is used to answer DNS queries that have negative responses (e.g., NXDOMAIN). RSA-based NSEC5 was recently submitted for specification in an Internet draft [draft-vcelak-nsec5-01], and a working implementation of a nameserver that supports RSA-based NSEC5 is also available [https://github.com/dipapado/nsec5-implementation].

However, recent years have seen the DNSSEC community aiming to replace RSA with elliptic curve cryptography (EC), in order to shorten the length of DNSSEC responses. Therefore, in this paper we present a new variant of NSEC5 that uses elliptic curve cryptography (ECC) to produce shorter NSEC5 responses. If a zone is signed with ECDSA at the 128-bit security level and also uses our new ECC-based NSEC5 scheme, its denial-of-existence responses (response code NXDOMAIN) will be about 2 times shorter than that a zone signed with 2048-bit RSA and RSA-based NSEC5. Moreover, our ECC-based NSEC5 has responses lengths that are comparable to NSEC3, DNSSEC's current authenticated-denial-of-existence mechanism that is vulnerable to zone enumeration via offline dictionary attacks. In fact, if a zone signed with ECDSA at the 128-bit security level also uses our new ECC-based NSEC5 scheme, it will have responses that are shorter than a zone using NSEC3 with 1024-bit RSA and SHA1 (for an 80-bit security level), which is today's dominant deployment configuration.

Group signatures are an important privacy-enhancing tool that allow to anonymously sign messages on behalf of a group. A recent feature for group signatures is controllable linkability, where a dedicated linking authority (LA) can determine whether two given signatures stem from the same signer without being able to identify the signer(s). Currently the linking authority is fully trusted, which is often not desirable.

In this paper, we firstly introduce a generic technique for non-interactive zero-knowledge plaintext equality and inequality proofs. In our setting, the prover is given two ciphertexts and some trapdoor information, but neither has access to the decryption key nor the randomness used to produce the respective ciphertexts. Thus, the prover performs these proofs on unknown plaintexts. Besides a generic technique, we also propose an efficient instantiation that adapts recent results from Blazy et al. (CT-RSA'15), and in particular a combination of Groth-Sahai (GS) proofs (or sigma proofs) and smooth projective hash functions (SPHFs).

While this result may be of independent interest, we use it to realize verifiable controllable linkability for group signatures. Here, the LA is required to non-interactively prove whether or not two signatures link (while it is not able to identify the signers). This significantly reduces the required trust in the linking authority. Moreover, we extend the model of group signatures to cover the feature of verifiable controllable linkability.

We analyze the handshake protocol of TLS 1.3 draft-ietf-tls-tls13-10 (published October 2015). This continues and extends our previous analysis (CCS 2015, Cryptology ePrint Archive 2015) of former TLS 1.3 drafts (draft-ietf-tls-tls13-05 and draft-ietf-tls-tls13-dh-based). Here we show that the full (EC)DHE Diffie-Hellman-based handshake of draft-10 is also secure in the multi-stage key exchange framework of Fischlin and Günther which captures classical Bellare-Rogaway key secrecy for key exchange protocols that derive multiple keys.

We also note that a recent protocol change---the introduction of a NewSessionTicket message for resumption, encrypted under the application traffic key---impairs the protocol modularity and hence our compositional guarantees that ideally would allow an independent analysis of the record protocol. We additionally analyze the pre-shared key modes (with and without ephemeral Diffie-Hellman key), and fit them into the composability framework, addressing composability with the input resumption secret from a previous handshake and of the output session keys.