International Association
for Cryptologic Research

The Department of Information Security and Communication Technology has a vacant tenure-track position as associate professor in cryptology within our Cryptology Discipline.

After six years of standardisation efforts to solicit, evaluate, and standardise one or more quantum-resistant public-key cryptographic algorithms, in the summer of 2022, the National Institute of Standards and Technology (NIST) from the USA has selected a portfolio of several algorithms. Those algorithms will be the new standards for Public-key Encryption and Key-establishment and for Digital Signatures.

We are now entering a phase where those post-quantum cryptographic standards must be efficiently implemented and deployed. The deployment phase faces challenges such as high-performance implementations, protocol updates with the post-quantum primitives, and levels of robustness and trustworthiness.

Duties of the position:

Teaching cryptology, information security and related subjects at undergraduate and graduate level

Developing and maintaining internationally recognized research activity within the area Deployment of Post-Quantum Cryptography

Take part in interdisciplinary research collaborations, both within NTNU and with other national and international partners

Securing research funding from national and international funding agencies

Contribute with developing an innovative course portfolio at the undergraduate and graduate level in cryptology

Educate and supervise students at BSc and MSc level, and supervising PhD and postdoctoral fellowships

Disseminate relevant research to a wider audience (public outreach)

Participate in the management of research, education and other relevant academic activities in agreement with the department

See https://www.jobbnorge.no/en/available-jobs/job/233227/associate-professor-in-post-quantum-cryptography for more details and how to apply.

Closing date for applications:

Contact: Professor Danilo Gligoroski (danilo.gligoroski@ntnu.no)

More information: https://www.jobbnorge.no/en/available-jobs/job/233227/associate-professor-in-post-quantum-cryptography

Fully Homomorphic encryption allows to evaluate any circuits over encrypted data while preserving the privacy of the data.

Another desirable property of FHE called circuit privacy enables to preserve the privacy of the evaluation circuit, i.e. all the information on the bootstrapped ciphertext, including the computation that was performed to obtain it, is destroyed.

In this paper, we show how to directly build a circuit private FHE scheme from TFHE bootstrapping (Asiacrypt 2016). Our proof frame is inspired from the techniques used in Bourse etal (Crypto 2016), we provide a statistical analysis of the error growth during the bootstrapping procedure where we adapt discrete Gaussian lemmata over rings. We make use of a randomized decomposition for the homomorphic external product and introduce a public key encryption scheme with invariance properties on the ciphertexts distribution. As a proof of concept, we provide a C implementation of our sanitization strategy.

We construct the first actively-secure threshold version of the cryptosystem based on class groups from the so-called CL framework (Castagnos and Laguillaumie, 2015). We then show how to use our threshold scheme to achieve general secure multiparty computation (MPC) with only transparent set-up, i.e., with no secret trapdoors involved.

To achieve this, we also design a new zero-knowledge protocol for proving multiplicative relations between encrypted values. As a result, the zero-knowledge proofs needed to get active security add only a constant factor overhead. Finally, we explain how to adapt our protocol for the so called "You-Only-Speak-Once" (YOSO) setting, which is a very promising recent approach for performing MPC over a blockchain.

Predicate encryption (PE) is a type of public-key encryption that captures many useful primitives such as attribute-based encryption (ABE). Although much progress has been made to generically achieve security against chosen-plaintext attacks (CPA) efficiently, in practice, we also require security against chosen-ciphertext attacks (CCA). Because achieving CCA-security on a case-by-case basis is a complicated task, several generic conversion methods have been proposed. However, these conversion methods may incur a significant efficiency trade-off. Notably, for ciphertext-policy ABE, all generic conversion methods provide a significant overhead in the key generation, encryption or decryption algorithm. Additionally, many generic conversion techniques use one-time signatures to achieve authenticity, which are also known to significantly impact the efficiency.

In this work, we present a new approach to achieving CCA-security as generically and efficiently as possible, by splitting the CCA-conversion in two steps. The predicate of the scheme is first extended in a certain way, which is then used to achieve CCA-security generically e.g., by combining it with a hash function. To facilitate the first step efficiently, we also propose a novel predicate-extension transformation for a large class of pairing-based PE---covered by the pair and the predicate encodings frameworks---which incurs only a small constant overhead for all algorithms. In particular, this yields the most efficient generic CCA-conversion for ciphertext-policy ABE.

