International Association
for Cryptologic Research

URL shorteners are a common online service that allows the shortening of a long URL (often a Google Maps URL or similar) into a much shorter one, to use for example on social media or in QR codes. However, URL shorteners are free to behave dishonestly: they can, for instance, map a short URL into a long URL honestly for one party, while redirecting some other party into a different malicious long URL for the same short URL.

DuckyZip is the first provably honest URL shortening service which cannot selectively provide different "long URLs" to different parties undetected. DuckyZip uses a combination of Verifiable Random Function (VRF) constructions and a smart contract in order to provide a URL shortening service with strong security guarantees: despite the transparency of the smart contract log, observers cannot feasibly create a mapping of all short URLs to long URLs that is faster than classical enumeration.

Although power LEDs have been integrated in various devices that perform cryptographic operations for decades, the cryptanalysis risk they pose has not yet been investigated. In this paper, we present optical cryptanalysis, a new form of cryptanalytic side-channel attack, in which secret keys are extracted by using a photodiode to measure the light emitted by a device’s power LED and analyzing subtle fluctuations in the light intensity during cryptographic operations. We analyze the optical leakage of power LEDs of various consumer devices and the factors that affect the optical SNR. We then demonstrate end-to-end optical cryptanalytic attacks against a range of consumer devices (smartphone, smartcard, and Raspberry Pi, along with their USB peripherals) and recover secret keys (RSA, ECDSA, SIKE) from prior and recent versions of popular cryptographic libraries (GnuPG, Libgcrypt, PQCrypto-SIDH) from a maximum distance of 25 meters

Most succinct arguments (SNARKs) are initially only proven knowledge sound (KS). We show that the commonly employed compilation strategy from polynomial interactive oracle proofs (PIOP) via polynomial commitments to knowledge sound SNARKS actually also achieves other desirable properties: weak unique response (WUR) and trapdoorless zero-knowledge (TLZK); and that together they imply simulation extractability (SIM-EXT).

The factoring of SIM-EXT into KS + WUR + TLZK is becoming a cornerstone of the analysis of non-malleable SNARK systems. We show how to prove WUR and TLZK for PIOP compiled SNARKs under mild falsifiable assumptions on the polynomial commitment scheme. This means that the analysis of knowledge soundness from PIOP properties that inherently relies on non-falsifiable or idealized assumption such as the algebraic group model (AGM) or generic group model (GGM) need not be repeated.

While the proof of WUR requires only mild assumptions on the PIOP, TLZK is a different matter. As perfectly hiding polynomial commitments sometimes come at a substantial performance premium, SNARK designers prefer to employ deterministic commitments with some leakage. This results in the need for a stronger zero-knowledge property for the PIOP.

The modularity of our approach implies that any analysis improvements, e.g. in terms of tightness, credibility of the knowledge assumption and model of the KS analysis, or the precision of capturing real-world optimizations for TLZK also benefits the SIM-EXT guarantees.

In this paper, we provide a systematic treatment for the batch arithmetic circuit satisfiability and evaluation problem. Building on the core idea which treats circuit inputs/outputs as a low-degree polynomials, we explore various interactive argument and proof schemes that can produce succinct proofs with short verification time. In particular, for the batch satisfiability problem, we provide a construction of succinct interactive argument of knowledge for generic log-space uniform circuits based on the bilinear pairing and common reference string assumption. Our argument has size in $O(poly(\lambda) \cdot (|\mathbf{w}| + d \log |C|))$, where $\lambda$ is the security parameter, $|\mathbf{w}|$ is the size of the witness, and $d$ and $|C|$ are the depth and size of the circuit, respectively. Note that the argument size is independent of the batch size. To the best of our knowledge, asymptotically it is the smallest among all known batch argument schemes that allow public verification. The batch satisfiablity problem simplifies to a batch evaluation problem when the circuit only takes in public inputs (i.e., no witness). For the evaluation problem, we construct statistically sound interactive proofs for various special yet highly important types of circuits, including linear circuits, and circuits representing sum of polynomials. Our proposed protocols are able to achieve proof sizes independent of the batch size. We also describe protocols optimized specifically for batch FFT and batch matrix multiplication which achieve desirable properties, including lower prover time and better composability. We believe these protocols are of interest in their own right and can be used as primitives in more complex applications.

