International Association
for Cryptologic Research

Event date: 10 September 2023
Submission deadline: 23 June 2023
Notification: 14 July 2023

The Department of Combinatorics and Optimization at the University of Waterloo invites applications from qualified candidates for two 3-year postdoctoral fellowship appointments in cryptography under the supervision of Prof. David Jao, Prof. Michele Mosca, and Prof. Douglas Stebila. Expertise in cryptography is essential. The focus of the positions is on post-quantum cryptography, and is funded by an NSERC Alliance Quantum Consortia grant entitled “Accelerating the transition to quantum-resistant cryptography”.

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 $66,000. In addition, a travel fund of $3,000 per year is provided. The positions are available immediately.

Interested individuals should apply using the MathJobs site https://www.mathjobs.org/jobs/list/22461. Applications should include a cover letter describing their interest in the position, a curriculum vitae and research statement and at least three reference letters.

Applications will be considered as they are submitted until the position is filled.

The University of Waterloo acknowledges that much of our work takes place on the traditional territory of the Neutral, Anishinaabeg and Haudenosaunee peoples. The University values the diverse and intersectional identities of its students, faculty, and staff. The University regards equity and diversity as an integral part of academic excellence and is committed to accessibility for all employees. The University of Waterloo seeks applicants who embrace our values of equity, anti-racism and inclusion. As such, we encourage applications from candidates who have been historically disadvantaged and marginalized, including applicants who identify as Indigenous peoples (e.g., First Nations, Métis, Inuit/Inuk), Black, racialized, people with disabilities, women and/or 2SLGBTQ+. All qualified candidates are encouraged to apply; however, Canadians and permanent residents will be given priority.

Closing date for applications:

Contact: Douglas Stebila (dstebila@uwaterloo.ca)

More information: https://www.mathjobs.org/jobs/list/22461

Perform fundamental research in the field of cryptography to advance the state-of-the-art in secure computation and communication. Advance cryptographic schemes and protocols in said fields to improve efficiency and practicality, especially in the fields of multi-party computation and secure and verifiable computation. Particular focus is expected on upcoming fields such as garbled random-access memory programs, and lattice-based cryptography applied to fully-homomorphic encryption and post-quantum cryptographic schemes.

Closing date for applications:

Contact: Charanjit S. Jutla

More information: https://careers.ibm.com/job/18358790/cryptography-researcher-visiting-scholar-yorktown-heights-ny/?codes=IBM_CareerWebSite

We show the following results:

- The post-quantum equivalence of indistinguishability obfuscation and differing inputs obfuscation in the restricted setting where the outputs differ on at most a polynomial number of points. Our result handles the case where the auxiliary input may contain a quantum state; previous results could only handle classical auxiliary input.

- Bounded collusion traitor tracing from general public key encryption, where the decoder is allowed to contain a quantum state. The parameters of the scheme grow polynomially in the collusion bound.

- Collusion-resistant traitor tracing with constant-size ciphertexts from general public key encryption, again for quantum state decoders. The public key and secret keys grow polynomially in the number of users.

- Traitor tracing with embedded identities in the keys, again for quantum state decoders, under a variety of different assumptions with different parameter size trade-offs.

Traitor tracing and differing inputs obfuscation with quantum decoders / auxiliary input arises naturally when considering the post-quantum security of these primitives. We obtain our results by abstracting out a core algorithmic model, which we call the Back One Step (BOS) model. We prove a general theorem, reducing many quantum results including ours to designing classical algorithms in the BOS model. We then provide simple algorithms for the particular instances studied in this work.

Millions of smart contracts have been deployed onto Ethereum for providing various services, whose functions can be invoked. For this purpose, the caller needs to know the function signature of a callee, which includes its function id and parameter types. Such signatures are critical to many applications focusing on smart contracts, e.g., reverse engineering, fuzzing, attack detection, and profiling. Unfortunately, it is challenging to recover the function signatures from contract bytecode, since neither debug information nor type information is present in the bytecode. To address this issue, prior approaches rely on source code, or a collection of known signatures from incomplete databases or incomplete heuristic rules, which, however, are far from adequate and cannot cope with the rapid growth of new contracts. In this paper, we propose a novel solution that leverages how functions are handled by Ethereum virtual machine (EVM) to automatically recover function signatures. In particular, we exploit how smart contracts determine the functions to be invoked to locate and extract function ids, and propose a new approach named type-aware symbolic execution (TASE) that utilizes the semantics of EVM operations on parameters to identify the number and the types of parameters. Moreover, we develop SigRec , a new tool for recovering function signatures from contract bytecode without the need of source code and function signature databases. The extensive experimental results show that SigRec outperforms all existing tools, achieving an unprecedented 98.7 percent accuracy within 0.074 seconds. We further demonstrate that the recovered function signatures are useful in attack detection, fuzzing and reverse engineering of EVM bytecode.

