International Association
for Cryptologic Research

We propose a new identification scheme and a new signature scheme from the multiple modular subset product with errors problem; as well as a new identification scheme and a new signature scheme from the multiple modular subset sum with errors problem.

Several privacy-preserving analytics frameworks have been proposed that use trusted execution environments (TEEs) like Intel SGX. Such frameworks often use compaction and shuffling as core primitives. However, due to advances in TEE side-channel attacks, these primitives, and the applications that use them, should be _fully oblivious_; that is, perform instruction sequences and memory accesses that do not depend on the secret inputs. Such obliviousness would eliminate the threat of leaking private information through memory or timing side channels, but achieving it naively can result in a significant performance cost.

In this work, we present fast, fully oblivious algorithms for compaction and shuffling. We implement and evaluate our designs to show that they are practical and outperform the state of the art. Our oblivious compaction algorithm, ORCompact, is always faster than the best alternative and can yield up to a 5x performance improvement. For oblivious shuffling, we provide two novel algorithms: ORShuffle and BORPStream. ORShuffle outperforms prior fully oblivious shuffles in all experiments, and it provides the largest speed increases—up to 1.8x—when shuffling a large number of small items. BORPStream outperforms all other algorithms when shuffling a large number of large items, with a speedup of up to 1.4x in such cases. It can obtain even larger performance improvements in application settings where the items to shuffle arrive incrementally over time, obtaining a speedup of as much as 4.2x. We additionally give parallel versions of all of our algorithms, prove that they have low parallel step complexity, and experimentally show a 5–6x speedup on an 8-core processor.

Finally, ours is the first work with the explicit goal of ensuring full obliviousness of complex functionalities down to the implementation level. To this end, we design Fully Oblivious Assembly Verifier (FOAV), a tool that verifies the binary has no secret-dependent conditional branches.

The classic MPC protocol for Schnorr Signatures (Classic Schnorr) consists of a simple three-round process for the signing operation, and the protocol is essentially as efficient as the underlying non-MPC scheme (modulo the round-complexity). In particular, Classic Schnorr does not contain any ZK proofs, not even for key-generation, and the only cryptographic “machinery” it uses is the underlying hash function. In this paper, we show that Classic Schnorr UC realizes the ideal threshold-signature functionality of Canetti, Makriyannis, and Peled (Manuscript’20) against adaptive adversaries for any number of corrupted parties. Furthermore, (1) the protocol does not impose any restrictions on the number of concurrent signings, (2) the protocol naturally supports identifiable abort, and (3) the protocol can be extended to achieve proactive security, almost for free. So, the main novelty of our work is showing that Classic Schnorr achieves the utmost security as a threshold-signatures protocol. We hold that the achieved security is truly surprising given how simple the protocol is.

On a technical level, we show the above by extending the proof technique of Canetti, Makriyannis, and Peled, recently generalized by Blokh, Makriyannis, and Peled (Manuscript’22) for arbitrary threshold-signature schemes, whereby the indistinguishability of the UC simulation is reduced to the unforgeability of the underlying signature scheme. Our results hold in the random oracle model under the discrete logarithm assumption.

Functional Commitments (FC) allow one to reveal functions of committed data in a succinct and verifiable way. In this paper we put forward the notion of additive-homomorphic FC and show two efficient, pairing-based, realizations of this primitive supporting multivariate polynomials of constant degree and monotone span programs, respectively. We also show applications of the new primitive in the contexts of homomorphic signatures: we show that additive-homomorphic FCs can be used to realize homomorphic signatures (supporting the same class of functionalities as the underlying FC) in a simple and elegant way. Using our new FCs as underlying building blocks, this leads to the (seemingly) first expressive realizations of multi-input homomorphic signatures not relying on lattices or multilinear maps.