We show that the key agreement scheme [IEEE Internet Things J., 9(12), 2022, 9918--9933] is flawed. In order to authenticate each other, all participants use message authentication code (MAC) to generate tags for exchanged data. But MAC is a cryptographic technique which requires that the sender and receiver share a symmetric key. The scheme tries to establish a new shared key by using an old shared key, which results in a vicious circle. To the best of our knowledge, it is the first time to discuss such a flaw in the related literatures.

We prove that the problem of decoding a quasi-cyclic code is NPhard, and the corresponding decision problem is NP-complete. Our proof is based on a new characterization of quasi-cyclic codes closely related to linear random codes. We also discuss the cryptographic significance of this result.

We design DiStefano: an efficient framework for generating private commitments over TLS-encrypted web traffic for a designated, untrusted third-party. DiStefano provides many improvements over previous TLS commitment systems, including: a modular security model that is applicable to TLS 1.3 traffic, and support for generating verifiable claims using applicable zero-knowledge systems; inherent 1-out-of-n privacy for the TLS server that the client communicates with; and various cryptographic optimisations to ensure fast online performance of the TLS session. We build an open-source implementation of DiStefano integrated into the BoringSSL cryptographic library, that is used within Chromium-based Internet browsers. We show that DiStefano is practical for committing to facts in arbitrary TLS traffic, with online times that are comparable with existing TLS 1.2 solutions. We also make improvements to certain cryptographic primitives used inside DiStefano, leading to 3x and 2x improvements in online computation time and bandwidth in specific situations.

We show that every language in NP has an Interactive Oracle Proof (IOP) with inverse polynomial soundness error and small query complexity. This achieves parameters that surpass all previously known PCPs and IOPs. Specifically, we construct an IOP with perfect completeness, soundness error $1/n$, round complexity $O(\log \log n)$, proof length $poly(n)$ over an alphabet of size $O(n)$, and query complexity $O(\log \log n)$. This is a step forward in the quest to establish the sliding-scale conjecture for IOPs (which would additionally require query complexity $O(1)$).

Our main technical contribution is a high-soundness small-query proximity test for the Reed-Solomon code. We construct an IOP of proximity for Reed-Solomon codes, over a field $\mathbb{F}$ with evaluation domain $L$ and degree $d$, with perfect completeness, soundness error (roughly) $\max\{1-\delta , O(\rho^{1/4})\}$ for $\delta$-far functions, round complexity $O(\log \log d)$, proof length $O(|L|/\rho)$ over $\mathbb{F}$, and query complexity $O(\log \log d)$; here $\rho = (d+1)/|L|$ is the code rate. En route, we obtain a new high-soundness proximity test for bivariate Reed-Muller codes.

The IOP for NP is then obtained via a high-soundness reduction from NP to Reed-Solomon proximity testing with rate $\rho = 1/poly(n)$ and distance $\delta = 1-1/poly(n)$ (and applying our proximity test). Our constructions are direct and efficient, and hold the potential for practical realizations that would improve the state-of-the-art in real-world applications of IOPs.

Maximal extractable value (MEV) in the context of blockchains and cryptocurrencies refers to the highest potential profit that an actor, particularly a miner or validator, can achieve through their ability to include, exclude, or re-order transactions within the blocks. MEV has become a topic of concern within the Web3 community as it impacts the fairness and security of the cryptocurrency ecosystem. In this work, we propose and explore techniques that utilize randomized permutations to shuffle the order of transactions of a committed block before they are executed. We also show that existing MEV mitigation approaches using an encrypted mempool can be readily extended by permutation-based techniques, thus providing multi-layer protection. With a focus on BFT consensus, we then propose BlindPerm, a framework enhancing an encrypted mempool with permutation at essentially no additional overheads and present various optimizations. Finally, we demonstrate how to extend our mitigation technique to support PoW longest-chain consensus protocols.

