International Association
for Cryptologic Research

The term Nakamoto consensus is generally used to refer to Bitcoin's novel consensus mechanism, by which agreement on its underlying transaction ledger is reached. It is argued that this agreement protocol represents the core innovation behind Bitcoin, because it promises to facilitate the decentralization of trusted third parties. Specifically, Nakamoto consensus seeks to enable mutually distrusting entities with weak pseudonymous identities to reach eventual agreement while the set of participants may change over time. When the Bitcoin white paper was published in late 2008, it lacked a formal analysis of the protocol and the guarantees it claimed to provide. It would take the scientific community several years before first steps towards such a formalization of the Bitcoin protocol and Nakamoto consensus were presented. However, since then the number of works addressing this topic has grown substantially, providing many new and valuable insights. Herein, we present a coherent picture of advancements towards the formalization of Nakamoto consensus, as well as a contextualization in respect to previous research on the agreement problem and fault tolerant distributed computing. Thereby, we outline how Bitcoin's consensus mechanism sets itself apart from previous approaches and where it can provide new impulses and directions to the scientific community. Understanding the core properties and characteristics of Nakamoto consensus is of key importance, not only for assessing the security and reliability of various blockchain systems that are based on the fundamentals of this scheme, but also for designing future systems that aim to fulfill comparable goals.

Event date: 29 July to 2 August 2018

We study the properties of an algorithm for solving the elliptic curve discrete logarithm problem presented by A.~Yu.~Nesterenko at the CTCrypt 2015 session. We show that for practically important instances of the problem its average complexity is not less than that of Pollard's rho-method.

Besides simple transfers of currency, Bitcoin also enables various forms of smart contracts, i.e. protocols where users interact within pre-agreed rules, which determine (possibly depending on the actual interaction) how currency is eventually distributed. This paper provides a gentle introduction to Bitcoin smart contracts, which we specify by abstracting from the underlying Bitcoin machinery. To this purpose we exploit BitML, a recent DSL for smart contracts executable on Bitcoin.

We are currently seeking to recruit 1 PhD student to work on the project Cryptographic privacy-preserving protocols for location based services.

Most apps, services, devices and even websites now require access to the user\'s location. But location information is very sensitive, and must be protected from data breaches and malicious tracking. How can we preserve the user\'s privacy without disrupting location based services? Location privacy is a growing research area in the field of privacy-enhancing technologies, with applications relating to personal privacy, autonomous vehicles and the Internet of Things (IoT). This project investigates the design and development of privacy-preserving protocols for location based services, including cryptographic protocols and data structures.

The PhD position is fully funded for 4 years, including a monthly stipend and a travel budget to present at international conferences. The successful candidate will also have the opportunity to work with the Principal Investigator extensive network of international research collaborations.

Candidates should have a background/strong interest in security and privacy, as well as a good grasp of mathematics. Previous experience in cryptography is an asset, but is not required.

Interested candidates should apply by email to Dr. Paolo Palmieri (p.palmieri (at) cs.ucc.ie), CC’ing the Department of Computer Science (csmanager (at) cs.ucc.ie), on or before the 20th of May 2018. Early applications are encouraged.

Applicants should include: 1) a covering letter (1 page) explaining their interest in the project topic, and mentioning any previous experience in security/privacy/cryptography; 2) a Curriculum Vitae.

Academic transcripts and references will be required after shortlisting.

Closing date for applications: 20 May 2018

Contact: Dr. Paolo Palmieri (p.palmieri (at) cs.ucc.ie)

