International Association
for Cryptologic Research

We are hiring postdoctoral researchers working on the foundations of computing. We welcome applicants working in all areas of theoretical computer science, broadly interpreted, including e.g. algorithmics and algorithm engineering, computability and computational complexity, computational logic, optimization, cryptography, computational geometry, natural computation, and foundations of distributed, parallel, and quantum computing.

We offer the possibility to participate and take initiative in leading-edge research in a young and growing research environment with 10 professors and their teams working on foundational topics in the Helsinki area at Aalto University and the University of Helsinki (*). The postdoctoral researcher positions are full-time research positions for a duration of one year, with the possibility of extension to a second year by mutual consent. Travel funding is available for travel permitted by the pandemic situation. Participation in teaching of advanced courses and thesis instruction is possible and encouraged, with 5-10% allocation of the total working time.

(*) https://research.cs.aalto.fi/theory/

Supervisors:

Chris Brzuska

Parinya Chalermsook

Petteri Kaski

Mikko Koivisto

Juha Kontinen

Sándor Kisfaludi-Bak

Pekka Orponen

Alexandru Paler

Jukka Suomela

Jara Uitto

Closing date for applications:

Contact:

General questions about HICT: Christina Sirviö, HICT team

General questions about recruitment process: Sanni Kirmanen, Aalto University HR

Questions about cryptography research at Aalto: Chris Brzuska

Firstname.lastname@aalto.fi

More information: https://www.hiit.fi/open-calls/

While many anonymous communication (AC) protocols have been proposed to provide anonymity over the internet, scaling to a large number of users while remaining provably secure is challenging. We tackle this challenge by proposing a new scaling technique to improve the scalability/anonymity of AC protocols that distributes the computational load over many nodes without completely disconnecting the paths different messages take through the network. We demonstrate that our scaling technique is useful and practical through a core sample AC protocol, Streams, that offers provable security guarantees and scales for a million messages. The scaling technique ensures that each node in the system does the computation-heavy public key operation only for a tiny fraction of the total messages routed through the Streams network while maximizing the mixing/shuffling in every round.

We demonstrate Streams' performance through a prototype implementation. Our results show that Streams can scale well even if the system has a load of one million messages at any point in time. Streams maintains a latency of $16$ seconds while offering provable ``one-in-a-billion'' unlinkability, and can be leveraged for applications such as anonymous microblogging and network-level anonymity for blockchains. We also illustrate by examples that our scaling technique can be useful to many other AC protocols to improve their scalability and privacy, and can be interesting to protocol developers.

At ITCS 2020, Bartusek et al. proposed a candidate indistinguishability obfuscator (iO) for affine determinant programs (ADPs). The candidate is special since it directly applies specific randomization techniques to the underlying ADP, without relying on the hardness of traditional cryptographic assumptions like discrete-log or learning with errors. It is relatively efficient compared to the rest of the iO candidates. However, the obfuscation scheme requires further cryptanalysis since it was not known to be based on any well-formed mathematical assumptions.

In this paper, we show cryptanalytic attacks on the iO candidate provided by Bartusek et al. Our attack exploits the weakness of one of the randomization steps in the candidate. The attack applies to a fairly general class of programs. At the end of the paper we discuss plausible countermeasures to defend against our attacks.

In this paper we propose Privacy-preserving User-data Bookkeeping & Analytics (PUBA), a building block destined to enable the implementation of business models (e.g., targeted advertising) and regulations (e.g., fraud detection) requiring user-data analysis in a privacy-preserving way.

In PUBA, users keep an unlinkable but authenticated cryptographic logbook containing their historic data on their device. This logbook can only be updated by the operator while its content is not revealed. Users can take part in a privacy-preserving analytics computation, where it is ensured that their logbook is up-to-date and authentic while the potentially secret analytics function is verified to be privacy-friendly. Taking constrained devices into account, users may also outsource analytic computations (to a potentially malicious proxy not colluding with the operator).

We model our novel building block in the Universal Composability framework and provide a practical protocol instantiation. To demonstrate the flexibility of PUBA, we sketch instantiations of privacy-preserving fraud detection and targeted advertising, although it could be used in many more scenarios, e.g. data analytics for multi-modal transportation systems. We implemented our bookkeeping protocols and an exemplary outsourced analytics computation based on logistic regression using the MP-SPDZ MPC framework. Performance evaluations using a smartphone as user device and more powerful hardware for operator and proxy suggest that PUBA for smaller logbooks can indeed be practical.