Isogeny-based cryptography is an active area of research in post-quantum public key cryptography. The problem of proving knowledge of an isogeny is a natural problem that has several applications in isogeny-based cryptography, such as allowing users to demonstrate that they are behaving honestly in a protocol. It is also related to isogeny-based digital signatures. Over the last few years, there have been a number of advances in this area, but there are still many open problems. This paper aims to give an overview of the topic and highlight some open problems and directions for future research.

Polynomial commitment schemes are fundamental building blocks in numerous cryptographic protocols such as verifiable secret sharing, zero-knowledge succinct non-interactive arguments, and many more. The most efficient polynomial commitment schemes rely on a trusted setup which is undesirable in trust-minimized applications, e.g., cryptocurrencies. However, transparent polynomial commitment schemes are inefficient (polylogarithmic opening proofs and/or verification time) compared to their trusted counterparts. It has been an open problem to devise a transparent, succinct polynomial commitment scheme or prove an impossibility result in the transparent setting. In this work, for the first time, we create a transparent, constant-size polynomial commitment scheme called Behemoth with constant-size opening proofs and a constant verifier. The downside of Behemoth is that it employs a quadratic prover in the degree of the committed polynomial. We prove the security of our scheme in the generic group model and discuss parameter settings in which Behemoth remains practical even for the prover.

We explore some connections between classical substitution ciphers, both monoalphabetic and polyalphabetic, and mathematical group theory. We try to do this in a way that is accessible to cryptographers who are not familiar with group theory, and to mathematicians who are not familiar with classical ciphers.

The notion of witness encryption introduced by Garg et al. (STOC'13) allows to encrypt a message under a statement $x$ from some NP-language $\mathcal{L}$ with associated relation $(x,w) \in \mathcal{R}$, where decryption can be carried out with the corresponding witness $w$. Unfortunately, known constructions for general-purpose witness encryption rely on strong assumptions, and are mostly of theoretical interest. To address these shortcomings, Goyal et al. (PKC'22) recently introduced a blockchain-based alternative, where a committee decrypts ciphertexts when provided with a valid witness w. Blockchain-based committee solutions have recently gained broad interest to offer security against more powerful adversaries and construct new cryptographic primitives.

We follow this line of work, and propose a new notion of statement-oblivious threshold witness encryption. Our new notion offers the functionality of committee-based witness encryption while additionally hiding the statement used for encryption. We present two ways to build statement-oblivious threshold witness encryption, one generic transformation based on anonymous threshold identity-based encryption (A-TIBE) and one direct construction based on bilinear maps. Due to the lack of efficient A-TIBE schemes, the former mainly constitutes a feasibility result, while the latter yields a concretely efficient scheme.

Majority voting is a simple mathematical function that returns the value that appears most often in a set. As a popular decision fusion technique, the majority voting function (MVF) finds applications in resolving conflicts, where a number of independent voters report their opinions on a classification problem. Despite its importance and its various applications in ensemble learning, data crowd-sourcing, remote sensing, and data oracles for blockchains, the accuracy of the MVF for the general multi-class classification problem has remained unknown. In this paper, we derive a new upper bound on the accuracy of the MVF for the multi-class classification problem. More specifically, we show that under certain conditions, the error rate of the MVF exponentially decays toward zero as the number of voters increases. Conversely, the error rate of the MVF exponentially grows towards one if these conditions are not met.

We first explore the problem for independent and identically distributed voters where we assume that every voter follows the same conditional probability distribution for voting for different classes, given the true classification of the data point. Next, we extend our results for the case where the voters are independent but non-identically distributed. Using the derived results, we then provide a discussion on the accuracy of the truth discovery algorithms. We show that in the best-case scenarios, truth discovery algorithms operate as an amplified MVF and thereby achieve a small error rate only when the MVF achieves a small error rate, and vice versa, achieve a large error rate when the MVF also achieves a large error rate. In the worst-case scenario, the truth discovery algorithms may achieve a higher error rate than the MVF. Finally, we confirm our theoretical results using simulations.

This note provides an update on the Open Specification Language (OSL) circuit compiler. OSL is a language based on predicate logic which is amenable to compilation to arithmetic constraint systems for use in constructing (zk-)SNARKs. This system provides an alternative to universal zk-VMs and low level ad hoc constructions of arithmetic constraint systems, which is potentially more efficient than universal zk-VMs but more cost effective as a development approach than low level ad hoc constructions.