The proliferation of Decentralised Finance (DeFi) and Decentralised Autonomous Organisations (DAO), which in current form are exposed to front-running of token transactions and proposal voting, demonstrate the need to shield user inputs and internal state from the parties executing smart contracts. In this work we present “Eagle”, an efficient UC-secure protocol which efficiently realises a notion of privacy preserving smart contracts where both the amounts of tokens and the auxiliary data given as input to a contract are kept private from all parties but the one providing the input. Prior proposals realizing privacy preserving smart contracts on public, permissionless blockchains generally offer a limited contract functionality or require a trusted third party to manage private inputs and state. We achieve our results through a combination of secure multi-party computation (MPC) and zero-knowledge proofs on Pedersen commitments. Although other approaches leverage MPC in this setting, these incur impractical computational overheads by requiring the computation of cryptographic primitives within MPC. Our solution achieves security without the need of any cryptographic primitives to be computed inside the MPC instance and only require a constant amount of exponentiations per client input.

The design of FLIP stream cipher presented at Eurocrypt $2016$ motivates the study of Boolean functions with good cryptographic criteria when restricted to subsets of $\mathbb F_2^n$. Since the security of FLIP relies on properties of functions restricted to subsets of constant Hamming weight, called slices, several studies investigate functions with good properties on the slices, i.e. weightwise properties. A major challenge is to build functions balanced on each slice, from which we get the notion of Weightwise Almost Perfectly Balanced (WAPB) functions. Although various constructions of WAPB functions have been exhibited since $2017$, building WAPB functions with high weightwise nonlinearities remains a difficult task. Lower bounds on the weightwise nonlinearities of WAPB functions are known for very few families, and exact values were computed only for functions in at most $16$ variables.

In this article, we introduce and study two new secondary constructions of WAPB functions. This new strategy allows us to bound the weightwise nonlinearities from those of the parent functions, enabling us to produce WAPB functions with high weightwise nonlinearities. As a practical application, we build several novel WAPB functions in up to $16$ variables by taking parent functions from two different known families. Moreover, combining these outputs, we also produce the $16$-variable WAPB function with the highest weightwise nonlinearities known so far.

We provide an expressive framework that allows analyzing and generating provably secure, state-of-the-art Byzantine fault-tolerant (BFT) protocols. Our framework is hierarchical, including three layers. The top layer is used to model the message pattern and abstract key functions on which BFT algorithms can be built. The intermediate layer provides the core functions with high-level properties sufficient to prove the security of the top-layer algorithms. The bottom layer carefully defines predicates according to which we offer operational realizations for the core functions. All three layers in our framework are extensible and enable innovation. One may modify or extend any layer to theoretically cover all BFT protocols, known and unknown. Indeed, unlike prior BFT frameworks, our framework can analyze and recast BFT protocols in an exceedingly fine-grained manner. More importantly, our framework can readily generate new BFT protocols by simply enumerating the parameters in the framework. In this paper, we show that the framework allows us to fully specify and formally prove the security for 23 BFT protocols, including protocols matching HotStuff, Fast-HotStuff, Jolteon, and Marlin, and among these protocols, seven new protocols outperforming existing ones or achieving meaningful trade-offs among various performance metrics.

A ring signature scheme allows a group member to generate a signature on behalf of the whole group, while the verifier can not tell who computed this signature. However, most predecessors do not guarantee security from the secret key leakage of signers. In 2002, Anderson proposed the forward security mechanism to reduce the effect of such leakage. In this paper, we construct the first lattice-based ring signature scheme with forward security. Our scheme combines the binary tree and lattice basis delegation technique to realize a key evolution mechanism, where secret keys are ephemeral and updated with generating nodes in the binary tree. Thus, the adversary cannot forge the past signature even if the users' present secret keys are revealed. Moreover, our scheme can offer unforgeability under standard models. Furthermore, our proposed scheme is expected to realize post-quantum security due to the underlying Short Integer Solution (SIS) problem in lattice-based cryptography.