The Learning with Errors (LWE) problem is one of the most prominent problems in lattice-based cryptography. Many practical LWE-based schemes, including Fully Homomorphic encryption (FHE), use sparse ternary secret for the sake of efficiency. Several (hybrid) attacks have been proposed that benefit from such sparseness, thus researchers believe the security of the schemes with sparse ternary secrets is not well-understood yet. Recently, May [Crypto 2021] proposed an efficient meet-in-the-middle attack named Meet-LWE for LWE with ternary se- cret, which significantly improves Odlyzko’s algorithm. In this work, we generalize May’s Meet-LWE and then introduce a new hybrid attack which combines Meet-LWE with lattice dual attack. We implement our algorithm to FHE-type parameters of LWE problem and compare it with the previous hybrid dual attacks. The result shows that our attack outperforms other attacks in a large range of parameters. We note that our attack has no impact on the LWE-based schemes in the PQC Standardization held by NIST as their secrets are not sparse and/or ternary.

We propose new time-memory trade-offs for the random subset sum problem defined on $(a_1,\ldots,a_n,t)$ over $\mathbb{Z}_{2^n}$.

Our trade-offs yield significant running time improvements for every fixed memory limit $M\geq2^{0.091n}$. Furthermore, we interpolate to the running times of the fastest known algorithms when memory is not limited. Technically, our design introduces a pruning strategy to the construction by Becker-Coron-Joux (BCJ) that allows for an exponentially small success probability. We compensate for this reduced probability by multiple randomized executions. Our main improvement stems from the clever reuse of parts of the computation in subsequent executions to reduce the time complexity per iteration.

As an application of our construction, we derive the first non-trivial time-memory trade-offs for Information Set Decoding (ISD) algorithms. Our new algorithms improve on previous (implicit) trade-offs asymptotically as well as practically. Moreover, our optimized implementation also improves on running time, due to reduced memory access costs. We demonstrate this by obtaining a new record computation in decoding quasi-cyclic codes (QC-3138). Using our newly obtained data points we then extrapolate the hardness of suggested parameter sets for the NIST PQC fourth round candidates McEliece, BIKE and HQC, lowering previous estimates by up to 6 bits and further increasing their reliability.

The syndrome decoding problem lies at the heart of code-based cryptographic constructions. Information Set Decoding (ISD) algorithms are commonly used to assess the security of these systems. The most efficient ISD algorithms rely heavily on nearest neighbor search techniques. However, the runtime result of the fastest known ISD algorithm by Both-May (PQCrypto '17) was recently challenged by Carrier et al. (Asiacrypt '22), which introduce themselves a new technique called RLPN decoding which yields improvements over ISD for codes with small rates $\frac{k}{n}\leq 0.3$.

In this work we first revisit the Both-May algorithm, by giving a clean exposition and a corrected analysis. We confirm the claim by Carrier et al. that the initial analysis is flawed. However, we find that the algorithm still (slightly) improves on time complexity and significantly improves on memory complexity over previous algorithms. Our first main contribution is therefore to set the correct baseline for further improvements.

As a second main contribution we then show how to improve on the Both-May algorithm, lowering the worst case running time in the full distance decoding setting to $2^{0.0948n}$. We obtain even higher time complexity gains for small rates, shifting the break even point with RLPN decoding to rate $\frac{k}{n}=0.25$. Moreover, we significantly improve on memory for all rates $\frac{k}{n}<0.5$. We obtain our improvement by introducing a novel technique to combine the list construction step and the list filtering step commonly applied by ISD algorithms. Therefore we treat the nearest neighbor routine in a non-blackbox fashion which allows us to embed the filtering into the nearest neighbor search. In this context we introduce the fixed-weight nearest neighbor problem, and propose a first algorithm to solve this problem. Besides resulting in an improved decoding algorithm this opens the direction for further improvements, since any faster algorithm for solving this fixed-weight nearest neighbor variant is likely to lead to further improvements of our ISD algorithm.

We give a new post-quantum public key cryptosystem from the multiple modular subset product with errors problem.

Non-malleable codes are a natural relaxation of error correction and error detection codes applicable in scenarios where error-correction or error-detection is impossible.

Over the last decade, non-malleable codes have been studied for a wide variety of tampering families. Among the most well studied of these is the split-state family of tampering channels, where the codeword is split into two or more parts and each part is tampered independently.

