International Association
for Cryptologic Research

The Department of Computer Science at the University of Surrey is looking for a new permanent faculty member at lecturer level. I would appreciate your assistance in bringing this to the attention of outstanding candidates who may be interested in moving to Surrey.

We seek to appoint a lecturer in one or more of the following areas: machine learning, cloud computing, programming-languages principles, and the intersection of security and AI, which are already areas of research within the Department. We are also interested in candidates who have experience in data science, edge networks, social computing and DevOps security, in order to expand our research in new directions.

The Department is renowned for its security and artificial intelligence research, with publications in leading venues in artificial intelligence (TNNLS, TEVC, CBY, TSP, Machine Learning, Neural Computation, Bioinformatics, IJCAI, AAMAS), programming languages (FASE, PODC), security (CCS, S&P, Esorics, Euro S&P, CSF, TDSC, TIFS ), cryptography (Crypto, Eurocrypt), cloud computing and networking (InfoCOM, Trans. Networking), and web & social computing (WWW, ICWSM, and Web Science)

Notably,

we are active within professional organisations, working groups and technical committees of several standardisation bodies, such the IEEE Computational Intelligence Society, ISO, IETF, LoRa Alliance, IEEE Standards WG, ETSI, W3C, and leading the IET WG on e-voting

we host major international conferences such as ESORICS, ACNS, WCCI and GECCO,

we are leading European collaborative research on TPMs

our research on Bio-inspired Swarm Robotics research has been reported by the BBC https://www.bbc.co.uk/programmes/p022brpj and TechXplore https://techxplore.com/news/2020-04-bio-inspired-algorithms-collaborative-behaviors-robot.html

we have worked with the UK Parliament on understanding digital citizen engagement

we have developed methodologies for Enabling Serverless Deployment of Large-Scale AI Workloads

We encourage ambitious post-docs and early career lecturers to apply.

Closing date for applications:

Contact: Professor Helen Treharne, Head of Department, (h.treharne@surrey.ac.uk)

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

Contact tracing is one of the most important interventions to mitigate the spread of COVID-19/SARS-CoV-2. Smartphone-facilitated digital contact tracing may help to increase tracing capabilities as well as extend the coverage to those contacts one does not know in person. The emerging consensus is that a decentralized approach with local Bluetooth Low Energy (BLE) communication to detect contagion-relevant proximity, together with cryptographic protections, is necessary to guarantee the privacy of the users of such a system.

However, current decentralized protocols, including DP3T and the protocol by Canetti, Trachtenberg and Varia, do not sufficiently protect infected users from having their status revealed to their contacts, which may raise fear of stigmatization.

By taking a dual approach, we propose a new and practical solution with stronger privacy guarantees even against active adversaries. In particular, we solve the aforementioned problem with additional pseudorandom warning identities that are associated to the broadcasted public identity, but this association is only known to a non-colluding dedicated server, which does not learn to whom the public identity belongs. Then, only these anonymous warning identities are published.

Moreover, our solution allows warned contacts to prove that they have been in contact with infected users, an important feature in times of restricted testing capacities. Among other additional security measures, we detail how the use of secret sharing can prevent the unnecessary and potentially panic-inducing warning of contacts that have only been around the infected person for a very brief time period.

Multiple protocols implementing exciting cryptographic functionalities using blockchains such as time-lock encryption, one-time programs and fair multi-party computation assume the existence of a cryptographic primitive called extractable witness encryption. Unfortunately, there are no known efficient constructions (or even constructions based on any well studied assumptions) of extractable witness encryption. In this work, we propose a protocol that uses a blockchain itself to provide a functionality that is effectively the same as extractable witness encryption. By making small adjustments to the blockchain code, it is possible to easily implement applications that rely on extractable witness encryption and existed only as theoretical designs until now. There is also potential for new applications. As a key building block, our protocol uses a new and highly efficient batched dynamic proactive secret sharing scheme which may be of independent interest. We provide a proof-of-concept implementation of the extractable witness encryption construction and the underlying dynamic proactive secret sharing protocol.

We propose a new encoding algorithm for the simultaneous differential multidimensional scalar point multiplication algorithm $d$-MUL. Previous encoding algorithms are known to have major drawbacks in their efficient and secure implementation. Some of these drawbacks have been avoided in a recent paper in 2018 at a cost of losing the general functionality of the point multiplication algorithm. In this paper, we address these issues. Our new encoding algorithm takes the binary representations of scalars as input, and constructs a compact binary sequence and a permutation, which explicitly determines a regular sequence of group operations to be performed in $d$-MUL. Our algorithm simply slides windows of size two over the scalars and it is very efficient. As a result, while preserving the full generality of $d$-MUL, we successfully eliminate the recursive integer matrix computations in the originally proposed encoding algorithms. We also expect that our new encoding algorithm will make it easier to implement $d$-MUL in constant time. Our results can be seen as the efficient and full generalization of the one dimensional Montgomery ladder to arbitrary dimension.

