International Association
for Cryptologic Research

As a quantum analogue of one-way function, the notion of one-way quantum state generator is recently proposed by Morimae and Yamakawa (CRYPTO'22), which is proved to be implied by the pseudorandom state, and can be used to devise a construction of one-time secure digital signature. Due to Kretschmer's result (TQC'20), it's believed that pseudorandom state generator requires less than post-quantum secure one-way function. Unfortunately, it remains to be unknown how to achieve the one-way quantum state generator without the existence of post-quantum secure one-way function. In this paper, we mainly study that problem and obtain the following results:

We propose two variants of one-way quantum state generator, which we call them the weak one-way quantum state generator and distributionally one-way quantum state generator, and show the equivalence among these three primitives.

The distributionally one-way quantum state generator from average-case hardness assumption of a promise problem belongs to \textsf{QSZK} is obtained, and hence a construction of one-way quantum state generator.

A direct construction of quantum bit commitment with statistical binding (sum-binding) and computational hiding from the average-case hardness of a complete problem of $\textsf{QSZK}$.

To show the non-triviality of the constructions above, a quantum oracle $\mathcal{U}$ is devised relative to which such promise problem in $\textsf{QSZK}$ doesn't belong to $\mathsf{QMA}^{\mathcal{U}}$.

Our results present the first non-trivial construction of one-way quantum state generator from the hardness assumption of complexity class, and give another evidence that one-way quantum state generator probably requires less than post-quantum secure one-way function.

In this paper we continue our work started in the article ‘Lin2-Xor lemma and Log-size Linkable Threshold Ring Signature’ by introducing another lemma called Lin2-Choice, which extends the Lin2-Xor lemma, and creating a general-purpose log-size linkable threshold ring signature scheme of size 2 log 2 (n) + 3l + 3, where n is the ring size and l is the threshold. The scheme is composed of several public coin honest verifier zero-knowledge arguments that have computational witness-extended emulation. We use an arbitrary vector commitment argument as the base building block, providing the possibility to use any concrete scheme for it, as long as the scheme is honest verifier zero-knowledge and has computational witness-extended emulation. Also, we present an extended version of our signature of size 2 log 2 (n + l) + 6l + 6, which simultaneously proves the sum of hidden amounts attached to the signing keys. All this in a prime order group without bilinear parings in which the decisional Diffie-Hellman assumption holds.

Zero-knowledge proof (ZKP) is a critical cryptographic protocol, and it has been deployed in various privacy-preserving applications such as cryptocurrencies and verifiable machine learning. Unfortunately, ZKP has a high overhead on its proof generation step, which consists of several time-consuming operations, including large-scale matrix-vector multiplication (MUL), number-theoretic transform (NTT), and multi-scalar multiplication (MSM) on elliptic curves. Currently, several GPU-accelerated implementations of ZKP have been developed to improve its performance. However, these existing GPU designs do not fully unleash the potential of GPUs. Therefore, this paper presents cuZK, an efficient GPU implementation of ZKP with the following three optimizations to achieve higher performance. First, we propose a new parallel MSM algorithm and deploy it in cuZK. This MSM algorithm is well adapted to the high parallelism provided by GPUs, and it achieves nearly perfect linear speedup over the Pippenger algorithm, a well-known serial MSM algorithm. Second, we parallelize the MUL operation, which is lightly disregarded by other existing GPU designs. Indeed, along with our self-designed MSM parallel scheme and well-studied NTT parallel scheme, cuZK achieves the parallelization of all operations in the proof generation step. Third, cuZK reduces the latency overhead caused by CPU-GPU data transfer (DT) by 1) reducing redundant data transfer and 2) overlapping data transfer and device computation with the multi-streaming technique. We design a series of evaluation schemes for cuZK. The evaluation results show that our MSM module provides over 2.08× (up to 2.63×) speedup versus the state-of-the-art GPU implementation. cuZK achieves over 2.65× (up to 4.47×) speedup on standard benchmarks and 2.18× speedup on a GPU-accelerated cryptocurrency application, Filecoin.

