International Association
for Cryptologic Research

Blockchain has the potential to accelerate the worldwide deployment of an emissions trading system (ETS) and improve the efficiency of existing systems. In this paper, we present a model for a permissioned blockchain implementation based on the successful European Union (EU) ETS and discuss its potential advantages over existing technology. The proposed ETS model is both backward compatible and future-proof, characterised by interconnectedness, transparency, tamper-resistance and continuous liquidity. Further, we identify key challenges to implementation of blockchain in ETS, as well as areas of future work required to enable a fully decentralised blockchain-based ETS.

Revocable identity-based encryption (RIBE) is an extension of identity-based encryption (IBE) and it supports efficient revocation of private keys. In the past, many efficient RIBE schemes have been proposed, but research on efficiently delegating the generation of update keys to a cloud server is somewhat insufficient. In this paper, we newly introduce the concept of delegated RIBE (DRIBE) that can delegate the generation of update keys to the cloud server and define the security models of DRIBE. Next, we propose a DRIBE scheme by generically combining a hierarchical IBE (HIBE) scheme, an identity-based broadcast encryption (IBBE) scheme, and a collision-resistant hash function. In addition, we propose a DRIBE-INC scheme that generates an occasional base update key and a periodic incremental update key to reduce the size of the update key in our DRIBE scheme.

A cryptographic protocol (CP) is a distributed algorithm designed to provide a secure communication in an insecure environment. CPs are used, for example, in electronic payments, electronic voting procedures, database access systems, etc. Errors in the CPs can lead to great financial and social damage, therefore it is necessary to use mathematical methods to justify the correctness and safety of the CPs. In this paper, a new mathematical model of a CP is introduced, which allows one to describe both the CPs and their properties. It is shown how, on the basis of this model, it is possible to solve the problems of verification of CPs.

Super-spreader events where one person infects many others have been a driving force of the Covid-19 pandemic. Such events often happen indoors, such as in restaurants, at choir practice or in gyms. Many systems for automated contact tracing (ACT) have been proposed, which will warn a user when they have been in proximity to an infected person. These generally fail to detect potential super-spreader events as only users who have come in close contact with the infected person, but not others who also visited the same location, are warned. Other approaches allow users to check into locations or venues, but these require user interaction.

We propose two designs how broadcast-based ACT systems can be enhanced to utilize location-specific information without the need for GPS traces or scanning of QR codes. This makes it possible to alert attendees of a potential super-spreader event while still remaining private. Our first design relies on cooperating lighthouses which cover a large area and send out pseudonyms. These are recorded by visitors and published by the health authority (HA) in case of an infection. The second design has lighthouses actively communicating with HAs after retrospectively detecting an infected visitor to warn everyone whose stay overlapped.

The advent of quantum computers is a threat to most currently deployed cryptographic primitives. Among these, zero-knowledge proofs play an important role, due to their numerous applications. The primitives and protocols presented in this work base their security on the difficulty of solving the Rank Syndrome Decoding (RSD) problem. This problem is believed to be hard even in the quantum model. We first present a perfectly binding commitment scheme. Using this scheme, we are able to build an interactive zero-knowledge proof to prove: the knowledge of a valid opening of a committed value, and that the valid openings of three committed values satisfy a given linear relation, and, more generally, any bitwise relation. With the above protocols it becomes possible to prove the relation of two committed values for an arbitrary circuit, with quasi-linear communication complexity and a soundness error of 2/3. To our knowledge, this is the first quantum resistant zero-knowledge protocol for arbitrary circuits based on the RSD problem. An important contribution of this work is the selection of a set of parameters, and an a full implementation, both for our proposal in the rank metric and for the original LPN based one by Jain et. al in the Hamming metric, from which we took the inspiration. Beside demonstrating the practicality of both constructions, we provide evidence of the convenience of rank metric, by reporting performance benchmarks and a detailed comparison.

We investigate the round complexity of maliciously-secure two-party quantum computation (2PQC) with setup, and obtain the following results:

∙ A three-message protocol (two-message if only one party receives output) in the common random string (CRS) model assuming classical two-message oblivious transfer (OT) with post-quantum malicious security. This round complexity is optimal for the sequential communication setting. Under the additional assumption of reusable malicious designated-verifier non-interactive zero-knowledge (MDV-NIZK) arguments for NP, our techniques give an MDV-NIZK for QMA. Each of the assumptions mentioned above is known from the quantum hardness of learning with errors (QLWE).

