International Association
for Cryptologic Research

The 2018 TCC Test-of-Time Award goes to Dan Boneh, Eu-Jin Goh and Kobbi Nissim, for their TCC 2005 paper "Evaluating 2-DNF Formulas on Ciphertexts".

The award committee recognizes this paper "for introducing compact two-operation homomorphic encryption and developing new bilinear map techniques that led to major improvements in the design of cryptographic schemes."

The TCC Test of Time Award recognizes outstanding papers, published in TCC at least eight years ago, making a significant contribution to the theory of cryptography, preferably with influence also in other area of cryptography, theory, and beyond. The inaugural TCC Test of Time Award was given in TCC 2015 for papers published no later than TCC 2007.

The Noise Protocol Framework, introduced recently, allows for the design and construction of secure channel protocols by describing them through a simple, restricted language from which complex key derivation and local state transitions are automatically inferred. Noise "Handshake Patterns" can support mutual authentication, forward secrecy, zero round-trip encryption, identity hiding and other advanced features. Since the framework's release, Noise-based protocols have been adopted by WhatsApp, WireGuard and other high-profile applications.

We present Noise Explorer, an online engine for designing, reasoning about and formally verifying arbitrary Noise Handshake Patterns. Based on our formal treatment of the Noise Protocol Framework, Noise Explorer can validate any Noise Handshake Pattern and then translate it into a model ready for automated verification. We use Noise Explorer to analyze 50 Noise Handshake Patterns. We confirm the stated security goals for 12 fundamental patterns and provide precise properties for the rest. We also analyze unsafe Noise patterns and discover potential attacks. All of this work is consolidated into a usable online tool that presents a compendium of results and can parse formal verification results to generate detailed-but-pedagogical reports regarding the exact security guarantees of each message of a Noise Handshake Pattern with respect to each party, under an active attacker and including malicious principals. Noise Explorer evolves alongside the standard Noise Protocol Framework, having already contributed new security goal verification results and stronger definitions for pattern validation and security parameters.

Symbolic methods have been used extensively for proving security of cryptographic protocols in the Dolev-Yao model, and more recently for proving security of cryptographic primitives and constructions in the computational model. However, existing methods for proving security of cryptographic constructions in the computational model often require significant expertise and interaction, or are fairly limited in scope and expressivity.