In the problem of two-party \emph{private function evaluation} (PFE), one party $P_A$ holds a \emph{private function} $f$ and (optionally) a private input $x_A$, while the other party $P_B$ possesses a private input $x_B$. Their goal is to evaluate $f$ on $x_A$ and $x_B$, and one or both parties may obtain the evaluation result $f(x_A, x_B)$ while no other information beyond $f(x_A, x_B)$ is revealed.

In this paper, we revisit the two-party PFE problem and provide several enhancements. We propose the \emph{first} constant-round actively secure PFE protocol with linear complexity. Based on this result, we further provide the \emph{first} constant-round publicly verifiable covertly (PVC) secure PFE protocol with linear complexity to gain better efficiency. For instance, when the deterrence factor is $\epsilon = 1/2$, compared to the passively secure protocol, its communication cost is very close and its computation cost is around $2.6\times$. In our constructions, as a by-product, we design a specific protocol for proving that a list of ElGamal ciphertexts is derived from an \emph{extended permutation} performed on a given list of elements. It should be noted that this protocol greatly improves the previous result and may be of independent interest. In addition, a reusability property is added to our two PFE protocols. Namely, if the same function $f$ is involved in multiple executions of the protocol between $P_A$ and $P_B$, then the protocol could be executed more efficiently from the second execution. Moreover, we further extend this property to be \emph{global}, such that it supports multiple executions for the same $f$ in a reusable fashion between $P_A$ and \emph{arbitrary} parties playing the role of $P_B$.

The Oriented Supersingular Isogeny Diffie-Hellman is a post-quantum key exchange scheme recently introduced by Colò and Kohel. It is based on the group action of an ideal class group of a quadratic imaginary order on a subset of supersingular elliptic curves, and in this sense it can be viewed as a generalization of the popular isogeny based key exchange CSIDH. From an algorithmic standpoint, however, OSIDH is quite different from CSIDH. In a sense, OSIDH uses class groups which are more structured than in CSIDH, creating a potential weakness that was already recognized by Colò and Kohel. To circumvent the weakness, they proposed an ingenious way to realize a key exchange by exchanging partial information on how the class group acts in the neighborhood of the public curves, and conjectured that this additional information would not impact security.

In this work we revisit the security of OSIDH by presenting a new attack, building upon previous work of Onuki. Our attack has exponential complexity, but it practically breaks Colò and Kohel's parameters unlike Onuki's attack. We also discuss countermeasures to our attack, and analyze their impact on OSIDH, both from an efficiency and a functionality point of view.

Anonymous attribute-based credentials (ABCs) are a powerful tool allowing users to authenticate while maintaining privacy. When instantiated from structure-preserving signatures on equivalence classes (SPS-EQ) we obtain a controlled form of malleability, and hence increased functionality and privacy for the user. Existing constructions consider equivalence classes on the message space, allowing the joint randomization of credentials and the corresponding signatures on them.