A fully-funded (22,000 GBP plus fees) PhD position in Cyber Security to work on a research project focusing on modelling and verification of distributed ledger technologies with respect to threat models and security analysis. The successful candidate will be working under supervision of Professor Steve Schneider(Principal Supervisor, http://www.surrey.ac.uk/cs/people/Steve_Schneider) and Dr David Williams (Co-Supervisor).

Closing date for applications: 31 May 2018

Contact: Professor Steve Schneider: s.schneider (at) surrey.ac.uk

More information: https://jobs.surrey.ac.uk/vacancy.aspx?ref=029018

Research Fellow in Voting on Ledger Technologies

Closing date for applications: 29 May 2018

Contact: Professor Steve Schneider

Director, Surrey Centre for Cyber Security

University of Surrey, Guildford, GU2 7XH

s.schneider (at) surrey.ac.uk

+44 1483 689637

More information: https://jobs.surrey.ac.uk/vacancy.aspx?ref=034017-R-R

Indistinguishability Obfuscation ($iO$) is a hopeful tool which obfuscates a program with the least leakage, and produces various applications including functional encryption. Recently, a state-of-the-art obfuscator implementation underlying the branching program matrix, HHSS, has been suggested by Halevi et. al. in ACM-CCS'17.

In this work, we describe the first attack algorithm which can be applied to HHSS obfuscation depending on the dimension of the branching program matrix. When two matrix branching programs and an obfuscated program using HHSS obfuscation are given, we can distinguish which branching program was used to make an obfuscated program.

Our attack uses a left kernel of the product of branching program matrices. If we obtain a short vector in the left kernel, we manipulate the result of the zerotesting procedure because HHSS obfuscation removes a special setting called `scalar bundling' in the initialization step for its efficiency. More precisely, the zerotesting procedure exposes the left kernel of the product of branching program matrices, so we can use the property employing a lattice reduction algorithm on the left kernel. Indeed, we find a short vector what we want using a lattice reduction algorithm. As a result, we can find a vector what we want in the complexity $2^{O(\frac{d}{B-\epsilon})}$, where $d$ is the dimension of the branching program matrices and a gap parameter $B$ and a real value $\epsilon$ are given. For example, we can find a short vector applying the LLL algorithm for the current parameter proposed by HHSS implementation with $d=100$. It takes less than a second with the precomputation of the evaluation of the obfuscated program.

In this paper, we optimize Bleichenbacher's statistical attack technique against (EC)DSA and other Schnorr-like signature schemes with biased or partially exposed nonces. Previous approaches to Bleichenbacher's attack suffered from very large memory consumption during the so-called "range reduction" phase. Using a carefully analyzed and highly parallelizable approach to this range reduction based on the Schroeppel-Shamir algorithm for knapsacks, we manage to overcome the memory barrier of previous work while maintaining a practical level of efficiency in terms of time complexity.

As a separate contribution, we present new fault attacks against the qDSA signature scheme of Renes and Smith (ASIACRYPT 2017) when instantiated over the Curve25519 Montgomery curve, and we validate some of them on the AVR microcontroller implementation of qDSA using actual fault experiments on the ChipWhisperer-Lite evaluation board. These fault attacks enable an adversary to generate signatures with 2 or 3 bits of the nonces known.

Combining our two contributions, we are able to achieve a full secret key recovery on qDSA by applying our version of Bleichenbacher's attack to these faulty signatures. Using a hybrid parallelization model relying on both shared and distributed memory, we achieve a very efficient implementation of our highly scalable range reduction algorithm. This allows us to complete Bleichenbacher's attack in the 252-bit prime order subgroup of Curve25519 within a reasonable time frame and using relatively modest computational resources both for 3-bit nonce exposure and for the much harder case of 2-bit nonce exposure. Both of these computations, and particularly the latter, set new records in the implementation of Bleichenbacher's attack.

Consider the following embedding problem. Alice has input $\mathbf{a} = (a_1,\dotsc,a_m)\in\mathbb{F}^m$ and Bob has input $\mathbf{b} = (b_1,\dotsc,b_m)\in\mathbb{F}^m$, where $\mathbb{F}$ is a finite field. The two parties want Bob to receive $\mathbf{c} = (c_1,\dotsc,c_m)$ such that $c_i=a_i\cdot b_i$, for all $i\in\{1,\dotsc,m\}$. Alice and Bob have access to an oracle that takes as input two elements $A,B\in \mathbb{K}$ from Alice and Bob, respectively, and outputs the product $C=A\cdot B\in\mathbb{K}$ to Bob, where $\mathbb{K}$ is a degree-$n$ extension of the finite field $\mathbb{F}$. Alice and Bob want to perform only one call to this oracle and enable Bob to compute $\mathbb{c}$ without any additional communication. Given $n$, how large can $m$ be?

More tersely: ``How many multiplications over the base field can we perform using only one multiplication over an extension field?''

Block, Maji, and Nguyen (CRYPTO--2017) proposed this problem and their combinatorial solution achieved $m=n^{1-o(1)}$. Our paper presents an explicit embedding that achieves the optimal asymptotic bound $m=\Theta(n)$, where the constant in the asymptotic notation depends on the size of the base field $|\mathbb{F}|$. The construction of our proposed embedding relies on the toolkit provided by algebraic function fields.

Although the study of this embedding problem is of independent theoretical interest, we present a few representative applications to secure computation. We construct a linear number of oblivious transfers based on the computational hardness assumptions like the pseudorandomness of noisy Reed Solomon codewords with a constant computational overhead. This result enables the efficient secure evaluation of arithmetic circuits that use arithmetic gates over extension fields of the same base field. Next, we construct the first correlation extractor with a linear production rate and $1/2$ resilience by composing our embedding with the correlation extractor of Block, Maji, and Nguyen (CRYPTO--2017).

The problem of Byzantine Agreement (BA) is of interest to both distributed computing and cryptography community. Following well-known results from the distributed computing literature, BA problem in the asynchronous network setting encounters inevitable non-termination issues. The impasse is overcome via randomization that allows construction of BA protocols in two flavours of termination guarantee -- with overwhelming probability and with probability one. The latter type termed as almost-surely terminating BAs are the focus of this paper. An eluding problem in the domain of almost-surely terminating BAs is achieving a constant expected running time. Our work makes progress in this direction.

In a setting with $n$ parties and an adversary with unbounded computing power controlling at most $t$ parties in Byzantine fashion, we present two almost-surely terminating BA protocols in the asynchronous setting:

1. With the optimal resilience of $t < \frac{n}{3}$, our first protocol runs for expected ${\cal O}(n)$ time. The existing protocols in the same setting either runs for expected ${\cal O}(n^2)$ time (Abraham et al, PODC 2008) or requires exponential computing power from the honest parties (Wang, CoRR 2015). In terms of communication complexity, our construction outperforms all the known constructions that offer almost-surely terminating feature.

2. With the resilience of $t < \frac{n}{3 + \epsilon}$ for any $\epsilon > 0$, our second protocol runs for expected ${\cal O}(\frac{1}{\epsilon})$ time. The expected running time of our protocol turns constant when $\epsilon$ is a constant fraction. The known constructions with constant expected running time either require $\epsilon$ to be at least $1$ (Feldman-Micali, STOC 1988), implying $t < n/4$, or calls for exponential computing power from the honest parties (Wang, CoRR 2015). We follow the traditional route of building BA via common coin protocol that in turn reduces to asynchronous verifiable secret-sharing (AVSS). Our constructions are built on a variant of AVSS that is termed as shunning. A shunning AVSS fails to offer the properties of AVSS when the corrupt parties strike, but allows the honest parties to locally detect and shun a set of corrupt parties for any future communication. Our shunning AVSS with $t < n/3$ and $t < \frac{n}{3 + \epsilon}$ guarantee $\Omega(n)$ and respectively $\Omega(\epsilon t^2)$ conflicts to be revealed when failure occurs. Turning this shunning AVSS to a common coin protocol efficiently constitutes yet another contribution of our paper.

In this paper, we analyze security properties of the WalnutDSA, a digital signature algorithm recently proposed by I. Anshel, D. Atkins, D. Goldfeld, and P. Gunnels,that has been accepted by the National Institute of Standards and Technology for evaluation as a standard for quantum-resistant public-key cryptography. At the core of the algorithm is an action, named E-multiplication, of a braid group on some finite set. The protocol assigns a pair of braids to the signer as a private key. A signature of a message $m$ is a specially constructed braid that is obtained as a product of private keys, the hash value of $m$ encoded as a braid, and three specially designed cloaking elements.

We present a heuristic algorithm that allows a passive eavesdropper to recover a substitute for the signer's private key by removing cloaking elements and then solving a system of conjugacy equations in braids. Our attack has $100\%$ success rate on randomly generated instances of the protocol. It works with braids only and its success rate is not affected by a choice of the base finite field. In particular, it has the same $100\%$ success rate for recently suggested parameters values (including a new way to generate cloaking elements, see NIST PQC forum https://groups.google.com/a/list.nist.gov/forum/#!forum/pqc-forum). Implementation of our attack in C++, as well as our implementation of the WalnutDSA protocol, is available on GitHub (https://github.com/stevens-crag/crag).

The introduction of the processor instructions AES-NI and VPCLMULQDQ, that are designed for speeding up encryption, and their continual performance improvements through processor generations, has significantly reduced the costs of encryption overheads. More and more applications and platforms encrypt all of their data and traffic. As an example, we note the world wide proliferation of the use of AES-GCM, with performance dropping down to 0.64 cycles per byte (from ~23 before the instructions), on the latest Intel processors. This is close to the theoretically achievable performance with the existing hardware support. Anticipating future applications and increasing demand for high performance encryption, Intel has recently announced that its future architecture (codename "Ice Lake") will introduce new encryption instructions. These will be able to vectorize the AES-NI and VPCLMULQDQ instructions, on wide registers that are available on the AVX512 architectures. In this paper, we explain how these new instructions can be used effectively, and how properly using them can lead to the anticipated theoretical encryption throughput of around 0.16 cycles per byte. The included examples demonstrate AES encryption in various modes of operation, AEAD such as AES-GCM, and the emerging nonce misuse resistant variant AES-GCM-SIV.

We present a new public key broadcast encryption scheme where both the ciphertext and secret keys consist of a constant number of group elements. Our result improves upon the work of Boneh, Gentry, and Waters (Crypto '05) as well as several recent follow-ups (TCC '16-A, Asiacrypt '16) in two ways: (i) we achieve adaptive security instead of selective security, and (ii) our construction relies on the decisional $k$-Linear Assumption in prime-order groups (as opposed to $q$-type assumptions or subgroup decisional assumptions in composite-order groups); our improvements come at the cost of a larger public key. Finally, we show that our scheme achieves adaptive security in the multi-ciphertext setting with a security loss that is independent of the number of challenge ciphertexts.

At Asiacrypt 2014, Sun et al. proposed a MILP model to search differential trails for bit-oriented block ciphers. In this paper, we improve this model to search differential characteristics of GIFT, a new lightweight block cipher proposed at CHES 2017. GIFT has two versions, namely GIFT-64 and GIFT-128. For GIFT-64, we find the best 12-round differential characteristic with MILP-based model and give a key-recovery attack on 19-round GIFT-64. For GIFT-128, we find a 20-round differential characteristic and give the first attack on 25-round GIFT-128.

SSH is a security network protocol that uses public key cryptography for client authentication. SSH connections are designed to be run between a client and a server and therefore in enterprise networks there is no centralized monitoring of all SSH connections. An attractive method for enforcing such centralized control, audit or even revocation is to require all clients to access a centralized service in order to obtain their SSH keys. Doing this will introduce security and availability issues. The benefits of centralized control come with new challenges in security and availability.

In this paper we present ESKM - a \emph{distributed enterprise SSH key manager}. ESKM is a secure and fault-tolerant logically-centralized SSH key manager. ESKM leverages $k$-out-of-$n$ threshold security to provide a high level of security. SSH private keys are never stored \emph{at any single node}, not even when they are used for signing. On a technical level, the system uses $k$-out-of-$n$ threshold RSA signatures, which are enforced with new methods that refresh the shares in order to achieve proactive security and prevent many side-channel attacks. In addition, we support password-based user authentication with security against offline dictionary attacks, that is achieved using threshold oblivious pseudo-random evaluation.

ESKM does not require modification in the server side or of the SSH protocol. We implemented the ESKM system, and a patch for OpenSSL libcrypto for client side services. We show that the system is scalable and that the overhead in the client connection setup time is marginal.

The designers of Radio-Frequency IDentification (RFID) systems have a challenging task for proposing secure mutual authentication protocols for Internet of Things (IoT) applications. Recently, Fan et al. proposed a new lightweight RFID mutual authentication protocol in the journal of IEEE Transactions on Industrial Informatics. They claimed that their protocol meets necessary security properties for RFID systems and can be applied for IoT. In this paper, we analyze the security of this protocol and show that it is vulnerable against secret disclosure, reader impersonation and tag traceability attacks. Additionally, we show that in their protocol the anonymity of the tag does not held.

We propose secret-sharing-based bit-decomposition and modulus conversion protocols for a prime order ring $\mathbb{Z}_p$ with an honest majority: an adversary can corrupt $k-1$ parties of $n$ parties and $2k-1 \le n$. Our protocols are secure against passive and active adversaries depending on the components of our protocols. We assume a secret is an $\ell$-bit element and $2^{\ell+\lceil \log m \rceil} < p$, where $m= k$ in the passive security and $m= \binom{n}{k-1}$ in the active security. The outputs of our bit-decomposition and modulus-conversion protocols are $\ell$ tuple of shares in $\mathbb{Z}_2$ and a share in $\mathbb{Z}_{p'}$, respectively, where $p'$ is the modulus to be converted. If $k$ and $n$ are small, the communication complexity of our passively secure bit-decomposition and modulus-conversion protocols are $O(\ell)$ bits and $O(\lceil \log p' \rceil)$ bits, respectively. Our key observation is that a quotient of additive shares can be computed from the \emph{least} significant $\lceil \log m \rceil$ bits. If a secret $a$ is ``shifted'' and additively shared by $x_i$ in $\mathbb{Z}_p$ as $2^{\lceil \log m \rceil}a = \sum_{i=0}^{m-1} x_i = 2^{ \lceil \log m \rceil} a + qp$, the least significant $\lceil \log m \rceil$ bits of $\sum_{i=0}^{m-1} x_i$ determines $q$ since $p$ is an odd prime and the least significant $\lceil \log m \rceil$ bits of $2^{\lceil \log m \rceil} a$ are $0$s.

We study the problem of finding efficiently computable non-degenerate multilinear maps from $G_1^n$ to $G_2$, where $G_1$ and $G_2$ are groups of the same prime order, and where computing discrete logarithms in $G_1$ is hard. We present several applications to cryptography, explore directions for building such maps, and give some reasons to believe that finding examples with $n>2$ may be difficult.

Certificateless public key cryptography (CL-PKC) is designed to have succinct public key management without using certificates at the same time avoid the key-escrow attribute in the identity-based cryptography. Security mechanisms employing implicit certificates achieve same goals. In this work, we first unify the security notions of these two types of mechanisms with a modified CL-PKC formulation. We further present a general key-pair generation algorithm for CL-PKC schemes and uses it to construct certificateless public key signature (CL-PKS) schemes from standard algorithms. The technique, which we apply, helps defeat known-attacks against existing constructions, and the resulting schemes could be quickly deployed based on the existing standard algorithm implementations. The proposed schemes are particularly useful to provide security services such as authentication, data integrity and non-repudiation in the Internet of Things because of their high efficiency of computation cost, bandwidth consumption and storage requirement.