International Association
for Cryptologic Research

Although the transactions on the Bitcoin blockchain have the main purpose of recording currency transfers, they can also carry a few bytes of metadata. A sequence of transaction metadata forms a subchain of the Bitcoin blockchain, and it can be used to store a tamper-proof execution trace of a smart contract. Except for the trivial case of contracts which admit any trace, in general there may exist inconsistent subchains which represent incorrect contract executions. A crucial issue is how to make it difficult, for an adversary, to subvert the execution of a contract by making its subchain inconsistent. Existing approaches either postulate that subchains are always consistent, or give weak guarantees about their security (for instance, they are susceptible to Sybil attacks). We propose a consensus protocol, based on Proof-of-Stake, that incentivizes nodes to consistently extend the subchain. We empirically evaluate the security of our protocol, and we show how to exploit it as the basis for smart contracts on Bitcoin.

The HB protocol and its $HB^+$ successor are lightweight authentication schemes based on the Learning Parity with Noise (LPN) problem. They both suffer from the so-called GRS-attack whereby a man-in-the-middle (MiM) adversary can recover the secret key. At WiSec 2015, Pagnin et al. proposed the $HB+DB$ protocol: $HB^+$ with an additional distance-bounding dimension added to detect and counteract such MiM attacks. They showed experimentally that $HB+DB$ was resistant to GRS adversaries, and also advanced $HB+DB$ as a distance-bounding protocol, discussing its resistance to worst-case distance-bounding attackers.

In this paper, we exhibit flaws both in the authentication and distance-bounding layers of $HB+DB$; these vulnerabilities encompass practical attacks as well as provable security shortcomings. First, we show that $HB+DB$ may be impractical as a secure distance-bounding protocol, as its distance-fraud and mafia-fraud security-levels scale poorly compared to other distance-bounding protocols. Secondly, we describe an effective MiM attack against $HB+DB$: our attack refines the GRS-strategy and still leads to key-recovery by the attacker, yet this is not deterred by $HB+DB$'s distance-bounding. Thirdly, we refute the claim that $HB+DB$'s security against passive attackers relies on the hardness of the LPN problem. We also discuss how (erroneously) requiring such hardness, in fact, lowers $HB+DB$'s efficiency and its resistance to authentication and distance-bounding attacks. Drawing on $HB+DB$'s design flaws, we also propose a new distance-bounding protocol: $\mathbb{BLOG}$. It retains parts of $HB+DB$, yet $\mathbb{BLOG}$ is provably secure, even --in particular-- against MiM attacks. Moreover, $\mathbb{BLOG}$ enjoys better practical security (asymptotical in the security parameter).

Private function evaluation (PFE) is a special case of secure multi-party computation (MPC), where the function to be computed is known by only one party. PFE is useful in several real-life settings where an algorithm or a function itself needs to remain secret due to its confidential classification or intellectual property. In this work, we look back at the seminal PFE framework presented by Mohassel and Sadeghian at Eurocrypt’13. We show how to adapt and utilize the well-known half gates garbling technique (Zahur et al., Eurocrypt’15) to their constant round 2-party PFE scheme. Compared to their scheme, our resulting optimization considerably improves the efficiency of both the underlying Oblivious Evaluation of Extended Permutation (OEP) and secure 2-party computation (2PC) protocol, and yields a more than 40% reduction in overall communication cost (the computation time is also slightly decreased, and the number of rounds remains unchanged).

The main efficiency metrics for a cryptographic primitive are its speed, its code size and its memory complexity. For a variety of reasons, many algorithms have been proposed that, instead of optimizing, try to increase one of these hardness forms.

We present for the first time a unified framework for describing the hardness of a primitive along any of these three axes: code-hardness, time-hardness and memory-hardness. This unified view allows us to present modular block cipher and sponge constructions which can have any of the three forms of hardness and can be used to build any higher level symmetric primitive: hash function, PRNG, etc.

We also formalize a new concept: asymmetric hardness. It creates two classes of users: common users have to compute a function with a certain hardness while users knowing a secret can compute the same function in a far cheaper way. Functions with such an asymmetric hardness can be directly used in both our modular structures, thus constructing any symmetric primitive with an asymmetric hardness. We also propose the first asymmetrically memory-hard function, DIODON.