GGM tree is widely used in the design of correlated oblivious transfer (COT), subfield vector oblivious linear evaluation (sVOLE), distributed point function (DPF), and distributed comparison function (DCF). Often, the cost associated with GGM tree dominates the computation and communication of these protocols. In this paper, we propose a suite of optimizations that can reduce this cost by half.

• Halving the cost of COT and sVOLE. Our COT protocol introduces extra correlation to each level of a GGM tree used by the state-of-the-art COT protocol. As a result, it reduces both the number of AES calls and the communication by half. Extending this idea to sVOLE, we are able to achieve similar improvement with either halved computation or halved communication.

• Halving the cost of DPF and DCF. We propose improved two-party protocols for the distributed generation of DPF/DCF keys. Our tree structures behind these protocols lead to more efficient full-domain evaluation and halve the communication and the round complexity of the state-of-the-art DPF/DCF protocols.

All protocols are provably secure in the random-permutation model and can be accelerated based on fixed-key AES-NI. We also improve the state-of-the-art schemes of puncturable pseudorandom function (PPRF), DPF, and DCF, which are of independent interest in dealer-available scenarios.

Over the last decade, indistinguishability obfuscation (iO) has emerged as a seemingly omnipotent primitive in cryptography. Moreover, recent breakthrough work has demonstrated that iO can be realized from well-founded assumptions. A thorn to all this remarkable progress is a limitation of all known constructions of general-purpose iO: the security reduction incurs a loss that is exponential in the input length of the function. This ``input-length barrier'' to iO stems from the non-falsifiability of the iO definition and is discussed in folklore as being possibly inherent. It has many negative consequences; notably, constructing iO for programs with inputs of unbounded length remains elusive due to this barrier.

We present a new framework aimed towards overcoming the input-length barrier. Our approach relies on short mathematical proofs of functional equivalence of circuits (and Turing machines) to avoid the brute-force ``input-by-input'' check employed in prior works. - We show how to obfuscate circuits that have efficient proofs of equivalence in Propositional Logic with a security loss independent of input length. - Next, we show how to obfuscate Turing machines with unbounded length inputs, whose functional equivalence can be proven in Cook's Theory $PV$. - Finally, we demonstrate applications of our results to succinct non-interactive arguments and witness encryption, and provide guidance on using our techniques for building new applications.

To realize our approach, we depart from prior work and develop a new gate-by-gate obfuscation template that preserves the topology of the input circuit.

Copy-protection is the task of encoding a program into a quantum state to prevent illegal duplications. A line of recent works studied copy-protection schemes under ``1 -> 2 attacks'': the adversary receiving one program copy can not produce two valid copies. However, under most circumstances, vendors need to sell more than one copy of a program and still ensure that no duplicates can be generated. In this work, we initiate the study of collusion resistant copy-protection in the plain model. Our results are twofold:

(*) The feasibility of copy-protecting all watermarkable functionalities is an open question raised by Aaronson et al. (CRYPTO' 21). In the literature, watermarking decryption, digital signature schemes and PRFs have been extensively studied. For the first time, we show that digital signature schemes can be copy-protected. Together with the previous work on copy-protection of decryption and PRFs by Coladangelo et al. (CRYPTO' 21), it suggests that many watermarkable functionalities can be copy-protected, partially answering the above open question by Aaronson et al. (*) We make all the above schemes (copy-protection of decryption, digital signatures, and PRFs) k bounded collusion resistant for any polynomial k, giving the first bounded collusion resistant copy-protection for various functionalities in the plain model.