We show how to generically improve the succinctness of non-interactive publicly verifiable batch argument ($\mathsf{BARG}$) systems. In particular, we show (under a mild additional assumption) how to convert a $\mathsf{BARG}$ that generates proofs of length $\mathsf{poly} (m)\cdot k^{1-\epsilon}$, where $m$ is the length of a single instance and $k$ is the number of instances being batched, into one that generates proofs of length $\mathsf{poly} (m)\cdot \mathsf{poly} \log k$, which is the gold standard for succinctness of $\mathsf{BARG}$s. By prior work, such $\mathsf{BARG}$s imply the existence of $\mathsf{SNARG}$s for deterministic time $T$ computation with optimal succinctness $\mathsf{poly}\log T$. Our result reduces the long-standing challenge of building publicly-verifiable delegation schemes to a much easier problem: building a batch argument system that beats the trivial construction. It also immediately implies new constructions of $\mathsf{BARG}$s and $\mathsf{SNARG}$s with polylogarithmic succinctness based on either bilinear maps or a combination of the $\mathsf{DDH}$ and $\mathsf{QR}$ assumptions. Along the way, we prove an equivalence between $\mathsf{BARG}$s and a new notion of $\mathsf{SNARG}$s for (deterministic) $\mathsf{RAM}$ computations that we call ``flexible $\mathsf{RAM}$ $\mathsf{SNARG}$s with partial input soundness." This is the first demonstration that $\mathsf{SNARG}$s for deterministic computation (of any kind) imply $\mathsf{BARG}$s. Our $\mathsf{RAM}$ $\mathsf{SNARG}$ notion is of independent interest and has already been used in a recent work on constructing rate-1 $\mathsf{BARG}$s (Devadas et. al. FOCS 2022).

We introduce a new direction for post-quantum key exchange based on the multiple modular subset product with errors problem.

Gordon and Katz, in "Partial Fairness in Secure Two-Party Computation", present a protocol for two-party computation with partial fairness which depends on presumptions on the size of the input or output of the functionality. They also show that for some other functionalities, this notion of partial fairness is impossible to achieve. In this work, we get around this impossibility result using verifiable delay functions, a primitive which brings in an assumption on the inability of an adversary to compute a certain function in a specified time. We present a gadget using VDFs which allows for any MPC to be carried out with ≈ 1/R partial fairness, where R is the number of communication rounds.

In this work we investigate the asymptotically best-possible succinctness and efficiency of functional encryption (FE) and attribute-based encryption (ABE), focusing on simultaneously minimizing the sizes of secret keys and ciphertexts and the decryption time. To this end, we consider the notion of partially hiding functional encryption (PHFE) that captures both FE and ABE, and the most efficient computation model of random access machine (RAM). A PHFE secret key $\mathsf{sk}_f$ is tied to a function $f$, whereas a ciphertext $\mathsf{ct}_x(y)$ is tied to a public input $x$ (e.g., ABE attribute) and encrypts a private input $y$. Decryption reveals $f(x,y)$ and nothing else about $y$.

We present the first PHFE scheme for RAMs based on the necessary assumption of FE for circuits. It achieves nearly optimal succinctness and efficiency:

* The secret keys $\mathsf{sk}_f$ are of (optimal) *constant size*, independent of the description size $|f|$ of the function tied to it.

* The ciphertexts $\mathsf{ct}_x(y)$ have (nearly optimal) *rate-2* dependency on the private input length $|y|$ and (optimal) independency of the public input length $|x|$.

* Decryption is efficient, running in time linear in the instance running time $T$ of the RAM computation, in addition to the input and function sizes, i.e., ${T_{\mathsf{Dec}}=(T+|f|+|x|+|y|)\operatorname{poly}(\lambda)}$.

Our construction significantly improves upon the asymptotic efficiency of prior schemes. As a corollary, we obtain the first ABE scheme with both constant-size keys and constant-size ciphertexts, and the best-possible decryption time matching an existing lower bound.