As a generalization of public key encryption with keyword search, public key encryption with equality test was proposed, and identity-based encryption with equality test (IBEET) is its identity-based variant. In IBEET, anyone can check whether two ciphertexts of distinct identities are encryptions of the same plaintext or not using trapdoors. Due to its functionality, IBEET cannot provide any indistinguishability-based security for trapdoor holders. As a variant of IBEET, IBEET against insider attacks (IBEETIA) was proposed, where a token is defined for each identity and is used for encryption, and anyone can check whether two ciphertexts of distinct identities are encryptions of the same plaintext or not without using trapdoors, and an indistinguishability security of IBEETIA was defined. Lee et al. (ACISP 2018) and Duong et al. (ProvSec 2019) proposed a paring-based and a lattice-based constructions, respectively. That is, current concrete IBEETIA schemes are constructed by identity-based encryption (IBE) related complexity assumptions. According to the implication result shown by Boneh et al. (FOCS 2008), IBE is recognized as a strong cryptographic primitive because no black-box construction of IBE from trapdoor permutations exist. However, Emura and Takayasu (IEICE Transactions 2023) demonstrated that symmetric key encryption and pseudo-random permutations are sufficient to construct IBEETIA which is secure in the previous security definition. These results suggest us to explore a condition of IBEETIA that requires to employ IBE-related complexity assumptions. In this paper, we demonstrate a sufficient condition that IBEETIA implies IBE. We define one-wayness against chosen-plaintext/ciphertext attacks for the token generator (OW-TG-CPA/CCA) and for token holders (OW-TH-CPA/CCA), which were not considered in the previous security definition. We show that OW-TG-CPA secure IBEETIA with additional conditions implies OW-CPA secure IBE, and show that Lee et al. and Duong et al. schemes provide the OW-TG-CPA security. On the other hand, we propose a generic construction of OW-TH-CCA secure IBEETIA from public key encryption. Our results suggest a design principle to efficiently construct IBEETIA without employing IBE-related complexity assumptions.

In this paper, we take inspiration from an invited talk presented at CBCrypto'23 to design identification protocols and signatures schemes from group actions using the MPC-in-the-head paradigm.

Lattice-based cryptosystems are some of the primary post-quantum secure alternatives to the asymmetric cryptography that is used today. These lattice-based cryptosystems typically rely on the hardness of some version of either the NTRU or the LWE problem. In this paper, we present the NTWE problem, a natural combination of the NTRU and LWE problems, and construct a new lattice-based cryptosystem based on the hardness of the NTWE problem. As with the NTRU and LWE problems, the NTWE problem naturally corresponds to a problem in a $q$-ary lattice. This allows the hardness of the NTWE problem to be estimated in the same way as it is estimated for the LWE and NTRU problems. We parametrize our cryptosystem from such a hardness estimate and the resulting scheme has performance that is competitive with that of typical lattice-based schemes. In some sense, our NTWE-based cryptosystem can be seen as a less structured and more compact version of a cryptosystem based on the module-NTRU problem. Thus, parameters for our cryptosystem can be selected with the flexibility of a module-LWE-based scheme, while other properties of our system are more similar to those in an NTRU-based system.

Bottleneck complexity is an efficiency measure of secure multiparty computation (MPC) introduced by Boyle et al. (ICALP 2018) to achieve load-balancing. Roughly speaking, it is defined as the maximum communication complexity required by any player within the protocol execution. Since it is impossible to achieve sublinear bottleneck complexity in the number of players $n$ for all functions, a prior work constructed MPC protocols with low bottleneck complexity for specific functions including the AND function and general symmetric functions. However, the previous protocol for a symmetric function needs to assume a computational primitive of garbled circuits. Its unconditionally secure variant has exponentially large bottleneck complexity in the depth of an arithmetic formula computing the function, which limits the class of symmetric functions the protocol can compute with sublinear bottleneck complexity in $n$. In this paper, we propose for the first time unconditionally secure MPC protocols computing any symmetric function with sublinear bottleneck complexity in $n$. Our first protocol is an application of the one-time truth-table protocol by Ishai et al. (TCC 2013). We devise a novel technique to express the truth-table as an array of two or higher dimensions and obtain two other protocols with better trade-offs. We also propose an unconditionally secure protocol with lower bottleneck complexity tailored to the AND function. It avoids pseudorandom functions used by the previous protocol, preserving bottleneck complexity up to a logarithmic factor in $n$. As an application, we construct an unconditionally secure protocol for private set intersection (PSI), which computes the intersection of players' private sets. This is the first PSI protocol with sublinear bottleneck complexity in $n$ and to the best of our knowledge, there has been no such protocol even under cryptographic assumptions.