Currently there exist many blockchains with weak trust guarantees, limiting applications and participation. Existing solutions to boost the trust using a stronger blockchain, e.g., via checkpointing, requires the weaker blockchain to give up sovereignty. In this paper we propose a family of protocols in which multiple blockchains interact to create a combined ledger with boosted trust. We show that even if several of the interacting blockchains cease to provide security guarantees, the combined ledger continues to be secure – our TrustBoost protocols achieve the optimal threshold of tolerating the insecure blockchains. Furthermore, the protocol simply operates via smart contracts and require no change to the underlying consensus protocols of the participating blockchains, a form of “consensus on top of consensus”. The protocols are lightweight and can be used on specific (e.g., high value) transactions; we demonstrate the practicality by implementing and deploying TrustBoost as cross-chain smart contracts in the Cosmos ecosystem using approximately 3,000 lines of Rust code, made available as open source. Our evaluation shows that using 10 Cosmos chains in a local testnet, TrustBoost has a gas cost of roughly $2 with a latency of 2 minutes per request, which is in line with the cost on a high security chain such as Bitcoin or Ethereum.

As the prevalence of quantum computing is growing in leaps and bounds over the past few years, there is an ever-growing need to analyze the symmetric-key ciphers against the upcoming threat. Indeed, we have seen a number of research works dedicated to this. Our work delves into this aspect of block ciphers, with respect to the SPECK family and LowMC family.

The SPECK family received two quantum analysis till date (Jang et al., Applied Sciences, 2020; Anand et al., Indocrypt, 2020). We revisit these two works, and present improved benchmarks SPECK (all 10 variants). Our implementations incur lower full depth compared to the previous works.

On the other hand, the quantum circuit of LowMC was explored earlier in Jaques et al.'s Eurocrypt 2020 paper. However, there is an already known bug in their paper, which we patch. On top of that, we present two versions of LowMC (on L1, L3 and L5 variants) in quantum, both of which incur significantly less full depth than the bug-fixed implementation.

Secure and scalable data sharing is one of the main concerns of the Internet of Things (IoT) ecosystem. In this paper, we introduce a novel blockchain-based data-sharing construction designed to ensure full anonymity for both the users and the data. To share the encrypted IoT data stored on the cloud, users generate tokens, prove their ownership using zk-SNARKs, and anonymously target the destination address. To tackle the privacy concerns arising from uploading the data to the cloud, we use key-private re-encryption and share as little information as possible with the proxy. Furthermore, we provide security proof of our construction.

While hardware implementations allow the production of highly efficient and performance oriented designs, exploiting features such as parallelization, their longer time to code and implement often bottlenecks rapid prototyping. On the other hand, high-level synthesis (HLS) tools allow for faster experimentation of software code to a hardware platform while demonstrating a reasonable extrapolation of the expected hardware behavior. In this work, we attempt to show a rapid, fast prototyping of the well known HQC algorithm, using HLS, and show how with a modification of certain parameters, varying degrees of comparable results can be obtained. These results, in turn, could be used as a guide for HDL-RTL developers to enhance their designs and better prototyping time in the future. Additionally, we also demonstrate that it is possible to benefit from HQC's versatility; by achieving a low hardware footprint whilst also maintaining good performances, even on low-cost FPGA devices, which we demonstrate on the well known Artix-7 xc7a100t-ftg256-1.

Traditional finance quantifies risk by collecting and vetting reputation information for an individual, such as credit scores or payment history. While decentralized finance (DeFi) is an exceptionally well-suited application of permissionless blockchains, it is severely constrained in its ability to reconcile identities and quantify associated transaction risk directly on-chain. Opening the ecosystem to a broad range of use cases requires consistent pseudonymity and quantifiable reputation. This paper defies the status quo: exploring methods of assessing risk on-chain by efficiently integrating off-chain identity- and attribute- verification and on-chain transaction activity. We achieve this while preserving individual privacy within a competitive and fair environment and retaining compatibility with existing platforms such as Ethereum. Even though blockchains are inherently public, our solution gives users control over release of information that pertains to them. Consequently, our contribution focuses on customized methods that balance the degree of disclosure of provably-sourced user information against the likelihood of the user successfully gaining access to a desired resource, such as a loan under suitable terms. Our solution is consistent with the zero-trust model in that it imports explicit trust from recognized sources through relevant metrics that are subject to continuous update.