The emergence of e-commerce has changed the way people trade. However, merchants are charged high fees for their use of the platform and for payment services. These costs are passed on to customers in the form of higher prices. Blockchain technology can provide lower transaction fees with high security and privacy level but is incapable of delivering the number of transactions per second demanded by real e-commerce. Establishing a layer above the blockchain to manage transactions which we called Blockchain Layer2 technology, has the potential to solve these issues. In this article, we focus on the effect that layer2 technology can provide in reducing fee costs and improving transaction volumes. We introduce the problems that the e-commerce industry is facing currently and how blockchain layer2 technology can help to address these issues. We list and describe the main layer2 mechanisms based on the Bitcoin and Ethereum blockchains. We discuss issues that arise when applying layer 2 technology to e-commerce. We analyse the costs associated with difference e-commerce payment network topologies and investigate the funds-capacity needed to support high levels of value transfer.

ECDSA is a widely adopted digital signature standard. A number of threshold protocols for ECDSA have been developed that let a set of parties jointly generate the secret signing key and compute signatures, without ever revealing the signing key. Threshold protocols for ECDSA have seen recent interest, in particular due to the need for additional security in cryptocurrency wallets where leakage of the signing key is equivalent to an immediate loss of money.

We propose a threshold ECDSA protocol secure against an active adversary in the honest majority model with abort. Our protocol is efficient in terms of both computation and bandwidth usage, and it allows the parties to pre-process parts of the signature, such that once the message to sign becomes known, they can compute a secret sharing of the signature very efficiently, using only local operations. We also show how to obtain fairness in the online phase at the cost of some additional work in the pre-processing, i.e., such that the protocol either aborts during the pre-processing phase, in which case nothing is revealed, or the signature is guaranteed to be delivered to all honest parties.

When designing a classical substitution-permutation network (SPN) permutation, every non-trivial choice of the S-box and of the affine layer provides security after a finite number of rounds. However, this is not necessarily the case for partial SPN (P-SPN) ciphers: Since the nonlinear part does not cover the full state, there may exist highly non-trivial choices of linear layers which, for example, do not provide security against statistical attacks.

Quite surprisingly, this direction has hardly been considered in the literature. For example, LowMC uses different linear layers in each round in order to avoid the problem, but this solution is quite expensive, both computationally and memory-wise. Zorro, another construction with an incomplete nonlinear layer, simply reuses the AES matrix, but this introduces weaknesses.

Working from an attacker's perspective and focusing on P-SPN ciphers, in this paper we present conditions which allow to set up attacks based on infinitely long invariant subspace trails -- even when using highly non-trivial linear layers. We also analyze the case in which the trail is not invariant, yet still an infinite number of rounds can be covered. In this paper, we consider two scenarios, namely active and inactive S-boxes. For the first case, we also provide a tool which is able to determine whether a given linear layer matrix is vulnerable against attacks based on our observations.

Finally, we point out that besides P-SPN ciphers, our results may also have a crucial impact on the HADES design strategy recently presented at Eurocrypt 2020, which mixes rounds with full S-box layers and rounds with partial S-box layers in order to guarantee security and achieve good performance in the target applications.

Recursive proof composition has been shown to lead to powerful primitives such as incrementally-verifiable computation (IVC) and proof-carrying data (PCD). All existing approaches to recursive composition take a succinct non-interactive argument of knowledge (SNARK) and use it to prove a statement about its own verifier. This technique requires that the verifier run in time sublinear in the size of the statement it is checking, a strong requirement that restricts the class of SNARKs from which PCD can be built. This in turn restricts the efficiency and security properties of the resulting scheme.

Bowe, Grigg, and Hopwood (ePrint 2019/1021) outlined how a modified recursive composition may be applied to a particular SNARK construction which does not have a sublinear-time verifier. However, they omit details about this method and do not prove that it satisfies any security property. Nonetheless, schemes based on this idea have already been implemented in software.

In this work we present a collection of results that establish the theoretical foundations for a significant generalization of the above approach. We define an accumulation scheme for a non-interactive argument, and show that this suffices to construct PCD, even if the argument itself does not have a sublinear-time verifier. Moreover we give constructions of accumulation schemes for SNARKs, which yield PCD schemes with novel efficiency and security features.