∙ A protocol with two simultaneous rounds of communication, in a quantum preprocessing model, assuming sub-exponential QLWE. In fact, we construct a three-round protocol in the CRS model with only two rounds of online communication, which implies the above result. Along the way, we develop a new delayed simulation technique that we call “simulation via teleportation,” which may be useful in other settings.

In addition, we perform a preliminary investigation into barriers and possible approaches for two-round 2PQC in the CRS model, including an impossibility result for a natural class of simulators, and a proof-of-concept construction from a strong form of quantum virtual black-box (VBB) obfuscation.

Prior to our work, maliciously-secure 2PQC required round complexity linear in the size of the quantum circuit.

Most state machine replication protocols are either based on the 40-years-old Byzantine Fault Tolerance (BFT) theory or the more recent Nakamoto’s longest chain design. Longest chain protocols, designed originally in the Proof-of-Work (PoW) setting, are available under dynamic participation, but has probabilistic confirmation with long latency dependent on the security parameter. BFT protocols, designed for the permissioned setting, has fast deterministic confirmation, but assume a fixed number of nodes always online. We present a new construction which combines a longest chain protocol and a BFT protocol to get the best of both worlds. Using this construction, we design TaiJi, the first dynamically available PoW protocol which has almost deterministic confirmation with latency independent of the security parameter. In contrast to previous hybrid approaches which use a single longest chain to sample participants to run a BFT protocol, our native PoW construction uses many independent longest chains to sample propose actions and vote actions for the BFT protocol. This design enables TaiJi to inherit the full dynamic availability of Bitcoin, as well as its full unpredictability, making it secure against fully-adaptive adversaries with up to 50% of online hash power.

In the universal blind quantum computation problem, a client wants to make use of a single quantum server to evaluate $C|0\rangle$ where $C$ is an arbitrary quantum circuit while keeping $C$ secret. The client's goal is to use as few resources as possible. This problem, first raised by Broadbent, Fitzsimons and Kashefi [FOCS09, arXiv:0807.4154], has become fundamental to the study of quantum cryptography, not only because of its own importance, but also because it provides a testbed for new techniques that can be later applied to related problems (for example, quantum computation verification). Known protocols on this problem are mainly either information-theoretically (IT) secure or based on trapdoor assumptions (public key encryptions). In this paper we study how the availability of symmetric-key primitives, modeled by a random oracle, changes the complexity of universal blind quantum computation. We give a new universal blind quantum computation protocol. Similar to previous works on IT-secure protocols (for example, BFK [FOCS09, arXiv:0807.4154]), our protocol can be divided into two phases. In the first phase the client prepares some quantum gadgets with relatively simple quantum gates and sends them to the server, and in the second phase the client is entirely classical -- it does not even need quantum storage. Crucially, the protocol's first phase is succinct, that is, its complexity is independent of the circuit size. Given the security parameter $\kappa$, its complexity is only a fixed polynomial of $\kappa$, and can be used to evaluate any circuit (or several circuits) of size up to a subexponential of $\kappa$. In contrast, known schemes either require the client to perform quantum computations that scale with the size of the circuit [FOCS09, arXiv:0807.4154], or require trapdoor assumptions [Mahadev, FOCS18, arXiv:1708.02130].

Cloud auditing with ownership transfer is a provable data possession scheme meeting verifiability and transferability simultaneously. In particular, not only cloud data can be transferred to other cloud clients, but also tags for integrity verification can be transferred to new data owners. More concretely, it requires that tags belonging to the old owner can be transformed into that of the new owner by replacing the secret key for tag generation while verifiability still remains. We found that existing solutions are less efficient due to the huge communication overhead linear with the number of tags. In this paper, we propose a secure auditing protocol with efficient ownership transfer for cloud data. Specifically, we sharply reduce the communication overhead produced by ownership transfer to be independent of the number of tags, making it with a constant size. Meanwhile, the computational cost during this process on both transfer parties is constant as well.

The Learning with Errors (LWE) problem is one of the main mathematical foundations of post-quantum cryptography. One of the main groups of algorithms for solving LWE is the Blum-Kalai-Wasserman (BKW) algorithm. This paper presents new improvements for BKW-style algorithms for solving LWE instances. We target minimum concrete complexity and we introduce a new reduction step where we partially reduce the last position in an iteration and finish the reduction in the next iteration, allowing non-integer step sizes. We also introduce a new procedure in the secret recovery by mapping the problem to binary problems and applying the Fast Walsh Hadamard Transform. The complexity of the resulting algorithm compares favourably to all other previous approaches, including lattice sieving. We additionally show the steps of implementing the approach for large LWE problem instances. The core idea here is to overcome RAM limitations by using large file-based memory.

