International Association
for Cryptologic Research

In this paper, we study the compartment-based and hierarchical delegation of signing power of the verifiable accountable subgroup multi-signature (vASM). ASM is a multi-signature in which the participants are accountable for the resulting signature, and the number of participants is not fixed. After Micali et al.’s and Boneh et al.’s ASM schemes, the verifiable-ASM (vASM) scheme with a verifiable group setup and more efficient verification phase was proposed recently. The verifiable group setup in vASM verifies the participants at the group setup phase. In this work, we show that the vASM scheme can also be considered as a proxy signature in which an authorized user (original signer, designator) delegates her signing rights to a single (or a group of) unauthorized user(s) (proxy signer). Namely, we propose four new constructions with the properties and functionalities of an ideal proxy signature and a compartment-based/hierarchical structure. In the first construction, we apply the vASM scheme recursively; in the second one, we use Shamir’s secret sharing (SSS) scheme; in the third construction, we use SSS again but in a nested fashion. In the last one, we use the hierarchical threshold secret sharing (HTSS) scheme for delegation. Then, we show the affiliation of our constructions to proxy signatures and compare our constructions with each other in terms of efficiency and security. Finally we compare the vASM scheme with the existing pairing-based proxy signature schemes.

Zero-knowledge (ZK) proof systems have emerged as a promising solution for building security-sensitive applications. However, bugs in ZK applications are extremely difficult to detect and can allow a malicious party to silently exploit the system without leaving any observable trace. This paper presents Coda, a novel statically-typed language for building zero-knowledge applications. Critically, Coda makes it possible to formally specify and statically check properties of a ZK application through a rich refinement type system. One of the key challenges in formally verifying ZK applications is that they require reasoning about polynomial equations over large prime fields that go beyond the capabilities of automated theorem provers. Coda mitigates this challenge by generating a set of Coq lemmas that can be proven in an interactive manner with the help of a tactic library. We have used Coda to re-implement 79 arithmetic circuits from widely-used Circom libraries and applications. Our evaluation shows that Coda makes it possible to specify important and formally verify correctness properties of these circuits. Our evaluation also revealed 6 previously-unknown vulnerabilities in the original Circom projects.

The Department of Computer Science invites applications for the position of
Doctoral Researcher (Research Assistant/PhD Student) in Cryptography and Complexity Theory
in the group of Professor Marc Fischlin. More information about our research is available under www.cryptoplexity.de. The starting date is as soon as possible. The initial funding for the position is for three years, but the contract should be renewable. Candidates are expected to perform scientific research in the areas of the projects, and to contribute to the teaching, research, and administrative tasks of the group.
Your Profile:
• Master’s degree (or equivalent) in Computer Science, Mathematics, or a similar discipline,
• Extensive knowledge in the areas of cryptography and IT security,
• fluent English language skills,
• experience in IT system administration is welcome.
How to Apply
• curriculum vitae, including references,
• copies of relevant diplomas and certificates,
• research statement.
TU Darmstadt is an autonomous university with broad research excellence, interdisciplinary profile and clear emphases in engineering and information and communication technology. The Department of Computer Science is one of the leading CS departments in Europe and placed regularly in the top group in nationwide rankings. In the area of Cybersecurity, TU Darmstadt is one of the leading research institutions within Europe focusing on a broad spectrum of applied and theoretical research. The services rendered as part of the positions function as the scientific qualification of the candidate. The candidates will be given the opportunity to accomplish a doctoral degree.
The application data should be bundled into a single PDF file.

Closing date for applications:

Contact: Prof. Dr. Marc Fischlin, jobs@cx.tu-darmstadt.de

More information: https://www.cryptoplexity.informatik.tu-darmstadt.de/cryptoplexity/jobs_3/index.en.jsp