The surge of interest in decentralization-enabling technologies sparked by the recent success of Bitcoin and other blockchains has led to several new challenges in cryptography and protocol design. One such challenge concerns the widely used digital signature scheme -- ECDSA -- that has in particular been chosen to secure transactions in Bitcoin and several other blockchain systems. To empower decentralized interoperability between such blockchains one would like to implement distributed custody over Bitcoin accounts, which technically can be realized via a threshold ECDSA protocol. Even though several threshold ECDSA protocols already exist, as we argue, due to lack of robustness in signature generation, they are not well suited for deployment scenarios with large committees of parties, out of which a significant fraction might be malicious or prone to DDoS attacks. We propose a new threshold ECDSA protocol that improves upon the state-of-the-art solutions by enabling robustness and fault attributability during signature generation. In addition to that, we improve the signing time and bandwidth of previous solutions by moving expensive operations that are oblivious to the signed message to a separate setup phase.

Collusion-free (CF) and collusion-preserving (CP) protocols offer alternatives to standard multi-party computation (MPC) in settings where subliminal communication is undesirable, e.g., in decentralizing mediators in mediated games. However, all existing solutions make too strong and uninstantiable assumptions on the setups, such as physical presence of the parties, access to physical envelopes and opaque ballot boxes, or extreme isolation, where the only means of communication is a star-topology network among the parties with a special resource, the mediator, at its center---and the mediator needs to be aware of the function to be computed. The above state of affairs remained a limitation of such protocols, which was even reinforced by impossibility results. Thus, for years, it has been unclear if and how the above setup assumptions could be relaxed towards more realistic application scenarios.

In this work we provide the first solution to collusion preserving computation which uses weaker and more common assumptions than the above, i.e., an authenticated broadcast functionality and access to honestly generated trusted hardware tokens. We prove that our protocol is collusion-preserving secure (in short, CP secure) as long as no parties abort. In the case of an aborting adversary our protocol loses CP security, but still achieves standard security---against monolithic adversaries---and additionally identifies a corrupted party.

Leveraging the above identifiability property, we augment our protocol with a collateral and compensation mechanism which ensures that it is not profitable to abort, thereby obtaining CP security against incentive driven adversaries. To define (and prove) this latter result, we combine the Rational Protocol Design (RPD) methodology by Garay et al. [FOCS 2013] with the CP framework of Alwen et al. [CRYPTO 2012] to derive a definition of security in the presence of incentive-driven local adversaries which can be of independent interest.

Similar to existing protocols in the CP/CF literature, our protocols preserve, as a fallback, the traditional security properties---i.e., security against monolithic adversaries---even when the setup (i.e., the hardware tokens) is compromised or corrupted.

ElGamal public key encryption scheme has been designed in the 80’s. It is one of the first partial homomorphic encryption and one of the first IND-CPA probabilistic public key encryption scheme. A linear version has been recently proposed by Boneh et al. In this paper, we present a linear encryption based on a generalized version of ElGamal encryption scheme. We prove that our scheme is IND-CPA secure under the linear assumption. We design a also generalized ElGamal scheme from the generalized linear. We also run an evaluation of performances of our scheme. We show that the decryption algorithm is faster than the existing versions.

Abstract: Rotation operator is frequently used in several stream ciphers, including HC-128, Rabbit, and Salsa20, the final candidates for eSTREAM. This is because ‘Rotation operator (ROT)’ is simple but has very good dispersibility. In this paper, we propose a ‘disperse rotation operator (DRT)’, which has the same structure as ROT but has better dispersibility. In addition, the use of DRT instead of ROT has shown that the quality of the output stream of all three stream ciphers is significantly improved. On the other hand, the use of DRT instead of ROT in HC-128 stream cipher prevents the expansion of differentiated attacks based on LSB.

We close the gap between black-box and non-black-box constructions of $\mathit{composable}$ secure multiparty computation in the plain model under the $\mathit{minimal}$ assumption of semi-honest oblivious transfer. The notion of protocol composition we target is $\mathit{angel\text{-}based}$ security, or more precisely, security with super-polynomial helpers. In this notion, both the simulator and the adversary are given access to an oracle called an $\mathit{angel}$ that can perform some predefined super-polynomial time task. Angel-based security maintains the attractive properties of the universal composition framework while providing meaningful security guarantees in complex environments without having to trust anyone.