As illustrations of our framework, we introduce WHALE and SKIPPER. WHALE is a code-hard hash function which could be used as a key derivation function and SKIPPER is the first asymmetrically time-hard block cipher.

Emerging technologies such as Spin-transfer torque magnetic random-access memory (STT-MRAM) are considered potential candidates for implementing low-power, high density storage systems. The vulnerability of such nonvolatile memory (NVM) based cryptosystems to standard side-channel attacks must be thoroughly assessed before deploying them in practice. In this paper, we outline a generic Correlation Power Analysis (CPA) attack strategy against STT-MRAM based cryptographic designs using a new power model. In our proposed attack methodology, an adversary exploits the power consumption patterns during the write operation of an STT-MRAM based cryptographic implementation to successfully retrieve the secret key. In order to validate our proposed attack technique, we mounted a CPA attack on MICKEY-128 2.0 stream cipher design consisting of STT-MRAM cells with Magnetic Tunnel Junctions (MTJs) as storage elements. The results of the experiments show that the STT-MRAM based implementation of the cipher circuit is susceptible to standard differential power analysis attack strategy provided a suitable hypothetical power model (such as the one proposed in this paper) is selected. In addition, we also investigated the effectiveness of state-of-the-art side-channel attack countermeasures for MRAMs and found that our proposed scheme is able to break such protected implementations as well.

Event date: 30 October to 3 November 2017
Submission deadline: 4 August 2017
Notification: 4 September 2017

Closing date for applications: 6 June 2017

Contact: Professor Steve Schneider

Director of Surrey Centre for Cyber Security

University of Surrey

Guildford

Surrey GU2 7XH

s.schneider (at) surrey.ac.uk

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

The Department of Computing is a leading department of Computer Science among U.K. Universities, and has consistently been awarded the highest research rating. In the 2014 REF assessment, The Department was ranked third (1st in the Research Intensity table published by The Times Higher Education), and was rated as Excellent in the previous national assessment of teaching quality.

Applications are invited for a PhD student broadly interested in the topics of security, privacy, and compilers. Dr. Livshits’ research involves a broad range of topics in application security, privacy, program analysis, general software reliability, and bug finding. Some of the prior work in recent years was in areas as diverse as malware detection and building augmented reality systems. A wide range of specific projects is available, although prospective students are expected to come up with some of the topics they are excited about.

To apply for this position, you will need to have a strong background in at least one of the following areas: security, privacy, compilers, program analysis, programming languages, or operating systems. You will also need some experience in building and working with large software systems and tools. This experience can come from either your academic projects or through working in the industry; candidates with a strong industrial background are encouraged to apply.

Applicants should have a Distinction/First class grade Master’s degree in Computer Science or a related field, and good communication and technical writing skills. The position is fully funded, covering tuition fees, travel funds and a stipend/bursary. The position is available to both EU and overseas students.

Closing date for applications: 31 December 2017

Contact: Dr. Ben Livshits (livshits (at) ic.ac.uk)

https://www.doc.ic.ac.uk/~livshits/

More information: http://www.imperial.ac.uk/computing/prospective-students/courses/phd/scholarships/security-privacy-compilers/

In this paper, we propose a reduction technique that can be used to determine the density of IV terms of a complex multivariable boolean polynomial. Using this technique, we revisit the dynamic cube attack on Grain-128. Based on choosing one more nullified state bit and one more dynamic bit, we are able to obtain the IV terms of degree $43$ with various of complicated reduction techniques for polynomials, so that the nonexistent IV terms can be determined. As a result, we improve the time complexity of the best previous attack on Grain-128 by a factor of $2^{16}$. Moreover, our attack applies to all keys.

A new algorithm for computing $x=a^{-1}\pmod{p^k}$ is introduced. It is based on the exact solution of linear equations using $p$-adic expansions. It starts with the initial value $c=a^{-1}\pmod{p}$ and iteratively computes the digits of the inverse $x=a^{-1}\pmod{p^k}$ in base $p$. The mod 2 version of the algorithm is significantly more efficient than the algorithm given by Duss\'{e} and Kaliski for computing $a^{-1}\pmod{2^k}$.

