International Association
for Cryptologic Research

Recently, blockchain technology has attracted much attention of the research community in several domains requiring transparency of data accountability, due to the removal of intermediate trust assumptions from third parties. One such application is enabling file sharing in blockchain enabled distributed cloud storage. Proxy re-encryption is a cryptographic primitive that allows such file sharing by re-encrypting ciphertexts towards legitimate users via semi-trusted proxies, without them learning any information about the underlying message. To facilitate secure data sharing in the distributed cloud, it is essential to construct efficient proxy re-encryption protocols. In this paper, we introduce the notion of proxy self re-encryption (SE-PRE) that is highly efficient, as compared to the existing PRE schemes in the literature. We show that our self encryption scheme is provably CCA secure based on the DLP assumption and our proxy re-encryption scheme with self encryption is CCA secure under the hardness of the Computational Diffie Hellman (CDH) and Discrete Logarithm (DLP) assumption. Our novel encryption scheme, called self encryption, has no exponentiation or costly pairing operation. Even the re-encryption in SE-PRE does not have such operations and this facilitates the service provider with efficiency gain.

We propose a new method to compare numbers which are encrypted by Homomorphic Encryption (HE). Previously, comparison and min/max functions were evaluated using Boolean functions where input numbers are encrypted bit-wisely. However, the bit-wise encryption methods require relatively expensive computation of basic arithmetic operations such as addition and multiplication.

In this paper, we introduce iterative algorithms that approximately compute the min/max and comparison operations of several numbers which are encrypted word-wisely. From the concrete error analyses, we show that our min/max and comparison algorithms have $\Theta(\alpha)$ and $\Theta(\alpha\log\alpha)$ computational complexity to obtain approximate values within an error rate $2^{-\alpha}$, while the previous minimax polynomial approximation method requires the exponential complexity $\Theta(2^{\alpha/2})$ and $\Theta(\sqrt{\alpha}\cdot 2^{\alpha/2})$, respectively. We also show the (sub-)optimality of our min/max and comparison algorithms in terms of asymptotic computational complexity among polynomial evaluations to obtain approximate min/max and comparison results. Our comparison algorithm is extended to several applications such as computing the top-$k$ elements and counting numbers over the threshold in encrypted state.

Our new method enables word-wise HEs to enjoy comparable performance in practice with bit-wise HEs for comparison operations while showing much better performance on polynomial operations. Computing an approximate maximum value of any two $\ell$-bit integers encrypted by HEAAN, up to error $2^{\ell-10}$, takes only $1.14$ milliseconds in amortized running time, which is comparable to the result based on bit-wise HEs.

Transactions are arguably the most important part in the bitcoin mechanism, with everything else facilitating the proper creation, propagation and validation; culminating with their addition to the public ledger – the blockchain. One crucial measure inevitably intertwined with transactions is, throughput, the number of transactions confirmed (or added to the blockchain) per second, or simply, tps. Understanding throughput capacity from different angles remains of paramount importance for gaining insights into the underlying infrastructure. We compute the exact upper bound for the maximal transaction throughput of the bitcoin protocol and obtain 27 tps. The previous best known bound for the average transaction throughput is 7 tps. All results are based on legacy infrastructure, i.e., pre-SegWit era.

