International Association
for Cryptologic Research

Server-Aided Verification (SAV) is a method that can be employed to speed up the process of verifying signatures by letting the verifier outsource part of its computation load to a third party. Achieving fast and reliable verification under the presence of an untrusted server is an attractive goal in cloud computing and internet of things scenarios. In this paper, we describe a simple framework for SAV where the interaction between a verifier and an untrusted server happens via a single-round protocol. We propose a security model for SAV that refines existing ones and includes the new notions of SAV-anonymity and extended unforgeability. In addition, we apply our definitional framework to provide the first generic transformation from any signature scheme to a single-round SAV scheme that incorporates verifiable computation. Our compiler identifies two independent ways to achieve SAV-anonymity: computationally, through the privacy of the verifiable computation scheme, or unconditionally, through the adaptibility of the signature scheme. Finally, we define three novel instantiations of SAV schemes obtained through our compiler. Compared to previous works, our proposals are the only ones which simultaneously achieve existential unforgeability and soundness against collusion.

This paper presents a constant-time fast implementation for a high-security code-based encryption system. The implementation is based on the “McBits” paper by Bernstein, Chou, and Schwabe in 2013: we use the same FFT algorithms for root finding and syndrome computation, similar algorithms for secret permutation, and bitslicing for low-level operations. As opposed to McBits, where a high decryption throughput is achieved by running many decryption operations in parallel, we take a different approach to exploit the internal parallelism in one decryption operation for the use of more applications. As the result, we manage to achieve a slightly better decryption throughput at a much higher security level than McBits. As a minor contribution, we also present a constant-time implementation for encryption and key-pair generation, with similar techniques used for decryption.

Bernstein et al. have proposed a new permutation, Gimli, which aims to provide simple and performant implementations on a wide variety of platforms ranging from the AVR ATmega and ARM-Cortex to the Intel Haswell. In a festive spirit of retrocomputing, this brief paper reports such a simple and (somewhat) performant implementation on the almost Third-Age-of-Middle-earth-dating TRS-80.

Merged mining refers to the concept of mining more than one cryptocurrency without necessitating additional proof-of-work effort. Although merged mining has been adopted by a number of cryptocurrencies already, to this date little is known about the effects and implications. We shed light on this topic area by performing a comprehensive analysis of merged mining in practice. As part of this analysis, we present a block attribution scheme for mining pools to assist in the evaluation of mining centralization. Our findings disclose that mining pools in merge-mined cryptocurrencies have operated at the edge of, and even beyond, the security guarantees offered by the underlying Nakamoto consensus for extended periods. We discuss the implications and security considerations for these cryptocurrencies and the mining ecosystem as a whole, and link our findings to the intended effects of merged mining.

We introduce a new approach to actively secure two-party computation based on so-called oblivious linear function evaluation (OLE), a natural generalisation of oblivious transfer (OT) and a special case of the notion of oblivious polynomial evaluation introduced by Naor and Pinkas at STOC 1999.

OLE works over a finite field F. In an OLE the sender inputs two eld elements $a$ and $b$, and the receiver inputs a field element $x$ and learns only $f(x) = ax + b$.

Our protocol can evaluate an arithmetic circuit over a finite field $F$ given black-box access to OLE for $F$. The protocol is unconditionally secure and consumes only a constant number of OLEs per multiplication gate. An OLE over a field $F$ of size $O(2^k)$ can be implemented with communication $O(k)$. This gives a protocol with communication complexity O(|C|) for large enough fields, where C is an arithmetic circuit computing the desired function. This asymptotically matches the best previous protocols, but our protocol at the same time obtains significantly smaller constants hidden by the big-O notation, yielding a highly practical protocol.

Conceptually our techniques lift the techniques for basing practical actively secure 2PC of Boolean circuits on OT introduced under the name TinyOT by Nielsen, Nordholt, Orlandi and Burra at Crypto 2012 to the arithmetic setting. In doing so we develop several novel techniques for generating various flavours of OLE and combining these.

We believe that the efficiency of our protocols, both in asymptotic and practical terms, establishes OLE as an important foundation for efficient actively secure 2PC.

The most important pre-quantum threat to AES-128 is the 1994 van Oorschot--Wiener "parallel rho method", a low-communication parallel pre-quantum multi-target preimage-search algorithm. This algorithm uses a mesh of p small processors, each running for approximately 2^128/pt fast steps, to find one of t independent AES keys k_1,...,k_t, given the ciphertexts AES_{k_1}(0),...,AES_{k_t}(0) for a shared plaintext 0.