Sharding is an approach to designing a highly scalable blockchain. A sharded blockchain achieves parallelism by dividing consensus nodes (validators) into groups called shards and making them process different transactions in each shard. In this paper, we economically analyze users’ behavior on sharded blockchains and identify a phenomenon that users’ accounts and smart contracts eventually get concentrated in a few shards, making shard loads unfair. This phenomenon leads to bad user experiences, such as delays in transaction inclusions and increased transaction fees. To solve the above problem, we propose a load balancing framework in sharded blockchains in which accounts and contracts are frequently reassigned into shards to reduce the difference of loads between shards. We formulate the contract reassignment as an optimization problem and present the algorithm to solve it. Further, we apply the framework to an existing sharding design (Ethereum 2.0) and modify the protocol to do load balancing. Finally, we simulate the protocol and observe smaller transaction delays and fees.

Recently, Kumar and Chand proposed an anonymous authentication protocol for wireless body area network. They claimed that their scheme meets major security requirements and is able to resist known attacks. However, in this paper we demonstrate that their scheme is prone to traceability attack. Followed by this attack, an attacker can launch a man-in-the-middle attack and share a session key with the victim node, and hence the scheme does not achieve secure authentication. Also, we show that this protocol does not provide perfect forward secrecy which considered as a key security property in the design of any secure key agreement protocol.

A recent result by Dulek et al. (EUROCRYPT 2020) showed a secure protocol for computing any quantum circuit even without the presence of an honest majority. Their protocol, however, is susceptible to a ``denial of service'' attack and allows even a single corrupted party to force an abort. We propose the first quantum protocol that admits security-with-identifiable-abort, which allows the honest parties to agree on the identity of a corrupted party in case of an abort. Additionally, our protocol is the first to have the property that the number of rounds where quantum communication is required is independent of the circuit complexity. Furthermore, if there exists a post-quantum secure classical protocol whose round complexity is independent of the circuit complexity, then our protocol has this property as well. Our protocol is secure under the assumption that classical fully homomorphic encryptions schemes exist.

In this article, we analyze and investigate two authenticated encryption algorithms: GIFT-COFB and HyENA. The two modes differ in some low levels details in both the design and security proofs. However, they share a lot of similarities. We take a look at the best-known attacks and security proofs of these designs. We show that the best-known attack is not a matching attack to the security bounds provided by the designers in the security proof. Second, we give a new attack that we characterize as an {\it "almost matching"} attack. It is significantly closer to the provable security bounds. The new attack requires $O(2^{n/4})$ encryptions and $O(2^{n/2})$ decryptions, as opposed to $O(2^{n/2})$ encryptions and $O(2^{n/2})$ decryptions shown previously. However, there is still a substantial logarithmic gap between this attack and the corresponding security bound. Next, we analyze why this gap still exists and why it is unlikely to find matching attacks. We give two arguments. The first argument is by analyzing the security proof and showing how it masks a term with non-negligible encryption complexity. The second argument looks at the attacker's point of view. A successful attack requires satisfying a non-trivial linear equation over secret random variables. Satisfying such an equation requires more decryption queries than what is bounded by the security proof. It is worth emphasizing that the analysis and attacks presented in this paper {\it do not} threaten the security claims made by the designers or the security of these designs within the parameters required by the NIST lightweight cryptography project. The results increase confidence in the security claims of GIFT-COFB and HyENA while showing their limitations by relying mostly on bounding the number of unsuccessful forgeries.

The Covid-19 pandemic created various new challenges for our societies. Quickly discovering new infections using automated contact tracing without endangering privacy of the general public is one of these. Most discussions concerning architectures for contact tracing applications revolved around centralized against decentralized approaches. In contrast, the system proposed in this work builds on the idea of message-based contact tracing to inform users of their risk. Our main contribution is the combination of a blind-signature approach to verify infections with an anonymous postbox service. In our evaluation we analyze all components in our system for performance and privacy, as well as security. We derive parameters for operating our system in a pandemic scenario.