Decentralised ledgers are a prime application case for consensus protocols. Changing sets of validators have to agree on a set of transactions in an asynchronous network and in the presence of Byzantine behaviour. Major research efforts focus on creating consensus protocols under such conditions, with proof-of-stake (PoS) representing a promising candidate for decentralised ledgers. PoS aims to reduce the waste of energy inherent to proof-of-work (PoW) consensus protocols. However, a significant challenge is to get PoS protocols "right", i.e. ensure that they are secure w.r.t. safety and liveness. Security proofs are provided using pen-and-paper approaches including the "Correct-by-Construction" (CBC) Casper proposed by the Ethereum project. CBC Casper's design philosophy deviates from traditional consensus protocols as it is an abstract framework to define consensus protocols and aims to prove its correctness without loss of abstractness. Each member of the CBC Casper family of protocols is defined by five parameters. CBC Casper models the protocol by a state of each validator and messages sent by validators. Each validator can transition its state using messages by other validators that include their current consensus value and a justification (i.e. their previous messages). We extend CBC Casper in three ways. First, we summarise the research of CBC Casper and extend the definitions of safety and liveness properties. To this end, we discuss an instance of CBC Casper called Casper The Friendly GHOST (TFG), a consensus protocol using a variant of the GHOST fork-choice rule. Second, we refine the properties of messages and states in CBC Casper and give a definition of blockchain safety for Casper TFG. Third, we formally verify CBC Casper together with our additional properties in the Isabelle/HOL proof assistant.

Event date: 15 November to 17 November 2019
Submission deadline: 10 June 2019
Notification: 20 April 2019

We are looking for outstanding Post doctoral researchers working on topics related to cryptography and IT Security.

Current topics of interest include (but are not limited to):

- Secure cryptographic implementations

- Leakage/tamper resilient cryptography

- Blockchains and cryptocurrencies

- Distributed cryptography

The application must include a curriculum vitae, a short research statement, and names of 2 contacts that can provide reference about the applicant and her/his work. The candidate shall be able to show solid expertise in cryptography/IT Security illustrated in form of publications at major crypto/security venues such as CRYPTO, EUROCRYPT, ASIACRYPT, TCC, PKC, CHES, FC, ACM CCS, IEEE S&P, USENIX Security, NDSS etc.

The position can be partially funded by the Ethereum Foundation and hence offers an internationally competitive salary including social benefits, and the opportunity for close collaboration with one of the leading cryptocurrencies.

TU Darmstadt offers excellent working environment and has a strong institute for research on IT security with more than 300 researchers working on all aspects of cybersecurity.

Review of applications starts immediately until the position is filled.

Closing date for applications: 14 June 2019

Contact: Prof. Sebastian Faust, Contact: sebastian.faust(at)cs(dot)tu-darmstadt(dot)de

This is an exciting opportunity for a Lecturer/Senior Lecturer in Cybersecurity at the University of Sheffield, a world top 100 University.