NIST has claimed a high post-quantum security level for AES-128, starting from the following rationale: "Grover's algorithm requires a long-running serial computation, which is difficult to implement in practice. In a realistic attack, one has to run many smaller instances of the algorithm in parallel, which makes the quantum speedup less dramatic." NIST has also stated that resistance to multi-key attacks is desirable; but, in a realistic parallel setting, a straightforward multi-key application of Grover's algorithm costs more than targeting one key at a time.

This paper introduces a different quantum algorithm for multi-target preimage search. This algorithm shows, in the same realistic parallel setting, that quantum preimage search benefits asymptotically from having multiple targets. The new algorithm requires a revision of NIST's AES-128, AES-192, and AES-256 security claims.

Although AES is designed to be secure against a wide variety of linear and differential attacks, security ultimately depends on a combination of the engineering implementation and proper application by intended users. In this work, we attack a publicly-available VHDL implementation of AES by exploiting a partial result visible at the top-level public interface of the implementation. The vulnerability renders the security of the implementation equivalent to a one-round version of AES. An algorithm is presented that exploits this vulnerability to recover the secret key in 2^31 operations. The algorithm is coded in an interpreted high-level language and successfully recovers secret keys, with one set of known plaintext, using a general-purpose CPU in an average of 30 minutes.

Opaque predicates are a commonly used technique in program obfuscation, intended to add complexity to control flow and to insert dummy code or watermarks. We survey a number of methods to remove opaque predicates from obfuscated programs, hence defeating the intentions of the obfuscator. Our main contribution is an obfuscation technique that introduces opaque constant predicates that are provably indistinguishable from obfuscations of certain other predicates in the program. Our technique resists all known efficient static attacks on opaque predicates. We present an evaluation of our implementation of the scheme. This includes measurements of its performance impact on an obfuscated instance versus a vanilla one and an experimental verification that the obfuscator is functionality preserving.

Hong Kong Applied science and technology research institute Security Lab (ASL) research team is currently looking for talented cryptography engineers. The ASL lab focuses on building privacy-preserving, scalable and usable blockchain/distributed ledger technology. ASL provides great opportunities to work with researchers and engineers from world-renowned research institutes and companies to revolutionize the FinTech industry.

The main duties and responsibilities of cryptography engineers are:

• Work with cryptographers in our team to design and implement novel cryptographic algorithms and protocols.

• Design, build and deploy blockchain/distributed ledger technologies with application to cryptocurrencies, micropayments and beyond.

• Design, develop and deploy innovative yet high-quality application software for FinTech initiatives.

Desired skills and experience:

• Bachelor or Master degree in Computer Science or related disciplines with at least 4+ years’ experience.

• Knowledge in Blockchain technologies and a good understanding of applied cryptography. A good understanding of distributed consensus protocol is a big plus.

• Experience in implementing and integrating cryptographic protocols (such as Elliptical Curve cryptography or Lattice-based cryptography) in a real-world distributed system is a plus. Experience in open-source project related to cryptocurrency is a huge plus. Experience in ethical hacking or attacking a real-world cryptosystem is also a big plus.

• Must possess extensive hands-on experience in one or more system programming languages: C/C++, Go, Rust, C#, etc.

• Team-based code and project management using revision control (e.g., Git), open-source workflows (e.g., GitHub).

• Must possess excellent interpersonal, verbal, and written communication skills, detail-oriented, problem-solving and multi-tasking skills.

• Self-motivated fast learning and willing to work under pressure. Team player and keen to share knowledge but can work independently.

Closing date for applications: 15 October 2017

Contact: The candidates should submit a full CV to Dr. Huang Lin (linhuang (at) astri.org) with “Application: cryptography engineer” in the subject line (PDF attachments only). Applications should be submitted by October 15, 2017, but the positions will remain open until filled.

Secure messaging systems such as TextSecure and Signal aim, among others, at providing authenticated and confidential channels between two or more communicating users. The general understanding seems to be that providing security in the sense of authenticated encryption (AE) for every point-to-point link suffices to make the constructed messaging systems secure, i.e., authentic and confidential. However, as recently shown (in FSE17/ToSC17), in the bidirectional (two-party) case, just requiring the two unidirectional links to provide security independently of each other does not lead to a secure communication channel in general. Briefly, the reason for this is that security notions need to take into account the increased level of interaction between users. This also applies, a fortiori, in a multi-user setting where many parties communicate concurrently and in multiple directions. We observe that in the current academic literature there is no rigorous definition of security for (broadcast) group communication. Applying the method of provable security, we fill this gap by defining security goals and showing how to provably achieve them.