In this work, we additionally consider equivalence classes on the signing-key space. In this regard, we obtain a signer-hiding notion, where the issuing organization is not revealed when a user shows a credential. To achieve this, we instantiate the ABC framework of Fuchsbauer, Hanser, and Slamanig (FHS, Journal of Cryptology '19) with a recent SPS-EQ scheme (ASIACRYPT '19) modified to support a fully adaptive NIZK from the framework of Couteau and Hartmann (CRYPTO '20). We also show how to obtain Mercurial Signatures (CT-RSA, 2019), extending the application of our construction to anonymous delegatable credentials.

To further increase functionality and efficiency, we augment the set-commitment scheme of FHS19 to support openings on attribute sets disjoint from those possessed by the user, while integrating a proof of exponentiation to allow for a more efficient verifier. Instantiating in the CRS model, we obtain an efficient credential system, anonymous under malicious organization keys, with increased expressiveness and privacy, proven secure in the standard model.

Incompressible encryption allows us to make the ciphertext size flexibly large and ensures that an adversary learns nothing about the encrypted data, even if the decryption key later leaks, unless she stores essentially the entire ciphertext. Incompressible signatures can be made arbitrarily large and ensure that an adversary cannot produce a signature on any message, even one she has seen signed before, unless she stores one of the signatures essentially in its entirety.

In this work, we give simple constructions of both incompressible public-key encryption and signatures under minimal assumptions. Furthermore, large incompressible ciphertexts (resp. signatures) can be decrypted (resp. verified) in a streaming manner with low storage. In particular, these notions strengthen the related concepts of disappearing encryption and signatures, recently introduced by Guan and Zhandry (TCC 2021), whose previous constructions relied on sophisticated techniques and strong, non-standard assumptions. We extend our constructions to achieve an optimal ``rate'', meaning the large ciphertexts (resp. signatures) can contain almost equally large messages, at the cost of stronger assumptions.

Event date: 1 August to 5 August 2022

Commitments to key-value maps (or, authenticated dictionaries) are an important building block in cryptographic applications, including cryptocurrencies and distributed file systems. In this work we study short commitments to key-value maps with two additional properties: full-hiding (both keys and values should be hidden) and homomorphism (we should be able to combine two commitments to obtain one that is the ``sum'' of their key-value openings). Furthermore, we require these commitments to be short and to support efficient transparent zero-knowledge arguments (i.e., without a trusted setup). As our main contribution, we show how to construct commitments with the properties above as well as efficient zero-knowledge arguments over them. We additionally discuss a range of practical optimizations that can be carried out depending on the application domain. Finally, we show a specific application of commitments to key-value maps to scalable anonymous ledgers. Our contribution there is to formalize multi-type anonimity ledgers and show how to extend QuisQuis (Fauzi et al., ASIACRYPT 2019). This results in an efficient, confidential multi-type system with a state whose size is independent of the number of transactions.

The Support-Minors (SM) method has opened new routes to attack multivariate schemes with rank properties that were previously impossible to exploit, as shown by the recent attacks of Tao at al. (CRYPTO 2021) and Beullens (EUROCRYPT 2021) on the NIST candidates GeMSS and Rainbow respectively. In this paper, we study this SM approach more in depth, which allows us first to propose a greatly improved attack on GeMSS, and also to define a more realistic cost model to evaluate the memory complexity of an XL strategy on the SM system using the Block-Wiedemann algorithm. Our new attack on GeMSS makes it completely unfeasible to repair the scheme by simply increasing the size of its parameters or even applying the projection technique from Øygarden et al. (PQCrypto 2021) as the signing time would be increased in a considerable way. Also, in our refined cost model, the rectangular MinRank attack from Beullens does indeed reduce the security of all Round 3 Rainbow parameter sets below their targeted security strengths.

In our paper we study the effect of changing the commutative group operation used in Feistel and Lai-Massey symmetric structures into a quasigroup operation. We prove that if the quasigroup operation is isotopic with a group $\mathbb G$, the complexity of mounting a differential attack against our generalization of the Feistel structure is the same as attacking the unkeyed version of the general Feistel iteration based on $\mathbb G$. Also, when $\mathbb G$ is non-commutative we show that both versions of the Feistel structure are equivalent from a differential point of view. For the Lai-Massey structure we introduce four non-commutative versions, we argue for the necessity of working over a group and we provide some necessary conditions for the differential equivalency of the four notions.

The main goal of traceable cryptography is to protect against unauthorized redistribution of cryptographic functionalities. Such schemes provide a way to embed identities (i.e., a "mark") within cryptographic objects (e.g., decryption keys in an encryption scheme, signing keys in a signature scheme). In turn, the tracing guarantee ensures that any "pirate device" that successfully replicates the underlying functionality can be successfully traced to the set of identities used to build the device.

In this work, we study traceable pseudorandom functions (PRFs). As PRFs are the workhorses of symmetric cryptography, traceable PRFs are useful for augmenting symmetric cryptographic primitives with strong traceable security guarantees. However, existing constructions of traceable PRFs either rely on strong notions like indistinguishability obfuscation or satisfy weak security guarantees like single-key security (i.e., tracing only works against adversaries that possess a single marked key).

In this work, we show how to use fingerprinting codes to upgrade a single-key traceable PRF into a fully collusion resistant traceable PRF, where security holds regardless of how many keys the adversary possesses. We additionally introduce a stronger notion of security where tracing security holds even against active adversaries that have oracle access to the tracing algorithm. In conjunction with known constructions of single-key traceable PRFs, we obtain the first fully collusion resistant traceable PRF from standard lattice assumptions. Our traceable PRFs directly imply new lattice-based secret-key traitor tracing schemes that are CCA-secure and where tracing security holds against active adversaries that have access to the tracing oracle.

We propose new zero-knowledge proofs for efficient and post-quantum ring confidential transaction (RingCT) protocols based on lattice assumptions in Blockchain systems. First, we introduce an inner-product based linear equation satisfiability approach for balance proofs with a wide range (e.g. 64-bit precision). Unlike existing balance proofs that require additional proofs for some ''corrector values'' [CCS'19], our approach avoids the corrector values for better efficiency. Furthermore, we design a ring signature scheme to efficiently hide a user's identity in large anonymity sets. Different from existing approaches that adopt a one-out-of-many proof [CCS'19, Crypto'19], we show that a linear sum proof suffices in ring signatures which could avoid the costly binary proof part. We further use the idea of ''unbalanced'' relations to build a logarithmic-size ring signature scheme. Finally, we show how to adopt these techniques in RingCT protocols and implement a prototype to compare the performance with existing approaches. The results show our solutions can reduce about 25% proof size of Crypto'19, and up to 70% proof size, 30% proving time, and 20% verification time of CCS'19. We also believe our techniques are of independent interest for other privacy-preserving applications such as secure e-voting and are applicable in a generic setting.

Succinct arguments are proof systems that allow a powerful, but untrusted, prover to convince a weak verifier that an input $x$ belongs to a language $L \in NP$, with communication that is much shorter than the $NP$ witness. Such arguments, which grew out of the theory literature, are now drawing immense interest also in practice, where a key bottleneck that has arisen is the high computational cost of \emph{proving} correctness.

In this work we address this problem by constructing succinct arguments for general computations, expressed as Boolean circuits (of bounded fan-in), with a \emph{strictly linear} size prover. The soundness error of the protocol is an arbitrarily small constant. Prior to this work, succinct arguments were known with a \emph{quasi-}linear size prover for general Boolean circuits or with linear-size only for arithmetic circuits, defined over large finite fields.

In more detail, for every Boolean circuit $C=C(x,w)$, we construct an $O(\log |C|)$-round argument-system in which the prover can be implemented by a size $O(|C|)$ Boolean circuit (given as input both the instance $x$ and the witness $w$), with arbitrarily small constant soundness error and using $poly(\lambda,\log |C|)$ communication, where $\lambda$ denotes the security parameter. The verifier can be implemented by a size $O(|x|) + poly(\lambda, \log |C|)$ circuit following a size $O(|C|)$ private pre-processing step, or, alternatively, by using a purely public-coin protocol (with no pre-processing) with a size $O(|C|)$ verifier. The protocol can be made zero-knowledge using standard techniques (and with similar parameters). The soundness of our protocol is computational and relies on the existence of collision resistant hash functions that can be computed by linear-size circuits, such as those proposed by Applebaum et al. (ITCS, 2017).

At the heart of our construction is a new information-theoretic \emph{interactive oracle proof} (IOP), an interactive analog of a PCP, for circuit satisfiability, with constant prover overhead. The improved efficiency of our IOP is obtained by bypassing a barrier faced by prior IOP constructions, which needed to (either explicitly or implicitly) encode the entire computation using a multiplication code.

Cryptographic accumulators are a common solution to proving information about a large set $S$. They allow to compute a short digest of $S$ and short certificates of some of its basic properties, notably membership of an element. Accumulators also allow to track set updates: a new accumulator is obtained by inserting/deleting a given element. In this work we consider the problem of generating membership and update proofs for {\em batches} of elements so that we can succinctly prove additional properties of the elements (i.e., proofs are of constant size regardless of the batch size), and we can preserve privacy. Solving this problem would allow to obtain blockchain systems with improved privacy and scalability. The state-of-the-art approach to achieve this goal is to combine accumulators (typically Merkle trees) with zkSNARKs. This solution is however expensive for provers and does not scale for large batches of elements. In particular, there is no scalable solution for proving batch membership proofs when we require zero-knowledge (a standard definition of privacy-preserving protocols). In this work we propose new techniques to efficiently use zkSNARKs with RSA accumulators. We design and implement two main schemes: 1) HARiSA, which proves batch membership in zero-knowledge; 2) B-INS-HARiSA, which proves batch updates. For batch membership, the prover in HARiSA is orders of magnitude faster than existing approaches based on Merkle trees (depending on the hash function). For batch updates we get similar cost savings compared to approaches based on Merkle tree; we also improve