We are looking for a German-speaking Research Officer Cryptology (m/f/d) in the middle of Germany starting at the earliest possible date. The most important resource for the Cyberagentur are satisfied, motivated and hard-working employees. Our goal is to offer an inspiring and creative environment in a great team. Our mission is to identify tomorrow’s topics in cyber security and related key technologies. We fund and supervise exciting and outstanding research projects. By doing so, we support Germany’s future technological leadership as well as the nation’s digital sovereignty. Modern cryptographic methods are essential building blocks of the cyber security for tomorrow and beyond. At the Cyberagentur, you will work on current topics such as encrypted computing, zero trust and holistic authentication. With your team, you will accompany attractive calls for tenders in the field of cryptology research, be an essential part of the evaluation of research projects, and accompany commissioned research projects from initiation to completion, thus ensuring the quality and usability of the results. Internally, you will contribute to our knowledge management in this domain. Furthermore, you will take appropriate measures to ensure that Germany remains an attractive location for research in cryptology.

Closing date for applications:

Contact: Matthias Strauß, Head of HR, bewerbung@cyberagentur.de

More information: https://app.connectoor.de/jobview?jobid=62d506deddb233fc338b4579

Monash cybersecurity group has several openings for PhD positions. The topics of interest are

1. Post-quantum cryptography (based on lattices and/or hash) and its applications e.g. to blockchain
2. Zero-knowledge proofs and their applications e.g. to blockchain
3. Blockchain protocols more broadly

We provide

1. highly competitive tuition fee and stipend scholarships
2. opportunities to collaborate with leading academic and industry experts in the related areas
3. opportunities to participate in international grant-funded projects
4. collaborative and friendly research environment
5. an opportunity to live/study in one of the most liveable and safest cities in the world

The positions will be filled as soon as suitable candidates are found.

Requirements. A strong mathematical background is required, but a strong cryptography background is not necessarily a must (but it’s of course a plus). Some knowledge/experience in coding (for example, Python, C/C++, SageMath) is also a plus. Candidates must have completed (or be about to complete within the next 6 months) a significant research component either as part of their undergraduate (honours) degree or masters degree. They should have excellent English verbal and written communication skills.

How to apply. please first refer to https://mfesgin.github.io/supervision/ for more information. Then, please email your CV and bachelor/master transcripts with the subject line "Prospective PhD Student - Your Name"

Closing date for applications:

Contact: Muhammed Esgin (firstname.lastname@monash.edu)

More information: https://mfesgin.github.io/supervision/

We are looking for a Research Engineer with knowledge in the field of implementing cryptography. The successful candidate will have knowledge of digital design and embedded systems applied to cryptography implementations, Side-Channel Attacks and Fault Analyses. The candidate must be eligible to work in the EU.

Closing date for applications:

Contact: ARQUIMEA web page

More information: https://arquimea.bamboohr.com/careers/240

As the technical feasibility of a quantum computer becomes more and more likely, post-quantum cryptography algorithms are receiving particular attention in recent years. Among them, code-based cryptosystems were first considered unsuited for hardware and embedded software implementations because of their very large key sizes. However, recent work has shown that such implementations are practical, which also makes them susceptible to physical attacks. In this article, we propose a horizontal correlation attack on the Classic McEliece cryptosystem, more precisely on the matrix-vector multiplication over $\mathbb{F}_2$ that computes the shared key in the encapsulation process. The attack is applicable in the broader context of Niederreiter-like code-based cryptosystems and is independent of the code structure, i.e. it does not need to exploit any particular structure in the parity check matrix. Instead, we take advantage of the constant time property of the matrix-vector multiplication over $\mathbb{F}_2$. We extend the feasibility of the basic attack by leveraging information-set decoding methods and carry it out successfully on the reference embedded software implementation. Interestingly, we highlight that implementation choices, like the word size or the compilation options, play a crucial role in the attack success, and even contradict the theoretical analysis.