Concretely, the contributions of this paper are as follows: We develop a set of formal definitions of security goals for broadcast communication, capturing targets like confidentiality and authenticity. Our notions in particular take into account the causal dependencies that exchanged messages might have. (Note that these have no counterpart in the much simpler unidirectional case.) We then switch to the constructive side, designing an efficient protocol that requires only reliable point-to-point links between users and a standard cryptographic building block (AEAD), achieving all security goals defined in this paper. Our work thus paves the ground towards understanding the exact level of security that current secure messaging systems achieve.

Consider three parties: Alice, Bob, and Polly. Alice keeps some encrypted data that she can decrypt with a secret key known to her. She wants to communicate the data to Bob, but not to Polly (nor anybody else). Assuming Alice knows Bob's public key, how can she communicate the data to him? Proxy reencryption provides an elegant answer: Alice creates a reencryption key that will enable Polly (the proxy) to reencrypt her data for Bob's use, but that will not help Polly learn anything about the data.

There are two well-studied notions of security for proxy reencryption schemes: security under chosen-plaintext attacks (CPA) and security under chosen-ciphertext attacks (CCA). Both definitions aim to formalize security against both Polly and Bob.

However, we observe that CPA security guarantees much less security against Bob than was previously understood. In particular, CPA security does not prevent Bob from learning Alice's secret key after receiving a single honestly reencrypted ciphertext. In common applications of proxy reencryption, this means that CPA security provides scant guarantees.

We propose security under honest-reencryption attacks (PRE-HRA), a new notion intermediate to CPA and CCA that better captures the goals of proxy reencryption. In applications, PRE-HRA security provides much more robust security. We identify a property of proxy reencryption schemes that suffices to amplify CPA security to PRE-HRA security and show that two existing proxy reencryption schemes are in fact PRE-HRA secure.

Secure channels are one of the most pivotal building blocks of cryptography today. Internet connections, secure messaging, protected IoT data, etc., all rely upon the security of the underlying channel. In this work we define channel protocols, as well as security for channels constructed from stateful length-hiding authenticated encryption (stLHAE) schemes. Furthermore, we initiate the concept of secure termination where, upon receipt of a signifying message, a receiver is guaranteed to have received every message that has been sent, and will ever be sent, on the channel. We apply our results to real-world protocols, linking the channel environment to previous analyses of TLS 1.2, and demonstrating that TLS 1.2 achieves secure termination via fatal alerts and close_notify messages, per the specification of the Alert Protocol.

Hardware manipulations pose a serious threat to numerous systems, ranging from myriads of smart-X devices to military systems. In many attack scenarios an adversary merely has access to the low-level, potentially obfuscated gate-level netlist. In general, the attacker possesses minimal information and faces the costly and time-consuming task of reverse engineering the design to identify security-critical circuitry, followed by insertion of a meaningful hardware Trojan. These challenges have been considered only in passing by the research community. The contribution of this work is threefold: First, we present HAL, a comprehensive reverse engineering and manipulation framework for gate-level netlists. HAL allows automating defensive design analysis (e.g., including arbitrary Trojan detection algorithms with minimal effort) as well as offensive reverse engineering and targeted logic insertion. Second, we present a novel static analysis Trojan detection technique ANGEL, which outperforms state-of-the-art algorithms by a considerable reduction of the false-positive rate. Furthermore, we demonstrate that ANGEL is capable of automatically detecting Trojans obfuscated with DeTrust. Third, we demonstrate how a malicious party can semi-automatically inject hardware Trojans in third-party designs. We present reverse engineering algorithms to disarm and trick cryptographic self-tests, and subtly leak cryptographic keys without any apriori knowledge of the design’s internal workings.

Cloud computing is very popular for its computing and storage capacity at lower cost. More and more data are being moved to the cloud to reduce storage cost. On the other hand, since the cloud is not fully trustable, in order to protect data privacy against third-parties and even the cloud server, they are usually encrypted before uploading. However, many operations, such as searching, are hard to perform on encrypted data. To solve this problem, searchable encryption has emerged. Searchable encryption in multi-user setting is much less efficient than in single-user setting. In order to address this problem, we propose a multi-owner to multi-user searchable encryption scheme based on attribute-based encryption. Our scheme keeps data secure in the cloud even against the cloud server. It allows users with appropriate authorizations to perform search operations on encrypted data. In addition, search tokens are generated by users instead of data owners. We prove that token privacy and index privacy are well protected in our scheme. The cloud server and illegimate users are not able to get any useful information about search tokens and ciphertexts. Ciphertexts of our scheme are constant-size, which reduce the time-complexity and bandwidth overhead of our scheme.

Event date: 3 July to 5 July 2018
Submission deadline: 26 January 2018
Notification: 31 March 2018