This paper introduces IronMask, a new versatile verification tool for masking security. IronMask is the first to offer the verification of standard simulation-based security notions in the probing model as well as recent composition and expandability notions in the random probing model. It supports any masking gadgets with linear randomness (e.g. addition, copy and refresh gadgets) as well as quadratic gadgets (e.g. multiplication gadgets) that might include non-linear randomness (e.g. by refreshing their inputs), while providing complete verification results for both types of gadgets. We achieve this complete verifiability by introducing a new algebraic characterization for such quadratic gadgets and exhibiting a complete method to determine the sets of input shares which are necessary and sufficient to perform a perfect simulation of any set of probes. We report various benchmarks which show that IronMask is competitive with state-of-the-art verification tools in the probing model (maskVerif, scVerif, SILVER, matverif). IronMask is also several orders of magnitude faster than VRAPS --the only previous tool verifying random probing composability and expandability-- as well as SILVER --the only previous tool providing complete verification for quadratic gadgets with non-linear randomness. Thanks to this completeness and increased performance, we obtain better bounds for the tolerated leakage probability of state-of-the-art random probing secure compilers.

The solving degree of a system of multivariate polynomial equations provides an upper bound for the complexity of computing the solutions of the system via Groebner basis methods. In this paper, we consider polynomial systems that are obtained via Weil restriction of scalars. The latter is an arithmetic construction which, given a finite Galois field extension $k\hookrightarrow K$, associates to a system $\mathcal{F}$ defined over $K$ a system $\mathrm{Weil}(\mathcal{F})$ defined over $k$, in such a way that the solutions of $\mathcal{F}$ over $K$ and those of $\mathrm{Weil}(\mathcal{F})$ over $k$ are in natural bijection. In this paper, we find upper bounds for the complexity of solving a polynomial system $\mathrm{Weil}(\mathcal{F})$ obtained via Weil restriction in terms of algebraic invariants of the system $\mathcal{F}$.