We develop two IND-CPA-secure multi-hop unidirectional Proxy Re-Encryption (PRE) schemes by applying the Ring-LWE (RLWE) relinearization approach from the homomorphic encryption literature. Unidirectional PRE is ideal for secure publish-subscribe operations where a publisher encrypts information using a public key without knowing upfront who the subscriber will be and what private key will be used for decryption. The proposed PRE schemes provide a multi-hop capability, meaning that when PRE-encrypted information is published onto a PRE-enabled server, the server can either delegate access to specific clients or enable other servers the right to delegate access. Our first scheme (which we call NTRU-ABD-PRE) is based on a variant of the NTRU-RLWE homomorphic encryption scheme. Our second and main PRE scheme (which we call BV-PRE) is built on top of the Brakerski-Vaikuntanathan (BV) homomorphic encryption scheme and relies solely on the RLWE assumption. We present an open-source C++ implementation of both schemes and discuss several algorithmic and software optimizations. We examine parameter selection tradeoffs in the context of security, runtime/latency, throughput, ciphertext expansion, memory usage, and multi-hop capabilities. Our experimental analysis demonstrates that BV-PRE outperforms NTRU-ABD-PRE both in single-hop and multi-hop settings. The BV-PRE scheme has a lower time and space complexity than existing IND-CPA-secure lattice-based PRE schemes, and requires small concrete parameters, making the scheme computationally efficient for use on low-resource embedded systems while still providing 100 bits of security. We present practical recommendations for applying the PRE schemes to several use cases of ad-hoc information sharing for publish-subscribe operations.