Event date: 14 August to 16 August 2019

In an accountable anonymous system, a user is guaranteed anonymity and unlinkability unless some well-defined condition is met. A line of research focus on schemes that do not rely on any trusted third party capable of de-anonymising users. Notable examples include $k$-times anonymous authentication ($k$-TAA), blacklistable anonymous credentials (BLAC) and linkable ring signatures (LRS). All instances of these schemes are based on traditional number theoretic assumptions, which are vulnerable to quantum attacks.

One common feature of these schemes is the need to limit the number of times a key can be (mis-)used. Traditionally, it is usually achieved through the use of a pseudorandom function (PRF) which maps a user's key to a pseudonym, along with a proof of correctness. However, existing lattice-based PRFs do not interact well with zero-knowledge proofs. To bridge this gap, we propose and develop the following techniques and primitives:

We formalize the notion of weak PRF with efficient protocols, which allows a prover to convince a verifier that the function $\mathsf{F}$ is evaluated correctly. Specifically, we provide an efficient construction based on the learning with rounding problem, which uses abstract Stern's Protocol to prove $y = \mathsf{F}_k(x)$ and $y \neq \mathsf{F}_k(x)$ without revealing $x$, $y$ or $k$.

We develop a general framework, which we call extended abstract Stern's protocol, to construct zero-knowledge arguments system for statements formed by conjunction and disjunction of sub-statements, who (or whose variants) are provable using abstract Stern's Protocol. Specifically, our system supports arbitrary monotonic propositions and allows a prover to argue polynomial relationships of the witnesses used in these sub-statements.

As many existing lattice-based primitives also admit proofs using abstract Stern's protocol, our techniques can easily glue different primitives together for privacy-enhancing applications in a simple and clean way. Indeed, we propose three new schemes, all of which are the first of its kind, in the lattice setting. They also enjoy additional advantages over instances of the number-theoretic counterpart. Our $k$-TAA and BLAC schemes support concurrent enrollment while our LRS features logarithmic signature size without relying on a trusted setup. Our techniques enrich the arsenal of privacy-enhancing techniques and could be useful in the constructions of other schemes such as e-cash, unique group signatures, public key encryption with verifiable decryption, etc.

The intractability of solving the LPN problem serves as the security source of many lightweight/post-quantum cryptographic schemes proposed over the past decade. There are several algorithms available so far to fulfill the solving task. In this paper, we present further algorithmic improvements to the existing work. We describe the first efficient algorithm for the single-list $k$-sum problem which naturally arises from the various BKW reduction settings, propose the hybrid mode of BKW reduction and show how to compute the matrix multiplication in the Gaussian elimination step with flexible and reduced time/memory complexities. The new algorithms yield the best known tradeoffs on the %time/memory/data complexity curve and clearly compromise the $80$-bit security of the LPN instances suggested in cryptographic schemes. Practical experiments on reduced LPN instances verified our results.

In this paper we consider both ``OR" and ``XOR" based monochrome random grid visual cryptographic schemes (RGVCS) for $t$-$(k,n)^*$ access structure which is a generalization of the threshold $(k,n)$ access structure in the sense that in all the successful attempts to recover the secret image, the $t$ essential participants must always be present, i.e., a group of $k$ or more participants can get back the secret if these $t$ essential participants are among them. Up to the best of our knowledge, the current proposed work is the first in the literature of RGVCS which provides efficient direct constructions for the $t$-$(k,n)^*$-RGVCS for both ``OR" and ``XOR" model. Finding the closed form of light contrast is a challenging work. However, in this paper we come up with the closed forms of the light contrasts for the ``OR" as well as for the ``XOR" model. As our proposed schemes are the first proposed schemes for $t$-$(k,n)^*$-RGVCS, it is not possible for us to compare our schemes directly with the existing schemes. However, we have constructed $t$-$(k,n)^*$-RGVCS, as a particular case, from the random grid based schemes for general access structures. Theoretical as well as simulation based data show that our proposed schemes work much efficiently than all these customized schemes.

We present ‘MCMix’, an anonymous messaging system that completely hides communication metadata and can scale in the order of hundreds of thousands of users. Our approach is to isolate two suitable functionalities, called dialing and conversation, that when used in succession realize anonymous messaging. With this as a starting point, we apply secure multiparty computation (``MC'' or MPC) and proceed to realize them. We present an implementation using a prevalent MPC system (Sharemind) that is competitive in terms of latency with previous messaging systems that only offer much weaker privacy guarantees. Our solution can be instantiated in a variety of different ways with different MPC implementations, overall illustrating how MPC is a viable and competitive alternative to mix-nets and DC-nets for anonymous communication.