Angel-based security can be achieved using non-black-box constructions in $\max(R_{\mathsf{OT}},\widetilde{O}(\log n))$ rounds where $R_{\mathsf{OT}}$ is the round-complexity of the semi-honest oblivious transfer. However, currently, the best known $\mathit{black\text{-}box}$ constructions under the same assumption require $\max(R_{\mathsf{OT}},\widetilde{O}(\log^2 n))$ rounds. If $R_{\mathsf{OT}}$ is a constant, the gap between non-black-box and black-box constructions can be a multiplicative factor $\log n$. We close this gap by presenting a $\max(R_{\mathsf{OT}},\widetilde{O}(\log n))$-round black-box construction. We achieve this result by constructing constant-round 1-1 CCA-secure commitments assuming only black-box access to one-way functions.

Mass surveillance can be more easily achieved leveraging fear and desire of the population to feel protected while affected by devastating events. In such cases governments are more legitimate to adopt exceptional measures that limit civil rights, usually receiving large support from their citizens.

The COVID-19 pandemic is currently affecting the freedom and life style of many citizens in the world. People are forced to stay home for several weeks, unemployment rates quickly increase, uncertainty and sadness generate an impelling desire to join any government effort in order to stop as soon as possible the spread of the virus.

Following recommendations of epidemiologists, governments are proposing the use of smartphone applications to allow automatic contact tracing of citizens. Such systems can be an effective way to defeat the spread of the SARS-CoV-2 virus since they allow to gain time in identifying potentially new infected persons that should therefore be in quarantine. This raises the natural question of whether this form of automatic contact tracing can be a subtle weapon for governments to violate the privacy of their citizens as part of new and more sophisticated mass surveillance programs.

In order to preserve privacy and at the same time to contribute to the containment of the pandemic, several research partnerships are proposing privacy-preserving contact-tracing systems where pseudonyms are updated periodically to avoid linkability attacks. A core component of such systems is Bluetooth low energy (BLE, for short) a technology that allows two smartphones to detect that they are in close proximity. Among such systems there are some proposals like DP-3T, PACT and the Apple&Google exposure notification system that through a decentralized approach guarantee better privacy properties compared to other centralized approaches (e.g., PEPP-PT-NTK, PEPP-PT-ROBERT). On the other hand, advocates of centralized approaches claim that centralization gives to epidemiologists more useful data, therefore allowing to take more effective actions to defeat the virus.

Motivated by Snowden's revelations about previous attempts of governments to realize mass surveillance programs, in this paper we first analyze mass surveillance attacks that leverage weaknesses of automatic contact systems. We focus in particular on the DP-3T system (still our analysis is significant also for PACT and Apple&Google systems) that has been endorsed by Apple&Google. The endorsement has the impact of integrating in the forthcoming update of Android and iOS special features like a synchronous rotation of the BLE MAC address of the smartphone with the update of the pseudonyms of the DP-3T system.

Based on recent literature and new findings, we discuss how a government can exploit the use of DP-3T to successfully mount privacy attacks as part of a mass surveillance program.

Interestingly, we also show that the privacy issues in DP-3T are not intrinsic in any BLE-based contact tracing system. Indeed, we propose a different system named $\textsf{Pronto-C2}$ that, in our view, enjoys a much better resilience with respect to mass surveillance attacks still relying on BLE. $\textsf{Pronto-C2}$ is based on a paradigm shift: instead of asking smartphones to send keys to the Big Brother (this corresponds to the approach of DP-3T), we construct a decentralized BLE-based ACT system where smartphones anonymously and confidentially talk to each other in the presence of the Big Brother.

$\textsf{Pronto-C2}$ can optionally be implemented using Blockchain technology, offering complete transparency and resilience through full decentralization, therefore being more appealing for citizens. Only through a large participation of citizens contact-tracing systems can be very useful to defeat COVID-19, and our proposal goes straight in this direction.

Building on the protocol of Gennaro and Goldfeder (CCS ’18), we present a threshold ECDSA protocol,for any number of signatories and any threshold, that improves as follows over the state of the art:

* Signature generation takes only 4 rounds (down from the current 8 rounds), with a comparable computational cost. Furthermore, 3 of these rounds can take place in a preprocessing stage before the signed message is known, lending to the first non-interactive threshold ECDSA protocol.

* The protocol withstands adaptive corruption of signatories. Furthermore, it includes a periodic refresh mechanism and offers full proactive security.

* The protocol realizes an ideal threshold signature functionality within the UC framework, in the global random oracle model, assuming Strong RSA, semantic security of Paillier encryption, and a somewhat enhanced variant of existential unforgeability of ECDSA.

These properties (low latency, compatibility with cold-wallet architectures, proactive security, and composable security) make the protocol ideal for threshold wallets for ECDSA-based cryptocurrencies.