The Cyber Science Lab at the School of Computer Science, University of Guelph, Canada, has two fully funded PhD positions in Cybersecurity. The Cyber Science Lab is a research lab focused on advancing knowledge and practice in AI for Security and Security of AI systems. There are also many opportunities to work on industry projects in the lab. Normally PhD students work on two industry projects during their study and can make an additional 30,000 CAD/year through industry projects. For more details see https://cybersciencelab.org/open-phd-positions

Closing date for applications:

Contact: Ali Dehghantanha (ali@cybersciencelab.org) or Khodakhast Bibak (bibakk@miamioh.edu).

The Cyber Science Lab at the School of Computer Science, University of Guelph, Canada, is looking for a Postdoctoral Research Fellow in Security of AI/ML systems. Strong applicants in other areas of Cybersecurity may also be considered. The initial appointment would be for one year and can be extended for another year. Salary will be in the range of $60,000 to $75,000 a year commensurate with experience, and extended health coverage is also provided. Candidates with strong track of publication or previous postdoc experience are normally receiving higher salaries. For more details see https://cybersciencelab.org/open-positions.

Closing date for applications:

Contact: Ali Dehghantanha (ali@cybersciencelab.org) or Khodakhast Bibak (bibakk@miamioh.edu).

There are two Ph.D. positions opening at Dr. Jiafeng Harvest Xie's research group at the Department of Electrical and Computer Engineering of Villanova University, Villanova, PA (west of Philadelphia), USA. The research topics of this position primarily focused on fault attack/detection related to the AI system and post-quantum cryptosystems. Interested ones are warmly welcomed to send their resume/CV to Dr. Xie through email: jiafeng.xie@villanova.edu

Requirements: preferred to be at the majors of Computer Science, Computer Engineering, Electrical Engineering and related others. Familiar with fault attack and analysis will be desirable. Proficiency in programming languages such as C/C++ and HDLs. Good at English communication and writing. Great enthusiasm of doing research oriented tasks. Excellent team work member.

Degree: both B.S. and M.S. graduates or similar are warmly welcomed to apply.

Start date: Spring 2021 and Fall 2021 are both ok. It is always better to apply as early as possible. Positions are open until they are filled.

The 2021 U.S. News & World Report ranks Villanova as tied for the 53th best National University in the U.S.

Brief introduction of Dr. Xie: Dr. Jiafeng Harvest Xie is currently an Assistant Professor at the Department of Electrical and Computer Engineering of Villanova University. His research interests include cryptographic engineering, hardware security, and VLSI digital design. He is the Best Paper Awardee of IEEE HOST 2019. He has served the Associate Editor for Microelectronics Journal, IEEE Access, and IEEE Trans. Circuits and Systems II. He has also been awarded the 2019 IEEE Access Outstanding Associate Editor.

Contact: Jiafeng Harvest Xie (jiafeng.xie@villanova.edu)

Closing date for applications:

Contact: Jiafeng Harvest Xie

The modular squaring operation has attracted significant attention due to its potential in constructing cryptographic time-lock puzzles and verifiable delay functions. In such applications, it is important to understand precisely how quickly a modular squaring operation can be computed, even in parallel on dedicated hardware.

We use tools from circuit complexity and number theory to prove concrete numerical lower bounds for squaring on a parallel machine, yielding nontrivial results for practical input bitlengths. For example, for $n=2048$, we prove that every logic circuit (over AND, OR, NAND, NOR gates of fan-in two) computing modular squaring on all $n$-bit inputs (and any modulus that is at least $2^{n-1}$) requires depth (critical path length) at least $12$. By a careful analysis of certain exponential Gauss sums related to the low-order bit of modular squaring, we also extend our results to the average case. For example, our results imply that every logic circuit (over any fan-in two basis) computing modular squaring on at least $76\%$ of all $2048$-bit inputs (for any RSA modulus that is at least $2^{n-1}$) requires depth at least $9$.

We present MAGIC, a mode for authenticated encryption that simultaneously supports encryption, message authentication and error correction, all with the same code. In MAGIC, the same code employed for cryptographic integrity is also the parity used for error correction. To correct errors, MAGIC employs the Galois Hash transformation, which due to its bit linearity can perform corrections in a similar way as other codes do (e.g., Reed Solomon). To provide a cryptographically strong MAC, MAGIC encrypts the output of the Galois Hash using a secret key. To analyze the security of this construction we adapt the definition of the MAC adversary so that it is applicable to systems that combine message authentication with error correction. We demonstrate that MAGIC offers security in the order of O(2^(N/2)) with N being the tag size.