This paper introduces a symbolic approach for proving security of cryptographic constructions based on the Learning With Errors assumption (Regev, STOC 2005). Such constructions are instances of lattice-based cryptography and are extremely important due to their potential role in post-quantum cryptography. Following (Barthe, Gr\'egoire and Schmidt, CCS 2015), our approach combines a computational logic and deducibility problems---a standard tool for representing the adversary's knowledge, the Dolev-Yao model. The computational logic is used to capture (indistinguishability-based) security notions and drive the security proofs whereas deducibility problems are used as side-conditions to control that rules of the logic are applied correctly. We then use \AutoLWE, an implementation of the logic, to deliver very short or even automatic proofs of several emblematic constructions, including CPA-PKE (Gentry et al., STOC 2008), (Hierarchical) Identity-Based Encryption (Agrawal et al. Eurocrypt 2010), Inner Product Encryption (Agrawal et al. Asiacrypt 2011), CCA-PKE (Micciancio et al., Eurocrypt 2012). The main technical novelty beyond AutoLWE is a set of (semi-)decision procedures for deducibility problems, using extensions of Gr\"obner basis computations for subalgebras in the (non-)commutative setting (instead of ideals in the commutative setting). Our procedures cover the theory of matrices, which is required for lattice-based assumption, as well as the theory of non-commutative rings, fields, and Diffie-Hellman exponentiation, in its standard, bilinear and multilinear forms. Additionally, AutoLWE supports oracle-relative assumptions, which are used specifically to apply (advanced forms of) the Leftover Hash Lemma, an information-theoretical tool widely used in lattice-based proofs.

Post-quantum cryptosystems involve basically the families of algorithms based on lattices, error correcting codes, multivariate quadratic systems (MQ), and schemes based on symmetric cryptography primitives in general, as well as on hash functions. The project in which the candidate will be inserted aims to specify, develop and analyze secure and hardware-friendly post-quantum cryptographic schemes for providing a variety of security services, including encryption, authentication and digital signatures.

The focus will be on performance improvements, possibly in terms of processing time and energy requirements, but especially in terms of key, signatures and ciphertext sizes. The security analysis of these schemes should consider both cryptanalytic attacks and implementation-related threats, such as side-channel attacks. The performance evaluation of the schemes will be both theoretical (considering computational complexity, underlying parallelism opportunities) and experimental (using software prototypes and hardware implementations).

The main requirements for the application are: (1) to have a solid background in cryptography, preferably (but not necessarily) with post-quantum primitives; (2) to have good design/programming skills, preferably (but not necessarily) in programming languages such as C and/or hardware description languages such as VHDL, and (3) to be enrolled (or to be willing to enroll) at the Graduate Program in Electrical Engineering, Escola Politécnica, Universidade de São Paulo, São Paulo campus (http://ppgee.poli.usp.br/en/), with a full time dedication.

This opportunity is open for candidates of any nationality.

Closing date for applications: 27 August 2018

Contact: Prof. Marcos A. Simplicio Jr -- msimplicio (at) larc.usp.br

Are You Interested in Cryptography And/Or Blockchain Technology?

Post-Doc Positions.

Professor Ivan Visconti is the scientific coordinator for University of Salerno of the project Privacy-Enhancing Cryptography in Distributed Ledgers (PRIViLEDGE) and is involved in several other research activities related to Cybersecurity, Cryptography and Blockchain Technology. Expressions of interest for post-doc positions in the field of privacy-preserving cryptography and distributed ledger technology, to be supervised by professor Ivan Visconti are welcome. Candidates are expected to have a solid publication record (e.g., IACR conferences, CCS, IEEE S&P,....). The positions are available immediately. The net salary can be even higher than the average net salary of an associate professor in Italy. There is also some travel budget to attend conferences, project meetings and research visits. In case you are interested, please send your CV and 2 names for letters of reference to Ivan Visconti (ivan DOT visconti AT gmail DOT com).

PhD Positions.

There are up to 14 PhD positions at the computer engineering department of University of Salerno (Italy). The deadline for applications is September 19, 2018, and the master degree must be obtained by November 6, 2018.

Closing date for applications: 6 November 2018

Contact: Ivan Visconti (ivan DOT visconti AT gmail DOT com)

More information: https://goo.gl/DmFgGM

When designing a new symmetric-key primitive, the designer must show resistance to know attacks. Perhaps most prominent amongst these are linear and differential cryptanalysis. However, it is notoriously difficult to accurately demonstrate e.g. a block cipher's resistance to these attacks, and thus most designer resort to deriving bounds on the linear correlations and differential probabilities of their cipher. On the other side of the spectrum, the cryptanalyst is also interested in accurately assessing the strength of a linear or differential attack.

While several tools have been developed to search for optimal linear and differential trails, e.g. MILP and SAT based methods, only few approaches specifically try to find as many trails of a single approximation or differential as possible. This can result in an overestimate of a ciphers resistance to linear and differential attacks, as was for example the case for PRESENT.

In this work, we present a new algorithm for linear and differential trail search. The algorithm represents the problem of estimating approximations and differentials as the problem of finding many paths through a multistage graph, and we demonstrate that this approach allows is to find a very large number of trails for each approximation or differential. Moreover, we show how the algorithm can be used to efficiently estimate the key dependent correlation distribution of a linear approximation, facilitating advanced linear attacks. We apply the algorithm to 17 different ciphers, and demonstrate new and improved results on several of these.

A new approach to invariant subspaces and nonlinear invariants is developed. This results in both theoretical insights and practical attacks on block ciphers. It is shown that, with minor modifications to some of the round constants, Midori-64 has a nonlinear invariant with $2^{96}$ corresponding weak keys. Furthermore, this invariant corresponds to a linear hull with maximal correlation. By combining the new invariant with integral cryptanalysis, a practical key-recovery attack on 10 rounds of unmodified Midori-64 is obtained. The attack works for $2^{96}$ weak keys and irrespective of the choice of round constants. The data complexity is $1.25 \cdot 2^{21}$ chosen plaintexts and the computational cost is dominated by $2^{56}$ block cipher calls. Finally, it is shown that similar techniques lead to a practical key-recovery attack on MANTIS-4. The full key is recovered using 640 chosen plaintexts and the attack requires about $2^{56}$ block cipher calls.

Protocols for secure multiparty computation (MPC) enable a set of mutually distrusting parties to compute an arbitrary function of their inputs while preserving basic security properties like \emph{privacy} and \emph{correctness}. The study of MPC was initiated in the 1980s where it was shown that any function can be securely computed, thus demonstrating the power of this notion. However, these proofs of feasibility were theoretical in nature and it is only recently that MPC protocols started to become efficient enough for use in practice. Today, we have protocols that can carry out large and complex computations in very reasonable time (and can even be very fast, depending on the computation and the setting). Despite this amazing progress, there is still a major obstacle to the adoption and use of MPC due to the huge expertise needed to design a specific MPC execution. In particular, the function to be computed needs to be represented as an appropriate Boolean or arithmetic circuit, and this requires very specific expertise. In order to overcome this, there has been considerable work on compilation of code to (typically) Boolean circuits. One work in this direction takes a different approach, and this is the SPDZ compiler (not to be confused with the SPDZ protocol) that takes high-level Python code and provides an MPC run-time environment for securely executing that code. The SPDZ compiler can deal with arithmetic and non-arithmetic operations and is extremely powerful. However, until now, the SPDZ compiler could only be used for the specific SPDZ family of protocols, making its general applicability and usefulness very limited.

In this paper, we extend the SPDZ compiler so that it can work with general underlying protocols. Our SPDZ extensions were made in mind to enable the use of SPDZ for arbitrary protocols and to make it easy for others to integrate existing and new protocols. We integrated three different types of protocols, an honest-majority protocol for computing arithmetic circuits over a field (for any number of parties), a three-party honest majority protocol for computing arithmetic circuits over the ring of integers $\Z_{2^n}$, and the multiparty BMR protocol for computing Boolean circuits. We show that a single high-level SPDZ-Python program can be executed using all of these underlying protocols (as well as the original SPDZ protocol), thereby making SPDZ a true general run-time MPC environment.

In order to be able to handle both arithmetic and non-arithmetic operations, the SPDZ compiler relies on conversions from field elements to bits and back. However, these conversions do not apply to ring elements (in particular, they require element division), and we therefore introduce new bit decomposition and recomposition protocols for the ring over integers with replicated secret sharing. These conversions are of independent interest and utilize the structure of $\Z_{2^n}$ (which is much more amenable to bit decomposition than prime-order fields), and are thus much more efficient than all previous methods.

We demonstrate our compiler extensions by running a complex SQL query and a decision tree evaluation over all protocols.

In 2005, Yen et al. proposed the first $N-1$ attack on the modular exponentiation algorithms such as BRIP and square-and-multiply-always methods. This attack makes use of the ciphertext $N-1$ as a distinguisher to obtain a strong relation between side-channel leakages and secret exponent. The so-called $N-1$ attack is one of the most important attacks, as it requires a non-adaptive chosen ciphertext which is considered as a more realistic attack model compared to adaptive chosen ciphertext scenario. To protect the implementation against $N-1$ attack, several literatures propose the simplest solution, i.e. \textquotedblleft block the special message $N-1$". In this paper, we conduct an in-depth research on the $N-1$ attack based on the square-and-multiply-always (SMA) and Montgomery Ladder (ML) algorithms. We show that despite the unaccepted ciphertext $N-1$ countermeasure, other types of $N-1$ attacks is applicable to specific classes of Elgamal cryptosystems. We propose new chosen-message power-analysis attacks which utilize a chosen ciphertext $c$ such that $c^2= -1 \bmod p$ where $p$ is the prime number used as a modulus in Elgamal. Such a ciphertext can be found simply when $p\equiv 1\mod 4$. We demonstrate that ML and SMA algorithms are subjected to our new $N-1$-type attack by utilizing a different ciphertext. We implement the proposed attacks on the TARGET Board of the ChipWhisperer CW1173 and our experiments validate the feasibility and effectiveness of the attacks by using only a single power trace.

In this paper, we study the authenticated key exchange (AKE) based on supersingular isogeny problems which are believed to be difficult for quantum computers. We first propose a three-pass AKE based on 1-Oracle SIDH assumption whose soundness is guaranteed by a strictly limited gap problem. To enhance the soundness, we propose a two-pass AKE based on standard SIDH assumption. The three-pass AKE achieves about 20\% speedup compared with the SIDH variant of FSXY scheme and narrows the bandwidth by approximately 49.3\% without lose of security. And the two-pass scheme narrows the bandwidth by around 23\% and yields a factor 12\% acceleration than the SIDH variant of FSXY scheme.

In the random oracle model, both three-pass AKE and two-pass AKE protocols are secure in the CK model, supporting arbitrary registration of public key, and resistant to the weak perfect forward secrecy (wPFS) attack, key-compromise impersonation (KCI) attack and maximal exposure (MEX) attack, which solves the open problem provided Galbraith of looking for new techniques to design and prove security of AKE in SIDH setting with the widest possible adversarial goals.

We study a simulation paradigm, referred to as local simulation, in garbling schemes. This paradigm captures simulation proof strategies in which the simulator consists of many local simulators that generate different blocks of the garbled circuit. A useful property of such a simulation strategy is that only a few of these local simulators depend on the input, whereas the rest of the local simulators only depend on the circuit.

We formalize this notion by defining locally simulatable garbling schemes. By suitably realizing this notion, we give a new construction of succinct garbling schemes for Turing machines assuming the polynomial hardness of compact functional encryption and standard assumptions (such as either CDH or LWE). Prior constructions of succinct garbling schemes either assumed sub-exponential hardness of compact functional encryption or were designed only for small-space Turing machines.

We also show that a variant of locally simulatable garbling schemes can be used to generically obtain adaptively secure garbling schemes for circuits. All prior constructions of adaptively secure garbling that use somewhere equivocal encryption can be seen as instantiations of our construction.

This work describes a common framework for scale-invariant families of fully homomorphic schemes based on Ring-LWE, unifying the plaintext space and the noise representation. This new formalization allows to build bridges between B/FV, HEAAN and TFHE and provides the possibility to take advantage of the best of these three schemes. In particular, we review how different strategies developed for each of these schemes, such as bootstrapping, external product, integer arithmetic and Fourier series, can be combined to evaluate the principle nonlinear functions involved in convolutional neural networks. Finally, we show that neural networks are particularly robust against perturbations that could potentially result from the propagation of large homomorphic noise. This allows choosing smaller and more performant parameters sets.

Cryptography is a key element in establishing trust and enabling services in the digital world. Currently, cryptography is realized with mathematical operations and represented in ways that are not accessible to human users. Thus, humans are left out of the loop when establishing trust and security in the digital world. In many areas the interaction between users and machines is being made more and more seamless and user-friendly, but cryptography has not really enjoyed such development. In this paper, we present ideas that could make cryptography more accessible to humans. We review previous research on this topic and some results that have been achieved. We propose several topics and problems that need to be solved in order to build cryptography for human senses. These measures range from practical implementations of existing methods and utilising a wider range of human senses all the way to building the theoretical foundations of this new form of cryptography.

We describe obfuscation schemes for matrix-product branching programs that are purely algebraic and employ matrix algebra and tensor algebra over a finite field. In contrast to the obfuscation schemes of Garg et al (SICOM 2016) which were based on multilinear maps, these schemes do not use noisy encodings. We prove that there is no efficient attack on our scheme based on re-linearization techniques of Kipnis-Shamir (CRYPTO 99) and its generalization called XL-methodology (Courtois et al, EC2000). We also provide analysis to claim that general Grobner-basis computation attacks will be inefficient. In a generic colored matrix model our construction leads to a virtual-black-box obfuscator for NC$^1$ circuits.

Security against selective opening attack (SOA) for receivers requires that in a multi-user setting, even if an adversary has access to all ciphertexts, and adaptively corrupts some fraction of the users to obtain the decryption keys corresponding to some of the ciphertexts, the remaining (potentially related) ciphertexts retain their privacy. In this paper, we study simulation-based selective opening security for receivers of public key encryption (PKE) schemes under chosen-ciphertext attacks (RSIM-SO-CCA).

Concretely, we first show that some known PKE schemes meet RSIM-SO-CCA security. Then, we introduce the notion of master-key SOA security for identity-based encryption (IBE), and extend the Canetti-Halevi-Katz (CHK) transformation to show generic PKE constructions achieving RSIM-SO-CCA security. Finally, we show how to construct an IBE scheme achieving master-key SOA security.

Consensus (a.k.a. Byzantine agreement) is arguably one of the most fundamental problems in distributed systems, playing also an important role in the area of cryptographic protocols as the enabler of a (secure) broadcast functionality. While the problem has a long and rich history and has been analyzed from many different perspectives, recently, with the advent of blockchain protocols like Bitcoin, it has experienced renewed interest from a much wider community of researchers and has seen its application expand to various novel settings.

One of the main issues in consensus research is the many different variants of the problem that exist as well as the various ways the problem behaves when different setup, computational assumptions and network models are considered. In this work we perform a systematization of knowledge in the landscape of consensus research starting with the original formulation in the early 1980s up to the present blockchain-based new class of consensus protocols. Our work is a roadmap for studying the consensus problem under its many guises, classifying the way it operates in many settings and highlighting the exciting new applications that have emerged in the blockchain era.

Attribute-based encryption (ABE) enables limiting access to encrypted data to users with certain attributes. Different aspects of ABE were studied, such as the multi-authority setting (MA-ABE), and policy hiding, meaning the access policy is unknown to unauthorized parties. However, no practical scheme so far provably provides both properties, which are often desirable in real-world applications: supporting decentralization, while hiding the access policy. We present the first practical decentralized ABE scheme with a proof of being policy-hiding. Our construction is based on a decentralized inner-product predicate encryption scheme, introduced in this paper, which hides the encryption policy. It results in an ABE scheme supporting conjunctions, disjunctions and threshold policies, that protects the access policy from parties that are not authorized to decrypt the content. Further, we address the issue of receiver privacy. By using our scheme in combination with vector commitments, we hide the overall set of attributes possessed by the receiver from individual authorities, only revealing the attribute that the authority is controlling. Finally, we propose randomizing-polynomial encodings that immunize the scheme in the presence of corrupt authorities.

We consider a situation in which two mutually distrusting parties, each possessing a secret piece of information, wish to exchange these secrets while communicating over a secure channel, in effect ``trading" them. Each is afraid of counterparty risk: Alice fears that as soon as she sends her secret to Bob he will cease communication without sending his secret in return, and likewise for the reverse case. In the situation where Alice and Bob's secrets are protected by isogenies, we propose a system in which Alice and Bob may fairly exchange their secrets without counterparty risk, and without a trusted third party. We then discuss potential applications.

Protocols for secure multiparty computation enable a set of parties to compute a joint function of their inputs, while preserving \emph{privacy}, \emph{correctness} and more. In theory, secure computation has broad applicability and can be used to solve many of the modern concerns around utilization of data and privacy. Huge steps have been made towards this vision in the past few years, and we now have protocols that can carry out large computations extremely efficiently, especially in the setting of an honest majority. However, in practice, there are still major barriers to widely deploying secure computation, especially in a decentralized manner.

In this paper, we present the first end-to-end automated system for deploying large-scale MPC protocols between end users, called MPSaaS (for \textit{MPC system-as-a-service}). Our system enables parties to pre-enroll in an upcoming MPC computation, and then participate by either running software on a VM instance (e.g., in Amazon), or by running the protocol on a mobile app, in Javascript in their browser, or even on an IoT device. Our system includes an automation system for deploying MPC protocols, an administration component for setting up an MPC computation and inviting participants, and an end-user component for running the MPC protocol in realistic end-user environments. We demonstrate our system for a specific application of running secure polls and surveys, where the secure computation is run end-to-end with each party actually running the protocol (i.e., without relying on a set of servers to run the protocol for them). This is the first such system constructed, and is a big step forward to the goal of commoditizing MPC.

One of the cryptographic difficulties that arise in this type of setting is due to the fact that end users may have low bandwidth connections, making it a challenge to run an MPC protocol with high bandwidth. We therefore present a protocol based on Beerliova-Trubiniova and Hirt (TCC 2008) with many optimizations, that has very low concrete communication, and the lowest published for small fields. Our protocol is secure as long as less than a third of the parties are \textit{malicious}, and is well suited for computing both arithmetic and Boolean circuits. We call our protocol HyperMPC and show that it has impressive performance. In particular, 150 parties can compute statistics---mean, standard deviation and regression---on 4,000,000 inputs (with a circuit of size 16,000,000 gates of which 6,000,000 are multiplication) in five minutes, and 10 parties can compute the same circuit in 30 seconds. Although our end-to-end system can be used to run any MPC protocol (and we have incorporated numerous protocols already), we demonstrate it for our new protocol that is optimized for end-users without high bandwidth.

The Computer Science Department at National Chengchi University invites applications for multiple tenure-track/tenured faculties from outstanding candidates at all ranks (assistant, associate, and full professor) to begin at Spring 2019 or Fall 2019.

Initial review of applications will begin on October 1st, 2018 and continue until the position is filled. The position may close when an adequate number of qualified applications are received.

We seek candidates in research areas related to all fields in Computer Science. Candidates from the following research areas are especially welcome:

• Artificial Intelligence

• Information Security

• Interdisciplinary fields of computer science and social science (eg., CS and Digital Content, CS and Communication, CS and Finance, etc. )

At a minimum, candidates must have a Ph.D. degree in Computer Science or a closely related field and have demonstrated strong research ability.

Applicants must send curriculum vitae, transcripts, diploma certificate, a copy of Ph.D. dissertation or abstract, recent publications, and at least two recommendation letters to recruit (at) cs.nccu.edu.tw or

Faculty Recruit Committee Department of Computer Science

National Chengchi University

64, Sec. 2, ZhiNan Rd. Wenshan District

Taipei, Taiwan, 11605

R.O.C.

Applicants are invited to visit our web page at https://www.cs.nccu.edu.tw .

Closing date for applications: 1 February 2019

Contact: Raylin Tso

Chairman of the Department of Computer Science, National Chengchi University

eMail: raylin (at) cs.nccu.edu.tw

More information: https://www.cs.nccu.edu.tw