In this work we consider the problem of oblivious linear function evaluation (OLE). OLE is a special case of oblivious polynomial evaluation (OPE) and deals with the oblivious evaluation of a linear function $f(x)=ax+b$. This problem is non-trivial in the sense that the sender chooses $a,b$ and the receiver $x$, but the receiver may only learn $f(x)$. We present a highly efficient and UC-secure construction of OLE in the OT-hybrid model that requires only $O(1)$ OTs per OLE. The construction is based on noisy encodings introduced by Naor and Pinkas (STOC'99). Our main technical contribution solves a problem left open in their work, namely we show in a generic way how to achieve full simulation-based security from noisy encodings. All previous constructions using noisy encodings achieve only passive security. Our result requires novel techniques that might be of independent interest.

Using our highly efficient OLE as a black box, we obtain a direct construction of an OPE protocol that simultaneously achieves UC-security and requires only $O(d)$ OTs, where $d$ is the degree of the polynomial that shall be evaluated.

Public key broadcast encryption is a cryptographic method to securely transmit a message from anyone to a group of receivers such that only privileged users can decrypt it. A secure multicast system allows a user to send a message to a dynamically changing group of users. The secure multicast can be realized by the broadcast encryption. In this paper, we propose a novel combinatorial subset difference (CSD) public key broadcast encryption algorithm which allows a generalized subset different representation in which wildcards can be placed at any position. The proposed CSD is applicable to a secure multicast as well as minimizes the header size compared with existing public key broadcast encryption schemes without sacrificing key storage and encryption/decryption performance. Experimental results show that the proposed CSD scheme not only reduces the ciphertext header size by 17% and 31% but also improves encryption performance (per subset) by 6 and 1.3 times, and decryption performance by 10 and 19 times compared with existing efficient subset difference (SD) and interval schemes, respectively. Furthermore, especially for subsets represented in a non-hierarchical manner, the proposed CSD reduces the number of subsets by a factor of 1000 times compared with SD and interval approaches. We prove semantic security of our proposed CSD scheme under l-BDHE assumption without the random oracle model.

In this paper we present SplitCommit, a portable and efficient C++ implementation of the recent additively homomorphic commmitment scheme of Frederiksen et al. [FJNT16]. We describe numerous optimizations that go into engineering such an implementation, including highly optimized general purpose bit-matrix transposition and efficient ECC encoding given the associated generator matrix. We also survey and analyze in detail the applicability of [FJNT16] and include a detailed comparison to the canonical (non-homomorphic) commitment scheme based on a Random Oracle. We include performance benchmarks of the implementation in various network setting, for instance on a 10 Gbps LAN we achieve amortized commitment and decommitment running times of $0.65\mu s$ and $0.27\mu s$, respectively. Finally we also include an extensive tutorial on how to use the library.

Event date: 12 December to 14 December 2017
Submission deadline: 14 July 2017
Notification: 5 September 2017

Designing a secure and open Distributed Ledger (DL) system that performs on par with classic payment-service providers such as Visa is a challenging task. Current proposals either do not scale-out or do so only at the cost of security or decentralization. OmniLedger is a new scalable DL that provides secure, decentralized, horizontal scaling by splitting the state into multiple shards and using distributed randomness to assign validators securely. To maintain intra- and cross-shard consistency validators run a novel parallel consensus algorithm for the former and an Atomic Commit protocol for the latter. To mitigate storage cost and enable fast, secure bootstrapping, OmniLedger introduces compact state-blocks that summarize shard-states.

OmniLedger offers tunable performance based on the assumed strength of the adversaries, and scales linearly with the number of shards. Experiments show that it achieves Visa-level throughput of 6000 transactions per second (peaking at 50000) for 1800 validators, of which up to 12.5% (5%) are assumed to be malicious. Finally, OmniLedger significantly reduces bandwidth cost for out-of-date validators to update: for a one-month-old view, a validator downloads 40% of the amount of data compared to Bitcoin, whereas a new validator downloads only 7% while bootstrapping.

With the synchronous development of both cloud computing and machine learning techniques, the clients are preferring to resort to the cloud server with substantial resources to train learning model. However, in this outsourcing paradigm it is of vital significance to address the privacy concern of client's data. Many researchers have been focusing on preserving the privacy of client's data in learning model. Recently, Wang et al. presented a privacy-preserving single-layer perceptron learning for e-healthcare scheme with using paillier cryptosystem and claimed that their scheme can protect the privacy of user's medical information. By analysing the process of iteration and the communication between the cloud and the user, we present that the honest-but-curious cloud can obtain the private medical information. Besides, the leakage of medical cases will lead to the exposure of the specific single-layer perceptron model of e-healthcare, which has gigantic commercial value.

Finding a short element $g$ of a number field, given the ideal generated by $g$, is a classic problem in computational algebraic number theory. Solving this problem recovers the private key in cryptosystems introduced by Gentry, Smart-Vercauteren, Gentry-Halevi, Garg-Gentry-Halevi, et al. Work over the last few years has shown that for some number fields this problem has a surprisingly low post-quantum security level. This paper shows, and experimentally verifies, that for some number fields this problem has a surprisingly low pre-quantum security level.

For a composite integer $N$ that we would like to factor, we consider a condition for the elliptic curve method using $N$ as a scalar value to succeed and show that if $N$ has a prime factor $p$ such that $p=(DV^2+1)/4,\ V \in {\mathbb Z},\ D\in \{$3, 11, 19, 35, 43, 51, 67, 91, 115, 123, 163, 187, 235, 267, 403, 427$\}$, we can find a non-trivial divisor of $N$ (multiple of $p$) in a short time. In the authors' implementation on PARI/GP, a 1024-bit $N$ was factored in a few seconds when $p$ was 512 bits.

We present a new approach towards constructing round-optimal secure multiparty computation (MPC) protocols against malicious adversaries without trusted setup assumptions. Our approach builds on ideas previously developed in the context of covert multiparty computation [Chandran et al., FOCS'07] even though we do not seek covert security. Using our new approach, we obtain the following results:

1. A five round MPC protocol based on the Decisional Diffie-Hellman (DDH) assumption.

2. A four round MPC protocol based on one-way permutations and sub-exponentially secure DDH. This result is {\em optimal} in the number of rounds.

Previously, no four-round MPC protocol for general functions was known and five-round protocols were only known based on indistinguishability obfuscation (and some additional assumptions) [Garg et al., EUROCRYPT'16].