We survey various constructions and applications of non-malleable codes in the split-state model.

We have a senior/staff cryptography researcher position available in the Blockchain Security team at Coinbase.

Full description available here:

• Senior role: https://www.coinbase.com/careers/positions/4582729
• Staff role: https://www.coinbase.com/careers/positions/4586906

Please reach out to me at [s] [last name] @pm.me if you have any questions.

Closing date for applications:

Contact: Shashank Agrawal

More information: https://www.coinbase.com/careers/positions/4582729

Aarhus University, Denmark - an international top-100 University - has made an ambitious strategic investment in a recruitment plan to radically expand the Department of Computer Science. For this call, we encourage applicants that can contribute to our basic and strategic research in Cryptography and Security. Therefore, the department invites applications from candidates that are driven by excellence in research and teaching as well as external collaboration on societal challenges. The successful candidate will have the opportunity to contribute to and shape the research and teaching as well as the industrial and societal collaboration associated with the department expansion. The position is open from February 1st, 2023. The department has research groups within "Algorithms, Data Structures and Foundations for Machine Learning", Data- Intensive Systems", “Computational Complexity and Game Theory”, "Cryptography and Security", "Logic and Semantics", "Ubiquitous Computing and Interaction", “Human Computer Interaction” and "Programming Languages”. This call is aimed at strengthening and expanding our strategic development of excellent research in Cryptography and Security including, for instance, public-key cryptography, cryptographic protocols, secure computation, post-quantum cryptography and quantum cryptography. Applicants for Full professor positions are expected to meet the criteria for full professors. All applicants are requested to include a link to their Google Scholar profile in their application. Your application must be uploaded together with letters of recommendation. As department we wish to build a computer science research and study environment with equality and diversity as a core value for recruitment as well as for daily study and work life. If you have visions for or experience with activities or initiatives to support such a core value in a computer science context, we encourage you to describe them in your application.

Closing date for applications:

Contact: Head of Department, Professor Kaj Grønbæk kgronbak@cs.au.dk.

More information: https://www.au.dk/om/stillinger/job/full-professorship-in-cryptography-and-security-at-computer-science-aarhus-university

The Department of Mathematical Sciences at the University of Alabama in Huntsville invites applications for a tenure-track/tenure position at the Assistant/Associate Professor level in Applied Algebra (Cryptography/Number Theory) to begin in August 2023. Applicants must have a Ph.D. in mathematics completed by the appointment date. Preference will be given to applicants who demonstrate excellence in teaching and research.

The Department of Mathematical Sciences offers academic programs that lead to Bachelor's and Master's degrees in Mathematics and a Doctor of Philosophy degree in Applied Mathematics. It has over 18 full-time faculty members whose expertise covers the essential topics in applied mathematics. The successful applicant will be expected to teach undergraduate and graduate courses, advise undergraduate and graduate students, and engage in funded research.

ABOUT THE UNIVERSITY: UAH is a Very High Research Activity (R1) university that provides academic and research programs in the Colleges of Arts, Humanities, and Social Sciences, Business, Education, Engineering, Nursing, Professional Studies, and Science. Huntsville has one of the greatest per capita incomes and living standards in the Southeast. It houses NASA's Marshall Space Flight Hub and is a national aerospace and high technology research center.

APPLICATION PROCEDURE AND DEADLINE: To apply for the position, please submit the following required application materials electronically no later than January 28, 2023: 1) Cover letter 2) Curriculum vitae 3) Research statement 4) Teaching statement 5) Transcripts 6) Three reference letters to the Search Committee through Dr. Toka Diagana, mathchair@uah.edu. Please refer to the log number: 23-24-583.

A formal review of the applications will begin on January 17, 2023, and continue until the position is filled.

UAH mandates that all employees maintain compliance with current federal regulations.

The University of Alabama in Huntsville is an affirmative action/equal opportunity employer of minorities/ females/veterans/disabled.

Closing date for applications:

Contact: Dr. Toka Diagana, e-mail: mathchair@uah.edu. Please refer to the log number: 23-24-583.