The Universal Thresholdizer (CRYPTO'18) is a cryptographic scheme that facilitates the transformation of any cryptosystem into a threshold cryptosystem, making it a versatile tool for threshold cryptography. For instance, this primitive enables the black-box construction of a one-round threshold signature scheme based on the Learning with Error problem, as well as a one-round threshold chosen ciphertext attack-secure public key encryption, by being combined with non-threshold schemes.

The compiler is constructed in a modular fashion and includes a compact threshold fully homomorphic encryption, a non-interactive zero-knowledge proof with preprocessing, and a non-interactive commitment. An instantiation of the Universal Thresholdizer can be achieved through the construction of a compact threshold fully homomorphic encryption. Currently, there are two threshold fully homomorphic encryptions based on linear secret sharing, with one using Shamir's secret sharing and the other using the $\{0,1\}$-linear secret sharing scheme ($\{0,1\}$-LSSS). The former fails to achieve compactness as the size of its ciphertext is $O(N\log N)$, where $N$ is the number of participants in the distributed system. Meanwhile, the latter provides compactness, with a ciphertext size of $O(\log N)$, but requires $O(N^{4.3})$ share keys on each party, leading to high communication costs.

In this paper, we propose a communication-efficient Universal Thresholdizer by revisiting the threshold fully homomorphic encryption. Our scheme reduces the number of share keys required on each party to $O(N^{2+o(1)})$ while preserving the ciphertext size of $O(\log N)$. To achieve this, we introduce a new linear secret sharing scheme called TreeSSS, which requires a smaller number of shared keys and satisfies compactness. As a result, the Threshold Fully Homomorphic Encryption underlying our linear secret sharing scheme has fewer shared keys during the setup algorithm and reduced communication costs during the partial decryption algorithm. Moreover, the construction of a Universal Thresholdizer can be achieved through the use of TreeSSS, as it reduces the number of shared keys compared to previous constructions. Additionally, TreeSSS may be of independent interest, as it improves the efficiency in terms of communication costs when used to replace $\{0,1\}$-LSSS.

Fully Homomorphic Encryption enables the evaluation of an arbitrary computable function over encrypted data. Among all such functions, particular interest goes for integer arithmetics. In this paper, we present a bundle of methods for fast arithmetic operations over encrypted data: addition/subtraction, multiplication, and some of their special cases. On top of that, we propose techniques for signum, maximum, and rounding. All methods are specifically tailored for computations with data encrypted with the TFHE scheme (Chillotti et al., Asiacrypt '16) and we mainly focus on parallelization of non-linear homomorphic operations, which are the most expensive ones. This way, evaluation times can be reduced significantly, provided that sufficient parallel resources are available. We implement all presented methods in the Parmesan Library and we provide an experimental evaluation. Compared to integer arithmetics of the Concrete Library, we achieve considerable speedups for all comparable operations. Major speedups are achieved for the multiplication of an encrypted integer by a cleartext one, where we employ special addition-subtraction chains, which save a vast amount of homomorphic operations.

Two fundamental properties of quantum states that quantum information theory explores are pseudorandomness and provability of destruction. We introduce the notion of quantum pseudorandom states with proofs of destruction (PRSPD) that combines both these properties. Like standard pseudorandom states (PRS), these are efficiently generated quantum states that are indistinguishable from random, but they can also be measured to create a classical string. This string is verifiable (given the secret key) and certifies that the state has been destructed.

We show that, similarly to PRS, PRSPD can be constructed from any post-quantum one-way function. As far as the authors are aware, this is the first construction of a family of states that satisfies both pseudorandomness and provability of destruction. We show that many cryptographic applications that were shown based on PRS variants using quantum communication can be based on (variants of) PRSPD using only classical communication. This includes symmetric encryption, message authentication, one-time signatures, commitments, and classically verifiable private quantum coins.

In this paper we introduce a multistep generalization of the guess-and-determine or hybrid strategy for solving a system of multivariate polynomial equations over a finite field. In particular, we propose performing the exhaustive evaluation of a subset of variables stepwise, that is, by incrementing the size of such subset each time that an evaluation leads to a polynomial system which is possibly unfeasible to solve. The decision about which evaluation to extend is based on a preprocessing consisting in computing an incomplete Grobner basis after the current evaluation, which possibly generates linear polynomials that are used to eliminate further variables. If the number of remaining variables in the system is deemed still too high, the evaluation is extended and the preprocessing is iterated. Otherwise, we solve the system by a Grobner basis computation.

Having in mind cryptanalytic applications, we present an implementation of this strategy in an algorithm called MultiSolve which is designed for polynomial systems having at most one solution. We prove explicit formulas for its complexity which are based on probability distributions that can be easily estimated by performing the proposed preprocessing on a testset of evaluations for different subsets of variables. We prove that an optimal complexity of MultiSolve is achieved by using a full multistep strategy with a maximum number of steps and in turn the classical guess-and-determine strategy, which essentially is a strategy consisting of a single step, is the worst choice. Finally, we extensively study the behaviour of MultiSolve when performing an algebraic attack on the well-known stream cipher Trivium.

This paper explores the design space of vector-optimized polynomial multiplications in the lattice-based key-encapsulation mechanisms NTRU and NTRU Prime. Since NTRU and NTRU Prime do not support straightforward applications of number– theoretic transforms, the state-of-the-art vector code either resorted to Toom–Cook, or introduced various techniques for coefficient ring extensions. All these techniques lead to a large number of small-degree polynomial multiplications, which is the bottleneck in our experiments. For NTRU Prime, we show how to reduce the number of small-degree polynomial multiplications to nearly 1/4 times compared to the previous vectorized code with the same functionality. Our transformations are based on careful choices of FFTs, including Good–Thomas, Rader’s, Schönhage’s, and Bruun’s FFTs. For NTRU, we show how to deploy Toom-5 with 3-bit losses. Furthermore, we show that the Toeplitz matrix–vector product naturally translates into efficient implementations with vector-by-scalar multiplication instructions which do not appear in all prior vector-optimized implementations. We choose the ARM Cortex-A72 CPU which implements the Armv8-A architecture for experiments, because of its wide uses in smartphones, and also the Neon vector instruction set implementing vector-by-scalar multiplications that do not appear in most other vector instruction sets like Intel’s AVX2. Even for platforms without vector-by-scalar multiplications, we expect significant improvements compared to the state of the art, since our transformations reduce the number of multiplication instructions by a large margin. Compared to the state-of-the-art optimized implementations, we achieve 2.18× and 6.7× faster polynomial multiplications for NTRU and NTRU Prime, respectively. For full schemes, we additionally vectorize the polynomial inversions, sorting network, and encoding/decoding subroutines in NTRU and NTRU Prime. For ntruhps2048677, we achieve 7.67×, 2.48×, and 1.77× faster key generation, encapsulation, and de- capsulation, respectively. For ntrulpr761, we achieve 3×, 2.87×, and 3.25× faster key generation, encapsulation, and decapsulation, respectively. For sntrup761, there are no previously optimized implementations and we significantly outperform the reference implementation.

We present an optimized constant-time implementation of the MAYO signature scheme on ARMv7-M. MAYO is a novel multivariate proposal based on the trapdoor function of the Unbalanced Oil and Vinegar scheme. Our implementation builds on existing techniques for UOV-based schemes and introduces a new approach for evaluating the polar forms of quadratic maps. We modify MAYO's original parameters to achieve greater benefits from the proposed optimizations, resulting in slightly larger keys and shorter signatures for the same level of security. We evaluate the optimized implementation with the new parameters on the STM32H753ZIT6 microcontroller and measure its performance for the signing and verification procedures. At NIST security level I, signing requires approximately 43M cycles, and verification requires approximately 6M cycles. Both are 2.6 times faster than the results obtained from the original parameters.

Assume that we have a group $G$ of known order $q$, in which we want to solve discrete logarithms (dlogs). In 1994, Maurer showed how to compute dlogs in $G$ in poly time given a Diffie-Hellman (DH) oracle in $G$, and an auxiliary elliptic curve $\hat E(\mathbb{F}_q)$ of smooth order. The problem of Maurer's reduction of solving dlogs via DH oracles is that no efficient algorithm for constructing such a smooth auxiliary curve is known. Thus, the implications of Maurer's approach to real-world applications remained widely unclear.

In this work, we explicitly construct smooth auxiliary curves for a dozen of mostly used, standardized elliptic curves of bit-sizes in the range $[204,256]$, including e.g., NIST P-256, Curve25519, SM2 and GOST R34.10. For all these curves we construct a corresponding cyclic auxiliary curve $\hat E(\mathbb{F}_q)$, whose order is $39$-bit smooth, i.e., its largest factor is of bit-length at most $39$ bits.

This in turn allows us to compute for all divisors of the order of $\hat E(\mathbb{F}_q)$ exhaustively a codebook for all discrete logarithms. As a consequence, dlogs on $\hat E(\mathbb{F}_q)$ can efficiently be computed in a matter of seconds. Our resulting codebook sizes are less than 29 TByte, and fit on our hard disk.

We also construct auxiliary curves for NIST P-384 and NIST P-521 with a $65$-bit and $110$-bit smooth order.

Further, we provide an efficient implementation of Maurer's reduction from the dlog computation in $G$ with order $q$ to the dlog computation on its auxiliary curve $\hat E(\mathbb{F}_q)$. Let us provide a flavor of our results, e.g., when $G$ is the NIST P-256 group, the results for other curves are similar. With the help of our codebook for the auxiliary curve $\hat E(\mathbb{F}_q)$, and less than 24,000 calls to a DH oracle in $G$ (that we simulate), we can solve discrete logarithms on NIST P-256 in around 30 secs.

From a security perspective, our results show that for current elliptic curve standards the difficulty of solving DH is practically tightly related to the difficulty of computing dlogs. Namely, unless dlogs are easy to compute on these curves $G$, we provide a very concrete security guarantee that DH in $G$ must also be hard.

From a cryptanalytic perspective, our results show a way to efficiently solve discrete logarithms in the presence of a DH oracle. Thus, if practical implementations unintentionally provide a DH oracle, dlog computations actually become surprisingly easy.

We present a general compiler to add the publicly verifiable deletion property for various cryptographic primitives including public key encryption, attribute-based encryption, and quantum fully homomorphic encryption. Our compiler only uses one-way functions, or more generally hard quantum planted problems for NP, which are implied by one-way functions. It relies on minimal assumptions and enables us to add the publicly verifiable deletion property with no additional assumption for the above primitives. Previously, such a compiler needs additional assumptions such as injective trapdoor one-way functions or pseudorandom group actions [Bartusek-Khurana-Poremba, ePrint:2023/370]. Technically, we upgrade an existing compiler for privately verifiable deletion [Bartusek-Khurana, ePrint:2022/1178] to achieve publicly verifiable deletion by using digital signatures.

POSEIDON is a hash function proposed by Grassi et al. in the USENIX Security ’21 conference. Due to its impressive efficiency and low arithmetic complexity it has garnered the attention of designers of integrity-proof systems such as SNARKS, STARKS, and Bulletproofs. In this work, we show some caveats in Poseidon’s security argument. Most notably, we extend on previous work by Sauer and quantify the rate at which the degree of regularity increases as a function of full and partial rounds. We observe that this degree grows slower than originally assumed, suggesting that there are cases where the recommended number of rounds is insufficient to meet claimed security. The findings presented in this paper are asymptotic in nature and do not affect all parameter sets equally. As a proof of concept, we present a full attack for an instance at the 1024-bit security level. We present two more parameter sets at the 512- and 384-bit security levels where the original security argument does not hold, but for which we were not able to demonstrate a full attack due to other aspects of the design. We were not able to find parameter sets in the 128- and 256-bit levels that are vulnerable

We are proud to announce the winners of the 2023 IACR Test-of-Time Award for Eurocrypt. The IACR Test-of-Time Award honors papers published at the 3 IACR flagship conferences 15 years ago which have had a lasting impact on the field. This year, we will be announcing the winners for each conference separately.

The Test-of-Time award for Eurocrypt 2008 is awarded to the following two papers:

Efficient Non-interactive Proof Systems for Bilinear Groups, by Jens Groth and Amit Sahai, for providing efficient Groth-Sahai proofs that have given rise to many applications including succinct non-interactive arguments.

On the Indifferentiability of the Sponge Construction, by Guido Bertoni, Joan Daemen, Michael Peeters and Gilles Van Assche, for introducing the Sponge construction that is deployed in world-wide standards such as SHA-3 and ASCON.

For more information, see https://www.iacr.org/testoftime.

Congratulations to all winners!

We present new protocols for *Asynchronous Verifiable Secret Sharing* for Shamir (i.e., threshold $t

Gadget decomposition is widely used in lattice based cryptography, especially homomorphic encryption (HE) to keep the noise growth slow. If it is randomized following a subgaussian distribution, it is called subgaussian (gadget) decomposition which guarantees that we can bound the noise contained in ciphertexts by its variance. This gives tighter and cleaner noise bound in average case, instead of the use of its norm. Even though there are few attempts to build efficient such algorithms, most of them are still not practical enough to be applied to homomorphic encryption schemes due to somewhat high overhead compared to the deterministic decomposition. Furthermore, there has been no detailed analysis of existing works. Therefore, HE schemes use the deterministic decomposition algorithm and rely on a Heuristic assumption that every output element follows a subgaussian distribution independently.

In this work, we introduce a new practical subgaussian gadget decomposition algorithm which has the least overhead (less than 14\%) among existing works for certain parameter sets, by combining two previous works. In other words, we bring an existing technique based on an uniform distribution to a simpler and faster design (PKC' 22) to exploit parallel computation, which allows to skip expensive parts due to pre-computation, resulting in even simpler and faster algorithm. When the modulus is large (over 100-bit), our algorithm is not always faster than the other similar work. Therefore, we give a detailed comparison, even for large modulus, with all the competitive algorithms for applications to choose the best algorithm for their choice of parameters.

Anonymous message delivery, as in private communication and privacy-preserving blockchain applications, ought to protect recipient metadata: a message should not be inadvertently linkable to its destination. But in this case, how can messages be delivered to each recipient, without every recipient scanning all the messages? Recent work constructed Oblivious Message Retrieval (OMR) protocols that outsource this job to untrusted servers in a privacy-preserving manner.

We consider the case of group messaging, where each message may have multiple recipients (e.g., in a group chat or blockchain transaction). A direct use of prior OMR protocols in the group setting increases the servers' work linearly in the group size, rendering it prohibitively costly for large groups.

We thus devise new protocols where the servers' cost grows very slowly with the group size, while recipients' cost is low and independent of the group size. Our approach uses Fully Homomorphic Encryption and other lattice-based techniques, building on and improving on prior work. The efficient handling of groups is attained by encoding multiple recipient-specific clues into a single polynomial or multilinear function that can be efficiently evaluated under FHE, and via preprocessing and amortization techniques.

We formally study several variants of Group Oblivious Message Retrieval (GOMR), and describe corresponding GOMR protocols.

Our implementation and benchmarks show, for parameters of interest, cost reductions of orders of magnitude compared to prior schemes. For example, the servers' cost is $3.36 per million messages scanned, where each message may address up to 15 recipients.