The Department of Computer Science (https://www.sheffield.ac.uk/dcs) is embarking on an ambitious growth strategy following our strong performance in the Research Excellence Framework (REF) 2014, in which we were ranked 5th out of 89 computer science departments in the UK. The Department is part of the Faculty of Engineering, ranked 84th globally by the recent Times Higher Education (THE) World University Rankings, and holds a Silver Athena SWAN award, in recognition of our commitment to equality and diversity.

We are seeking candidates with an outstanding record of scholarship in cybersecurity. Suitable areas of expertise include (but are not limited to): security policies, threat modelling, authentication, access control, malware and malware detection, network security, secure protocols, secure software, security testing, and human factors and security. Candidates whose expertise includes elements of ‘security by design’ (primarily focused on software based systems) are particularly encouraged to apply.

You will hold a PhD in Computer Science or a relevant discipline (or have equivalent experience), and you will be able to conduct research to the highest standards. You will secure research funding, publish in high impact journals, supervise research students and manage research projects. As a teacher, you will play a key role in maintaining our reputation for high-quality teaching by designing, delivering and assessing undergraduate and postgraduate-level courses in cybersecurity and other core topics in computer science.

We’re one of the best not-for-profit organisations to work for in the UK. The University’s Total Reward Package includes a competitive salary, a generous Pension Scheme and annual leave entitlement, as well as access to a range of learning and development courses to support your personal and professional development.

Closing date for applications: 21 May 2019

Contact: Prof John Clark, Security of Advanced Systems Research Group Lead. An initial contact via email (john.clark (at) sheffield.ac.uk) is encouraged.

More information: https://www.jobs.ac.uk/job/BRR743/lecturer-senior-lecturer-in-cybersecurity

We show a new general approach for constructing maliciously secure two-round oblivious transfer (OT). Specifically, we provide a generic sequence of transformations to upgrade a very basic notion of two-round OT, which we call elementary OT, to UC-secure OT. We then give simple constructions of elementary OT under the Computational Diffie-Hellman (CDH) assumption or the Learning Parity with Noise (LPN) assumption, yielding the first constructions of malicious (UC-secure) two-round OT under these assumptions. Since two-round OT is complete for two-round 2-party and multi-party computation in the malicious setting, we also achieve the first constructions of the latter under these assumptions.

An adversary with $S$ bits of memory obtains a stream of $Q$ elements that are uniformly drawn from the set $\{1,2,\ldots,N\}$, either with or without replacement. This corresponds to sampling $Q$ elements using either a random function or a random permutation. The adversary's goal is to distinguish between these two cases.

This problem was first considered by Jaeger and Tessaro (EUROCRYPT 2019), which proved that the adversary's advantage is upper bounded by $\sqrt{Q \cdot S/N}$. Jaeger and Tessaro used this bound as a streaming switching lemma which allowed proving that known time-memory tradeoff attacks on several modes of operation (such as counter-mode) are optimal up to a factor of $O(\log N)$ if $Q \cdot S \approx N$. However, if $Q \cdot S \ll N$ there is a gap between the upper bound of $\sqrt{Q \cdot S/N}$ and the $Q \cdot S/N$ advantage obtained by known attacks. Moreover, the bound's proof assumed an unproven combinatorial conjecture.

In this paper, we prove a tight upper bound (up to poly-logarithmic factors) of $O(\log Q \cdot Q \cdot S/N)$ on the adversary's advantage in the streaming distinguishing problem. The proof does not require a conjecture and is based on a reduction from communication complexity to streaming.

In this document, we investigate the complexity of an old-time combinatorial problem - namely Permuted Kernel Problem (PKP) - about which no new breakthrough were reported for a while. PKP is an NP-complete algebraic problem that consists of finding a kernel vector with particular entries for a publicly known matrix. It’s simple, and needs only basic linear algebra. Hence, this problem was used to develop the first Identification Scheme (IDS) which has an efficient implementation on low-cost smart cards. The Permuted Kernel Problem has been extensively studied. We present a summary of previously known algorithms devoted to solve this problem and give an update to their complexity. Contrary to what is shown in JOUX-JAULMES's article, and after a thorough analysis of the State-of-the-art attacks of PKP, we claim that the most efficient algorithm for solving PKP is still the one introduced by J. PATARIN and P. CHAUVAUD. We have been able to specify a theoretical bound on the complexity of PKP which allows us to identify hard instances of this latter. Among all the attacks, the problem PKP is in spite of the research effort, still exponential.

As of 12th January 2019, Monero is ranked as the first privacy-preserving cryptocurrency by market capitalization, and the 14th among all cryptocurrencies. This paper aims at improving the understanding of the Monero peer-to-peer network. We develop a tool set to explore the Monero peer-to-peer network, including its network size, distribution, and connectivity. In addition, we set up four Monero nodes that run our tools: two in the U.S., one in Asia, and one in Europe. We show that through a short time (one week) data collection, our tool is already able to discover 68.7% more daily active peers (in average) compared to a Monero mining pool, called Monerohash, that also provides data on the Monero node distribution. Overall, we discovered 21,678 peer IP addresses in the Monero network. Our results show that only 4,329 (about 20%) peers are active. We also show that the nodes in the Monero network follow the power law distribution concerning the number of connections they maintain. In particular, only 0.7% of the active maintain more than 250 outgoing connections simultaneously, and a large proportion (86.8%) of the nodes maintain less than 8 outgoing connections. These 86.8% nodes only maintain 17.14% of the overall connections in the network, whereas the remaining 13.2% nodes maintain 82.86% of the overall connections. We also show that our tool is able to dynamically infer the complete outgoing connections of 99.3% nodes in the network, and infer 250 outgoing connections of the remaining 0.7% nodes.

Sanitizable signatures allow a single, and signer-defined, sanitizer to modify signed messages in a controlled way without invalidating the respective signature. They turned out to be a fascinating primitive, proven by different variants and extensions, e.g., allowing multiple sanitizers or adding new sanitizers one-by-one. Still, existing constructions are very limited regarding their flexibility in specifying potential sanitizers. In this paper, we propose a different and more powerful approach: Instead of using the sanitizers' public keys directly, we assign attributes to them. Sanitizing is then based on policies, i.e., access structures defined over attributes. A sanitizer can sanitize, if, and only if, it holds a secret key to attributes satisfying the policy associated to a signature, while offering full-scale accountability.

This paper presents a novel, yet efficient secret-key authentication and MAC, which provide post-quantum security promise, whose security is reduced to the quantum-safe conjectured hardness of Mersenne Low Hamming Combination (MERS) assumption recently introduced by Aggarwal, Joux, Prakash, and Santha (CRYPTO 2018). Our protocols are very suitable to weak devices like smart card and RFID tags.

This document includes a collision/forgery attack against SNEIKEN128/192/256, where every message with more than 128 bytes of associated data can be converted into another message with different associated data and the same ciphertext/tag. The attack is a direct application of the probability 1 differential of the SNEIK permutation found by Léo Perrin in [Per19]. We verify the attack using the reference implementation of SNEIKEN128 provided by the designers, providing an example of such collisions.

The end-users communicating over a network path currently have no control over the path. For a better quality of service, the source node often opts for a superior (or premium) network path in order to send packets to the destination node. However, the current Internet architecture provides no assurance that the packets indeed follow the designated path. Network path validation schemes address this issue and enable each node present on a network path to validate whether each packet has followed the specific path so far. In this work, we introduce two notions of privacy -- path privacy and index privacy -- in the context of network path validation. We show that, in case a network path validation scheme does not satisfy these two properties, the scheme is vulnerable to certain practical attacks (that affect the reliability, neutrality and quality of service offered by the underlying network). To the best of our knowledge, ours is the first work that addresses privacy issues related to network path validation. We design PrivNPV, a privacy-preserving network path validation protocol, that satisfies both path privacy and index privacy. We discuss several attacks related to network path validation and how PrivNPV defends against these attacks. Finally, we discuss the practicality of PrivNPV based on relevant parameters.

Blockchain technologies recently received a considerable amount of attention. While the initial focus was mainly on the use of blockchains in the context of cryptocurrencies such as Bitcoin, application scenarios now go far beyond this. Most blockchains have the property that once some object, e.g., a block or a transaction, has been registered to be included into the blockchain, it is persisted and there are no means to modify it again. While this is an essential feature of most blockchain scenarios, it is still often desirable - at times it may be even legally required - to allow for breaking this immutability in a controlled way. Only recently, Ateniese et al. (EuroS&P 2017) proposed an elegant solution to this problem on the block level. Thereby, the authors replace standard hash functions with so-called chameleon-hashes (Krawczyk and Rabin, NDSS 2000). While their work seems to offer a suitable solution to the problem of controlled re-writing of blockchains, their approach is too coarse-grained in that it only offers an all-or-nothing solution. We revisit this idea and introduce the novel concept of policy-based chameleonhashes (PCH). PCHs generalize the notion of chameleon-hashes by giving the party computing a hash the ability to associate access policies to the generated hashes. Anyone who possesses enough privileges to satisfy the policy can then find arbitrary collisions for a given hash. We then apply this concept to transaction-level rewriting within blockchains, and thus support fine-grained and controlled modifiability of blockchain objects. Besides modeling PCHs, we present a generic construction of PCHs (using a strengthened version of chameleon-hashes with ephemeral trapdoors which we also introduce), rigorously prove its security, and instantiate it with efficient building blocks. We report first implementation results.

Field-Programmable Gate Arrays or FPGAs are popular platforms for hardware-based attestation. They offer protection against physical and remote attacks by verifying if an embedded processor is running the intended application code. However, since FPGAs are configurable after deployment (thus not tamper-resistant), they are susceptible to attacks, just like microprocessors. Therefore, attesting an electronic system that uses an FPGA should be done by verifying the status of both the software and the hardware, without the availability of a dedicated tamper-resistant hardware module. Inspired by the work of Perito and Tsudik, this paper proposes a partially reconfigurable FPGA architecture and attestation protocol that enable the self-attestation of the FPGA. Through the use of our solution, the FPGA can be used as a trusted hardware module to perform hardware-based attestation of a processor. This way, an entire hardware/software system can be protected against malicious code updates.

Message authentication code, MAC for short, is a symmetric-key cryptographic function for authenticity. A standard MAC verification only tells whether the message is valid or invalid, and thus we can not identify which part is corrupted in case of invalid message. In this paper we study a class of MAC functions that enables to identify the part of corruption, which we call group testing MAC (GTM). This can be seen as an application of a classical (non-adaptive) combinatorial group testing to MAC. Although the basic concept of GTM (or its keyless variant) has been proposed in various application areas, such as data forensics and computer virus testing, they rather treat the underlying MAC function as a black box, and exact computation cost for GTM seems to be overlooked. In this paper, we study the computational aspect of GTM, and show that a simple yet non-trivial extension of parallelizable MAC (PMAC) enables $O(m+t)$ computation for $m$ data items and $t$ tests, irrespective of the underlying test matrix we use, under a natural security model. This greatly improves efficiency from naively applying a black-box MAC for each test, which requires $O(mt)$ time. Based on existing group testing methods, we also present experimental results of our proposal and observe that ours runs as fast as taking single MAC tag, with speed-up from the conventional method by factor around 8 to 15 for $m=10^4$ to $10^5$ items.

Pairing-friendly elliptic curves in the Barreto-Lynn-Scott family have experienced a resurgence in popularity due to their use in a number of real-world projects. One particular Barreto-Lynn-Scott curve, called BLS12-381, is the locus of significant development and deployment effort, especially in blockchain applications. This effort has sparked interest in using BLS12-381 for BLS signatures, and in particular for aggregatable signatures, which requires hashing to one of the groups of the bilinear pairing defined by the BLS12-381 elliptic curve.

While there is a substantial body of literature on the problem of hashing to elliptic curves, much of this work does not apply to Barreto-Lynn-Scott curves. Moreover, the work that does apply has the unfortunate property that fast implementations are complex, while simple implementations are slow.

In this work, we address these issues. First, we show a straightforward way of adapting the "simplified SWU" map of Brier et al. to BLS12-381. Second, we describe optimizations to the SWU map that both simplify its implementation and improve its performance; these optimizations may be of interest in other contexts. Third, we implement and evaluate. We find that our work yields constant-time hash functions that are simple to implement, yet perform within 9% of the fastest, non--constant-time alternatives, which require much more complex implementations.

The universal composability (UC) framework is the established standard for analyzing cryptographic protocols in a modular way, such that security is preserved under concurrent composition with arbitrary other protocols. However, although UC is widely used for on-paper proofs, prior attempts at systemizing it have fallen short, either by using a symbolic model (thereby ruling out computational reduction proofs), or by limiting its expressiveness.

In this paper, we lay the groundwork for building a concrete, executable implementation of the UC framework. Our main contribution is a process calculus, dubbed the Interactive Lambda Calculus (ILC). ILC faithfully captures the computational model underlying UC---interactive Turing machines (ITMs)---by adapting ITMs to a subset of the pi-calculus through an affine typing discipline. In other words, well-typed ILC programs are expressible as ITMs. In turn, ILC's strong confluence property enables reasoning about cryptographic security reductions. We use ILC to develop a simplified implementation of UC called SaUCy.