More information: https://www.uah.edu/hr/careers/faculty-careers#COS

Applications are invited for a postdoctoral research position in the Privacy and Applied Cryptography (PACY) research lab. Our activities focus on privacy-enhancing cryptographic protocols and their applications.

We are looking for a bright postdoc (or a PhD student nearing completion) with expertise in any of the following areas:

• Confidential computing (ZKP, FHE, MPC, ABC techniques)
• Distributed cryptography (key generation, signatures, encryption)
• Secure and private messaging (authentication, key exchange)
• Design of post-quantum secure cryptographic protocols

There is an opportunity to engage in current projects, collaborate with international partners, and work closely with PhD students of the PACY lab. The candidate will benefit from our modern infrastructure and availability of funds to support own research. Munich is amongst best places to live in Germany.

The position is available for immediate start, funded at federal salary levels TV-ÖD E13/14 (~50k to 65k EUR p.a. depending on qualifications and experience). Initial contract for 2 years with a possibility of extension. (Due to the nature of funding restrictions on the eligibility of some candidates may apply.)

Requirements:

• Completed PhD in cryptography, information security, computer science or mathematics.
• Alternatively, PhD students with a relevant Master degree nearing PhD completion.
• Strong background knowledge / experience in privacy-enhancing cryptography (research and development)
• Relevant publications in top cryptography / security / privacy venues
• Fluency in written and spoken English.

Applications (cover letter, CV, transcripts, contacts for references) can be emailed to the head of PACY lab, Prof. Mark Manulis, by the nominal deadline of Nov 4th, 2022. Applications will be processed as they arrive. The search will continue until the position is filled.

Closing date for applications:

Contact: Prof. Mark Manulis, mark.manulis AT unibw.de

More information: https://www.unibw.de/pacy-en/

We are looking for an internationally orientated candidate with excellent research experience and educational competence in computer science, and with extensive expertise in the dimension of research valorization. The candidate, while being strong in some subdomains of security and privacy, must at the same time be capable in building bridges between multiple disciplines and between academic research and industry adoption.

The area is interpreted broadly, and covers for example security and privacy, reliability and resilience of digital services, of software products and of internet-based systems.

Closing date for applications:

Contact: Prof. dr. ir. Wouter Joosen chair of DistriNet Wouter.Joosen@kuleuven.be +32 16 32 76 53

Prof. dr. ir. Stefan Vandewalle chair of Computer Science Stefan.Vandewalle@kuleuven.be +32 16 32 76 54

More information: https://distrinet.cs.kuleuven.be/jobs/PDF/Flyer_ZAP-2022-48_Sep22.pdf

Binary elliptic curves are elliptic curves defined over finite fields of characteristic 2. On software platforms that offer carryless multiplication opcodes (e.g. pclmul on x86), they have very good performance. However, they suffer from some drawbacks, in particular that non-supersingular binary curves have an even order, and that most known formulas for point operations have exceptional cases that are detrimental to safe implementation.

In this paper, we show how to make a prime order group abstraction out of standard binary curves. We describe a new canonical compression scheme that yields a canonical and compact encoding. We also describe complete formulas for operations on the group. The formulas have no exceptional case, and are furthermore faster than previously known complete and incomplete formulas (general point addition in cost 8M+2S+2mb on all curves, 7M+2S+2mb on half of the curves). We also show how the same formulas can be applied to computations on the entire original curve, if full backward compatibility with standard curves is needed. Finally, we implemented our method over the standard NIST curves B-233 and K-233. Our strictly constant-time code achieves generic point multiplication by a scalar on curve K-233 in as little as 29600 clock cycles on an Intel x86 CPU (Coffee Lake core).

We construct adaptively secure multiparty non-interactive key exchange (NIKE) from polynomially hard indistinguishability obfuscation and other standard assumptions. This improves on all prior such protocols, which required sub-exponential hardness. Along the way, we establish several compilers which simplify the task of constructing new multiparty NIKE protocols, and also establish a close connection with a particular type of constrained PRF.

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).