This technical paper explores two solutions for arithmetization of computational integrity statements in STARKs, namely the algebraic intermediate representation, AIR, and is preprocessed variant, PAIR. The work then focuses on their soundness implications for Reed-Solomon proximity testing. It proceeds by presenting a comparative study of these methods, providing their theoretical foundations and deriving the degree bounds for low-degree proximity testing. The study shows that using PAIR increases the degree bound for Reed-Solomon proximity testing, which affects its soundness and complexity, but also explores the possibility of reducing the degree bound with multiple selector columns. The paper concludes that, while PAIR might simplify constraint enforcement, it can be easily translated to AIR, and system testing with benchmarks is necessary to determine the application-specific superiority of either method. This work should provide insight into the strengths and limitations of each method, helping researchers and practitioners in the field of STARKs make informed design choices.

We introduce FESTA, an efficient isogeny-based public-key encryption (PKE) protocol based on a constructive application of the SIDH attacks. At its core, FESTA is based on a novel trapdoor function, which uses an improved version of the techniques proposed in the SIDH attacks to develop a trapdoor mechanism. Using standard transformations, we construct an efficient PKE that is IND-CCA secure in the QROM. Additionally, using a different transformation, we obtain the first isogeny-based PKE that is IND-CCA secure in the standard model. Lastly, we propose a method to efficiently find parameters for FESTA, and we develop a proof-of-concept implementation of the protocol. We expect FESTA to offer practical performance that is competitive with existing isogeny-based constructions.

Code-based cryptography has received a lot of attention recently because it is considered secure under quantum computing. Among them, the QC-MDPC based scheme is one of the most promising due to its excellent performance. QC-MDPC based scheme is usually subject to a small rate of decryption failure, which can leak information about the secret key. This raises two crucial problems: how to accurately estimate the decryption failure rate and how to use the failure information to recover the secret key. However, the two problems are challenging due to the difficulty of geometrically characterizing the bit-flipping decoder employed in QC-MDPC, such as using decoding radius.

In this work, we introduce the gathering property and show that it is strongly connected with the decryption failure rate of QC-MDPC. Based on the gathering property, we present two results for QC-MDPC based schemes. The first is a new construction of weak keys obtained by extending the keys that have gathering property via ring isomorphism. For the set of weak keys, we present a rigorous analysis of the probability, as well as experimental simulation of the decryption failure rates. Considering BIKE's parameter set targeting $128$-bit security, our result eventually indicates that the average decryption failure rate is lower bounded by $DFR_{avg} \ge 2^{-122.57}$. The second is a key recovery attack against CCA secure QC-MDPC schemes using decryption failures in a multi-target setting. By decrypting ciphertexts with errors satisfying the gathering property, we show that a single decryption failure can be used to identify whether a target's secret key satisfies the gathering property. Then using the gathering property as extra information, we present a modified information set decoding algorithm that efficiently retrieves the target's secret key. For BIKE's parameter set targeting $128$-bit security, a key recovery attack with complexity $2^{119.88}$ can be expected by using extrapolated decryption failure rates.

We show that the data de-duplication scheme [Internet of Things, 2021(14): 100376] is flawed. (1) There are some inconsistent notations and false equations, which should be corrected. (2) The scheme fails to keep user anonymity, not as claimed. (3) The scheme could fail to keep data confidentiality.

A zero-knowledge proof (ZKP) is a powerful cryptographic primitive used in many decentralized or privacy-focused applications. However, the high overhead of ZKPs can restrict their practical applicability. We design a programming language, Ou, aimed at easing the programmer's burden when writing efficient ZKPs, and a compiler framework, Lian, that automates the analysis and distribution of statements to a computing cluster. Lian uses programming language semantics, formal methods, and combinatorial optimization to automatically partition an Ou program into efficiently sized chunks for parallel ZK-proving and/or verification.

We contribute: • A front-end language where users can write proof statements as imperative programs in a familiar syntax; • A compiler architecture and implementation that automatically analyzes the program and compiles it into an optimized IR that can be lifted to a variety of ZKP constructions; and • A cutting algorithm, based on Pseudo-Boolean optimization and Integer Linear Programming, that reorders instructions and then partitions the program into efficiently sized chunks for parallel evaluation and efficient state reconciliation.