The rise of blockchain technology has boosted interest in privacy-enhancing technologies, in particular, anonymous transaction authentication. Permissionless blockchains realize transaction anonymity through one-time pseudonyms, whereas permissioned blockchains leverage anonymous credentials. Earlier solutions of anonymous credentials assume a single issuer; as a result, they hide the identity of users but still reveal the identity of the issuer. A countermeasure is delegatable credentials, which support multiple issuers as long as a root authority exists. Assuming a root authority however, is unsuitable for blockchain technology and decentralized applications. This paper introduces a solution for anonymous credentials that guarantees user anonymity, even without a root authority. The proposed solution is secure in the universal composability framework and allows users to produce anonymous signatures that are logarithmic in the number of issuers and constant in the number of user attributes.

Publish-subscribe protocols enable real-time multi-point-to-multi-point communications for many dispersed computing systems like Internet of Things (IoT) applications. Recent interest has focused on adding processing to such publish-subscribe protocols to enable computation over real-time streams such that the protocols can provide functionalities such as sensor fusion, compression, and other statistical analysis on raw sensor data. However, unlike pure publish-subscribe protocols, which can be easily deployed with end-to-end transport layer encryption, it is challenging to ensure security in such publish-process-subscribe protocols when the processing is carried out on an untrusted third party. In this work, we present XYZ, a secure publish-process-subscribe system that can preserve the confidentiality of computations and support multi-publisher-multi-subscriber settings. Within XYZ, we design two distinct schemes: the first using Yao's garbled circuits (the GC-Based Scheme) and the second using homomorphic encryption with proxy re-encryption (the Proxy-HE Scheme). We build implementations of the two schemes as an integrated system atop the Message Queue Telemetry Transport (MQTT) pub-sub protocol. We evaluate our system on several functions and also demonstrate real-world applications based on it. The evaluation shows that the GC-Based Scheme can finish most tasks two orders of magnitude times faster than the Proxy-HE Scheme while Proxy-HE can still securely complete tasks within an acceptable time for most functions but with a different security assumption and a simpler system structure.