The proof of work mechanism by which many blockchain-based protocols achieve consensus may be undermined by the use of quantum computing in mining—even when all cryptographic primitives are replaced with post-quantum secure alternatives. First, we offer an impossibility result: we prove that quantum (Grover) speedups in solving a large, natural class of proof-of-work puzzles cause an inevitable incentive incompatibility in mining, by distorting the reward structure of mining in proof-of-work-based protocols such as Bitcoin. We refer to such distortion as the Superlinearity Problem. Our impossibility result suggests that for robust post-quantum proof-of-work-based consensus, we may need to look beyond standard cryptographic models. We thus propose a proof-of-work design in a random-beacon model, which is tailored to bypass the earlier impossibility. We conclude with a discussion of open problems, and of the challenges of integrating our new proof-of-work scheme into decentralised consensus protocols under realistic conditions.

In CT-RSA 2020, P3S was proposed as the first policy-based sanitizable signature scheme which allows the signer to designate future message sanitizers by defining an access policy relative to their attributes rather than their keys. However, since P3S utilizes a policy-based chameleon hash (PCH), it does not achieve unlinkability which is a required notion in privacy-preserving applications. Moreover, P3S requires running a procedure to share the secret trapdoor information for PCH with each new sanitizer before sanitizing a new message. We further observe that in order to maintain the transparency in P3S’s multiple-sanitizers setting, the signature size should grow linearly with the number of sanitizers. In this work, we propose an unlinkable policy-based sanitizable signature scheme (UP3S) where we employ a rerandomizable digital signature scheme and a traceable attribute-based signature scheme as its building blocks. Compared to P3S, UP3S achieves unlinkability, does not require new secrets to be shared with future sanitizers prior to sanitizing each message, and has a fixed signature size for a given sanitization policy. We define and formally prove the security notions of the generic scheme, propose an instantiation of UP3S utilizing the Pointcheval-Sanders rerandomizable signature scheme and DTABS traceable attribute-based signature scheme, and analyze its efficiency. Finally, we compare UP3S with P3S in terms of the features of the procedures, scalability, and security models.

Time-lock puzzles (TLP) are a fascinating type of cryptographic problem that is easy to generate, but takes a certain time to solve, even when arbitrary parallel speedup is allowed. TLPs have wide-ranging applications including fairness, round efficient computation, and more. To reduce the effort needed to solve large numbers of TLPs, prior work has proposed batching techniques to reduce the cost of solving. However, these proposals either require: (1) a trusted setup or (2) the puzzle size linear in the maximum batch size, which implies setting an a priori bound on the maximum size of the batch. Any of these limitations restrict the utility of TLPs in decentralized and dynamic settings like permissionless blockchains.

In this work, we demonstrate the feasibility and usefulness of a TLP that overcomes all of the above limitations. Our construction is based on indistinguishable obfuscation and shows that there are no fundamental barriers in achieving such a TLP construction. As a main application of our TLP, we show how to improve the resilience of consensus protocols toward network-level adversaries in the following two settings: (1) We show a generic compiler that boosts the resilience of a Byzantine broadcast protocol $\Pi$ as follows: if $\Pi$ is secure against $t

The always-available liquidity of automated market makers (AMMs) has been one of the most important catalysts in early cryptocurrency adoption. However, it has become increasingly evident that AMMs in their current form are not viable investment options for passive liquidity providers. This is because of the cost incurred by AMMs providing stale prices to arbitrageurs against external market prices, formalized as loss-versus-rebalancing (LVR) [Milionis et al., 2022].

In this paper, we present Diamond, an automated market making protocol that aligns the incentives of liquidity providers and block producers in the protocol-level retention of LVR. In Diamond, block producers effectively auction the right to capture any arbitrage that exists between the external market price of a Diamond pool, and the price of the pool itself. The proceeds of these auctions are shared by the Diamond pool and block producer in a way that is proven to remain incentive compatible for the block producer. Given the participation of competing arbitrageurs, LVR is effectively prevented in Diamond. We formally prove this result, and detail an implementation of Diamond. We also provide comparative simulations of Diamond to relevant benchmarks, further evidencing the LVR-protection capabilities of Diamond. With this new protection, passive liquidity provision on blockchains becomes rationally viable, beckoning a new age for decentralized finance.