International Association
for Cryptologic Research

Widespread efforts to subvert acccess to strong cryptography has renewed interest in steganography, the practice of embedding sensitive messages in mundane cover messages. Recent efforts at provably secure steganography have only focused on text-based generative models and cannot support other types of models, such as diffusion models, which are used for high-quality image synthesis. In this work, we initiate the study of securely embedding steganographic messages into the output of image diffusion models. We identify that the use of variance noise during image generation provides a suitable steganographic channel. We develop our construction, Pulsar, by building optimizations to make this channel practical for communication. Our implementation of Pulsar is capable of embedding $\approx 275$-$542$ bytes (on average) into a single image without altering the distribution of the generated image, all in the span of $\approx 3$ seconds of online time on a laptop. In addition, we discuss how the results of Pulsar can inform future research into diffusion models. Pulsar shows that diffusion models are a promising medium for steganography and censorship resistance.

We consider the mainstream model in secure computation known as the bare PKI setup, also as the {bulletin-board PKI}. It assumes that players can broadcast once and non-interactively before they receive their inputs and start the execution. We consider both the problems of consensus with strong unanimity, also known as ``Byzantine agreement'' (BA), and of ``Validated Byzantine agreement'' [CKPS, Crypto'01] (VBA, also known as MVBA). Most works on BA use a bulletin-board PKI setup only for the purpose of publishing verification keys. This implements the {messages-authentication model}, i.e., when $P$ is forwarded a message issued by $R$, it is convinced that $R$ is the author. Without messages-authentication, it is known since [Lamport et al, 82] that BA under honest majority is impossible, let alone secure computation. Thus, since the bare PKI setup and the messages-authentication model seem close, this raizes the question whether there is a separation between the two. In the bare PKI setup, the most communication-efficient synchronous BA is the one of [Boyle-Cohen-Goel, Podc'21 \& J. Cryptol.'24], which has $O(n.\text{polylog}(n))$ bit complexity, $f
{- Optimality.} We show that resilience up to a tight honest majority $f
{- Separation.} We show impossibility of subquadratic multicast-based BA in the messages-authentication model. Our model for this lower bound is even stronger, since it onboards other assumptions at least as strong as all popular implications of a bulletin-board PKI setup: {secure channels}, {a (possibly structured) random string}, {NIZK}.

{- Partial synchrony.} We then show that the separation also holds under partial synchrony. On the one hand, our upper-bound also holds, with $f
{- Extension to VBA.} We extend to VBA the logarithmic latency lower bound. This is the first communication lower bound for adaptively secure VBA to our knowledge. It shows that the separation under partial synchrony also holds for VBA. Along the way, we close the categorization of [Civit et al, Podc'23] of validity conditions in authenticated consensus, by apparently new results on VBA: both BA and VBA are infeasible under partial synchrony beyond $f

Quantum copy protection, introduced by Aaronson, enables giving out a quantum program-description that cannot be meaningfully duplicated. Despite over a decade of study, copy protection is only known to be possible for a very limited class of programs.

As our first contribution, we show how to achieve "best-possible" copy protection for all programs. We do this by introducing quantum state indistinguishability obfuscation (qsiO), a notion of obfuscation for quantum descriptions of classical programs. We show that applying qsiO to a program immediately achieves best-possible copy protection.

Our second contribution is to show that, assuming injective one-way functions exist, qsiO is concrete copy protection for a large family of puncturable programs --- significantly expanding the class of copy-protectable programs. A key tool in our proof is a new variant of unclonable encryption (UE) that we call coupled unclonable encryption (cUE). While constructing UE in the standard model remains an important open problem, we are able to build cUE from one-way functions. If we additionally assume the existence of UE, then we can further expand the class of puncturable programs for which qsiO is copy protection.

Finally, we construct qsiO relative to an efficient quantum oracle.

Regular access to unpredictable and bias-resistant randomness is important for applications such as blockchains, voting, and secure distributed computing. Distributed random beacon protocols address this need by distributing trust across multiple nodes, with the majority of them assumed to be honest. These protocols have found applications in blockchain technology, leading to the proposal of several distributed random beacon protocols, with some already implemented. However, many current random beacon systems rely on threshold cryptographic setups or exhibit high computational costs, while others assume partial or bounded synchronous networks. To overcome these limitations, we propose HashRand, a computation and communication-efficient asynchronous random beacon protocol that uses a secure Hash function to generate beacons and pairwise secure channels. HashRand has a per-node communication complexity of $\mathcal{O}(\lambda n \log(n))$ bits per beacon. The computational efficiency of HashRand is attributed to the two orders of magnitude lower time of a one-way Hash computation compared to discrete log exponentiation. Interestingly, besides reduced overhead, HashRand achieves Post-Quantum security by leveraging the secure Hash function against quantum adversaries, setting it apart from other random beacon protocols that use discrete log cryptography. In a geo-distributed testbed of $n=160$ nodes, HashRand produces 1 beacon every second, which is at least 4x higher than Spurt. We also demonstrate the practical utility of HashRand by implementing a Post-Quantum secure Asynchronous SMR protocol, which has a response rate of over 122k txns per second over a WAN at $n=40$ nodes.

The Snowden's revelations kick-started a community-wide effort to develop cryptographic tools against mass surveillance. In this work, we propose to add another primitive to that toolbox: Fail-Stop Signatures (FSS) [EC'89]. FSS are digital signatures enhanced with a forgery-detection mechanism that can protect a PPT signer from more powerful attackers. Despite the fascinating concept, research in this area stalled after the '90s. However, the ongoing transition to post-quantum cryptography, with its hiccups due to the novelty of underlying assumptions, has become the perfect use case for FSS. This paper aims to reboot research on FSS with practical use in mind: Our framework for FSS includes ``fine-grained'' security definitions (that assume a powerful, but bounded adversary e.g: can break $128$-bit of security, but not $256$-bit). As an application, we show new FSS constructions for the post-quantum setting. We show that FSS are equivalent to standard, provably secure digital signatures that do not require rewinding or programming random oracles, and that this implies lattice-based FSS. Our main construction is an FSS version of SPHINCS, which required building FSS versions of all its building blocks: WOTS, XMSS, and FORS. In the process, we identify and provide generic solutions for two fundamental issues arising when deriving a large number of private keys from a single seed, and when building FSS for Hash-and-Sign-based signatures.

The Internet Key Exchange version 2 (IKEv2) (RFC 7296) is a component of IPsec used to authenticate two parties (the initiator and responder) to each other and to establish a set of security parameters for the communications. The security parameters include secret keys to encrypt and authenticate data as well as the negotiation of a set of cryptographic algorithms. The core documentation uses exclusively Diffie-Hellman exchanges to agree the security information. However, this is not a quantum-secure option due to the ability of Shor's algorithm to break the security assumption underlying the Diffie-Hellman. A post-quantum solution is to include a preshared key in the exchange, as proposed by the extension RFC 8784; assuming that this preshared key has sufficient entropy, the keys created in the IKEv2 exchange will be resistant to a quantum computer. In this paper, we investigate the security claims of RFC 8784 using formal verification methods. We find that keys created using the preshared key are secret from an adversary. However, certain authentication properties of the protocol that are weakened under the assumption that Diffie-Hellman is insecure are not recovered using the preshared key.

This paper introduces a novel approach to enhancing cryp- tographic security. It proposes the use of one-time message sharing com- bined with Physically Unclonable Functions (PUF) to securely exchange keys and generate an S-subbyte-box for encryption. This innovative tech- nique aims to elevate the security standards of cryptographic applica- tions.

In this paper, we describe an algorithm to compute chains of $(2,2)$-isogenies between products of elliptic curves in the theta model. The description of the algorithm is split into various subroutines to allow for a precise field operation counting.

We present a constant time implementation of our algorithm in Rust and an alternative implementation in SageMath. Our work in SageMath runs ten times faster than a comparable implementation of an isogeny chain using the Richelot correspondence. The Rust implementation runs up to forty times faster than the equivalent isogeny in SageMath and has been designed to be portable for future research in higher-dimensional isogeny-based cryptography.

With the Institute for Photonic Quantum Systems (PhoQS), Paderborn University wants to establish an international research centre in the field of photonic quantum technologies. The aim is to develop new technologies for photon-based quantum applications as well as new theoretical and experimental concepts and research approaches. Ultimately, the focus is on understanding and controlling photonic quantum simulators and quantum computers. In the Faculty of Electrical Engineering, Computer Science and Mathematics, the Institute of Computer Science - Department "Codes and Cryptography" - has a vacancy for a

Postdoc (m/f/d)
(salary is according to 13 TV-L)

position with 100% of the regular working hours within the framework of the MKW (Ministry of Culture and Science of the State of North Rhine-Westphalia) NRW project "Photonic Quantum Computing (PhoQC)". The employment is initially limited to three years and is based on the legal regulations of the WissZeitVG.
Your duties and responsibilities:
- Complexity-theoretical analysis of boson sampling-like experiments
- Development of quantum algorithms using boson sampling for practical applications
- Development and analysis of theoretical frameworks for universal quantum computing based on quantum photonics
Hiring requirements:
- Completed PhD in computer science, mathematics or physics or comparable qualification

It is expected that the applicant has experience in at least one of the following areas:

- Quantum algorithms
- Quantum complexity
- Theoretical quantum photonics
- Quantum information theory

Closing date for applications:

Contact: Please send your application including a CV (preferably in a single pdf file) using the Ref. No. 6207 by bloemer@upb.de. Information regarding the processing of your person data can be located at: https://www.uni-paderborn.de/en/zv/personaldatenschutz.

More information: https://cs.uni-paderborn.de/en/cuk/?cHash=8829d72369c94558f8571cc307314a2c

LIST is looking for a highly motivated candidate with proven skills in federated data processing such as applying simple statistics or advanced machine learning tools, to improve the utility of the obtained information. For example, collaborative cyberthreat intelligence systems that use advanced analytics solutions can offer significant advantages over the local systems by detecting cyberattacks early and promptly responding to them. While recent developments in cryptography and the rise of homomorphic encryption and secure multi-party computation allow operations without revealing the underlying data in cleartext, these technologies still suffer from a noticeable overhead in terms of computation and communication. The main mission of the candidate, together with local and international collaborators, is to continue research on these technologies to address scalability and performance requirements.

Closing date for applications:

Contact: Dr. Qiang Tang (qiang.tang@list.lu)

Event date: 5 March to 8 March 2024

As NIST is putting the final touches on the standardization of PQC (Post Quantum Cryptography) public key algorithms, it is a racing certainty that peskier cryptographic attacks undeterred by those new PQC algorithms will surface. Such a trend in turn will prompt more follow-up studies of attacks and countermeasures. As things stand, from the attackers’ perspective, one viable form of attack that can be implemented thereupon is the so-called “side-channel attack”. Two best-known countermeasures heralded to be durable against side-channel attacks are: “masking” and “hiding”. In that dichotomous picture, of particular note are successful single-trace attacks on some of the NIST’s PQC then-candidates, which worked to the detriment of the former: “masking”. In this paper, we cast an eye over the latter: “hiding”. Hiding proves to be durable against both side-channel attacks and another equally robust type of attacks called “fault injection attacks”, and hence is deemed an auspicious countermeasure to be implemented. Mathematically, the hiding method is fundamentally based on random permutations. There has been a cornucopia of studies on generating random permutations. However, those are not tied to implementation of the hiding method. In this paper, we propose a reliable and efficient verification of permutation implementation, through employing Fisher–Yates’ shuffling method. We introduce the concept of an ?-th order permutation and explain how it can be used to verify that our implementation is more efficient than its previous-gen counterparts for hiding countermeasures.

Existing protocols for proving the correct execution of a RAM program in zero-knowledge are plagued by a processor expressiveness trade-off : supporting fewer instructions results in smaller processor circuits (which improves performance), but may result in more program execution steps because non-supported instruction must be emulated over multiple processor steps (which diminishes performance).

We present Dora, a concretely efficient zero-knowledge protocol for RAM programs that sidesteps this tension by making it (nearly) free to add additional instructions to the processor. The computational and communication complexity of proving each step of a computation in Dora, is constant in the number of supported instructions. Dora is also highly generic and only assumes the existence of linearly homomorphic commitments. We implement Dora and demonstrate that on commodity hardware it can prove the correct execution of a processor with thousands of instruction, each of which has thousands of gates, in just a few milliseconds per step.

A recent preprint [ePrint 2023/1475] suggests the use of polynomials over a tropical algebra to construct a digital signature scheme "based on" the problem of factoring such polynomials, which is known to be NP‑hard. This short note presents two very efficient forgery attacks on the scheme, bypassing the need to factorize tropical polynomials and thus demonstrating that security in fact rests on a different, empirically easier problem.

In this paper, we describe an algorithm to compute chains of $(2,2)$-isogenies between products of elliptic curves in the theta model. The description of the algorithm is split into various subroutines to allow for a precise field operation counting.

We present a constant time implementation of our algorithm in Rust and an alternative implementation in SageMath. Our work in SageMath runs ten times faster than a comparable implementation of an isogeny chain using the Richelot correspondence. The Rust implementation runs up to forty times faster than the equivalent isogeny in SageMath and has been designed to be portable for future research in higher-dimensional isogeny-based cryptography.

In the attacker models of Side-Channel Attacks (SCA) and Fault Injection Attacks (FIA), the opponent has access to a noisy version of the internal behavior of the hardware. Since the end of the nineties, many works have shown that this type of attacks constitutes a serious threat to cryptosystems implemented in embedded devices. In the state-of-the-art, there exist several countermeasures to protect symmetric encryption (especially AES-128). Most of them protect only against one of these two attacks (either SCA or FIA). The main known counter-measure against SCA is masking; it makes the complexity of SCA growing exponentially with its order d. The most general version of masking is based on error correcting codes. It has the advantage of offering in principle a protection against both types of attacks (SCA and FIA), but all the functions implemented in the algorithm need to be masked accordingly, and this is not a simple task in general. We propose a particular version of such construction that has several advantages: it has a very low computation complexity, it offers a concrete protection against both SCA and FIA, and finally it allows flexibility: being not specifically dedicated to AES, it can be applied to any block cipher with any S-boxes. In the state-of-art, masking schemes all come with pros and cons concerning the different types of complexity (time, memory, amount of randomness). Our masking scheme concretely achieves the complexity of the best known scheme, for each complexity type

Given a set of matrices $\mathbf{A} := \{A_0, \dotsc, A_{k-1}\}$, and a matrix $M$ guaranteed to be the product of some ordered subset of $\mathbf{L}\subset\mathbf{A}$, can $\mathbf{L}$ be efficiently recovered? We begin by observing that the answer is positive under some assumptions on $\mathbf{A}$.

Noting that appropriate transformations seem to make $\mathbf{L}$'s recovery difficult we provide the blueprint of two new public-key cryptosystems based upon this problem.

We term those constructions "blueprints because, given their novelty, we are still uncertain of their exact security. Yet, we daringly conjecture that even if attacks are found on the proposed constructions, these attacks could be thwarted by adjustments in the key generation, key size or the encryption mechanism, thereby resulting on the long run in fully-fledged public-key cryptosystems that do not seem to belong to any of the mainstream public-key encryption paradigms known to date.

Secure multi-party computation (MPC) enables (joint) computations on sensitive data while maintaining privacy. In real-world scenarios, asymmetric trust assumptions are often most realistic, where one somewhat trustworthy entity interacts with smaller clients. We generalize previous two-party computation (2PC) protocols like MUSE (USENIX Security'21) and SIMC (USENIX Security'22) to the three-party setting (3PC) with one malicious party, avoiding the performance limitations of dishonest-majority inherent to 2PC.

We introduce two protocols, Auxiliator and Socium, in a machine learning (ML) friendly design with a fast online phase and novel verification techniques in the setup phase. These protocols bridge the gap between prior 3PC approaches that considered either fully semi-honest or malicious settings. Auxiliator enhances the semi-honest two-party setting with a malicious helper, significantly improving communication by at least two orders of magnitude. Socium extends the client-malicious setting with one malicious client and a semi-honest server, achieving substantial communication improvement by at least one order of magnitude compared to SIMC.

Besides an implementation of our new protocols, we provide the first open-source implementation of the semi-honest 3PC protocol ASTRA (CCSW'19) and a variant of the malicious 3PC protocol SWIFT (USENIX Security'21).

Private Simultaneous Messages (PSM) is a minimal model of secure computation, where the input players with shared randomness send messages to the output player simultaneously and only once. In this field, finding upper and lower bounds on communication complexity of PSM protocols is important, and in particular, identifying the optimal one where the upper and lower bounds coincide is the ultimate goal. However, up until now, functions for which the optimal communication complexity has been determined are few: An example of such a function is the two-input AND function where $(2\log_2 3)$-bit communication is optimal. In this paper, we provide new upper and lower bounds for several concrete functions. For lower bounds, we introduce a novel approach using combinatorial objects called abstract simplicial complexes to represent PSM protocols. Our method is suitable for obtaining non-asymptotic explicit lower bounds for concrete functions. By deriving lower bounds and constructing concrete protocols, we show that the optimal communication complexity for the equality and majority functions with three input bits are $3\log_2 3$ bits and $6$ bits, respectively. We also derive new lower bounds for the $n$-input AND function, three-valued comparison function, and multiplication over finite rings.

A central direction of research in secure multiparty computation with dishonest majority has been to achieve three main goals:

1. reduce the total number of rounds of communication (to four, which is optimal); 2. use only polynomial-time hardness assumptions, and 3. rely solely on cryptographic assumptions in a black-box manner.

This is especially challenging when we do not allow a trusted setup assumption of any kind. While protocols achieving two out of three goals in this setting have been designed in recent literature, achieving all three simultaneously remained an elusive open question. Specifically, it was answered positively only for a restricted class of functionalities. In this paper, we completely resolve this long-standing open question. Specifically, we present a protocol for all polynomial-time computable functions that does not require any trusted setup assumptions and achieves all three of the above goals simultaneously.