During the pandemic, the limited functionality of existing privacy-preserving contact tracing systems highlights the need for new designs. Wang et al. proposed an environmental-adaptive framework (CSS '21) but failed to formalize the security. The similarity between their framework and attribute-based credentials (ABC) inspires us to reconsider contact tracing from the perspective of ABC schemes. In such schemes, users can obtain credentials on attributes from issuers and prove the credentials anonymously (i.e., hiding sensitive information of both user and issuer). This work first extends ABC schemes with auditability, which enables designated auditing authorities to revoke the anonymity of particular issuers. We show a concrete construction by adding a DDH-based ``auditable public key'' mechanism to the Connolly et al.'s ABC scheme (PKC '22). In this work we present three contributions regarding the auditable ABC: (1) we refine the environmental-adaptive contact tracing framework, (2) present a formal treatment which includes game-based security definition and a detailed protocol construction. Finally, (3) we implement our construction to showcase the practicality of our protocol.

Proof-of-useful-work (PoUW), an alternative to the widely used proof-of-work (PoW), aims to re-purpose the network's computing power. Namely, users evaluate meaningful computational problems, e.g., solving optimization problems, instead of computing numerous hash function values as in PoW. A recent approach utilizes the training process of deep learning as ``useful work''. However, these works lack security analysis when deploying them with blockchain-based protocols, let alone the informal and over-complicated system design. This work proposes a distributed proof-of-deep-learning (D-PoDL) scheme concerning PoUW's requirements. With a novel hash-traininßg-hash structure and model-referencing mechanism, our scheme is the first deep learning-based PoUW scheme that enables achieving better accuracy distributively. Next, we introduce a transformation from the D-PoDL scheme to a generic D-PoDL blockchain protocol which can be instantiated with two chain selection rules, i.e., the longest-chain rule and the weight-based blockchain framework (LatinCrypt' 21). This work is the first to provide formal proofs for deep learning-involved blockchain protocols concerning the robust ledger properties, i.e., chain growth, chain quality, and common prefix. Finally, we implement the D-PoDL scheme to discuss the effectiveness of our design.

An encryption scheme is Key Dependent Message (KDM) secure if it is safe to encrypt messages that can arbitrarily depend on the secret keys themselves. In this work, we show how to upgrade essentially the weakest form of KDM security into the strongest one. In particular, we assume the existence of a symmetric-key bit-encryption that is circular-secure in the $1$-key setting, meaning that it maintains security even if one can encrypt individual bits of a single secret key under itself. We also rely on a standard CPA-secure public-key encryption. We construct a public-key encryption scheme that is KDM secure for general functions (of a-priori bounded circuit size) in the multi-key setting, meaning that it maintains security even if one can encrypt arbitrary functions of arbitrarily many secret keys under each of the public keys. As a special case, the latter guarantees security in the presence of arbitrary length key cycles. Prior work already showed how to amplify $n$-key circular to $n$-key KDM security for general functions. Therefore, the main novelty of our work is to upgrade from $1$-key to $n$-key security for arbitrary $n$.

As an independently interesting feature of our result, our construction does not need to know the actual specification of the underlying 1-key circular secure scheme, and we only rely on the existence of some such scheme in the proof of security. In particular, we present a universal construction of a multi-key KDM-secure encryption that is secure as long as some 1-key circular-secure scheme exists. While this feature is similar in spirit to Levin's universal construction of one-way functions, the way we achieve it is quite different technically, and does not come with the same ``galactic inefficiency''.

In this work, we extend the MPC-in-the-head framework, used in recent efficient zero-knowledge protocols, to work over the ring $\mathbb{Z}_{2^k}$, which is the primary operating domain for modern CPUs. The proposed schemes are compatible with any threshold linear secret sharing scheme and draw inspiration from MPC protocols adapted for ring operations. Additionally, we explore various batching methodologies, leveraging Shamir's secret sharing schemes and Galois ring extensions, and show the applicability of our approach in RAM program verification. Finally, we analyse different options for instantiating the resulting ZK scheme over rings and compare their communication costs.

Public data can be authenticated by obtaining from a trustworthy website with TLS. Private data, such as user profile, are usually restricted from public access. If a user wants to authenticate his private data (e.g., address) provided by a restricted website (e.g., user profile page of a utility company website) to a verifier, he cannot simply give his username and password to the verifier. DECO (CCS 2020) provides a solution for liberating these data without introducing undesirable trust assumption, nor requiring server-side modification. Their implementation is mainly based on TLS 1.2.

In this paper, we propose an optimized solution for TLS 1.3 websites. We tackle a number of open problems, including the support of X25519 key exchange in TLS 1.3, the design of round-optimal three-party key exchange, the architecture of two-party computation of TLS 1.3 key scheduling, and circuit design optimized for two-party computation. We test our implementation with real world website and show that our optimization is necessary to avoid timeout in TLS handshake.

Deep neural networks (DNNs) represent a powerful technique for assessing cryptographic security concerning side-channel analysis (SCA) due to their ability to aggregate leakages automatically, rendering attacks more efficient without preprocessing. Nevertheless, despite their effectiveness, DNNs employed in SCA are predominantly black-box algorithms, posing considerable interpretability challenges. In this paper, we propose a novel technique called Key Guessing Occlusion (KGO) that acquires a minimal set of sample points required by the DNN for key recovery, which we call OccPoIs. These OccPoIs provide information on which areas of the traces are important to the DNN for retrieving the key, enabling evaluators to know where to refine their cryptographic implementation. After obtaining the OccPoIs, we first explore the leakages found in these OccPoIs to understand what the DNN is learning with first-order Correlation Power Analysis (CPA). We show that KGO obtains relevant sample points that have a high correlation with the given leakage model but also acquires sample points that first-order CPA fails to capture. Furthermore, unlike the first-order CPA in the masking setting, KGO obtains these OccPoIs without the knowledge of the shares or mask. Next, we employ the template attack (TA) using the OccPoIs to investigate if KGO could be used as a feature selection tool. We show that using the OccPoIs with TA can recover the key for all the considered synchronized datasets and is consistent as a feature selection tool even on datasets protected by first-order masking. Furthermore, it also allows a more efficient attack than other feature selections on the first-order masking dataset called ASCADf.

This paper studies the quantum computational complexity of the discrete logarithm and related group-theoretic problems in the context of ``generic algorithms''---that is, algorithms that do not exploit any properties of the group encoding.

We establish a generic model of quantum computation for group-theoretic problems, which we call the quantum generic group model, as a quantum analog of its classical counterpart. Shor's algorithm for the discrete logarithm problem and related algorithms can be described in this model. We show the quantum complexity lower bounds and (almost) matching algorithms of the discrete logarithm and related problems in this model. More precisely, we prove the following results for a cyclic group $\mathcal G$ of prime order.

(1) Any generic quantum discrete logarithm algorithm must make $\Omega(\log |\mathcal G|)$ depth of group operation queries. This shows that Shor's algorithm that makes $O(\log |\mathcal G|)$ group operations is asymptotically optimal among the generic quantum algorithms, even considering parallel algorithms. (2) We observe that some (known) variations of Shor's algorithm can take advantage of classical computations to reduce the number and depth of quantum group operations. We introduce a model for generic hybrid quantum-classical algorithm that captures these variants, and show that these algorithms are almost optimal in this model. Any generic hybrid quantum-classical algorithm for the discrete logarithm problem with a total number of (classical or quantum) group operations $Q$ must make $\Omega(\log |\mathcal G|/\log Q)$ quantum group operations of depth $\Omega(\log\log |\mathcal G| - \log\log Q)$. In particular, if $Q={\rm poly}\log |\mathcal G|$, classical group operations can only save the number of quantum queries by a factor of $O(\log\log |\mathcal G|)$ and the quantum depth remains as $\Omega(\log\log |\mathcal G|)$. (3) When the quantum memory can only store $t$ group elements and use quantum random access memory (qRAM) of $r$ group elements, any generic hybrid quantum-classical algorithm must make either $\Omega(\sqrt{|\mathcal G|})$ group operation queries in total or $\Omega(\log |\mathcal G|/\log (tr))$ quantum group operation queries. In particular, classical queries cannot reduce the number of quantum queries beyond $\Omega(\log |\mathcal G|/\log (tr))$.

As a side contribution, we show a multiple discrete logarithm problem admits a better algorithm than solving each instance one by one, refuting a strong form of the quantum annoying property suggested in the context of password-authenticated key exchange protocol.

The majority of secure messengers have single, centralized service providers that relay ciphertexts between users to enable asynchronous communication. However, in some scenarios such as mass protests in censored networks, relying on a centralized provider is fatal. Mesh messengers attempt to solve this problem by building ad hoc networks in which user clients perform the ciphertext-relaying task. Yet, recent analyses of widely deployed mesh messengers discover severe security weaknesses (Albrecht et al. CT-RSA'21 & USENIX Security'22).

To support the design of secure mesh messengers, we provide a new, more complete security model for mesh messaging. Our model captures forward and post-compromise security, as well as forward and post-compromise anonymity, both of which are especially important in this setting. We also identify novel, stronger confidentiality goals that can be achieved due to the special characteristics of mesh networks (e.g., delayed communication, distributed network and adversary).

Finally, we develop a new protocol, called ASMesh, that provably satisfies these security goals. For this, we revisit Signal's Double Ratchet and propose non-trivial enhancements. On top of that, we add a mechanism that provides forward and post-compromise anonymity. Thus, our protocol efficiently provides strong confidentiality and anonymity under past and future user corruptions. Most of our results are also applicable to traditional messaging.

We prove security of our protocols and evaluate their performance in simulated mesh networks. Finally, we develop a proof of concept implementation.

Postdoctoral Fellowship in Cryptography
Applications are invited from qualified candidates for a 2-year postdoctoral fellowship appointment (extendable for one more year) in cryptography. Expertise in cryptography and strong mathematics background are essential, and knowledge of quantum information and computation are important advantages. The focus of the positions is on quantum-resistant cryptography and its application to securing communication in two-party and group settings.

A Ph.D. degree and evidence of excellence in research are required. Successful applicants are expected to maintain an active program of research, and participate in research activities with academic and industry partners in the grant. The annual salary is $55,000 - $65,000 (CAD) depending on the qualifications and experience. The positions are available immediately.

Applicants should include a cover letter describing their interest in the position, a curriculum vitae, a short research statement and at least two contacts for reference letters. Interested individuals should send their application to espri@ucalgary.ca
Inquiries may be addressed to Rei Safavi-Naini, (rei@ucalgary.ca). Applications will be considered as they are submitted until the position is filled.

About the University of Calgary & Calgary
The University of Calgary is Canada’s leading next-generation university. The university has reached its Eyes High goal to be recognized as one of Canada’s top five research universities. The University of Calgary recognizes that a diverse staff/faculty benefits and enriches the work, learning and research experiences of the entire campus and greater community.

Calgary has been named one of the world's most livable cities for years. Calgary is less than an hour’s drive from the Rocky Mountains and boasts the most extensive urban pathway and bikeway network in North America.

Closing date for applications:

Contact: Rei Safavi-Naini

Event date: 25 May to 26 May 2024
Submission deadline: 4 September 2023
Notification: 15 September 2023

What you do? 1. Design and implement the proving system algorithms that are to be used in zkEVM/zkVM solutions. 2. Optimize Elliptic Curve Primitives and proof generation processes. 3. Survey the emerging zkEVM, zkVM, and various ZKP protocols with in-depth understanding on their academic papers and code implementations. Requirements: 1. Strong background in Math, Cryptography, or Zero Knowledge Proof. 2 Solid experience on Plonk & Halo2 proving systems with both BN and BLS Elliptic Curve families. 3. Proficiency in Rust & Go. 4. Ability to pick up new things beyond cryptography (i.e. details of EVM). 5. Experience in blockchain infrastructure development or cryptography preferred.

Closing date for applications:

Contact: mia