We propose a leveled homomorphic encryption scheme based on the Approximate Greatest Common Divisor (AGCD) problem that operates natively on vectors and matrices. To overcome the limitation of large ciphertext expansion that is typical in AGCD-based schemes, we randomize the ciphertexts with a hidden matrix, which allows us to choose smaller parameters. To be able to efficiently evaluate circuits with large multiplicative depth, we use a decomposition technique à la GSW. The running times and ciphertext sizes are practical: for instance, for 100 bits of security, we can perform a sequence of 128 homomorphic products between 128-dimensional vectors and $128\times 128$ matrices in less than one second. We show how to use our scheme to homomorphically evaluate nondeterministic finite automata and also a Naïve Bayes Classifier. We also present a generalization of the GCD attacks against the some variants of the AGCD problem.

Since David Chaum introduced the idea of mix nets 40 years ago, they have become widely used building blocks for privacy-preserving protocols. Several important applications, such as secure e-voting, require that the employed mix net be verifiable. In the literature, numerous techniques have been proposed to make mix nets verifiable. Some of them have also been employed in politically binding elections.

Verifiable mix nets differ in many aspects, including their precise verifiability levels, possible trust assumptions, and required cryptographic primitives; unfortunately, these differences are often opaque, making comparison painful.

To shed light on this intransparent state of affairs, we provide the following contributions. For each verifiability technique proposed to date, we first precisely describe how the underlying basic mix net is to be extended and which (additional) cryptographic primitives are required, and then study its verifiability level, including possible trust assumptions, within one generic and expressive verifiability framework. Based on our uniform treatment, we are able to transparently compare all known verifiability techniques for mix nets, including their advantages and limitations.

Altogether, our work offers a detailed and expressive reference point for the design, employment, and comparison of verifiable mix nets.

In this paper, we review different approaches on proximity tracing apps which are supposed to automate the current labor-intensive contact tracing approach conducted by national health officials. The purpose of these apps is to automatically notify people who are at risk of being infected with SARS-CoV-2 to interrupt infection chains as early as possible. However, a privacy-preserving and yet functional and scalable design of such apps is not trivial and in some parts leads to counter-intuitive properties. This paper reviews the most prominent European approaches, DP-3T, the German variant "NTK"' of PEPP-PT, and its closely related concept ROBERT. We discuss their design decisions from a privacy perspective and point out the fundamentally different adversary models assumed by the approaches. In addition, we touch on practical aspects such as scalability and ease of implementation.

Since Cheon et al. introduced an approximate homomorphic encryption scheme for complex numbers called Cheon-Kim-Kim-Song (CKKS) scheme, it has been widely used and applied in real-life situations, such as privacy-preserving machine learning. The polynomial approximation of a modulus reduction is the most difficult part of the bootstrapping for the CKKS scheme. In this paper, we cast the problem of finding an approximate polynomial for a modulus reduction into an L2-norm minimization problem. As a result, we find an approximate polynomial for the modulus reduction without using the sine function, which is the upper bound for the approximation of the modulus reduction. With the proposed method, we can reduce the degree of the polynomial required for an approximate modulus reduction, while also reducing the error compared with the most recent result reported by Han et al. (CT-RSA' 20). Consequently, we can achieve a low-error approximation, such that the maximum error is less than $2^{-40}$ for the size of the message $m/q\approx 2^{-10}$. By using the proposed method, the constraint of $q = O(m^{3/2})$ is relaxed as $O(m)$, and thus the level loss in bootstrapping can be reduced. The solution of the cast problem is determined in an efficient manner without iteration.

Motivated by recent results on solving large batches of closest vector problem (CVP) instances, we study how these techniques can be combined with lattice enumeration to obtain faster methods for solving the shortest vector problem (SVP) on high-dimensional lattices.

Theoretically, under common heuristic assumptions we show how to solve SVP in dimension $d$ with a cost proportional to running a sieve in dimension $d - \Theta(d / \log d)$, resulting in a $2^{\Theta(d / \log d)}$ speedup and memory reduction compared to running a full sieve. Combined with techniques from [Ducas, Eurocrypt 2018] we can asymptotically get a total of $[\log(13/9) + o(1)] \cdot d / \log d$ dimensions \textit{for free} for solving SVP.

Practically, the main obstacles for observing a speedup in moderate dimensions appear to be that the leading constant in the $\Theta(d / \log d)$ term is rather small; that the overhead of the (batched) slicer may be large; and that competitive enumeration algorithms heavily rely on aggressive pruning techniques, which appear to be incompatible with our algorithms. These obstacles prevented this asymptotic speedup (compared to full sieving) from being observed in our experiments. However, it could be expected to become visible once optimized CVPP techniques are used in higher dimensional experiments.