We show barriers to further improvement on the asymptotic efficiency of (PH-)FE. We prove the first unconditional space-time trade-off for (PH-)FE. *No* secure (PH-)FE scheme can have both key size and decryption time sublinear in the function size $|f|$, and *no* secure PHFE scheme can have both ciphertext size and decryption time sublinear in the public input length $|x|$. These space-time trade-offs apply even in the simplest selective 1-key 1-ciphertext secret-key setting. Furthermore, we show a conditional barrier towards achieving the optimal decryption time ${T_{\mathsf{Dec}}=T\operatorname{poly}(\lambda)}$ — any such (PH-)FE scheme implies a primitive called secret-key doubly efficient private information retrieval (SK-DE-PIR), for which so far the only known candidates rely on new and non-standard hardness conjectures.

We present a novel approach to honest majority secure multiparty computation in the preprocessing model with information theoretic security that achieves the best online communication complexity. The online phase of our protocol requires $12$ elements in total per multiplication gate with circuit-dependent preprocessing, or $20$ elements in total with circuit-independent preprocessing. Prior works achieved linear online communication complexity in $n$, the number of parties, with the best prior existing solution involving $1.5n$ elements per multiplication gate. Only one recent work (Goyal et al, CRYPTO'22) achieves constant online communication complexity, but the constants are large ($108$ elements for passive security, and twice that for active security). That said, our protocol offers a very efficient information theoretic online phase for any number of parties. The total end-to-end communication cost with the preprocessing phase is linear in $n$, i.e., $10n + 44$, which is larger than the $4n$ complexity of the state-of-the-art protocols. The gap is not significant when the online phase must be optimized as a priority and a reasonably large number of parties is involved. Unlike previous works based on packed secret-sharing to reduce communication complexity, we further reduce the communication by avoiding the use of complex and expensive network routing or permutations tools. Furthermore, we also allow for a maximal honest majority adversary, while most previous works require the set of honest parties to be strictly larger than a majority. Our protocol is simple and offers concrete efficiency. To illustrate this we present a full-fledged implementation together with experimental results that show improvements in online phase runtimes that go up to $5\times$ in certain settings (e.g. $45$ parties, LAN network, circuit of depth $10$ with $1$M gates).

Also referred to as the Holy Grail of Cryptography, Fully Homomorphic Encryption (FHE) allows for arbitrary calculations over encrypted data. As a basic use-case, FHE enables a User to delegate a computation over her sensitive data to a semi-trusted Cloud: in such a setup, the User provides her data $x$ encrypted to the Cloud, the Cloud evaluates a function $f$ over the encrypted data without ever decrypting it, and sends the (encrypted) result back to the User, who finally decrypts it and obtains the desired value $f(x)$. However, even after more than twelve years of advances in this field, FHE schemes are still fairly slow in evaluation, therefore any optimization is welcome.

Among existing FHE schemes, in this contribution we focus on the TFHE Scheme by Chillotti et al., which currently achieves the best evaluation times for generic functions. To be instantiated, TFHE however requires an extensive set of parameters. These parameters affect several aspects, including but not limited to the cleartext size, the bit-security level, the probability of errors and also the evaluation time. We propose, implement and evaluate a (semi-)automated approach to generate a set of TFHE parameters with particular respect to the evaluation time, given just the desired security level, cleartext precision, and a parameter that relates to the properties of the evaluated function $f$. With our tool, we re-generate some of the existing TFHE parameters, while achieving up to 39% better execution times in an equivalent setup.

Most cryptographic protocols use cryptographic hash functions as a building block. The security analyses of these protocols typically assume that the hash functions are perfect (such as in the random oracle model). However, in practice, most widely deployed hash functions are far from perfect -- and as a result, the analysis may miss attacks that exploit the gap between the model and the actual hash function used.

We develop the first methodology to systematically discover attacks on security protocols that exploit weaknesses in widely deployed hash functions. We achieve this by revisiting the gap between theoretical properties of hash functions and the weaknesses of real-world hash functions, from which we develop a lattice of threat models. For all of these threat models, we develop fine-grained symbolic models.

Our methodology's fine-grained models cannot be directly encoded in existing state-of-the-art analysis tools by just using their equational reasoning. We therefore develop extensions for the two leading tools, Tamarin and Proverif. In extensive case studies using our methodology, the extended tools rediscover all attacks that were previously reported for these protocols and discover several new variants.

Motivated by new applications such as secure Multi-Party Computation (MPC), Homomorphic Encryption (HE), and Zero-Knowledge proofs (ZK), many MPC-, HE- and ZK-friendly symmetric-key primitives that minimize the number of multiplications over $\mathbb F_p$ for a large prime $p$ have been recently proposed in the literature. These symmetric primitive are usually defined via invertible functions, including (i) Feistel and Lai--Massey schemes and (ii) SPN constructions instantiated with invertible non-linear S-Boxes (as invertible power maps $x\mapsto x^d$). However, the ``invertibility'' property is actually never required in any of the mentioned applications.

In this paper, we discuss the possibility to set up MPC-/HE-/ZK-friendly symmetric primitives instantiated with non-invertible weak bijective functions. With respect to one-to-one correspondence functions, any output of a weak bijective function admits at most two pre-images. The simplest example of such function is the square map over $\mathbb F_p$ for a prime $p\ge 3$, for which $x^2 = (-x)^2$. When working over $\mathbb F_p^n$ for $n\gg 1$, a weak bijective function can be set up by re-considering the recent results of Grassi, Onofri, Pedicini and Sozzi as starting point. Given a quadratic local map $F:\mathbb F_p^2 \rightarrow \mathbb F_p$, they proved that the non-linear function over $\mathbb F_p^n$ for $n\ge 3$ defined as $\mathcal S_F(x_0, x_1, \ldots, x_{n-1}) = y_0\| y_1\| \ldots \| y_{n-1}$ where $y_i := F(x_i, x_{i+1})$ is never invertible. Here, we prove that -- the quadratic function $F:\mathbb F_p^2 \rightarrow \mathbb F_p$ that minimizes the probability of having a collision for $\mathcal S_F$ over $\mathbb F_p^n$ is of the form $F(x_0, x_1) = x_0^2 + x_1$ (or equivalent); -- the function $\mathcal S_F$ over $\mathbb F_p^n$ defined as before via $F(x_0, x_1) = x_0^2 + x_1$ (or equivalent) is weak bijective.

As concrete applications, we propose modified versions of the MPC-friendly schemes MiMC, HadesMiMC, and (partially of) Hydra, and of the HE-friendly schemes Masta, Pasta, and Rubato. By instantiating them with the weak bijective quadratic functions proposed in this paper, we are able to improve the security and/or the performances in the target applications/protocols.

We propose the multiple modular subset product with errors problem over unique factorization domains and give search-to-decision reduction as well as average-case-solution to worst-case-solution reduction for it.

Decentralized multi-authority attribute-based encryption (MA-ABE) is a distributed generalization of standard (ciphertext-policy) attribute-based encryption where there is no trusted central authority: any party can become an authority and issue private keys, and there is no requirement for any global coordination other than the creation of an initial set of common reference parameters.

We present the first multi-authority attribute-based encryption schemes that are provably fully-adaptively secure. Namely, our construction is secure against an attacker that may corrupt some of the authorities as well as perform key queries adaptively throughout the life-time of the system. Our main construction relies on a prime order bilinear group where the $k$-linear assumption holds as well as on a random oracle. Along the way, we present a conceptually simpler construction relying on a composite order bilinear group with standard subgroup decision assumptions as well as on a random oracle.

Prior to this work, there was no construction that could resist adaptive corruptions of authorities, no matter the assumptions used. In fact, we point out that even standard complexity leveraging style arguments do not work in the multi-authority setting.

We give a probabilistic polynomial time algorithm for high F_ell-rank subset product problem over the order O_K of any algebraic field K with O_K a principal ideal domain and the ell-th power residue symbol in O_K polynomial time computable, for some rational prime ell.

In this paper we introduce dCommon - auditable and programmable MPC as a service for solving multichain governance coordination problems throughout DeFi and Web3; Along with its on-chain part Common Interest Protocol (CIP) - an autonomous and immutable registry smart contract suite. CIP enables arbitrary business logic for off-chain computations using dCommon’s network/subnetworks with Ethereum smart contracts. In Stakehouse, CIP facilitates a trustless recovery of signing keys and key management for validator owners on demand. The paper elucidates a formal overview of the MPC system cryptography mechanics and its smart contract business logic for the Stakehouse CIP (SH-CIP) application implementation.

It is well-known that the subset product problem is NP-hard. We give a probabilistic polynomial time algorithm for the special case of high F_2-rank.

We give a construction of an efficient one-out-of-many proof system, in which a prover shows that he knows the pre-image for one element in a set, based on the hardness of lattice problems. The construction employs the recent zero-knowledge framework of Lyubashevsky et al. (Crypto 2022) together with an improved, over prior lattice-based one-out-of-many proofs, recursive procedure, and a novel rejection sampling proof that allows to use the efficient bimodal rejection sampling throughout the protocol.

Using these new primitives and techniques, we give instantiations of the most compact lattice-based ring and group signatures schemes. The improvement in signature sizes over prior works ranges between $25\%$ and $2$X. Perhaps of even more significance, the size of the user public keys, which need to be stored somewhere publicly accessible in order for ring signatures to be meaningful, is reduced by factors ranging from $7$X to $15$X. In what could be of independent interest, we also provide noticeably improved proofs for integer relations which, together with one-out-of-many proofs are key components of confidential payment systems.

In this note, we introduce a class of card-based protocols called single-shuffle full-open (SSFO) protocols and show that any SSFO protocol for a function $f: \{0,1\}^n \rightarrow [d]$ using $k$ cards is generically converted to a private simultaneous messages (PSM) protocol for $f$ with $(nk)$-bit communication. As an example application, we obtain an 18-bit PSM protocol for the three-bit equality function from the six-card trick (Heather-Schneider-Teague, Formal Aspects of Computing 2014), which is an SSFO protocol in our terminology. We then generalize this result to another class of protocols which we name single-shuffle single-branch (SSSB) protocols, which contains SSFO protocols as a subclass. As an example application, we obtain an 8-bit PSM protocol for the two-bit AND function from the four-card trick (Mizuki-Kumamoto-Sone, ASIACRYPT 2012), which is an SSSB protocol in our terminology.

It has been half a century since the first several NP-complete problems were discovered by Cook, Karp and Levin in the early 1970s. Till today, thousands of NP-complete problems have been found. Most of them are of combinatorial flavor. We discover new possibilities in purer mathematics and introduce more structures to the theory of computation. We propose a family of abstract problems related to the subset product problem. To describe hardness of abstract problems, we propose a new hardness notion called global-case hardness, which is stronger than worst-case hardness and incomparable with average-case hardness. It is about whether all prespecified subproblems of a problem are NP-hard. We prove that our problems are generally NP-hard in all/a wide range of unique factorization domains with efficient multiplication or all/a wide range of ideal class groups of Dedekind domains with efficient ideal multiplication.

The IT University of Copenhagen is searching a PhD candidate within Machine Learning for Eye Information privacy and security as part of the European Training Network EYES4ICU on Eyes for Information, Communication, and Understanding. The PhD project aims to identify sensitive eye information and develop methods for legal-compliance and safe access control and “private” data control using Eye Information. The goal is to work towards a fully GDPR (General Data Protection Regulation) compliant Eye Information pipeline that balances utility and security for everyday use of Eye information (e.g., such as in schools, and clinical settings).

The successful candidate should have a good background in one or more of the following: machine learning, statistics and computer science. Strong programming and mathematical skills Ideally also have a knowledge of and desire to work with eye tracking, human-machine interfaces, cognitive modelling, security/privacy, federated learning, and cryptographic protocols. You are enthusiastic about traveling for research conferences, PhD schools, and for internships with partners in different countries, e.g., Poland.

Benefits include: a 3-year employment contract with a competitive salary and additional family allowance (if married or having dependent children); access to high quality public education and healthcare in Denmark; budget for work-related travel, books, conferences and workshops etc.; Connections to potential employers in Europe; A rich and versatile PhD program with diverse educational modules, including mentorship, summer and winter schools, workshops... lots of fun!

Closing date for applications:

Contact: Dan Witzner

More information: https://candidate.hr-manager.net/ApplicationInit.aspx?cid=119&ProjectId=181482&DepartmentId=3439&MediaId=1282