482 results sorted by ID
Tight Security of Double-Block Nonce-Based MACs
Wonseok Choi, Jooyoung Lee, Yeongmin Lee
Secret-key cryptography
In this paper, we study the security of MAC constructions among those classified by Chen et al. in ASIACRYPT '21. Precisely, $F^{\text{EDM}}_{B_2}$ (or $\mathsf{EWCDM}$ as named by Cogliati and Seurin in CRYPTO '16), $F^{\text{EDM}}_{B_3}$, $F^{\text{SoP}}_{B_2}$, $F^{\text{SoP}}_{B_3}$ (all as named by Chen et al.) are proved to be fully secure up to $2^n$ MAC queries in the nonce-respecting setting, improving the previous bound of $\frac{3n}{4}$-bit security. In particular,...
Let Attackers Program Ideal Models: Modularity and Composability for Adaptive Compromise
Joseph Jaeger
Foundations
We show that the adaptive compromise security definitions of Jaeger and Tyagi (Crypto '20) cannot be applied in several natural use-cases. These include proving multi-user security from single-user security, the security of the cascade PRF, and the security of schemes sharing the same ideal primitive. We provide new variants of the definitions and show that they resolve these issues with composition. Extending these definitions to the asymmetric settings, we establish the security of the...
Multi User Security of LightMAC and LightMAC_Plus
Nilanjan Datta, Shreya Dey, Avijit Dutta, Devdutto Kanungo
Secret-key cryptography
In FSE'16, Luykx et al. have proposed $\textsf{LightMAC}$ that provably achieves a query length independent PRF security bound. To be precise, the construction achieves security roughly in the order of $O(q^2/2^n)$, when instantiated with two independently keyed $n$-bit block ciphers and $q$ is the total number of queries made by the adversary. Subsequently, in ASIACRYPT'17, Naito proposed a beyond-birthday-bound variant of the $\textsf{LightMAC}$ construction, dubbed as...
Linicrypt in the Ideal Cipher Model
Zahra Javar, Bruce M. Kapron
Foundations
We extend the Linicrypt framework for characterizing hash function security as proposed by McQuoid, Swope, and Rosulek (TCC 2018) to support constructions in the ideal cipher model.
In this setting, we give a characterization of collision- and second-preimage-resistance in terms of a linear-algebraic condition on Linicrypt programs, and present an efficient algorithm for determining whether a program satisfies the condition. As an application, we consider the case of the block cipherbased...
A Note of $\mathsf{Anemoi}$ Gröbner Bases
Pierre Briaud
Attacks and cryptanalysis
Recently, [eprint/2024/250] and [eprint/2024/347] proposed two algebraic attacks on the $\mathsf{Anemoi}$ permutation [Crypto '23]. In this note, we construct a Gröbner basis for the ideal generated by the naive modeling of the $\mathsf{CICO}$ problem associated to $\mathsf{Anemoi}$, in odd and in even characteristics, for one and several branches. We also infer the degree of the ideal from this Gröbner basis, while previous works relied on upper bounds.
Fast Parallelizable Misuse-Resistant Authenticated Encryption: Low Latency (Decryption-Fast) SIV
Mustafa Khairallah
Secret-key cryptography
MRAE security is an important goal for many AEAD applications where the nonce uniqueness cannot be maintained and security risks are significant. However, MRAE schemes can be quite expensive. Two of the SoTA MRAE-secure schemes; Deoxys-II and AES-GCM-SIV rely on internal parallelism and special instructions to achieve competitive performance. However, they both suffer from the same bottleneck, they have at least one call to the underlying primitive that cannot be parallelized to any other...
CryptoVampire: Automated Reasoning for the Complete Symbolic Attacker Cryptographic Model
Simon Jeanteur, Laura Kovács, Matteo Maffei, Michael Rawson
Cryptographic protocols
Cryptographic protocols are hard to design and prove correct, as witnessed by the ever-growing list of attacks even on protocol standards. Symbolic models of cryptography enable automated formal security proofs of such protocols against an idealized cryptographic model, which abstracts away from the algebraic properties of cryptographic schemes and thus misses attacks. Computational models of cryptography yield rigorous guarantees but support at present only interactive proofs and/or...
CCA Secure Updatable Encryption from Non-Mappable Group Actions
Jonas Meers, Doreen Riepel
Cryptographic protocols
Ciphertext-independent updatable encryption (UE) allows to rotate encryption keys and update ciphertexts via a token without the need to first download the ciphertexts. Although, syntactically, UE is a symmetric-key primitive, ciphertext-independent UE with forward secrecy and post-compromise security is known to imply public-key encryption (Alamati, Montgomery and Patranabis, CRYPTO 2019).
Constructing post-quantum secure UE turns out to be a difficult task. While lattices offer the...
Two-Round Threshold Signature from Algebraic One-More Learning with Errors
Thomas Espitau, Shuichi Katsumata, Kaoru Takemure
Cryptographic protocols
Threshold signatures have recently seen a renewed interest due to applications in cryptocurrency while NIST has released a call for multi-party threshold schemes, with a deadline for submission expected for the first half of 2025. So far, all lattice-based threshold signatures requiring less than two-rounds are based on heavy tools such as (fully) homomorphic encryption (FHE) and homomorphic trapdoor commitments (HTDC). This is not unexpected considering that most efficient two-round...
HW-token-based Common Random String Setup
István Vajda
Applications
In the common random string model, the parties executing a protocol have access to a uniformly random bit string. It is known that under standard intractability assumptions, we can realize any ideal functionality with universally composable (UC) security if a trusted common random string (CrS) setup is available. It was always a question of where this CrS should come from since the parties provably could not compute it themselves. Trust assumptions are required, so minimizing the level of...
Single Server PIR via Homomorphic Thorp Shuffles
Ben Fisch, Arthur Lazzaretti, Zeyu Liu, Charalampos Papamanthou
Cryptographic protocols
Private Information Retrieval (PIR) is a two player protocol where the client, given some query $x \in [N]$ interacts with the server, which holds a $N$-bit string $\textsf{DB}$ in order to privately retrieve $\textsf{DB}[x]$. In this work, we focus on the single server client-preprocessing model, initially idealized by Corrigan-Gibbs and Kogan (EUROCRYPT 2020), where the client and server first run some joint preprocessing algorithm, after which the client can retrieve elements of the...
Threshold Structure-Preserving Signatures: Strong and Adaptive Security under Standard Assumptions
Aikaterini Mitrokotsa, Sayantan Mukherjee, Mahdi Sedaghat, Daniel Slamanig, Jenit Tomy
Public-key cryptography
Structure-preserving signatures (SPS) have emerged as an important cryptographic building block, as their compatibility with the Groth-Sahai (GS) NIZK framework allows to construct protocols under standard assumptions with reasonable efficiency.
Over the last years there has been a significant interest in the design of threshold signature schemes. However, only very recently Crites et al. (ASIACRYPT 2023) have introduced threshold SPS (TSPS) along with a fully non-interactive construction....
C'est très CHIC: A compact password-authenticated key exchange from lattice-based KEM
Afonso Arriaga, Manuel Barbosa, Stanislaw Jarecki, Marjan Skrobot
Cryptographic protocols
Several Password Authenticated Key Exchange (PAKE) protocols have been recently proposed that leverage a Key-Encapsulation Mechanism (KEM) to create an efficient and easy-to-implement post-quantum secure PAKE. This line of work is driven by the intention of the National Institute of Standards and Technology (NIST) to soon standardize a lattice-based post-quantum KEM called $\mathsf{Kyber}$. In two recent works, Beguinet et al. (ACNS 2023) and Pan and Zeng (ASIACRYPT 2023) proposed generic...
A New Approach to Generic Lower Bounds: Classical/Quantum MDL, Quantum Factoring, and More
Minki Hhan
Foundations
This paper studies the limitations of the generic approaches to solving cryptographic problems in classical and quantum settings in various models.
- In the classical generic group model (GGM), we find simple alternative proofs for the lower bounds of variants of the discrete logarithm (DL) problem: the multiple-instance DL and one-more DL problems (and their mixture). We also re-prove the unknown-order GGM lower bounds, such as the order finding, root extraction, and repeated squaring.
-...
Short Signatures from Regular Syndrome Decoding, Revisited
Dung Bui, Eliana Carozza, Geoffroy Couteau, Dahmun Goudarzi, Antoine Joux
Cryptographic protocols
We revisit the construction of signature scheme using the MPC-in-the-head paradigm, and focus in particular on constructions from the regular syndrome decoding assumption, a well-known variant of the syndrome decoding assumption. We obtain two main contributions:
– We observe that previous signatures in the MPC-in-the-head paradigm must rely on a salted version of the GGM puncturable pseudorandom function (PPRF) to avoid collision attacks. We design a new efficient PPRF construction...
Robust Additive Randomized Encodings from IO and Pseudo-Non-linear Codes
Nir Bitansky, Sapir Freizeit
Cryptographic protocols
Additive randomized encodings (ARE), introduced by Halevi, Ishai, Kushilevitz, and Rabin (CRYPTO 2023), reduce the computation of a k-party function $f (x_1, . . . , x_k )$ to locally computing encodings $\hat{x}_i$ of each input xi and then adding them together over some Abelian group into an output encoding $\hat{y} = ∑ \hat{x}_i$, which reveals nothing but the result. In robust ARE (RARE) the sum of any subset of $\hat{x}_i$, reveals only the residual function obtained by restricting the...
Direct FSS Constructions for Branching Programs and More from PRGs with Encoded-Output Homomorphism
Elette Boyle, Lisa Kohl, Zhe Li, Peter Scholl
Cryptographic protocols
Function secret sharing (FSS) for a class $\cal{F}$ allows to split a secret function $f \in \cal{F}$ into (succinct) secret shares $f_0,f_1$, such that for all $x\in \{0,1\}^n$ it holds $f_0(x)-f_1(x)=f(x)$. FSS has numerous applications, including private database queries, nearest neighbour search, private heavy hitters and secure computation in the preprocessing model, where the supported class $\cal{F}$ translates to richness in the application. Unfortunately, concretely efficient FSS...
Constant-Size zk-SNARKs in ROM from Falsifiable Assumptions
Helger Lipmaa, Roberto Parisella, Janno Siim
Cryptographic protocols
We prove that the seminal KZG polynomial commitment scheme (PCS) is black-box extractable under a simple falsifiable assumption ARSDH. To create an interactive argument, we construct a compiler that combines a black-box extractable non-interactive PCS and a polynomial IOP (PIOP). The compiler incurs a minor cost per every committed polynomial. Applying the Fiat-Shamir transformation, we obtain slightly less efficient variants of well-known PIOP-based zk-SNARKs, such as Plonk, that are...
Zero-Knowledge Proofs of Training for Deep Neural Networks
Kasra Abbaszadeh, Christodoulos Pappas, Dimitrios Papadopoulos, Jonathan Katz
Cryptographic protocols
A zero-knowledge proof of training (zkPoT) enables a party to prove that they have correctly trained a committed model based on a committed dataset without revealing any additional information about the model or the dataset. An ideal zkPoT should offer provable security and privacy guarantees, succinct proof size and verifier runtime, and practical prover efficiency. In this work, we present Kaizen, a zkPoT targeted for deep neural networks (DNNs) that achieves the above ideals all at once....
Layout Graphs, Random Walks and the t-wise Independence of SPN Block Ciphers
Tianren Liu, Angelos Pelecanos, Stefano Tessaro, Vinod Vaikuntanathan
Secret-key cryptography
We continue the study of $t$-wise independence of substitution-permutation networks (SPNs) initiated by the recent work of Liu, Tessaro, and Vaikuntanathan (CRYPTO 2021).
Our key technical result shows that when the S-boxes are randomly and independently chosen and kept secret, an $r$-round SPN with input length $n = b \cdot k$ is $2^{-\Theta(n)}$-close to $t$-wise independent within $r = O(\min\{k, \log t\})$ rounds for any $t$ almost as large as $2^{b/2}$. Here, $b$ is the input length of...
On Efficient and Secure Compression Modes for Arithmetization-Oriented Hashing
Elena Andreeva, Rishiraj Bhattacharyya, Arnab Roy, Stefano Trevisani
Secret-key cryptography
ZK-SNARKs, a fundamental component of privacy-oriented payment systems, identity protocols, or anonymous voting systems, are advanced cryptographic protocols for verifiable computation: modern SNARKs allow to encode the invariants of a program, expressed as an arithmetic circuit, in an appropriate constraint language from which short, zero-knowledge proofs for correct computations can be constructed.
One of the most important computations that is run through SNARK systems is the...
Towards Compact Identity-based Encryption on Ideal Lattices
Huiwen Jia, Yupu Hu, Chunming Tang, Lin Wang
Public-key cryptography
Basic encryption and signature on lattices have comparable efficiency to their classical counterparts in terms of speed and key size. However, Identity-based Encryption (IBE) on lattices is much less efficient in terms of compactness, even when instantiated on ideal lattices and in the Random Oracle Model (ROM). This is because the underlying preimage sampling algorithm used to extract the users' secret keys requires huge public parameters. In this work, we specify a compact IBE...
Lattice-based Programmable Hash Functions and Applications
Jiang Zhang, Yu Chen, Zhenfeng Zhang
Public-key cryptography
Driven by the open problem raised by Hofheinz and Kiltz
(Journal of Cryptology, 2012), we study the formalization of lattice-based programmable hash function (PHF), and give three types of concrete constructions by using several techniques such as a novel combination of cover-free sets and lattice trapdoors. Under the Inhomogeneous Small Integer Solution (ISIS) assumption, we show that any (non-trivial) lattice-based PHF is a collision-resistant hash function, which gives a direct...
Unclonable Cryptography with Unbounded Collusions
Alper Çakan, Vipul Goyal
Foundations
Quantum no-cloning theorem gives rise to the intriguing possibility of quantum copy protection where we encode a program in a quantum state such that a user in possession of $k$ such states cannot create $k+1$ working copies. Introduced by Aaronson (CCC'09) over a decade ago, copy protection has proven to be notoriously hard to achieve.
In this work, we construct public-key encryption and functional encryption schemes whose secret keys are copy-protected against unbounded collusions in...
CASE: A New Frontier in Public-Key Authenticated Encryption
Shashank Agrawal, Shweta Agrawal, Manoj Prabhakaran, Rajeev Raghunath, Jayesh Singla
Public-key cryptography
We introduce a new cryptographic primitive, called Completely Anonymous Signed Encryption (CASE). CASE is a public-key authenticated encryption primitive, that offers anonymity for senders as well as receivers. A "case-packet" should appear, without a (decryption) key for opening it, to be a blackbox that reveals no information at all about its contents. To decase a case-packet fully - so that the message is retrieved and authenticated - a verifcation key is also required.
Defining security...
Adaptively Secure Consensus with Linear Complexity and Constant Round under Honest Majority in the Bare PKI Model, and Separation Bounds from the Idealized Message-Authentication Model
Matthieu Rambaud
Foundations
We consider the mainstream model in secure computation known as the bare PKI setup, also as the {bulletin-board PKI}. It allows players to broadcast once and non-interactively before they receive their inputs and start the execution. A bulletin-board PKI is essentially the minimum setup known so far to implement the model known as {messages-authentication}, i.e., when $P$ is forwarded a signed message, it considers it to be issued by $R$ if and only if $R$ signed it. It is known since...
On Overidealizing Ideal Worlds: Xor of Two Permutations and its Applications
Wonseok Choi, Minki Hhan, Yu Wei, Vassilis Zikas
Secret-key cryptography
Security proofs of symmetric-key primitives typically consider an idealized world with access to a (uniformly) random function. The starting point of our work is the observation that such an ideal world can lead to underestimating the actual security of certain primitives. As a demonstrating example, $\mathsf{XoP2}$, which relies on two independent random permutations, has been proven to exhibit superior concrete security compared to $\mathsf{XoP}$, which employs a single permutation with...
Security Bounds for Proof-Carrying Data from Straightline Extractors
Alessandro Chiesa, Ziyi Guan, Shahar Samocha, Eylon Yogev
Foundations
Proof-carrying data (PCD) is a powerful cryptographic primitive that allows mutually distrustful parties to perform distributed computation in an efficiently verifiable manner. Real-world deployments of PCD have sparked keen interest within the applied community and industry.
Known constructions of PCD are obtained by recursively-composing SNARKs or related primitives. Unfortunately, known security analyses incur expensive blowups, which practitioners have disregarded as the analyses...
Unmodified Half-Gates is Adaptively Secure - So is Unmodified Three-Halves
Xiaojie Guo, Kang Yang, Xiao Wang, Yu Yu, Zheli Liu
Cryptographic protocols
Adaptive security is a crucial property for garbling schemes in pushing the communication of garbled circuits to an offline phase when the input is unknown. In this paper, we show that the popular half-gates scheme by Zahur et al. (Eurocrypt'15), without any modification, is adaptively secure in the non-programmable random permutation model (npRPM). Since real implementations of selective-secure half-gates are already based on npRPM, our result shows that these implementations are already...
Making an Asymmetric PAKE Quantum-Annoying by Hiding Group Elements
Marcel Tiepelt, Edward Eaton, Douglas Stebila
Cryptographic protocols
The KHAPE-HMQV protocol is a state-of-the-art highly efficient asymmetric password-authenticated key exchange protocol that provides several desirable security properties, but has the drawback of being vulnerable to quantum adversaries due to its reliance on discrete logarithm-based building blocks: solving a single discrete logarithm allows the attacker to perform an offline dictionary attack and recover the password. We show how to modify KHAPE-HMQV to make the protocol quantum-annoying: a...
Efficient Agreement Over Byzantine Gossip
Ran Cohen, Julian Loss, Tal Moran
Cryptographic protocols
Byzantine agreement (BA) asks for a set of parties to reach agreement in an adversarial setting. A central question is how to construct efficient BA protocols that scale well with the number of parties. In particular, the communication complexity is a critical barrier for large-scale implementations.
State-of-the-art, scalable BA protocols typically work by sampling a small, unpredictable committee of parties that will send messages in each round. These messages must reach all honest...
Towards post-quantum secure PAKE - A tight security proof for OCAKE in the BPR model
Nouri Alnahawi, Kathrin Hövelmanns, Andreas Hülsing, Silvia Ritsch, Alexander Wiesmaier
Cryptographic protocols
We revisit OCAKE (ACNS 23), a generic recipe that constructs password-based authenticated key exchange (PAKE) from key encapsulation mechanisms (KEMs) in a black-box way. This allows to potentially achieve post-quantum security by instantiating the KEM with a post-quantum KEM like KYBER.
It was left as an open problem to further adapt the proof such that it also holds against quantum attackers. The security proof is given in the universal composability (UC) framework, which is common for...
On the Security of KZG Commitment for VSS
Atsuki Momose, Sourav Das, Ling Ren
Cryptographic protocols
The constant-sized polynomial commitment scheme by Kate, Zaverucha, and Goldberg (Asiscrypt 2010), also known as the KZG commitment, is an essential component in designing bandwidth-efficient verifiable secret-sharing (VSS) protocols. We point out, however, that the KZG commitment is missing two important properties that are crucial for VSS protocols.
First, the KZG commitment has not been proven to be degree binding in the standard adversary model without idealized group assumptions. In...
A Generic Construction of Tightly Secure Password-based Authenticated Key Exchange
Jiaxin Pan, Runzhi Zeng
Public-key cryptography
We propose a generic construction of password-based authenticated key exchange (PAKE) from key encapsulation mechanisms (KEM). Assuming that the KEM is oneway secure against plaintext-checkable attacks (OW-PCA), we prove that our PAKE protocol is \textit{tightly secure} in the Bellare-Pointcheval-Rogaway model (EUROCRYPT 2000). Our tight security proofs require ideal ciphers and random oracles. The OW-PCA security is relatively weak and can be implemented tightly with the Diffie-Hellman...
A Methodology to Achieve Provable Side-Channel Security in Real-World Implementations
Sonia Belaïd, Gaëtan Cassiers, Camille Mutschler, Matthieu Rivain, Thomas Roche, François-Xavier Standaert, Abdul Rahman Taleb
Physical side-channel attacks exploit a device's emanations to compromise the security of cryptographic implementations.
Many countermeasures have been proposed against these attacks, especially the widely-used and efficient masking countermeasure.
While theoretical models offer formal security proofs, they often rest on unrealistic assumptions, leading current approaches to prove the security of masked implementations to primarily rely on empirical verification.
Consequently, the...
Streebog as a Random Oracle
Liliya Akhmetzyanova, Alexandra Babueva, Andrey Bozhko
Secret-key cryptography
The random oracle model is an instrument used for proving that protocol has no structural flaws when settling with standard hash properties is impossible or fairly difficult. In practice, however, random oracles have to be instantiated with some specific hash functions, which are not random oracles. Hence, in the real world, an adversary has broader capabilities than considered in the random oracle proof — it can exploit the peculiarities of a specific hash function to achieve its goal. In a...
How to Compile Polynomial IOP into Simulation-Extractable SNARKs: A Modular Approach
Markulf Kohlweiss, Mahak Pancholi, Akira Takahashi
Foundations
Most succinct arguments (SNARKs) are initially only proven knowledge sound (KS).
We show that the commonly employed compilation strategy from polynomial interactive oracle proofs (PIOP) via polynomial commitments to knowledge sound SNARKS actually also achieves other desirable properties: weak unique response (WUR) and trapdoorless zero-knowledge (TLZK); and that together they imply simulation extractability (SIM-EXT).
The factoring of SIM-EXT into KS + WUR + TLZK is becoming a...
Limits in the Provable Security of ECDSA Signatures
Dominik Hartmann, Eike Kiltz
Foundations
Digital Signatures are ubiquitous in modern computing. One of the most widely used digital signature schemes is ECDSA due to its use in TLS, various Blockchains such as Bitcoin and Etherum, and many other applications. Yet the formal analysis of ECDSA is comparatively sparse. In particular, all known security results for ECDSA rely on some idealized model such as the generic group model or the programmable (bijective) random oracle model.
In this work, we study the question whether these...
Practical Schnorr Threshold Signatures Without the Algebraic Group Model
Hien Chu, Paul Gerhart, Tim Ruffing, Dominique Schröder
Public-key cryptography
Threshold signatures are digital signature schemes in which a set of $n$ signers specify a threshold $t$ such that any subset of size $t$ is authorized to produce signatures on behalf of the group. There has recently been a renewed interest in this primitive, largely driven by the need to secure highly valuable signing keys, e.g., DNSSEC keys or keys protecting digital wallets in the cryptocurrency ecosystem. Of special interest is FROST, a practical Schnorr threshold signature scheme, which...
Additive Randomized Encodings and Their Applications
Shai Halevi, Yuval Ishai, Eyal Kushilevitz, Tal Rabin
Foundations
Addition of $n$ inputs is often the easiest nontrivial function to compute securely. Motivated by several open questions, we ask what can be computed securely given only an oracle that computes the sum. Namely, what functions can be computed in a model where parties can only encode their input locally, then sum up the encodings over some Abelian group $\G$, and decode the result to get the function output.
An *additive randomized encoding* (ARE) of a function $f(x_1,\ldots,x_n)$ maps...
On the (Im)possibility of Distributed Samplers: Lower Bounds and Party-Dynamic Constructions
Damiano Abram, Maciej Obremski, Peter Scholl
Cryptographic protocols
Distributed samplers, introduced by Abram, Scholl and Yakoubov (Eurocrypt ’22), are a one-round, multi-party protocol for securely sampling from any distribution. We give new lower and upper bounds for constructing distributed samplers in challenging scenarios. First, we consider the feasibility of distributed samplers with a malicious adversary in the standard model; the only previous construction in this setting relies on a random oracle. We show that for any UC-secure construction in the...
The Query-Complexity of Preprocessing Attacks
Ashrujit Ghoshal, Stefano Tessaro
Foundations
A large number of works prove lower bounds on space-time trade-offs in preprocessing attacks, i.e., trade-offs between the size of the advice and the time needed to break a scheme given such advice. We contend that the question of how much {\em time} is needed to produce this advice is equally important, and often highly non-trivial. However, this question has received significantly less attention. In this paper, we present lower bounds on the complexity of preprocessing attacks that depend...
History-Free Sequential Aggregate Signatures from Generic Trapdoor Functions
Alessio Meneghetti, Edoardo Signorini
Public-key cryptography
A sequential aggregate signature (SAS) scheme allows multiple users to sequentially combine their respective signatures in order to reduce communication costs. Historically, early proposals required the use of trapdoor permutation (e.g., RSA).
In recent years, a number of attempts have been made to extend SAS schemes to post-quantum assumptions. Many post-quantum signatures have been proposed in the hash-and-sign paradigm, which requires the use of trapdoor functions and appears to be an...
Secure Computation with Shared EPR Pairs (Or: How to Teleport in Zero-Knowledge)
James Bartusek, Dakshita Khurana, Akshayaram Srinivasan
Cryptographic protocols
Can a sender non-interactively transmit one of two strings to a receiver without knowing which string was received? Does there exist minimally-interactive secure multiparty computation that only makes (black-box) use of symmetric-key primitives? We provide affirmative answers to these questions in a model where parties have access to shared EPR pairs, thus demonstrating the cryptographic power of this resource.
First, we construct a one-shot (i.e., single message) string oblivious...
A Framework for UC Secure Privacy Preserving Biometric Authentication using Efficient Functional Encryption
Johannes Ernst, Aikaterini Mitrokotsa
Cryptographic protocols
Despite its popularity, password based authentication is susceptible to various kinds of attacks, such as online or offline dictionary attacks. Employing biometric credentials in the authentication process can strengthen the provided security guarantees, but raises significant privacy concerns. This is mainly due to the inherent variability of biometric readings that prevents us from simply applying a standard hash function to them. In this paper we first propose an ideal functionality for...
Standard Model Time-Lock Puzzles: Defining Security and Constructing via Composition
Karim Eldefrawy, Sashidhar Jakkamsetti, Ben Terner, Moti Yung
Foundations
The introduction of time-lock puzzles initiated the study of publicly “sending information into the future.” For time-lock puzzles, the underlying security-enabling mechanism is the computational complexity of the operations needed to solve the puzzle, which must be tunable to reveal the solution after a predetermined time, and not before that time. Time-lock puzzles are typically constructed via a commitment to a secret, paired with a reveal algorithm that sequentially iterates a basic...
Programmable Payment Channels
Yibin Yang, Mohsen Minaei, Srinivasan Raghuraman, Ranjit Kumaresan, Duc V. Le, Mahdi Zamani
Applications
One approach for scaling blockchains is to create bilateral, offchain channels, known as payment/state channels, that can protect parties against cheating via onchain collateralization. While such channels have been studied extensively, not much attention has been given to programmability, where the parties can agree to dynamically enforce arbitrary conditions over their payments without going onchain.
We introduce the notion of a programmable payment channel ($\mathsf{PPC}$) that allows...
A Lower Bound on the Length of Signatures Based on Group Actions and Generic Isogenies
Dan Boneh, Jiaxin Guan, Mark Zhandry
Foundations
We give the first black box lower bound for signature protocols that can be described as group actions, which include many based on isogenies. We show that, for a large class of signature schemes making black box use of a (potentially non-abelian) group action, the signature length must be $\Omega(\lambda^2/\log\lambda)$. Our class of signatures generalizes all known signatures that derive security exclusively from the group action, and our lower bound matches the state of the art, showing...
Sender-binding Key Encapsulation
Rebecca Schwerdt, Laurin Benz, Wasilij Beskorovajnov, Sarai Eilebrecht, Jörn Müller-Quade, Astrid Ottenhues
Public-key cryptography
Secure communication is gained by combining encryption with authentication. In real-world applications encryption commonly takes the form of KEM-DEM hybrid encryption, which is combined with ideal authentication. The pivotal question is how weak the employed key encapsulation mechanism (KEM) is allowed to be to still yield universally composable (UC) secure communication when paired with symmetric encryption and ideal authentication. This question has so far been addressed for public-key...
Fully Succinct Batch Arguments for NP from Indistinguishability Obfuscation
Rachit Garg, Kristin Sheridan, Brent Waters, David J. Wu
Cryptographic protocols
Non-interactive batch arguments for $\mathsf{NP}$ provide a way to amortize the cost of $\mathsf{NP}$ verification across multiple instances. In particular, they allow a prover to convince a verifier of multiple $\mathsf{NP}$ statements with communication that scales sublinearly in the number of instances.
In this work, we study fully succinct batch arguments for $\mathsf{NP}$ in the common reference string (CRS) model where the length of the proof scales not only sublinearly in the...
CRS-Updatable Asymmetric Quasi-Adaptive NIZK Arguments
Behzad Abdolmaleki, Daniel Slamanig
Cryptographic protocols
A critical aspect for the practical use of non-interactive zero-knowledge (NIZK) arguments in the common reference string (CRS) model is the demand for a trusted setup, i.e., a trusted generation of the CRS. Recently, motivated by its increased use in real-world applications, there has been a growing interest in concepts that allow to reduce the trust in this setup. In particular one demands that the zero-knowledge and ideally also the soundness property hold even when the CRS generation is...
Towards Secure Evaluation of Online Functionalities (Corrected and Extended Version)
Andreas Klinger, Ulrike Meyer
Foundations
To date, ideal functionalities securely realized with secure multi-party computation (SMPC) mainly considers functions of the private inputs of a fixed number of a priori known parties. In this paper, we generalize these definitions such that protocols implementing online algorithms in a distributed fashion can be proven to be privacy-preserving. Online algorithms compute online functionalities that allow parties to arrive and leave over time, to provide multiple inputs and to obtain...
ELSA: Secure Aggregation for Federated Learning with Malicious Actors
Mayank Rathee, Conghao Shen, Sameer Wagh, Raluca Ada Popa
Cryptographic protocols
Federated learning (FL) is an increasingly popular
approach for machine learning (ML) in cases where the train-
ing dataset is highly distributed. Clients perform local training
on their datasets and the updates are then aggregated into
the global model. Existing protocols for aggregation are either
inefficient, or don’t consider the case of malicious actors in the
system. This is a major barrier in making FL an ideal solution
for privacy-sensitive ML applications. We present ELSA,...
TokenWeaver: Privacy Preserving and Post-Compromise Secure Attestation
Cas Cremers, Gal Horowitz, Charlie Jacomme, Eyal Ronen
Cryptographic protocols
Modern attestation based on Trusted Execution Environments (TEEs) can significantly reduce the risk of secret compromise, allowing users to securely perform sensitive computations such as running cryptographic protocols for authentication across security critical services. However, this has also made TEEs a high-value attack target, driving an arms race between novel compromise attacks and continuous TEEs updates.
Ideally, we want to achieve Post-Compromise Security (PCS): even after a...
Practical Asynchronous Distributed Key Generation: Improved Efficiency, Weaker Assumption, and Standard Model
Haibin Zhang, Sisi Duan, Chao Liu, Boxin Zhao, Xuanji Meng, Shengli Liu, Yong Yu, Fangguo Zhang, Liehuang Zhu
Cryptographic protocols
Distributed key generation (DKG) allows bootstrapping threshold cryptosystems without relying on a trusted party, nowadays enabling fully decentralized applications in blockchains and multiparty computation (MPC). While we have recently seen new advancements for asynchronous DKG (ADKG) protocols, their performance remains the bottleneck for many applications, with only one protocol being implemented (DYX+ ADKG, IEEE S&P 2022). DYX+ ADKG relies on the Decisional Composite Residuosity...
Finding Collisions for Round-Reduced Romulus-H
Marcel Nageler, Felix Pallua, Maria Eichlseder
Attacks and cryptanalysis
The hash function Romulus-H is a finalist in the NIST Lightweight Cryptography competition. It is based on the Hirose double block-length (DBL) construction which is provably secure when used with an ideal block cipher. However, in practice, ideal block ciphers can only be approximated. Therefore, the security of concrete instantiations must be cryptanalyzed carefully; the security margin may be higher or lower than in the secret-key setting. So far, the Hirose DBL construction has been...
Anonymous Tokens with Hidden Metadata Bit from Algebraic MACs
Melissa Chase, F. Betül Durak, Serge Vaudenay
Cryptographic protocols
On the one hand, the web needs to be secured from malicious activities such as bots or DoS attacks; on the other hand, such needs ideally should not justify services tracking people's activities on the web. Anonymous tokens provide a nice tradeoff between allowing an issuer to ensure that a user has been vetted and protecting the users' privacy. However, in some cases, whether or not a token is issued reveals a lot of information to an adversary about the strategies used to distinguish...
Verifiable Private Information Retrieval
Shany Ben-David, Yael Tauman Kalai, Omer Paneth
Cryptographic protocols
A computational PIR scheme allows a client to privately query a database hosted on a single server without downloading the entire database.
We introduce the notion of verifiable PIR (vPIR) where the server can convince the client that the database satisfies certain properties without additional rounds and while keeping the communication sub-linear. For example, the server can prove that the number of rows in the database that satisfy a predicate $P$ is exactly $n$.
We define security...
How to Hide MetaData in MLS-Like Secure Group Messaging: Simple, Modular, and Post-Quantum
Keitaro Hashimoto, Shuichi Katsumata, Thomas Prest
Cryptographic protocols
Secure group messaging (SGM) protocols allow large groups of users to communicate in a secure and asynchronous manner. In recent years, continuous group key agreements (CGKAs) have provided a powerful abstraction to reason on the security properties we expect from SGM protocols. While robust techniques have been developed to protect the contents of conversations in this context, it is in general more challenging to protect metadata (e.g. the identity and social relationships of group...
On Perfectly Secure Two-Party Computation for Symmetric Functionalities with Correlated Randomness
Bar Alon, Olga Nissenbaum, Eran Omri, Anat Paskin-Cherniavsky, Arpita Patra
Cryptographic protocols
A multiparty computation protocol is {\em perfectly secure} for some function $f$ if it perfectly emulates an ideal computation of $f$. Thus, perfect security is the strongest and most desirable notion of security, as it guarantees security in the face of any adversary and eliminates the dependency on any security parameter. Ben-Or et al. [STOC '88] and Chaum et al. [STOC '88] showed that any function can be computed with perfect security if strictly less than one-third of the parties can...
Beyond Uber: Instantiating Generic Groups via PGGs
Balthazar Bauer, Pooya Farshim, Patrick Harasser, Adam O'Neill
Foundations
The generic-group model (GGM) has been very successful in making the analyses of many cryptographic assumptions and protocols tractable. It is, however, well known that the GGM is “uninstantiable,” i.e., there are protocols secure in the GGM that are insecure when using any real-world group. This motivates the study of standard-model notions formalizing that a real-world group in some sense “looks generic.”
We introduce a standard-model definition called pseudo-generic group (PGG), where...
A Pairing-Free Signature Scheme from Correlation Intractable Hash Function and Strong Diffie-Hellman Assumption
Benoit Chevallier-Mames
Public-key cryptography
Goh and Jarecki (Eurocrypt 2003) showed how to get a signature scheme from the computational Diffie-Hellman assumption, and they introduced the name EDL for signatures of this type. The corresponding EDL family of signature schemes is remarkable for several reasons: elegance, simplicity and tight security. However, EDL security proofs stand in the random oracle model, and, to the best of our knowledge, extending this family without using an idealization of hash functions has never been...
Agile Cryptography: A Universally Composable Approach
Christian Badertscher, Michele Ciampi, Aggelos Kiayias
Foundations
Being capable of updating cryptographic algorithms is an inevitable and essential practice in cryptographic engineering. This cryptographic agility, as it has been called, is a fundamental desideratum for long term cryptographic system security that still poses significant challenges from a modeling perspective. For instance, current formulations of agility fail to express the fundamental security that is expected to stem from timely implementation updates, namely the fact that the system...
On the Optimal Succinctness and Efficiency of Functional Encryption and Attribute-Based Encryption
Aayush Jain, Huijia Lin, Ji Luo
Public-key cryptography
We investigate the optimal (asymptotic) efficiency of functional encryption (FE) and attribute-based encryption (ABE) by proving inherent space-time trade-offs and constructing nearly optimal schemes. We consider the general notion of partially hiding functional encryption (PHFE), capturing both FE and ABE, and the most efficient computation model of random-access machines (RAM). In PHFE, a secret key $\mathsf{sk}_f$ is associated with a function $f$, whereas a...
Round-Optimal Black-Box Secure Computation from Two-Round Malicious OT
Yuval Ishai, Dakshita Khurana, Amit Sahai, Akshayaram Srinivasan
Cryptographic protocols
We give round-optimal {\em black-box} constructions of two-party and multiparty protocols in the common random/reference string (CRS) model, with security against malicious adversaries, based on any two-round oblivious transfer (OT) protocol in the same model. Specifically, we obtain two types of results.
\begin{enumerate}
\item {\bf Two-party protocol.} We give a (two-round) {\it two-sided NISC} protocol that makes black-box use of two-round (malicious-secure) OT in the CRS model....
A Modular Approach to the Security Analysis of Two-Permutation Constructions
Yu Long Chen
Secret-key cryptography
Constructions based on two public permutation calls are very common in today’s cryptographic community. However, each time a new construction is introduced, a dedicated proof must be carried out to study the security of the construction. In this work, we propose a new tool to analyze the security of these constructions in a modular way. This tool is built on the idea of the classical mirror theory for block cipher based constructions, such that it can be used for security proofs in the ideal...
The Pseudorandom Oracle Model and Ideal Obfuscation
Aayush Jain, Huijia Lin, Ji Luo, Daniel Wichs
We introduce a new idealized model of hash functions, which we refer to as the *pseudorandom oracle* (${\mathrm{Pr}\mathcal{O}}$) model. Intuitively, it allows us to model cryptosystems that use the code of an ideal hash function in a non-black-box way. Formally, we model hash functions via a combination of a pseudorandom function (PRF) family and an ideal oracle. A user can initialize the hash function by choosing a PRF key $k$ and mapping it to a public handle $h$ using the oracle. ...
Leakage Certification Made Simple
Aakash Chowdhury, Arnab Roy, Carlo Brunetta, Elisabeth Oswald
Implementation
Side channel evaluations benefit from sound characterisations of adversarial leakage models, which are the determining factor for attack success. Two questions are of interest: can we estimate a quantity that captures the ideal adversary (who knows the distributions that are involved in an attack), and can we judge how good one (or several) given leakage models are in relation to the ideal adversary?
Existing work has led to a proliferation of custom quantities (the hypothetical...
A New Framework for Quantum Oblivious Transfer
Amit Agarwal, James Bartusek, Dakshita Khurana, Nishant Kumar
Foundations
We present a new template for building oblivious transfer from quantum information that we call the ``fixed basis'' framework. Our framework departs from prior work (eg., Crepeau and Kilian, FOCS '88) by fixing the correct choice of measurement basis used by each player, except for some hidden trap qubits that are intentionally measured in a conjugate basis.
We instantiate this template in the quantum random oracle model (QROM) to obtain simple protocols that implement, with security...
On the security of data markets: controlled Private Function Evaluation
István Vajda
Cryptographic protocols
The income of companies working on data markets steadily grows year by year. Private function evaluation (PFE) is a valuable tool in solving corresponding security problems. The task of Controlled Private Function Evaluation (CPFE) and its relaxed version (rCPFE) was proposed in [11]. We define an ideal functionality for the latter task and present a UC-secure realization of the functionality against static malicious parties. The core primitive is functional encryption (FE) and essentially...
DEEPAND: In-Depth Modeling of Correlated AND Gates for NLFSR-based Lightweight Block Ciphers
Amit Jana, Mostafizar Rahman, Dhiman Saha
Attacks and cryptanalysis
Automated cryptanalysis has taken center stage in the arena of cryptanalysis since the pioneering work by Mouha et al. which showcased the power of Mixed Integer Linear Programming (MILP) in solving cryptanalysis problems that otherwise, required significant effort. Since its inception, research in this area has moved in primarily two directions. One is to model more and more classical cryptanalysis tools as optimization problems to leverage the ease provided by state-of-the-art solvers. The...
Short Non-Malleable Codes from Related-Key Secure Block Ciphers, Revisited
Gianluca Brian, Antonio Faonio, João Ribeiro, Daniele Venturi
Cryptographic protocols
We construct non-malleable codes in the split-state model with codeword length $m + 3\lambda$ or $m+5\lambda$, where $m$ is the message size and $\lambda$ is the security parameter, depending on how conservative one is. Our scheme is very simple and involves a single call to a block cipher meeting a new security notion which we dub entropic fixed-related-key security, which essentially means that the block cipher behaves like a pseudorandom permutation when queried upon inputs sampled from a...
Finding All Impossible Differentials When Considering the DDT
Kai Hu, Thomas Peyrin, Meiqin Wang
Secret-key cryptography
Impossible differential (ID) cryptanalysis is one of the most important attacks on block ciphers.
The Mixed Integer Linear Programming (MILP) model is a popular method to determine whether a specific difference pair is an ID.
Unfortunately, due to the huge search space (approximately $2^{2n}$ for a cipher with a block size $n$ bits), we cannot leverage this technique to exhaust all difference pairs, which is a well-known long-standing problem.
In this paper, we propose a systematic...
2022/979
Last updated: 2022-09-07
Secure and Lightweight User Authentication Scheme for Cloud-Aided Internet of Things
Chenyu Wang, Ding Wang, Yihe Duan, Xiaofeng Tao
Cryptographic protocols
Cloud-aided Internet of Things (IoT) overcomes the resource-constrained nature of the traditional IoT and develops rapidly. In a cloud-aided IoT system, users can remotely control the IoT devices or send specific instructions to them. In this case, if the user identity is not verified, adversaries can send fake and malicious instructions to the IoT devices, thereby compromising the security of the entire system. Thus, an authentication mechanism is indispensable to ensure security. In a...
Non-Malleable Multi-Party Computation
Fuchun Lin
Foundations
We study a tamper-tolerant implementation security notion for general purpose Multi-Party Computation (MPC) protocols, as an analogue of the leakage-tolerant notion in the MPC literature. An MPC protocol is tamper-tolerant, or more specifically, non-malleable (with respect to a certain type of tampering) if the processing of the protocol under corruption of parties (and tampering of some ideal resource assumed by the protocol) can be simulated by an ideal world adversary who, after the...
Foundations of Coin Mixing Services
Noemi Glaeser, Matteo Maffei, Giulio Malavolta, Pedro Moreno-Sanchez, Erkan Tairi, Sri AravindaKrishnan Thyagarajan
Applications
Coin mixing services allow users to mix their cryptocurrency coins and thus enable unlinkable payments in a way that prevents tracking of honest users' coins by both the service provider and the users themselves. The easy bootstrapping of new users and backwards compatibility with cryptocurrencies (such as Bitcoin) with limited support for scripts are attractive features of this architecture, which has recently gained considerable attention in both academia and industry.
A recent work...
Estimating the Hidden Overheads in the BDGL Lattice Sieving Algorithm
Léo Ducas
Public-key cryptography
The lattice sieving algorithm based on list-decoding of Becker-Ducas-Gama-Laarhoven (SODA 2016) is currently at the center of cryptanalysis cost estimates of candidate lattice schemes for post-quantum standardization.
Yet, only an idealized version of this algorithm has been carefully modelled, i.e. given an efficient list-decoding oracle for a perfectly random spherical code. In this work, we propose an experimental analysis of the actual algorithm. The difficulty lies in estimating the...
2022/910
Last updated: 2022-07-21
Round Optimal Blind Signatures: Short Signatures with Post-Quantum Blindness
Shweta Agrawal, Jung Hee Cheon, Hyeongmin Choe, Damien Stehlé, Anshu Yadav
Public-key cryptography
Blind signatures are a fascinating primitive which allow a user to obtain signatures from a signer, while hiding the message. Tremendously useful, these have been studied extensively for decades. Yet, to the best of our knowledge, all concretely practical blind signatures rely on non-standard assumptions and/or achieve sub-optimal round complexity.
In this work, we provide an efficient, round-optimal (two-round) blind signature scheme from the hardness of the discrete log (DL) problem...
A Random Oracle for All of Us
Marc Fischlin, Felix Rohrbach, Tobias Schmalz
Foundations
We introduce the notion of a universal random oracle. Analogously to a classical random oracle it idealizes hash functions as random functions. However, as opposed to a classical random oracle which is created freshly and independently for each adversary, the universal random oracle should provide security of a cryptographic protocol against all adversaries simultaneously. This should even hold if the adversary now depends on the random function. This reflects better the idea that the strong...
Provably Secure Reflection Ciphers
Tim Beyne, Yu Long Chen
Secret-key cryptography
This paper provides the first analysis of reflection ciphers such as PRINCE from a provable security viewpoint.
As a first contribution, we initiate the study of key-alternating reflection ciphers in the ideal permutation model. Specifically, we prove the security of the two-round case and give matching attacks. The resulting security bound takes form \(O(qp^2/2^{2n}+q^2/2^n)\), where \(q\) is the number of construction evaluations and \(p\) is the number of direct adversarial queries to...
Quadratic Multiparty Randomized Encodings Beyond Honest Majority and Their Applications
Benny Applebaum, Yuval Ishai, Or Karni, Arpita Patra
Foundations
Multiparty randomized encodings (Applebaum, Brakerski, and Tsabary, SICOMP 2021) reduce the task of securely computing a complicated multiparty functionality $f$ to the task of securely computing a simpler functionality $g$. The reduction is non-interactive and preserves information-theoretic security against a passive (semi-honest) adversary, also referred to as privacy. The special case of a degree-2 encoding $g$ (2MPRE) has recently found several applications to secure multiparty...
Tight Preimage Resistance of the Sponge Construction
Charlotte Lefevre, Bart Mennink
Secret-key cryptography
The cryptographic sponge is a popular method for hash function design. The construction is in the ideal permutation model proven to be indifferentiable from a random oracle up to the birthday bound in the capacity of the sponge. This result in particular implies that, as long as the attack complexity does not exceed this bound, the sponge construction achieves a comparable level of collision, preimage, and second preimage resistance as a random oracle. We investigate these state-of-the-art...
Tight Multi-User Security Bound of $\textsf{DbHtS}$
Nilanjan Datta, Avijit Dutta, Mridul Nandi, Suprita Talnikar
Secret-key cryptography
In CRYPTO'21, Shen et al. have proved in the ideal cipher model that $\textsf{Two-Keyed-DbHtS}$ construction is secure up to $2^{2n/3}$ queries in the multi-user setting independent of the number of users, where the underlying double-block hash function $\textsf{H}$ of the \textsf{Two-Keyed-DbHtS} construction is realized as the concatenation of two independent $n$-bit keyed hash functions $(\textsf{H}_{K_h,1}, \textsf{H}_{K_h, 2})$ such that each of the $n$-bit keyed hash function is...
Refuting the Dream XOR Lemma via Ideal Obfuscation and Resettable MPC
Saikrishna Badrinarayanan, Yuval Ishai, Dakshita Khurana, Amit Sahai, Daniel Wichs
Foundations
We provide counterexamples to the ``dream'' version of Yao's XOR Lemma. In particular, we put forward explicit candidates for hard predicates, such that the advantage of predicting the XOR of many independent copies does not decrease beyond some fixed negligible function, even as the number of copies gets arbitrarily large.
We provide two such constructions:
1) Our first construction is in the ideal obfuscation model (alternatively, assuming virtual black-box obfuscation for a concrete...
SO-CCA Secure PKE in the Quantum Random Oracle Model or the Quantum Ideal Cipher Model
Shingo Sato, Junji Shikata
Public-key cryptography
Selective opening (SO) security is one of the most important security notions of public key encryption (PKE) in a multi-user setting. Even though messages and random coins used in some ciphertexts are leaked, SO security guarantees the confidentiality of the other ciphertexts. Actually, it is shown that there exist PKE schemes which meet the standard security such as indistinguishability against chosen ciphertext attacks (IND-CCA security) but do not meet SO security against chosen...
Security Against Honorific Adversaries: Efficient MPC with Server-aided Public Verifiability
Li Duan, Yufan Jiang, Yong Li, Jörn Müller-Quade, Andy Rupp
Foundations
Secure multiparty computation (MPC) allows distrustful parties to jointly compute some functions while keeping their private secrets unrevealed. MPC adversaries are often categorized as semi-honest and malicious, depending on whether they follow the protocol specifications or not. Covert security was first introduced by Aumann and Lindell in 2007, which models a third type of active adversaries who cheat but can be caught with a probability. However, this probability is predefined...
The Generals’ Scuttlebutt: Byzantine-Resilient Gossip Protocols
Sandro Coretti, Aggelos Kiayias, Cristopher Moore, Alexander Russell
Cryptographic protocols
One of the most successful applications of peer-to-peer communication networks is in the context of blockchain protocols, which—in Satoshi Nakamoto's own words—rely on the "nature of information being easy to spread and hard to stifle." Significant efforts were invested in the last decade into analyzing the security of these protocols, and invariably the security arguments known for longest-chain Nakamoto-style consensus use an idealization of this tenet.
Unfortunately, the real-world...
Distributed (Correlation) Samplers: How to Remove a Trusted Dealer in One Round
Damiano Abram, Peter Scholl, Sophia Yakoubov
Cryptographic protocols
Structured random strings (SRSs) and correlated randomness are important for many cryptographic protocols. In settings where interaction is expensive, it is desirable to obtain such randomness in as few rounds of communication as possible; ideally, simply by exchanging one reusable round of messages which can be considered public keys.
In this paper, we describe how to generate any SRS or correlated randomness in such a single round of communication, using, among other things,...
On the Adaptive Security of the Threshold BLS Signature Scheme
Renas Bacho, Julian Loss
Foundations
Threshold signatures are a crucial tool for many distributed protocols. As shown by Cachin, Kursawe, and Shoup (PODC '00), schemes with unique signatures are of particular importance, as they allow to implement distributed coin flipping very efficiently and without any timing assumptions. This makes them an ideal building block for (inherently randomized) asynchronous consensus protocols. The threshold BLS signature of Boldyreva (PKC '03) is both unique and very compact, but unfortunately...
Jammin' on the deck
Norica Băcuieți, Joan Daemen, Seth Hoffert, Gilles Van Assche, Ronny Van Keer
Secret-key cryptography
Currently, a vast majority of symmetric-key cryptographic schemes are built as block cipher modes. The block cipher is designed to be hard to distinguish from a random permutation and this is supported by cryptanalysis, while (good) modes can be proven secure if a random permutation takes the place of the block cipher. As such, block ciphers form an abstraction level that marks the border between cryptanalysis and security proofs. In this paper, we investigate a re-factored version of...
Security of Truncated Permutation Without Initial Value
Lorenzo Grassi, Bart Mennink
Secret-key cryptography
Indifferentiability is a powerful notion in cryptography. If a construction is proven to be indifferentiable from an ideal object, it can under certain assumptions instantiate that ideal object in higher-level constructions. Indifferentiability is a particularly useful model for cryptographic hash functions, and myriad results are known proving that a hash function behaves like a random oracle under the assumption that the underlying primitive (typically a compression function, a block...
Universally Composable End-to-End Secure Messaging
Ran Canetti, Palak Jain, Marika Swanberg, Mayank Varia
Cryptographic protocols
We model and analyze the Signal end-to-end secure messaging protocol within the Universal Composability (UC) framework. Specifically:
(1) We formulate an ideal functionality that captures end-to-end secure messaging in a setting with Public Key Infrastructure (PKI) and an untrusted server, against an adversary that has full control over the network and can adaptively and momentarily compromise parties at any time, obtaining their entire internal states. Our analysis captures the forward...
Simple Three-Round Multiparty Schnorr Signing with Full Simulatability
Yehuda Lindell
Public-key cryptography
In a multiparty signing protocol, also known as a threshold signature scheme, the private signing key is shared amongst a set of parties and only a quorum of those parties can generate a signature. Research on multiparty signing has been growing in popularity recently due to its application to cryptocurrencies. Most work has focused on reducing the number of rounds to two, and as a result: (a) are not fully simulatable in the sense of MPC real/ideal security definitions, and/or (b) are not...
An Analysis of the Algebraic Group Model
Jonathan Katz, Cong Zhang, Hong-Sheng Zhou
Foundations
The algebraic group model (AGM), formalized by Fuchsbauer, Kiltz, and Loss, has recently received significant attention. One of the appealing properties of the AGM is that it is viewed as being (strictly) weaker than the generic group model (GGM), in the sense that hardness results for algebraic algorithms imply hardness results for generic algorithms, and generic reductions in the AGM (namely, between the algebraic formulations of two problems) imply generic reductions in the GGM. We...
Practical (Post-Quantum) Key Combiners from One-Wayness and Applications to TLS
Nimrod Aviram, Benjamin Dowling, Ilan Komargodski, Kenneth G. Paterson, Eyal Ronen, Eylon Yogev
The task of combining cryptographic keys, some of which may be maliciously formed, into one key, which is (pseudo)random is a central task in cryptographic systems. For example, it is a crucial component in the widely used TLS and Signal protocols. From an analytical standpoint, current security proofs model such key combiners as dual-PRFs -- a function which is a PRF when keyed by either of its two inputs -- guaranteeing pseudo-randomness if one of the keys is compromised or even...
Structural and Statistical Analysis of Multidimensional Linear Approximations of Random Functions and Permutations
Tomer Ashur, Mohsin Khan, Kaisa Nyberg
Secret-key cryptography
The goal of this paper is to investigate linear approximations of random functions and permutations. Our motivation is twofold. First, before the distinguishability of a practical cipher from an ideal one can be analysed, the cryptanalyst must have an accurate understanding of the statistical behaviour of the ideal cipher. Secondly, this issue has been neglected both in old and in more recent studies, particularly when multiple linear approximations are being used simultaneously. Traditional...
Longest Chain Consensus Under Bandwidth Constraint
Joachim Neu, Srivatsan Sridhar, Lei Yang, David Tse, Mohammad Alizadeh
Cryptographic protocols
Spamming attacks are a serious concern for consensus protocols, as witnessed by recent outages of a major blockchain, Solana. They cause congestion and excessive message delays in a real network due to its bandwidth constraints. In contrast, longest chain (LC), an important family of consensus protocols, has previously only been proven secure assuming an idealized network model in which all messages are delivered within bounded delay. This model-reality mismatch is further aggravated for...
Revisiting the Security of COMET Authenticated Encryption Scheme
Shay Gueron, Ashwin Jha, Mridul Nandi
Secret-key cryptography
COMETv1, by Gueron, Jha and Nandi, is a mode of operation for nonce-based authenticated encryption with associated data functionality. It was one of the second round candidates in the ongoing NIST Lightweight Cryptography Standardization Process. In this paper, we study a generalized version of COMETv1, that we call gCOMET, from provable security perspective. First, we present a comprehensive and complete security proof for gCOMET in the ideal cipher model. Second, we view COMET, the...
Perfect Trees: Designing Energy-Optimal Symmetric Encryption Primitives
Andrea Caforio, Subhadeep Banik, Yosuke Todo, Willi Meier, Takanori Isobe, Fukang Liu, Bin Zhang
Implementation
Energy efficiency is critical in battery-driven devices, and designing energy-
optimal symmetric-key ciphers is one of the goals for the use of ciphers in such
environments. In the paper by Banik et al. (IACR ToSC 2018), stream ciphers were
identified as ideal candidates for low-energy solutions. One of the main conclusions of
this paper was that Trivium, when implemented in an unrolled fashion, was by far the
most energy-efficient way of encrypting larger quantity of data. In fact, it was...
Non-randomness of S-unit lattices
Daniel J. Bernstein, Tanja Lange
Public-key cryptography
Spherical models of lattices are standard tools in the study of lattice-based cryptography, except for variations in terminology and minor details. Spherical models are used to predict the lengths of short vectors in lattices and the effectiveness of reduction modulo those short vectors. These predictions are consistent with an asymptotic theorem by Gauss, theorems on short vectors in almost all lattices from the invariant distribution, and a variety of experiments in the...
In this paper, we study the security of MAC constructions among those classified by Chen et al. in ASIACRYPT '21. Precisely, $F^{\text{EDM}}_{B_2}$ (or $\mathsf{EWCDM}$ as named by Cogliati and Seurin in CRYPTO '16), $F^{\text{EDM}}_{B_3}$, $F^{\text{SoP}}_{B_2}$, $F^{\text{SoP}}_{B_3}$ (all as named by Chen et al.) are proved to be fully secure up to $2^n$ MAC queries in the nonce-respecting setting, improving the previous bound of $\frac{3n}{4}$-bit security. In particular,...
We show that the adaptive compromise security definitions of Jaeger and Tyagi (Crypto '20) cannot be applied in several natural use-cases. These include proving multi-user security from single-user security, the security of the cascade PRF, and the security of schemes sharing the same ideal primitive. We provide new variants of the definitions and show that they resolve these issues with composition. Extending these definitions to the asymmetric settings, we establish the security of the...
In FSE'16, Luykx et al. have proposed $\textsf{LightMAC}$ that provably achieves a query length independent PRF security bound. To be precise, the construction achieves security roughly in the order of $O(q^2/2^n)$, when instantiated with two independently keyed $n$-bit block ciphers and $q$ is the total number of queries made by the adversary. Subsequently, in ASIACRYPT'17, Naito proposed a beyond-birthday-bound variant of the $\textsf{LightMAC}$ construction, dubbed as...
We extend the Linicrypt framework for characterizing hash function security as proposed by McQuoid, Swope, and Rosulek (TCC 2018) to support constructions in the ideal cipher model. In this setting, we give a characterization of collision- and second-preimage-resistance in terms of a linear-algebraic condition on Linicrypt programs, and present an efficient algorithm for determining whether a program satisfies the condition. As an application, we consider the case of the block cipherbased...
Recently, [eprint/2024/250] and [eprint/2024/347] proposed two algebraic attacks on the $\mathsf{Anemoi}$ permutation [Crypto '23]. In this note, we construct a Gröbner basis for the ideal generated by the naive modeling of the $\mathsf{CICO}$ problem associated to $\mathsf{Anemoi}$, in odd and in even characteristics, for one and several branches. We also infer the degree of the ideal from this Gröbner basis, while previous works relied on upper bounds.
MRAE security is an important goal for many AEAD applications where the nonce uniqueness cannot be maintained and security risks are significant. However, MRAE schemes can be quite expensive. Two of the SoTA MRAE-secure schemes; Deoxys-II and AES-GCM-SIV rely on internal parallelism and special instructions to achieve competitive performance. However, they both suffer from the same bottleneck, they have at least one call to the underlying primitive that cannot be parallelized to any other...
Cryptographic protocols are hard to design and prove correct, as witnessed by the ever-growing list of attacks even on protocol standards. Symbolic models of cryptography enable automated formal security proofs of such protocols against an idealized cryptographic model, which abstracts away from the algebraic properties of cryptographic schemes and thus misses attacks. Computational models of cryptography yield rigorous guarantees but support at present only interactive proofs and/or...
Ciphertext-independent updatable encryption (UE) allows to rotate encryption keys and update ciphertexts via a token without the need to first download the ciphertexts. Although, syntactically, UE is a symmetric-key primitive, ciphertext-independent UE with forward secrecy and post-compromise security is known to imply public-key encryption (Alamati, Montgomery and Patranabis, CRYPTO 2019). Constructing post-quantum secure UE turns out to be a difficult task. While lattices offer the...
Threshold signatures have recently seen a renewed interest due to applications in cryptocurrency while NIST has released a call for multi-party threshold schemes, with a deadline for submission expected for the first half of 2025. So far, all lattice-based threshold signatures requiring less than two-rounds are based on heavy tools such as (fully) homomorphic encryption (FHE) and homomorphic trapdoor commitments (HTDC). This is not unexpected considering that most efficient two-round...
In the common random string model, the parties executing a protocol have access to a uniformly random bit string. It is known that under standard intractability assumptions, we can realize any ideal functionality with universally composable (UC) security if a trusted common random string (CrS) setup is available. It was always a question of where this CrS should come from since the parties provably could not compute it themselves. Trust assumptions are required, so minimizing the level of...
Private Information Retrieval (PIR) is a two player protocol where the client, given some query $x \in [N]$ interacts with the server, which holds a $N$-bit string $\textsf{DB}$ in order to privately retrieve $\textsf{DB}[x]$. In this work, we focus on the single server client-preprocessing model, initially idealized by Corrigan-Gibbs and Kogan (EUROCRYPT 2020), where the client and server first run some joint preprocessing algorithm, after which the client can retrieve elements of the...
Structure-preserving signatures (SPS) have emerged as an important cryptographic building block, as their compatibility with the Groth-Sahai (GS) NIZK framework allows to construct protocols under standard assumptions with reasonable efficiency. Over the last years there has been a significant interest in the design of threshold signature schemes. However, only very recently Crites et al. (ASIACRYPT 2023) have introduced threshold SPS (TSPS) along with a fully non-interactive construction....
Several Password Authenticated Key Exchange (PAKE) protocols have been recently proposed that leverage a Key-Encapsulation Mechanism (KEM) to create an efficient and easy-to-implement post-quantum secure PAKE. This line of work is driven by the intention of the National Institute of Standards and Technology (NIST) to soon standardize a lattice-based post-quantum KEM called $\mathsf{Kyber}$. In two recent works, Beguinet et al. (ACNS 2023) and Pan and Zeng (ASIACRYPT 2023) proposed generic...
This paper studies the limitations of the generic approaches to solving cryptographic problems in classical and quantum settings in various models. - In the classical generic group model (GGM), we find simple alternative proofs for the lower bounds of variants of the discrete logarithm (DL) problem: the multiple-instance DL and one-more DL problems (and their mixture). We also re-prove the unknown-order GGM lower bounds, such as the order finding, root extraction, and repeated squaring. -...
We revisit the construction of signature scheme using the MPC-in-the-head paradigm, and focus in particular on constructions from the regular syndrome decoding assumption, a well-known variant of the syndrome decoding assumption. We obtain two main contributions: – We observe that previous signatures in the MPC-in-the-head paradigm must rely on a salted version of the GGM puncturable pseudorandom function (PPRF) to avoid collision attacks. We design a new efficient PPRF construction...
Additive randomized encodings (ARE), introduced by Halevi, Ishai, Kushilevitz, and Rabin (CRYPTO 2023), reduce the computation of a k-party function $f (x_1, . . . , x_k )$ to locally computing encodings $\hat{x}_i$ of each input xi and then adding them together over some Abelian group into an output encoding $\hat{y} = ∑ \hat{x}_i$, which reveals nothing but the result. In robust ARE (RARE) the sum of any subset of $\hat{x}_i$, reveals only the residual function obtained by restricting the...
Function secret sharing (FSS) for a class $\cal{F}$ allows to split a secret function $f \in \cal{F}$ into (succinct) secret shares $f_0,f_1$, such that for all $x\in \{0,1\}^n$ it holds $f_0(x)-f_1(x)=f(x)$. FSS has numerous applications, including private database queries, nearest neighbour search, private heavy hitters and secure computation in the preprocessing model, where the supported class $\cal{F}$ translates to richness in the application. Unfortunately, concretely efficient FSS...
We prove that the seminal KZG polynomial commitment scheme (PCS) is black-box extractable under a simple falsifiable assumption ARSDH. To create an interactive argument, we construct a compiler that combines a black-box extractable non-interactive PCS and a polynomial IOP (PIOP). The compiler incurs a minor cost per every committed polynomial. Applying the Fiat-Shamir transformation, we obtain slightly less efficient variants of well-known PIOP-based zk-SNARKs, such as Plonk, that are...
A zero-knowledge proof of training (zkPoT) enables a party to prove that they have correctly trained a committed model based on a committed dataset without revealing any additional information about the model or the dataset. An ideal zkPoT should offer provable security and privacy guarantees, succinct proof size and verifier runtime, and practical prover efficiency. In this work, we present Kaizen, a zkPoT targeted for deep neural networks (DNNs) that achieves the above ideals all at once....
We continue the study of $t$-wise independence of substitution-permutation networks (SPNs) initiated by the recent work of Liu, Tessaro, and Vaikuntanathan (CRYPTO 2021). Our key technical result shows that when the S-boxes are randomly and independently chosen and kept secret, an $r$-round SPN with input length $n = b \cdot k$ is $2^{-\Theta(n)}$-close to $t$-wise independent within $r = O(\min\{k, \log t\})$ rounds for any $t$ almost as large as $2^{b/2}$. Here, $b$ is the input length of...
ZK-SNARKs, a fundamental component of privacy-oriented payment systems, identity protocols, or anonymous voting systems, are advanced cryptographic protocols for verifiable computation: modern SNARKs allow to encode the invariants of a program, expressed as an arithmetic circuit, in an appropriate constraint language from which short, zero-knowledge proofs for correct computations can be constructed. One of the most important computations that is run through SNARK systems is the...
Basic encryption and signature on lattices have comparable efficiency to their classical counterparts in terms of speed and key size. However, Identity-based Encryption (IBE) on lattices is much less efficient in terms of compactness, even when instantiated on ideal lattices and in the Random Oracle Model (ROM). This is because the underlying preimage sampling algorithm used to extract the users' secret keys requires huge public parameters. In this work, we specify a compact IBE...
Driven by the open problem raised by Hofheinz and Kiltz (Journal of Cryptology, 2012), we study the formalization of lattice-based programmable hash function (PHF), and give three types of concrete constructions by using several techniques such as a novel combination of cover-free sets and lattice trapdoors. Under the Inhomogeneous Small Integer Solution (ISIS) assumption, we show that any (non-trivial) lattice-based PHF is a collision-resistant hash function, which gives a direct...
Quantum no-cloning theorem gives rise to the intriguing possibility of quantum copy protection where we encode a program in a quantum state such that a user in possession of $k$ such states cannot create $k+1$ working copies. Introduced by Aaronson (CCC'09) over a decade ago, copy protection has proven to be notoriously hard to achieve. In this work, we construct public-key encryption and functional encryption schemes whose secret keys are copy-protected against unbounded collusions in...
We introduce a new cryptographic primitive, called Completely Anonymous Signed Encryption (CASE). CASE is a public-key authenticated encryption primitive, that offers anonymity for senders as well as receivers. A "case-packet" should appear, without a (decryption) key for opening it, to be a blackbox that reveals no information at all about its contents. To decase a case-packet fully - so that the message is retrieved and authenticated - a verifcation key is also required. Defining security...
We consider the mainstream model in secure computation known as the bare PKI setup, also as the {bulletin-board PKI}. It allows players to broadcast once and non-interactively before they receive their inputs and start the execution. A bulletin-board PKI is essentially the minimum setup known so far to implement the model known as {messages-authentication}, i.e., when $P$ is forwarded a signed message, it considers it to be issued by $R$ if and only if $R$ signed it. It is known since...
Security proofs of symmetric-key primitives typically consider an idealized world with access to a (uniformly) random function. The starting point of our work is the observation that such an ideal world can lead to underestimating the actual security of certain primitives. As a demonstrating example, $\mathsf{XoP2}$, which relies on two independent random permutations, has been proven to exhibit superior concrete security compared to $\mathsf{XoP}$, which employs a single permutation with...
Proof-carrying data (PCD) is a powerful cryptographic primitive that allows mutually distrustful parties to perform distributed computation in an efficiently verifiable manner. Real-world deployments of PCD have sparked keen interest within the applied community and industry. Known constructions of PCD are obtained by recursively-composing SNARKs or related primitives. Unfortunately, known security analyses incur expensive blowups, which practitioners have disregarded as the analyses...
Adaptive security is a crucial property for garbling schemes in pushing the communication of garbled circuits to an offline phase when the input is unknown. In this paper, we show that the popular half-gates scheme by Zahur et al. (Eurocrypt'15), without any modification, is adaptively secure in the non-programmable random permutation model (npRPM). Since real implementations of selective-secure half-gates are already based on npRPM, our result shows that these implementations are already...
The KHAPE-HMQV protocol is a state-of-the-art highly efficient asymmetric password-authenticated key exchange protocol that provides several desirable security properties, but has the drawback of being vulnerable to quantum adversaries due to its reliance on discrete logarithm-based building blocks: solving a single discrete logarithm allows the attacker to perform an offline dictionary attack and recover the password. We show how to modify KHAPE-HMQV to make the protocol quantum-annoying: a...
Byzantine agreement (BA) asks for a set of parties to reach agreement in an adversarial setting. A central question is how to construct efficient BA protocols that scale well with the number of parties. In particular, the communication complexity is a critical barrier for large-scale implementations. State-of-the-art, scalable BA protocols typically work by sampling a small, unpredictable committee of parties that will send messages in each round. These messages must reach all honest...
We revisit OCAKE (ACNS 23), a generic recipe that constructs password-based authenticated key exchange (PAKE) from key encapsulation mechanisms (KEMs) in a black-box way. This allows to potentially achieve post-quantum security by instantiating the KEM with a post-quantum KEM like KYBER. It was left as an open problem to further adapt the proof such that it also holds against quantum attackers. The security proof is given in the universal composability (UC) framework, which is common for...
The constant-sized polynomial commitment scheme by Kate, Zaverucha, and Goldberg (Asiscrypt 2010), also known as the KZG commitment, is an essential component in designing bandwidth-efficient verifiable secret-sharing (VSS) protocols. We point out, however, that the KZG commitment is missing two important properties that are crucial for VSS protocols. First, the KZG commitment has not been proven to be degree binding in the standard adversary model without idealized group assumptions. In...
We propose a generic construction of password-based authenticated key exchange (PAKE) from key encapsulation mechanisms (KEM). Assuming that the KEM is oneway secure against plaintext-checkable attacks (OW-PCA), we prove that our PAKE protocol is \textit{tightly secure} in the Bellare-Pointcheval-Rogaway model (EUROCRYPT 2000). Our tight security proofs require ideal ciphers and random oracles. The OW-PCA security is relatively weak and can be implemented tightly with the Diffie-Hellman...
Physical side-channel attacks exploit a device's emanations to compromise the security of cryptographic implementations. Many countermeasures have been proposed against these attacks, especially the widely-used and efficient masking countermeasure. While theoretical models offer formal security proofs, they often rest on unrealistic assumptions, leading current approaches to prove the security of masked implementations to primarily rely on empirical verification. Consequently, the...
The random oracle model is an instrument used for proving that protocol has no structural flaws when settling with standard hash properties is impossible or fairly difficult. In practice, however, random oracles have to be instantiated with some specific hash functions, which are not random oracles. Hence, in the real world, an adversary has broader capabilities than considered in the random oracle proof — it can exploit the peculiarities of a specific hash function to achieve its goal. In a...
Most succinct arguments (SNARKs) are initially only proven knowledge sound (KS). We show that the commonly employed compilation strategy from polynomial interactive oracle proofs (PIOP) via polynomial commitments to knowledge sound SNARKS actually also achieves other desirable properties: weak unique response (WUR) and trapdoorless zero-knowledge (TLZK); and that together they imply simulation extractability (SIM-EXT). The factoring of SIM-EXT into KS + WUR + TLZK is becoming a...
Digital Signatures are ubiquitous in modern computing. One of the most widely used digital signature schemes is ECDSA due to its use in TLS, various Blockchains such as Bitcoin and Etherum, and many other applications. Yet the formal analysis of ECDSA is comparatively sparse. In particular, all known security results for ECDSA rely on some idealized model such as the generic group model or the programmable (bijective) random oracle model. In this work, we study the question whether these...
Threshold signatures are digital signature schemes in which a set of $n$ signers specify a threshold $t$ such that any subset of size $t$ is authorized to produce signatures on behalf of the group. There has recently been a renewed interest in this primitive, largely driven by the need to secure highly valuable signing keys, e.g., DNSSEC keys or keys protecting digital wallets in the cryptocurrency ecosystem. Of special interest is FROST, a practical Schnorr threshold signature scheme, which...
Addition of $n$ inputs is often the easiest nontrivial function to compute securely. Motivated by several open questions, we ask what can be computed securely given only an oracle that computes the sum. Namely, what functions can be computed in a model where parties can only encode their input locally, then sum up the encodings over some Abelian group $\G$, and decode the result to get the function output. An *additive randomized encoding* (ARE) of a function $f(x_1,\ldots,x_n)$ maps...
Distributed samplers, introduced by Abram, Scholl and Yakoubov (Eurocrypt ’22), are a one-round, multi-party protocol for securely sampling from any distribution. We give new lower and upper bounds for constructing distributed samplers in challenging scenarios. First, we consider the feasibility of distributed samplers with a malicious adversary in the standard model; the only previous construction in this setting relies on a random oracle. We show that for any UC-secure construction in the...
A large number of works prove lower bounds on space-time trade-offs in preprocessing attacks, i.e., trade-offs between the size of the advice and the time needed to break a scheme given such advice. We contend that the question of how much {\em time} is needed to produce this advice is equally important, and often highly non-trivial. However, this question has received significantly less attention. In this paper, we present lower bounds on the complexity of preprocessing attacks that depend...
A sequential aggregate signature (SAS) scheme allows multiple users to sequentially combine their respective signatures in order to reduce communication costs. Historically, early proposals required the use of trapdoor permutation (e.g., RSA). In recent years, a number of attempts have been made to extend SAS schemes to post-quantum assumptions. Many post-quantum signatures have been proposed in the hash-and-sign paradigm, which requires the use of trapdoor functions and appears to be an...
Can a sender non-interactively transmit one of two strings to a receiver without knowing which string was received? Does there exist minimally-interactive secure multiparty computation that only makes (black-box) use of symmetric-key primitives? We provide affirmative answers to these questions in a model where parties have access to shared EPR pairs, thus demonstrating the cryptographic power of this resource. First, we construct a one-shot (i.e., single message) string oblivious...
Despite its popularity, password based authentication is susceptible to various kinds of attacks, such as online or offline dictionary attacks. Employing biometric credentials in the authentication process can strengthen the provided security guarantees, but raises significant privacy concerns. This is mainly due to the inherent variability of biometric readings that prevents us from simply applying a standard hash function to them. In this paper we first propose an ideal functionality for...
The introduction of time-lock puzzles initiated the study of publicly “sending information into the future.” For time-lock puzzles, the underlying security-enabling mechanism is the computational complexity of the operations needed to solve the puzzle, which must be tunable to reveal the solution after a predetermined time, and not before that time. Time-lock puzzles are typically constructed via a commitment to a secret, paired with a reveal algorithm that sequentially iterates a basic...
One approach for scaling blockchains is to create bilateral, offchain channels, known as payment/state channels, that can protect parties against cheating via onchain collateralization. While such channels have been studied extensively, not much attention has been given to programmability, where the parties can agree to dynamically enforce arbitrary conditions over their payments without going onchain. We introduce the notion of a programmable payment channel ($\mathsf{PPC}$) that allows...
We give the first black box lower bound for signature protocols that can be described as group actions, which include many based on isogenies. We show that, for a large class of signature schemes making black box use of a (potentially non-abelian) group action, the signature length must be $\Omega(\lambda^2/\log\lambda)$. Our class of signatures generalizes all known signatures that derive security exclusively from the group action, and our lower bound matches the state of the art, showing...
Secure communication is gained by combining encryption with authentication. In real-world applications encryption commonly takes the form of KEM-DEM hybrid encryption, which is combined with ideal authentication. The pivotal question is how weak the employed key encapsulation mechanism (KEM) is allowed to be to still yield universally composable (UC) secure communication when paired with symmetric encryption and ideal authentication. This question has so far been addressed for public-key...
Non-interactive batch arguments for $\mathsf{NP}$ provide a way to amortize the cost of $\mathsf{NP}$ verification across multiple instances. In particular, they allow a prover to convince a verifier of multiple $\mathsf{NP}$ statements with communication that scales sublinearly in the number of instances. In this work, we study fully succinct batch arguments for $\mathsf{NP}$ in the common reference string (CRS) model where the length of the proof scales not only sublinearly in the...
A critical aspect for the practical use of non-interactive zero-knowledge (NIZK) arguments in the common reference string (CRS) model is the demand for a trusted setup, i.e., a trusted generation of the CRS. Recently, motivated by its increased use in real-world applications, there has been a growing interest in concepts that allow to reduce the trust in this setup. In particular one demands that the zero-knowledge and ideally also the soundness property hold even when the CRS generation is...
To date, ideal functionalities securely realized with secure multi-party computation (SMPC) mainly considers functions of the private inputs of a fixed number of a priori known parties. In this paper, we generalize these definitions such that protocols implementing online algorithms in a distributed fashion can be proven to be privacy-preserving. Online algorithms compute online functionalities that allow parties to arrive and leave over time, to provide multiple inputs and to obtain...
Federated learning (FL) is an increasingly popular approach for machine learning (ML) in cases where the train- ing dataset is highly distributed. Clients perform local training on their datasets and the updates are then aggregated into the global model. Existing protocols for aggregation are either inefficient, or don’t consider the case of malicious actors in the system. This is a major barrier in making FL an ideal solution for privacy-sensitive ML applications. We present ELSA,...
Modern attestation based on Trusted Execution Environments (TEEs) can significantly reduce the risk of secret compromise, allowing users to securely perform sensitive computations such as running cryptographic protocols for authentication across security critical services. However, this has also made TEEs a high-value attack target, driving an arms race between novel compromise attacks and continuous TEEs updates. Ideally, we want to achieve Post-Compromise Security (PCS): even after a...
Distributed key generation (DKG) allows bootstrapping threshold cryptosystems without relying on a trusted party, nowadays enabling fully decentralized applications in blockchains and multiparty computation (MPC). While we have recently seen new advancements for asynchronous DKG (ADKG) protocols, their performance remains the bottleneck for many applications, with only one protocol being implemented (DYX+ ADKG, IEEE S&P 2022). DYX+ ADKG relies on the Decisional Composite Residuosity...
The hash function Romulus-H is a finalist in the NIST Lightweight Cryptography competition. It is based on the Hirose double block-length (DBL) construction which is provably secure when used with an ideal block cipher. However, in practice, ideal block ciphers can only be approximated. Therefore, the security of concrete instantiations must be cryptanalyzed carefully; the security margin may be higher or lower than in the secret-key setting. So far, the Hirose DBL construction has been...
On the one hand, the web needs to be secured from malicious activities such as bots or DoS attacks; on the other hand, such needs ideally should not justify services tracking people's activities on the web. Anonymous tokens provide a nice tradeoff between allowing an issuer to ensure that a user has been vetted and protecting the users' privacy. However, in some cases, whether or not a token is issued reveals a lot of information to an adversary about the strategies used to distinguish...
A computational PIR scheme allows a client to privately query a database hosted on a single server without downloading the entire database. We introduce the notion of verifiable PIR (vPIR) where the server can convince the client that the database satisfies certain properties without additional rounds and while keeping the communication sub-linear. For example, the server can prove that the number of rows in the database that satisfy a predicate $P$ is exactly $n$. We define security...
Secure group messaging (SGM) protocols allow large groups of users to communicate in a secure and asynchronous manner. In recent years, continuous group key agreements (CGKAs) have provided a powerful abstraction to reason on the security properties we expect from SGM protocols. While robust techniques have been developed to protect the contents of conversations in this context, it is in general more challenging to protect metadata (e.g. the identity and social relationships of group...
A multiparty computation protocol is {\em perfectly secure} for some function $f$ if it perfectly emulates an ideal computation of $f$. Thus, perfect security is the strongest and most desirable notion of security, as it guarantees security in the face of any adversary and eliminates the dependency on any security parameter. Ben-Or et al. [STOC '88] and Chaum et al. [STOC '88] showed that any function can be computed with perfect security if strictly less than one-third of the parties can...
The generic-group model (GGM) has been very successful in making the analyses of many cryptographic assumptions and protocols tractable. It is, however, well known that the GGM is “uninstantiable,” i.e., there are protocols secure in the GGM that are insecure when using any real-world group. This motivates the study of standard-model notions formalizing that a real-world group in some sense “looks generic.” We introduce a standard-model definition called pseudo-generic group (PGG), where...
Goh and Jarecki (Eurocrypt 2003) showed how to get a signature scheme from the computational Diffie-Hellman assumption, and they introduced the name EDL for signatures of this type. The corresponding EDL family of signature schemes is remarkable for several reasons: elegance, simplicity and tight security. However, EDL security proofs stand in the random oracle model, and, to the best of our knowledge, extending this family without using an idealization of hash functions has never been...
Being capable of updating cryptographic algorithms is an inevitable and essential practice in cryptographic engineering. This cryptographic agility, as it has been called, is a fundamental desideratum for long term cryptographic system security that still poses significant challenges from a modeling perspective. For instance, current formulations of agility fail to express the fundamental security that is expected to stem from timely implementation updates, namely the fact that the system...
We investigate the optimal (asymptotic) efficiency of functional encryption (FE) and attribute-based encryption (ABE) by proving inherent space-time trade-offs and constructing nearly optimal schemes. We consider the general notion of partially hiding functional encryption (PHFE), capturing both FE and ABE, and the most efficient computation model of random-access machines (RAM). In PHFE, a secret key $\mathsf{sk}_f$ is associated with a function $f$, whereas a...
We give round-optimal {\em black-box} constructions of two-party and multiparty protocols in the common random/reference string (CRS) model, with security against malicious adversaries, based on any two-round oblivious transfer (OT) protocol in the same model. Specifically, we obtain two types of results. \begin{enumerate} \item {\bf Two-party protocol.} We give a (two-round) {\it two-sided NISC} protocol that makes black-box use of two-round (malicious-secure) OT in the CRS model....
Constructions based on two public permutation calls are very common in today’s cryptographic community. However, each time a new construction is introduced, a dedicated proof must be carried out to study the security of the construction. In this work, we propose a new tool to analyze the security of these constructions in a modular way. This tool is built on the idea of the classical mirror theory for block cipher based constructions, such that it can be used for security proofs in the ideal...
We introduce a new idealized model of hash functions, which we refer to as the *pseudorandom oracle* (${\mathrm{Pr}\mathcal{O}}$) model. Intuitively, it allows us to model cryptosystems that use the code of an ideal hash function in a non-black-box way. Formally, we model hash functions via a combination of a pseudorandom function (PRF) family and an ideal oracle. A user can initialize the hash function by choosing a PRF key $k$ and mapping it to a public handle $h$ using the oracle. ...
Side channel evaluations benefit from sound characterisations of adversarial leakage models, which are the determining factor for attack success. Two questions are of interest: can we estimate a quantity that captures the ideal adversary (who knows the distributions that are involved in an attack), and can we judge how good one (or several) given leakage models are in relation to the ideal adversary? Existing work has led to a proliferation of custom quantities (the hypothetical...
We present a new template for building oblivious transfer from quantum information that we call the ``fixed basis'' framework. Our framework departs from prior work (eg., Crepeau and Kilian, FOCS '88) by fixing the correct choice of measurement basis used by each player, except for some hidden trap qubits that are intentionally measured in a conjugate basis. We instantiate this template in the quantum random oracle model (QROM) to obtain simple protocols that implement, with security...
The income of companies working on data markets steadily grows year by year. Private function evaluation (PFE) is a valuable tool in solving corresponding security problems. The task of Controlled Private Function Evaluation (CPFE) and its relaxed version (rCPFE) was proposed in [11]. We define an ideal functionality for the latter task and present a UC-secure realization of the functionality against static malicious parties. The core primitive is functional encryption (FE) and essentially...
Automated cryptanalysis has taken center stage in the arena of cryptanalysis since the pioneering work by Mouha et al. which showcased the power of Mixed Integer Linear Programming (MILP) in solving cryptanalysis problems that otherwise, required significant effort. Since its inception, research in this area has moved in primarily two directions. One is to model more and more classical cryptanalysis tools as optimization problems to leverage the ease provided by state-of-the-art solvers. The...
We construct non-malleable codes in the split-state model with codeword length $m + 3\lambda$ or $m+5\lambda$, where $m$ is the message size and $\lambda$ is the security parameter, depending on how conservative one is. Our scheme is very simple and involves a single call to a block cipher meeting a new security notion which we dub entropic fixed-related-key security, which essentially means that the block cipher behaves like a pseudorandom permutation when queried upon inputs sampled from a...
Impossible differential (ID) cryptanalysis is one of the most important attacks on block ciphers. The Mixed Integer Linear Programming (MILP) model is a popular method to determine whether a specific difference pair is an ID. Unfortunately, due to the huge search space (approximately $2^{2n}$ for a cipher with a block size $n$ bits), we cannot leverage this technique to exhaust all difference pairs, which is a well-known long-standing problem. In this paper, we propose a systematic...
Cloud-aided Internet of Things (IoT) overcomes the resource-constrained nature of the traditional IoT and develops rapidly. In a cloud-aided IoT system, users can remotely control the IoT devices or send specific instructions to them. In this case, if the user identity is not verified, adversaries can send fake and malicious instructions to the IoT devices, thereby compromising the security of the entire system. Thus, an authentication mechanism is indispensable to ensure security. In a...
We study a tamper-tolerant implementation security notion for general purpose Multi-Party Computation (MPC) protocols, as an analogue of the leakage-tolerant notion in the MPC literature. An MPC protocol is tamper-tolerant, or more specifically, non-malleable (with respect to a certain type of tampering) if the processing of the protocol under corruption of parties (and tampering of some ideal resource assumed by the protocol) can be simulated by an ideal world adversary who, after the...
Coin mixing services allow users to mix their cryptocurrency coins and thus enable unlinkable payments in a way that prevents tracking of honest users' coins by both the service provider and the users themselves. The easy bootstrapping of new users and backwards compatibility with cryptocurrencies (such as Bitcoin) with limited support for scripts are attractive features of this architecture, which has recently gained considerable attention in both academia and industry. A recent work...
The lattice sieving algorithm based on list-decoding of Becker-Ducas-Gama-Laarhoven (SODA 2016) is currently at the center of cryptanalysis cost estimates of candidate lattice schemes for post-quantum standardization. Yet, only an idealized version of this algorithm has been carefully modelled, i.e. given an efficient list-decoding oracle for a perfectly random spherical code. In this work, we propose an experimental analysis of the actual algorithm. The difficulty lies in estimating the...
Blind signatures are a fascinating primitive which allow a user to obtain signatures from a signer, while hiding the message. Tremendously useful, these have been studied extensively for decades. Yet, to the best of our knowledge, all concretely practical blind signatures rely on non-standard assumptions and/or achieve sub-optimal round complexity. In this work, we provide an efficient, round-optimal (two-round) blind signature scheme from the hardness of the discrete log (DL) problem...
We introduce the notion of a universal random oracle. Analogously to a classical random oracle it idealizes hash functions as random functions. However, as opposed to a classical random oracle which is created freshly and independently for each adversary, the universal random oracle should provide security of a cryptographic protocol against all adversaries simultaneously. This should even hold if the adversary now depends on the random function. This reflects better the idea that the strong...
This paper provides the first analysis of reflection ciphers such as PRINCE from a provable security viewpoint. As a first contribution, we initiate the study of key-alternating reflection ciphers in the ideal permutation model. Specifically, we prove the security of the two-round case and give matching attacks. The resulting security bound takes form \(O(qp^2/2^{2n}+q^2/2^n)\), where \(q\) is the number of construction evaluations and \(p\) is the number of direct adversarial queries to...
Multiparty randomized encodings (Applebaum, Brakerski, and Tsabary, SICOMP 2021) reduce the task of securely computing a complicated multiparty functionality $f$ to the task of securely computing a simpler functionality $g$. The reduction is non-interactive and preserves information-theoretic security against a passive (semi-honest) adversary, also referred to as privacy. The special case of a degree-2 encoding $g$ (2MPRE) has recently found several applications to secure multiparty...
The cryptographic sponge is a popular method for hash function design. The construction is in the ideal permutation model proven to be indifferentiable from a random oracle up to the birthday bound in the capacity of the sponge. This result in particular implies that, as long as the attack complexity does not exceed this bound, the sponge construction achieves a comparable level of collision, preimage, and second preimage resistance as a random oracle. We investigate these state-of-the-art...
In CRYPTO'21, Shen et al. have proved in the ideal cipher model that $\textsf{Two-Keyed-DbHtS}$ construction is secure up to $2^{2n/3}$ queries in the multi-user setting independent of the number of users, where the underlying double-block hash function $\textsf{H}$ of the \textsf{Two-Keyed-DbHtS} construction is realized as the concatenation of two independent $n$-bit keyed hash functions $(\textsf{H}_{K_h,1}, \textsf{H}_{K_h, 2})$ such that each of the $n$-bit keyed hash function is...
We provide counterexamples to the ``dream'' version of Yao's XOR Lemma. In particular, we put forward explicit candidates for hard predicates, such that the advantage of predicting the XOR of many independent copies does not decrease beyond some fixed negligible function, even as the number of copies gets arbitrarily large. We provide two such constructions: 1) Our first construction is in the ideal obfuscation model (alternatively, assuming virtual black-box obfuscation for a concrete...
Selective opening (SO) security is one of the most important security notions of public key encryption (PKE) in a multi-user setting. Even though messages and random coins used in some ciphertexts are leaked, SO security guarantees the confidentiality of the other ciphertexts. Actually, it is shown that there exist PKE schemes which meet the standard security such as indistinguishability against chosen ciphertext attacks (IND-CCA security) but do not meet SO security against chosen...
Secure multiparty computation (MPC) allows distrustful parties to jointly compute some functions while keeping their private secrets unrevealed. MPC adversaries are often categorized as semi-honest and malicious, depending on whether they follow the protocol specifications or not. Covert security was first introduced by Aumann and Lindell in 2007, which models a third type of active adversaries who cheat but can be caught with a probability. However, this probability is predefined...
One of the most successful applications of peer-to-peer communication networks is in the context of blockchain protocols, which—in Satoshi Nakamoto's own words—rely on the "nature of information being easy to spread and hard to stifle." Significant efforts were invested in the last decade into analyzing the security of these protocols, and invariably the security arguments known for longest-chain Nakamoto-style consensus use an idealization of this tenet. Unfortunately, the real-world...
Structured random strings (SRSs) and correlated randomness are important for many cryptographic protocols. In settings where interaction is expensive, it is desirable to obtain such randomness in as few rounds of communication as possible; ideally, simply by exchanging one reusable round of messages which can be considered public keys. In this paper, we describe how to generate any SRS or correlated randomness in such a single round of communication, using, among other things,...
Threshold signatures are a crucial tool for many distributed protocols. As shown by Cachin, Kursawe, and Shoup (PODC '00), schemes with unique signatures are of particular importance, as they allow to implement distributed coin flipping very efficiently and without any timing assumptions. This makes them an ideal building block for (inherently randomized) asynchronous consensus protocols. The threshold BLS signature of Boldyreva (PKC '03) is both unique and very compact, but unfortunately...
Currently, a vast majority of symmetric-key cryptographic schemes are built as block cipher modes. The block cipher is designed to be hard to distinguish from a random permutation and this is supported by cryptanalysis, while (good) modes can be proven secure if a random permutation takes the place of the block cipher. As such, block ciphers form an abstraction level that marks the border between cryptanalysis and security proofs. In this paper, we investigate a re-factored version of...
Indifferentiability is a powerful notion in cryptography. If a construction is proven to be indifferentiable from an ideal object, it can under certain assumptions instantiate that ideal object in higher-level constructions. Indifferentiability is a particularly useful model for cryptographic hash functions, and myriad results are known proving that a hash function behaves like a random oracle under the assumption that the underlying primitive (typically a compression function, a block...
We model and analyze the Signal end-to-end secure messaging protocol within the Universal Composability (UC) framework. Specifically: (1) We formulate an ideal functionality that captures end-to-end secure messaging in a setting with Public Key Infrastructure (PKI) and an untrusted server, against an adversary that has full control over the network and can adaptively and momentarily compromise parties at any time, obtaining their entire internal states. Our analysis captures the forward...
In a multiparty signing protocol, also known as a threshold signature scheme, the private signing key is shared amongst a set of parties and only a quorum of those parties can generate a signature. Research on multiparty signing has been growing in popularity recently due to its application to cryptocurrencies. Most work has focused on reducing the number of rounds to two, and as a result: (a) are not fully simulatable in the sense of MPC real/ideal security definitions, and/or (b) are not...
The algebraic group model (AGM), formalized by Fuchsbauer, Kiltz, and Loss, has recently received significant attention. One of the appealing properties of the AGM is that it is viewed as being (strictly) weaker than the generic group model (GGM), in the sense that hardness results for algebraic algorithms imply hardness results for generic algorithms, and generic reductions in the AGM (namely, between the algebraic formulations of two problems) imply generic reductions in the GGM. We...
The task of combining cryptographic keys, some of which may be maliciously formed, into one key, which is (pseudo)random is a central task in cryptographic systems. For example, it is a crucial component in the widely used TLS and Signal protocols. From an analytical standpoint, current security proofs model such key combiners as dual-PRFs -- a function which is a PRF when keyed by either of its two inputs -- guaranteeing pseudo-randomness if one of the keys is compromised or even...
The goal of this paper is to investigate linear approximations of random functions and permutations. Our motivation is twofold. First, before the distinguishability of a practical cipher from an ideal one can be analysed, the cryptanalyst must have an accurate understanding of the statistical behaviour of the ideal cipher. Secondly, this issue has been neglected both in old and in more recent studies, particularly when multiple linear approximations are being used simultaneously. Traditional...
Spamming attacks are a serious concern for consensus protocols, as witnessed by recent outages of a major blockchain, Solana. They cause congestion and excessive message delays in a real network due to its bandwidth constraints. In contrast, longest chain (LC), an important family of consensus protocols, has previously only been proven secure assuming an idealized network model in which all messages are delivered within bounded delay. This model-reality mismatch is further aggravated for...
COMETv1, by Gueron, Jha and Nandi, is a mode of operation for nonce-based authenticated encryption with associated data functionality. It was one of the second round candidates in the ongoing NIST Lightweight Cryptography Standardization Process. In this paper, we study a generalized version of COMETv1, that we call gCOMET, from provable security perspective. First, we present a comprehensive and complete security proof for gCOMET in the ideal cipher model. Second, we view COMET, the...
Energy efficiency is critical in battery-driven devices, and designing energy- optimal symmetric-key ciphers is one of the goals for the use of ciphers in such environments. In the paper by Banik et al. (IACR ToSC 2018), stream ciphers were identified as ideal candidates for low-energy solutions. One of the main conclusions of this paper was that Trivium, when implemented in an unrolled fashion, was by far the most energy-efficient way of encrypting larger quantity of data. In fact, it was...
Spherical models of lattices are standard tools in the study of lattice-based cryptography, except for variations in terminology and minor details. Spherical models are used to predict the lengths of short vectors in lattices and the effectiveness of reduction modulo those short vectors. These predictions are consistent with an asymptotic theorem by Gauss, theorems on short vectors in almost all lattices from the invariant distribution, and a variety of experiments in the...
