440 results sorted by ID
Possible spell-corrected query: Cryptographic has Functions
Performance and Privacy: A Low-Latency Secure Anonymous Authentication Protocol with OPRF
Wenjv Hu, Yanping Ye, Yin Li
Cryptographic protocols
erforming privacy-preserving queries, particularly anonymous authentication, against large-scale datasets presents critical tradeoffs between security, latency, scalability. Existing cryptographic solutions often impose linear
computation or communication overheads. This paper introduces a novel,
efficient protocol for secure anonymous authentication, uniquely combining matrix partitioning via hash prefixes with Oblivious Pseudorandom Functions in a
three-server semi-honest model....
Cryptographic Treatment of Key Control Security -- In Light of NIST SP 800-108
Ritam Bhaumik, Avijit Dutta, Akiko Inoue, Tetsu Iwata, Ashwin Jha, Kazuhiko Minematsu, Mridul Nandi, Yu Sasaki, Meltem Sönmez Turan, Stefano Tessaro
Secret-key cryptography
This paper studies the security of key derivation functions (KDFs), a central class of cryptographic algorithms used to derive multiple independent-looking keys (each associated with a particular context) from a single secret. The main security requirement is that these keys are pseudorandom (i.e., the KDF is a pseudorandom function). This paper initiates the study of an additional security property, called key control (KC) security, first informally put forward in a recent update to NIST...
Cryptography meets worst-case complexity: Optimal security and more from iO and worst-case assumptions
Rahul Ilango, Alex Lombardi
Foundations
We study several problems in the intersection of cryptography and complexity theory based on the following high-level thesis.
1) Obfuscation can serve as a general-purpose worst-case to average-case reduction, reducing the existence of various forms of cryptography to corresponding worst-case assumptions.
2) We can therefore hope to overcome barriers in cryptography and average-case complexity by (i) making worst-case hardness assumptions beyond $\mathsf{P}\neq \mathsf{NP}$, and...
Leftover Hash Lemma(s) Over Cyclotomic Rings
Katharina Boudgoust, Oleksandra Lapiha
Foundations
In this work, we propose a novel systematic approach for obtaining leftover hash lemmas (LHLs) over cyclotomic rings. Such LHLs build a fundamental tool in lattice-based cryptography, both in theoretical reductions as well as in the design of cryptographic primitives. The scattered set of prior works makes it difficult to navigate the landscape and requires a substantial effort to understand the mathematical constraints under which the LHL holds over cyclotomic rings. This is especially...
Full Anonymity in the Asynchronous Setting from Peony Onion Encryption
Megumi Ando, Miranda Christ, Kashvi Gupta, Tal Malkin, Dane Smith
Cryptographic protocols
Onion routing is a popular practical approach to anonymous communication, and the subject of a growing body of foundational theoretical work aiming to design efficient schemes with provable anonymity, the strongest notion of which is full anonymity.
Unfortunately, all previous schemes that achieve full anonymity assume the synchronous communication setting, which is unrealistic as real networks may experience message loss and timing attacks that render such schemes insecure. Recently,...
Permutation-Based Hashing with Stronger (Second) Preimage Resistance - Application to Hash-Based Signature Schemes
Siwei Sun, Shun Li, Zhiyu Zhang, Charlotte Lefevre, Bart Mennink, Zhen Qin, Dengguo Feng
Secret-key cryptography
The sponge is a popular construction of hash function design. It operates with a $b$-bit permutation on a $b$-bit state, that is split into a $c$-bit inner part and an $r$-bit outer part. However, the security bounds of the sponge are most often dominated by the capacity $c$: If the length of the digest is $n$ bits, the construction achieves $\min\{n/2,c/2\}$-bit collision resistance and $\min\{n,c/2\}$-bit second preimage resistance (and a slightly more complex but similar bound for...
Breaking Poseidon Challenges with Graeffe Transforms and Complexity Analysis by FFT Lower Bounds
Ziyu Zhao, Jintai Ding
Attacks and cryptanalysis
Poseidon and Poseidon2 are cryptographic hash functions designed for efficient zero-knowledge proof protocols and have been widely adopted in Ethereum applications. To encourage security research, the Ethereum Foundation announced a bounty program in November 2024 for breaking the Poseidon challenges, i.e. solving the CICO (Constrained Input, Constrained Output) problems for round-reduced Poseidon constructions. In this paper, we explain how to apply the Graeffe transform to univariate...
Scrutinizing the Security of AES-based Hashing and One-way Functions
Shiyao Chen, Jian Guo, Eik List, Danping Shi, Tianyu Zhang
Attacks and cryptanalysis
AES has cemented its position as the primary symmetric-key primitive for a wide range of cryptographic applications, which motivates the analysis on the concrete security of AES in practical instantiations, for instance, the collision resistance of AES-based hashing, the key commitment security of AES-based authenticated encryption schemes, and the one-wayness of AES-based one-way functions in ZK and MPC protocols. In this work, we introduce single-color initial structures (SCIS) into...
Time-Space Tradeoffs of Truncation with Preprocessing
Krzysztof Pietrzak, Pengxiang Wang
Foundations
Truncation of cryptographic outputs is a technique that was recently introduced in Baldimtsi et al. [BCCK22]. The general idea is to try out many inputs to some cryptographic algorithm until the output (e.g. a public-key or some hash value) falls into some sparse set and thus can be compressed: by trying out an expected $2^k$ different inputs one will find an output that starts with $k$ zeros.
Using such truncation one can for example save substantial gas fees on Blockchains where...
Let us walk on the 3-isogeny graph: efficient, fast, and simple
Jesús-Javier Chi-Domínguez, Eduardo Ochoa-Jimenez, Ricardo-Neftalí Pontaza-Rodas
Public-key cryptography
Constructing and implementing isogeny-based cryptographic primitives is an active research. In particular, performing length-$n$ isogenies walks over quadratic field extensions of $\mathbb{F}_p$ plays an exciting role in some constructions, including
Hash functions, Verifiable Delay Functions, Key-Encapsulation Mechanisms, and generic proof systems for isogeny knowledge.
Remarkably, many isogeny-based constructions, for efficiency, perform $2$-isogenies through square root...
Adaptive Robustness of Hypergrid Johnson-Lindenstrauss
Andrej Bogdanov, Alon Rosen, Neekon Vafa, Vinod Vaikuntanathan
Foundations
Johnson and Lindenstrauss (Contemporary Mathematics, 1984) showed that for $n > m$, a scaled random projection $\mathbf{A}$ from $\mathbb{R}^n$ to $\mathbb{R}^m$ is an approximate isometry on any set $S$ of size at most exponential in $m$. If $S$ is larger, however, its points can contract arbitrarily under $\mathbf{A}$. In particular, the hypergrid $([-B, B] \cap \mathbb{Z})^n$ is expected to contain a point that is contracted by a factor of $\kappa_{\mathsf{stat}} = \Theta(B)^{-1/\alpha}$,...
Lattice-Based Sanitizable Signature Schemes: Chameleon Hash Functions and More
Sebastian Clermont, Samed Düzlü, Christian Janson, Laurens Porzenheim, Patrick Struck
Public-key cryptography
Sanitizable Signature Schemes (SSS) enable a designated party, the sanitizer, to modify predefined parts of a signed message without invalidating the signature, making them useful for applications like pseudonymization and redaction. Since their introduction by Ateniese et al. (ESORICS'05), several classical SSS constructions have been proposed, but none have been instantiated from quantum-resistant assumptions. In this work, we develop the first quantum-secure sanitizable signature schemes...
A Fiat-Shamir Transformation From Duplex Sponges
Alessandro Chiesa, Michele Orrù
Cryptographic protocols
The Fiat-Shamir transformation underlies numerous non-interactive arguments, with variants that differ in important ways. This paper addresses a gap between variants analyzed by theoreticians and variants implemented (and deployed) by practitioners. Specifically, theoretical analyses typically assume parties have access to random oracles with sufficiently large input and output size, while cryptographic hash functions in practice have fixed input and output sizes (pushing practitioners...
Black-Box Constant-Round Secure 2PC with Succinct Communication
Michele Ciampi, Ankit Kumar Misra, Rafail Ostrovsky, Akash Shah
Cryptographic protocols
The most fundamental performance metrics of secure multi-party computation (MPC) protocols are related to the number of messages the parties exchange (i.e., round complexity), the size of these messages (i.e., communication complexity), and the overall computational resources required to execute the protocol (i.e., computational complexity). Another quality metric of MPC protocols is related to the black-box or non-black-box use of the underlying cryptographic primitives. Indeed, the design...
SoK: Efficient Design and Implementation of Polynomial Hash Functions over Prime Fields
Jean Paul Degabriele, Jan Gilcher, Jérôme Govinden, Kenneth G. Paterson
Implementation
Poly1305 is a widely-deployed polynomial hash function. The rationale behind its design was laid out in a series of papers by Bernstein, the last of which dates back to 2005. As computer architectures evolved, some of its design features became less relevant, but implementers found new ways of exploiting these features to boost its performance. However, would we still converge to this same design if we started afresh with today's computer architectures and applications? To answer this...
Trapdoor Hash Functions and PIR from Low-Noise LPN
Damiano Abram, Giulio Malavolta, Lawrence Roy
Public-key cryptography
Trapdoor hash functions (TDHs) are compressing hash functions, with an additional trapdoor functionality: Given a encoding key for a function $f$, a hash on $x$ together with a (small) input encoding allow one to recover $f(x)$. TDHs are a versatile tool and a useful building block for more complex cryptographic protocols.
In this work, we propose the first TDH construction assuming the (quasi-polynomial) hardness of the LPN problem with noise rate $\epsilon = O(\log^{1+\beta} n / n)$ for...
Succinct Oblivious Tensor Evaluation and Applications: Adaptively-Secure Laconic Function Evaluation and Trapdoor Hashing for All Circuits
Damiano Abram, Giulio Malavolta, Lawrence Roy
Public-key cryptography
We propose the notion of succinct oblivious tensor evaluation (OTE), where two parties compute an additive secret sharing of a tensor product of two vectors $\mathbf{x} \otimes \mathbf{y}$, exchanging two simultaneous messages. Crucially, the size of both messages and of the CRS is independent of the dimension of $\mathbf{x}$.
We present a construction of OTE with optimal complexity from the standard learning with errors (LWE) problem. Then we show how this new technical tool enables a...
On the Adaptive Security of Free-XOR-based Garbling Schemes in the Plain Model
Anasuya Acharya, Karen Azari, Chethan Kamath
Foundations
A Garbling Scheme is a fundamental cryptographic primitive, with numerous theoretical and practical applications. Since its inception by Yao (FOCS'82, '86), optimizing the communication and computation complexities of securely garbling circuits has been an area of active research. One such optimization, and perhaps the most fundamental, is the `Free-XOR' technique (Kolesnikov and Schneider, ICALP'08) which allows XOR gates in a function garbling to not require representation, and therefore...
The Malice of ELFs: Practical Anamorphic-Resistant Encryption without Random Oracles
Gennaro Avitabile, Vincenzo Botta, Emanuele Giunta, Marcin Mielniczuk, Francesco Migliaro
Public-key cryptography
The concept of Anamorphic Encryption (Persiano, Phan and Yung, Eurocrypt '22), aims to enable private communication in settings where the usage of encryption is heavily controlled by a central authority (henceforth called the dictator) who can obtain users' secret keys.
Since then, various works have improved our understanding of AE in several aspects, including its limitations. To this regard, two recent works constructed various Anamorphic-Resistant Encryption (ARE) schemes, i.e., schemes...
Securely Instantiating 'Half Gates' Garbling in the Standard Model
Anasuya Acharya, Karen Azari, Mirza Ahad Baig, Dennis Hofheinz, Chethan Kamath
Foundations
Garbling is a fundamental cryptographic primitive, with numerous theoretical and practical applications. Since the first construction by Yao (FOCS’82, ’86), a line of work has concerned itself with reducing the communication and computational complexity of that construction. One of the most efficient garbling schemes presently is the ‘Half Gates’ scheme by Zahur, Rosulek, and Evans (Eurocrypt’15). Despite its widespread adoption, the provable security of this scheme has been based on...
Improved Resultant Attack against Arithmetization-Oriented Primitives
Augustin Bariant, Aurélien Boeuf, Pierre Briaud, Maël Hostettler, Morten Øygarden, Håvard Raddum
Attacks and cryptanalysis
In the last decade, the introduction of advanced cryptographic protocols operating on large finite fields $\mathbb{F}_q$ has raised the need for efficient cryptographic primitives in this setting, commonly referred to as Arithmetization-Oriented (AO). The cryptanalysis of AO hash functions is essentially done through the study of the CICO problem on the underlying permutation. Two recent works at Crypto 2024 and Asiacrypt 2024 managed to solve the CICO problem much more efficiently than...
On the Power of Polynomial Preprocessing: Proving Computations in Sublinear Time, and More
Matteo Campanelli, Mario Carrillo, Ignacio Cascudo, Dario Fiore, Danilo Francati, Rosario Gennaro
Cryptographic protocols
Cryptographic proof systems enable a verifier to be convinced of a computation's correctness without re-executing it; common efficiency requirements include both succinct proofs and fast verification. In this work we put forth the general study of cryptographic proof systems with \textit{sublinear} proving time (after a preprocessing).
Prior work has achieved sublinear proving only for limited computational settings (e.g., vector commitments and lookup arguments), relying on specific...
Preprocessing Security in Multiple Idealized Models with Applications to Schnorr Signatures and PSEC-KEM
Jeremiah Blocki, Seunghoon Lee
Public-key cryptography
In modern cryptography, relatively few instantiations of foundational cryptographic primitives are used across most cryptographic protocols. For example, elliptic curve groups are typically instantiated using P-256, P-384, Curve25519, or Curve448, while block ciphers are commonly instantiated with AES, and hash functions with SHA-2, SHA-3, or SHAKE. This limited diversity raises concerns that an adversary with nation-state-level resources could perform a preprocessing attack, generating a...
Skyscraper-v2: Fast Hashing on Big Primes
Clémence Bouvier, Lorenzo Grassi, Dmitry Khovratovich, Katharina Koschatko, Christian Rechberger, Fabian Schmid, Markus Schofnegger
Secret-key cryptography
Arithmetic hash functions defined over prime fields have been actively developed and used in verifiable computation (VC) protocols. Among those, elliptic-curve-based SNARKs require large (256-bit and higher) primes. Such hash functions are notably slow, losing a factor of up to 1000 compared to regular constructions like SHA-2/3.
In this paper, we present the hash function Skyscraper-v2, which is aimed at large prime fields and provides major improvements compared to Reinforced Concrete...
Hash-Based Multi-Signatures for Post-Quantum Ethereum
Justin Drake, Dmitry Khovratovich, Mikhail Kudinov, Benedikt Wagner
Public-key cryptography
With the threat posed by quantum computers on the horizon, systems like Ethereum must transition to cryptographic primitives resistant to quantum attacks. One of the most critical of these primitives is the non-interactive multi-signature scheme used in Ethereum's proof-of-stake consensus, currently implemented with BLS signatures. This primitive enables validators to independently sign blocks, with their signatures then publicly aggregated into a compact aggregate signature.
In this...
Vote&Check: Secure Postal Voting with Reduced Trust Assumptions
Véronique Cortier, Alexandre Debant, Pierrick Gaudry, Léo Louistisserand
Applications
Postal voting is a frequently used alternative to on-site voting. Traditionally, its security relies on organizational measures, and voters have to trust many entities. In the recent years, several schemes have been proposed to add verifiability properties to postal voting, while preserving vote privacy.
Postal voting comes with specific constraints. We conduct a systematic analysis of this setting and we identify a list of generic attacks, highlighting that some attacks seem unavoidable....
DGMT: A Fully Dynamic Group Signature From Symmetric-key Primitives
Mojtaba Fadavi, Sabyasachi Karati, Aylar Erfanian, Reihaneh Safavi-Naini
Foundations
A group signatures allows a user to sign a message anonymously on behalf of a group and provides accountability by using an opening authority who can ``open'' a signature and reveal the signer's identity. Group signatures have been widely used in privacy-preserving applications including anonymous attestation and anonymous authentication. Fully dynamic group signatures allow new members to join the group and existing members to be revoked if needed. Symmetric-key based group signature...
On the Insecurity of Bloom Filter-Based Private Set Intersections
Jelle Vos, Jorrit van Assen, Tjitske Koster, Evangelia Anna Markatou, Zekeriya Erkin
Attacks and cryptanalysis
Private set intersections are cryptographic protocols that compute the intersection of multiple parties' private sets without revealing elements that are not in the intersection. These protocols become less efficient when the number of parties grows, or the size of the sets increases. For this reason, many protocols are based on Bloom filters, which speed up the protocol by approximating the intersections, introducing false positives with a small but non-negligible probability. These false...
An Efficient and Secure Boolean Function Evaluation Protocol
Sushmita Sarkar, Vikas Srivastava, Tapaswini Mohanty, Nibedita Kundu, Sumit Kumar Debnath
Cryptographic protocols
Boolean functions play an important role in designing and analyzing many cryptographic systems, such as block ciphers, stream ciphers, and hash functions, due to their unique cryptographic properties such as nonlinearity, correlation immunity, and algebraic properties. The secure evaluation of Boolean functions or Secure Boolean Evaluation (SBE) is an important area of research. SBE allows parties to jointly compute Boolean functions without exposing their private inputs. SBE finds...
Resilience-Optimal Lightweight High-threshold Asynchronous Verifiable Secret Sharing
Hao Cheng, Jiliang Li, Yizhong Liu, Yuan Lu, Weizhi Meng, Zhenfeng Zhang
Cryptographic protocols
Shoup and Smart (SS24) recently introduced a lightweight asynchronous verifiable secret sharing (AVSS) protocol with optimal resilience directly from cryptographic hash functions (JoC 2024), offering plausible quantum resilience and computational efficiency. However, SS24 AVSS only achieves standard secrecy to keep the secret confidential against $n/3$ corrupted parties \textit{if no honest party publishes its share}. In contrast, from ``heavyweight'' public-key cryptography, one can...
Radical 2-isogenies and cryptographic hash functions in dimensions 1, 2 and 3
Sabrina Kunzweiler, Luciano Maino, Tomoki Moriya, Christophe Petit, Giacomo Pope, Damien Robert, Miha Stopar, Yan Bo Ti
Implementation
We provide explicit descriptions for radical 2-isogenies in dimensions
one, two and three using theta coordinates. These formulas allow us to efficiently
navigate in the corresponding isogeny graphs.
As an application of this, we implement different versions of the CGL hash func-
tion. Notably, the three-dimensional version is fastest, which demonstrates yet
another potential of using higher dimensional isogeny graphs in cryptography.
$\widetilde{\mbox{O}}$ptimal Adaptively Secure Hash-based Asynchronous Common Subset
Hanwen Feng, Zhenliang Lu, Qiang Tang
Cryptographic protocols
Asynchronous multiparty computation (AMPC) requires an input agreement phase where all participants have a consistent view of the set of private inputs. While the input agreement problem can be precisely addressed by a Byzantine fault-tolerant consensus known as Asynchronous Common Subset (ACS), existing ACS constructions with potential post-quantum security have a large $\widetilde{\mathcal{O}}(n^3)$ communication complexity for a network of $n$ nodes. This poses a bottleneck for AMPC in...
Overlapped Bootstrapping for FHEW/TFHE and Its Application to SHA3
Deokhwa Hong, Youngjin Choi, Yongwoo Lee, Young-Sik Kim
Implementation
Homomorphic Encryption (HE) enables operations on encrypted data without requiring decryption, thus allowing for secure handling of confidential data within smart contracts. Among the known HE schemes, FHEW and TFHE are particularly notable for use in smart contracts due to their lightweight nature and support for arbitrary logical gates. In contrast, other HE schemes often require several gigabytes of keys and are limited to supporting only addition and multiplication. As a result, there...
Instance Compression, Revisited
Gal Arnon, Shany Ben-David, Eylon Yogev
Foundations
Collision-resistant hashing (CRH) is a cornerstone of cryptographic protocols. However, despite decades of research, no construction of a CRH based solely on one-way functions has been found. Moreover, there are black-box limitations that separate these two primitives.
Harnik and Naor [HN10] overcame this black-box barrier by introducing the notion of instance compression. Instance compression reduces large NP instances to a size that depends on their witness size while preserving the...
Maximizing the Utility of Cryptographic Setups: Secure PAKEs, with either functional RO or CRS
Yuting Xiao, Rui Zhang, Hong-Sheng Zhou
Cryptographic protocols
For Password-Based Authenticated Key Exchange (PAKE), an idealized setup such as random oracle (RO) or a trusted setup such as common reference string (CRS) is a must in the universal composability (UC) framework (Canetti, FOCS 2001). Given the potential failure of a CRS or RO setup, it is natural to consider distributing trust among the two setups, resulting a CRS-or-RO-setup (i.e., CoR-setup).
However, the infeasibility highlighted by Katz et al. (PODC 2014) suggested that it is...
The Power of NAPs: Compressing OR-Proofs via Collision-Resistant Hashing
Katharina Boudgoust, Mark Simkin
Foundations
Proofs of partial knowledge, first considered by Cramer, Damgård and Schoenmakers (CRYPTO'94) and De Santis et al. (FOCS'94), allow for proving the validity of $k$ out of $n$ different statements without revealing which ones those are. In this work, we present a new approach for transforming certain proofs system into new ones that allows for proving partial knowledge. The communication complexity of the resulting proof system only depends logarithmically on the total number of statements...
Mystrium: Wide Block Encryption Efficient on Entry-Level Processors
Parisa Amiri Eliasi, Koustabh Ghosh, Joan Daemen
Secret-key cryptography
We present a tweakable wide block cipher called Mystrium and show it as the fastest such primitive on low-end processors that lack dedicated AES or other cryptographic instructions, such as ARM Cortex-A7.
Mystrium is based on the provably secure double-decker mode, that requires a doubly extendable cryptographic keyed (deck) function and a universal hash function.
We build a new deck function called Xymmer that for its compression part uses Multimixer-128, the fastest universal hash for...
$\Pi$-signHD: A New Structure for the SQIsign Family with Flexible Applicability
Kaizhan Lin, Weize Wang, Chang-An Zhao, Yunlei Zhao
Implementation
Digital signature is a fundamental cryptographic primitive and is widely used in the real world. Unfortunately, the current digital signature standards like EC-DSA and RSA are not quantum-resistant. Among post-quantum cryptography (PQC), isogeny-based signatures preserve some advantages of elliptic curve cryptosystems, particularly offering small signature sizes. Currently, SQIsign and its variants are the most promising isogeny-based digital signature schemes.
In this paper, we propose a...
Generalized Triangular Dynamical System: An Algebraic System for Constructing Cryptographic Permutations over Finite Fields
Arnab Roy, Matthias Johann Steiner
Secret-key cryptography
In recent years a new class of symmetric-key primitives over $\mathbb{F}_p$ that are essential to Multi-Party Computation and Zero-Knowledge Proofs based protocols has emerged. Towards improving the efficiency of such primitives, a number of new block ciphers and hash functions over $\mathbb{F}_p$ were proposed. These new primitives also showed that following alternative design strategies to the classical Substitution-Permutation Network (SPN) and Feistel Networks leads to more efficient...
Probabilistic Data Structures in the Wild: A Security Analysis of Redis
Mia Filić, Jonas Hofmann, Sam A. Markelon, Kenneth G. Paterson, Anupama Unnikrishnan
Attacks and cryptanalysis
Redis (Remote Dictionary Server) is a general purpose, in-memory database that supports a rich array of functionality, including various Probabilistic Data Structures (PDS), such as Bloom filters, Cuckoo filters, as well as cardinality and frequency estimators.
These PDS typically perform well in the average case. However, given that Redis is intended to be used across a diverse array of applications, it is crucial to evaluate how these PDS perform under worst-case scenarios, i.e., when...
Non-Interactive Zero-Knowledge from LPN and MQ
Quang Dao, Aayush Jain, Zhengzhong Jin
Cryptographic protocols
We give the first construction of non-interactive zero-knowledge (NIZK) arguments from post-quantum assumptions other than Learning with Errors. In particular, we achieve NIZK under the polynomial hardness of the Learning Parity with Noise (LPN) assumption, and the exponential hardness of solving random under-determined multivariate quadratic equations (MQ). We also construct NIZK satisfying statistical zero-knowledge assuming a new variant of LPN, Dense-Sparse LPN, introduced by Dao and...
Shift-invariant functions and almost liftings
Jan Kristian Haugland, Tron Omland
Foundations
We investigate shift-invariant vectorial Boolean functions on $n$ bits that are lifted from Boolean functions on $k$ bits, for $k\leq n$. We consider vectorial functions that are not necessarily permutations, but are, in some sense, almost bijective. In this context, we define an almost lifting as a Boolean function for which there is an upper bound on the number of collisions of its lifted functions that does not depend on $n$. We show that if a Boolean function with diameter $k$ is an...
Probabilistic Linearization: Internal Differential Collisions in up to 6 Rounds of SHA-3
Zhongyi Zhang, Chengan Hou, Meicheng Liu
Attacks and cryptanalysis
The SHA-3 standard consists of four cryptographic hash functions, called SHA3-224, SHA3-256, SHA3-384 and SHA3-512, and two extendable-output functions (XOFs), called SHAKE128 and SHAKE256. In this paper, we study the collision resistance of the SHA-3 instances. By analyzing the nonlinear layer, we introduce the concept of maximum difference density subspace, and develop a new target internal difference algorithm by probabilistic linearization. We also exploit new strategies for optimizing...
MATHEMATICAL SPECULATIONS ON CRYPTOGRAPHY
Anjali C B
Foundations
The current cryptographic frameworks like RSA, ECC, and AES are potentially under quantum threat. Quantum cryptographic and post-quantum cryptography are being extensively researched for securing future information. The quantum computer and quantum algorithms are still in the early developmental stage and thus lack scalability for practical application. As a result of these challenges, most researched PQC methods are lattice-based, code-based, ECC isogeny, hash-based, and multivariate...
Generalized Indifferentiable Sponge and its Application to Polygon Miden VM
Tomer Ashur, Amit Singh Bhati
Secret-key cryptography
Cryptographic hash functions are said to be the work-horses of modern cryptography. One of the strongest approaches to assess a cryptographic hash function's security is indifferentiability. Informally, indifferentiability measures to what degree the function resembles a random oracle when instantiated with an ideal underlying primitive. However, proving the indifferentiability security of hash functions has been challenging due to complex simulator designs and proof arguments. The Sponge...
A Tight Security Proof for $\mathrm{SPHINCS^{+}}$, Formally Verified
Manuel Barbosa, François Dupressoir, Andreas Hülsing, Matthias Meijers, Pierre-Yves Strub
Public-key cryptography
$\mathrm{SPHINCS^{+}}$ is a post-quantum signature scheme that, at the time of writing, is being standardized as $\mathrm{SLH\text{-}DSA}$. It is the most conservative option for post-quantum signatures, but the original tight proofs of security were flawed—as reported by Kudinov, Kiktenko and Fedorov in 2020. In this work, we formally prove a tight security bound for $\mathrm{SPHINCS^{+}}$ using the EasyCrypt proof assistant, establishing greater confidence in the general security of the...
Loquat: A SNARK-Friendly Post-Quantum Signature based on the Legendre PRF with Applications in Ring and Aggregate Signatures
Xinyu Zhang, Ron Steinfeld, Muhammed F. Esgin, Joseph K. Liu, Dongxi Liu, Sushmita Ruj
Cryptographic protocols
We design and implement a novel post-quantum signature scheme based on the Legendre PRF, named Loquat. Prior to this work, efficient approaches for constructing post-quantum signatures with comparable security assumptions mainly used the MPC-in-the-head paradigm or hash trees. Our method departs from these paradigms and, notably, is SNARK-friendly, a feature not commonly found in earlier designs. Loquat requires significantly fewer computational operations for verification than other...
Breaking Verifiable Delay Functions in the Random Oracle Model
Ziyi Guan, Artur Riazanov, Weiqiang Yuan
Foundations
This work resolves the open problem of whether verifiable delay functions (VDFs) can be constructed in the random oracle model.A VDF is a cryptographic primitive that requires a long time to compute (even with parallelization), but produces a unique output that is efficiently and publicly verifiable.
We prove that VDFs do not exist in the random oracle model. This also rules out black-box constructions of VDFs from other cryptographic primitives, such as one-way functions, one-way...
Automated Creation of Source Code Variants of a Cryptographic Hash Function Implementation Using Generative Pre-Trained Transformer Models
Elijah Pelofske, Vincent Urias, Lorie M. Liebrock
Implementation
Generative pre-trained transformers (GPT's) are a type of large language machine learning model that are unusually adept at producing novel, and coherent, natural language. Notably, these technologies have also been extended to computer programming languages with great success. However, GPT model outputs in general are stochastic and not always correct. For programming languages, the exact specification of the computer code, syntactically and algorithmically, is strictly required in order to...
Asynchronous Consensus without Trusted Setup or Public-Key Cryptography
Sourav Das, Sisi Duan, Shengqi Liu, Atsuki Momose, Ling Ren, Victor Shoup
Cryptographic protocols
Byzantine consensus is a fundamental building block in distributed cryptographic problems. Despite decades of research, most existing asynchronous consensus protocols require a strong trusted setup and expensive public-key cryptography. In this paper, we study asynchronous Byzantine consensus protocols that do not rely on a trusted setup and do not use public-key cryptography such as digital signatures. We give an Asynchronous Common Subset (ACS) protocol whose security is only based on...
2024/513
Last updated: 2025-02-26
Quantum Implementation and Analysis of SHA-2 and SHA-3
Kyungbae Jang, Sejin Lim, Yujin Oh, Hyunjun Kim, Anubhab Baksi, Sumanta Chakraborty, Hwajeong Seo
Implementation
Quantum computers have the potential to solve hard problems that are nearly impossible to solve by classical computers, this has sparked a surge of research to apply quantum technology and algorithm against the cryptographic systems to evaluate for its quantum resistance. In the process of selecting post-quantum standards, NIST categorizes security levels based on the complexity that quantum computers would require to crack AES encryption (levels 1, 3 and 5) and SHA-2 or SHA-3 (levels 2 and...
Faster Hash-based Multi-valued Validated Asynchronous Byzantine Agreement
Hanwen Feng, Zhenliang Lu, Tiancheng Mai, Qiang Tang
Cryptographic protocols
Multi-valued Validated Byzantine Agreement (MVBA) is vital for asynchronous distributed protocols like asynchronous BFT consensus and distributed key generation, making performance improvements a long-standing goal. Existing communication-optimal MVBA protocols rely on computationally intensive public-key cryptographic tools, such as non-interactive threshold signatures, which are also vulnerable to quantum attacks. While hash-based MVBA protocols have been proposed to address these...
A Cautionary Note: Side-Channel Leakage Implications of Deterministic Signature Schemes
Hermann Seuschek, Johann Heyszl, Fabrizio De Santis
Two recent proposals by Bernstein and Pornin emphasize the use of deterministic signatures in DSA and its elliptic curve-based variants. Deterministic signatures derive the required ephemeral key value in a deterministic manner from the message to be signed and the secret key instead of using random number generators. The goal is to prevent severe security issues, such as the straight-forward secret key recovery from low quality random numbers. Recent developments have raised skepticism...
Polynomial Commitments from Lattices: Post-Quantum Security, Fast Verification and Transparent Setup
Valerio Cini, Giulio Malavolta, Ngoc Khanh Nguyen, Hoeteck Wee
Cryptographic protocols
Polynomial commitment scheme allows a prover to commit to a polynomial $f \in \mathcal{R}[X]$ of degree $L$, and later prove that the committed function was correctly evaluated at a specified point $x$; in other words $f(x)=u$ for public $x,u \in\mathcal{R}$. Most applications of polynomial commitments, e.g. succinct non-interactive arguments of knowledge (SNARKs), require that (i) both the commitment and evaluation proof are succinct (i.e., polylogarithmic in the degree $L$) - with the...
Fiat-Shamir for Bounded-Depth Adversaries
Liyan Chen, Yilei Chen, Zikuan Huang, Nuozhou Sun, Tianqi Yang, Yiding Zhang
Foundations
We study how to construct hash functions that can securely instantiate the Fiat-Shamir transformation against bounded-depth adversaries. The motivation is twofold. First, given the recent fruitful line of research of constructing cryptographic primitives against bounded-depth adversaries under worst-case complexity assumptions, and the rich applications of Fiat-Shamir, instantiating Fiat-Shamir hash functions against bounded-depth adversaries under worst-case complexity assumptions might...
Lossy Cryptography from Code-Based Assumptions
Quang Dao, Aayush Jain
Public-key cryptography
Over the past few decades, we have seen a proliferation of advanced cryptographic primitives with lossy or homomorphic properties built from various assumptions such as Quadratic Residuosity, Decisional Diffie-Hellman, and Learning with Errors. These primitives imply hard problems in the complexity class $\mathcal{SZK}$ (statistical zero-knowledge); as a consequence, they can only be based on assumptions that are broken in $\mathcal{BPP}^{\mathcal{SZK}}$. This poses a barrier for building...
2024/063
Last updated: 2024-03-04
A Study of Soft Analytical Side-Channel Attacks on Secure Hash Algorithms
Julien Maillard, Thomas Hiscock, Maxime Lecomte, Christophe Clavier
Attacks and cryptanalysis
Hashing algorithms are one-way functions that are used in cryptographic protocols as Pseudo Random Functions (PRF), to assess data integrity or to create a Hash-based Message Authentication Code (HMAC). In many cryptographic constructions, secret data is processed with hashing functions. In these cases, recovering the input given to the hashing algorithm allows retrieving secret data. In this paper, we investigate the application of Soft Analytical Side-Channel Attacks (SASCA), based on a...
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...
How (not) to hash into class groups of imaginary quadratic fields?
István András Seres, Péter Burcsi, Péter Kutas
Secret-key cryptography
Class groups of imaginary quadratic fields (class groups for short) have seen a resurgence in cryptography as transparent groups of unknown order. They are a prime candidate for being a trustless alternative to RSA groups because class groups do not need a (distributed) trusted setup to sample a cryptographically secure group of unknown order. Class groups have recently found many applications in verifiable secret sharing, secure multiparty computation, transparent polynomial commitments,...
Hard Languages in $\mathsf{NP} \cap \mathsf{coNP}$ and NIZK Proofs from Unstructured Hardness
Riddhi Ghosal, Yuval Ishai, Alexis Korb, Eyal Kushilevitz, Paul Lou, Amit Sahai
Foundations
The existence of "unstructured" hard languages in $\mathsf{NP} \,\cap\,\mathsf{coNP}$ is an intriguing open question. Bennett and Gill (SICOMP, 1981) asked whether $\mathsf{P}$ is separated from $\mathsf{NP} \cap \mathsf{coNP}$ relative to a random oracle, a question that remained open ever since. While a hard language in $\mathsf{NP} \,\cap\,\mathsf{coNP}$ can be constructed in a black-box way from a one-way permutation, for which only few (structured) candidates exist, Bitansky et al....
Non-Interactive Classical Verification of Quantum Depth: A Fine-Grained Characterization
Nai-Hui Chia, Shih-Han Hung
Cryptographic protocols
We introduce protocols for classical verification of quantum depth (CVQD). These protocols enable a classical verifier to differentiate between devices of varying quantum circuit depths, even in the presence of classical computation. The goal is to demonstrate that a classical verifier can reject a device with a quantum circuit depth of no more than $d$, even if the prover employs additional polynomial-time classical computation to deceive. Conversely, the verifier accepts a device with a...
Automatic Verification of Cryptographic Block Function Implementations with Logical Equivalence Checking
Li-Chang Lai, Jiaxiang Liu, Xiaomu Shi, Ming-Hsien Tsai, Bow-Yaw Wang, Bo-Yin Yang
Implementation
Given a fixed-size block, cryptographic block functions gen-
erate outputs by a sequence of bitwise operations. Block functions are
widely used in the design of hash functions and stream ciphers. Their
correct implementations hence are crucial to computer security. We pro-
pose a method that leverages logic equivalence checking to verify assem-
bly implementations of cryptographic block functions. Logic equivalence
checking is a well-established technique from hardware verification....
Privacy-Preserving Cross-Facility Early Warning for Unknown Epidemics
Shiyu Li, Yuan Zhang, Yaqing Song, Fan Wu, Feng Lyu, Kan Yang, Qiang Tang
Applications
Syndrome-based early epidemic warning plays a vital role in preventing and controlling unknown epidemic outbreaks. It monitors the frequency of each syndrome, issues a warning if some frequency is aberrant, identifies potential epidemic outbreaks, and alerts governments as early as possible. Existing systems adopt a cloud-assisted paradigm to achieve cross-facility statistics on the syndrome frequencies. However, in these systems, all symptom data would be directly leaked to the cloud, which...
Immunizing Backdoored PRGs
Marshall Ball, Yevgeniy Dodis, Eli Goldin
Secret-key cryptography
A backdoored Pseudorandom Generator (PRG) is a PRG which looks pseudorandom to the outside world, but a saboteur can break PRG security by planting a backdoor into a seemingly honest choice of public parameters, $pk$, for the system. Backdoored PRGs became increasingly important due to revelations about NIST’s backdoored Dual EC PRG, and later results about its practical exploitability.
Motivated by this, at Eurocrypt'15 Dodis et al. [21] initiated the question of immunizing backdoored...
A Quantum Approach For Reducing Communications in Classical Secure Computations with Long Outputs
Jiayu Zhang
Cryptographic protocols
How could quantum cryptography help us achieve what are not achievable in classical cryptography? In this work we study the classical cryptographic problem that two parties would like to perform secure computations with long outputs. As a basic primitive and example, we first consider the following problem which we call secure function sampling with long outputs: suppose $f:\{0,1\}^n\rightarrow \{0,1\}^m$ is a public, efficient classical function, where $m$ is big; Alice would like to sample...
Subversion-Resilient Signatures without Random Oracles
Pascal Bemmann, Sebastian Berndt, Rongmao Chen
Public-key cryptography
In the aftermath of the Snowden revelations in 2013, concerns about the integrity and security of cryptographic systems have grown significantly. As adversaries with substantial resources might attempt to subvert cryptographic algorithms and undermine their intended security guarantees, the need for subversion-resilient cryptography has become paramount. Security properties are preserved in subversion-resilient schemes, even if the adversary implements the scheme used in the security...
Searching for ELFs in the Cryptographic Forest
Marc Fischlin, Felix Rohrbach
Foundations
Extremely Lossy Functions (ELFs) are families of functions that, depending on the choice during key generation, either operate in injective mode or instead have only a polynomial image size. The choice of the mode is indistinguishable to an outsider. ELFs were introduced by Zhandry (Crypto 2016) and have been shown to be very useful in replacing random oracles in a number of applications.
One open question is to determine the minimal assumption needed to instantiate ELFs. While all...
On The Black-Box Complexity of Correlation Intractability
Nico Döttling, Tamer Mour
Foundations
Correlation intractability is an emerging cryptographic paradigm that enabled several recent breakthroughs in establishing soundness of the Fiat-Shamir transform and, consequently, basing non-interactive zero-knowledge proofs and succinct arguments on standard cryptographic assumptions. In a nutshell, a hash family is said to be \emph{correlation intractable} for a class of relations $\mathcal{R}$ if, for any relation $R\in\mathcal{R}$, it is hard given a random hash function $h\gets H$ to...
Applications of Finite non-Abelian Simple Groups to Cryptography in the Quantum Era
María Isabel González Vasco, Delaram Kahrobaei, Eilidh McKemmie
Cryptographic protocols
The theory of finite simple groups is a (rather unexplored) area likely to provide interesting computational problems and modelling tools useful in a cryptographic context. In this note, we review some applications of finite non-abelian simple groups to cryptography and discuss different scenarios in which this theory is clearly central, providing the relevant definitions to make the material accessible to both cryptographers and group theorists, in the hope of stimulating further...
Dually Computable Cryptographic Accumulators and Their Application to Attribute Based Encryption
Anaïs Barthoulot, Olivier Blazy, Sébastien Canard
Public-key cryptography
In 1993, Benaloh and De Mare introduced cryptographic accumulator, a primitive that allows the representation of a set of values by a short object (the accumulator) and offers the possibility to prove that some input values are in the accumulator. For this purpose, so-called asymmetric accumulators require the creation of an additional cryptographic object, called a witness. Through the years, several instantiations of accumulators were proposed either based on number theoretic assumptions,...
Random Oracle Combiners: Breaking the Concatenation Barrier for Collision-Resistance
Yevgeniy Dodis, Niels Ferguson, Eli Goldin, Peter Hall, Krzysztof Pietrzak
Secret-key cryptography
Suppose two parties have hash functions $h_1$ and $h_2$ respectively, but each only trusts the security of their own. We wish to build a hash combiner $C^{h_1, h_2}$ which is secure so long as either one of the underlying hash functions is. This question has been well-studied in the regime of collision resistance. In this case, concatenating the two hash outputs clearly works. Unfortunately, a long series of works (Boneh and Boyen, CRYPTO'06; Pietrzak, Eurocrypt'07; Pietrzak, CRYPTO'08)...
OWF Candidates Based on: Xors, Error Detection Codes, Permutations, Polynomials, Interaction and Nesting
Paweł Cyprys, Shlomi Dolev, Oded Margalit
Foundations
Our research focuses on designing efficient commitment schemes by drawing inspiration from (perfect) information-theoretical secure primitives, e.g., the one-time pad and secret sharing. We use a random input as a mask for the committed value, outputting a function on the random input. Then, couple the output with the committed value xored with folded random input.
First, we explore the potential of leveraging the unique properties of the one-time pad to design effective one-way functions....
Invertible Bloom Lookup Tables with Less Memory and Randomness
Nils Fleischhacker, Kasper Green Larsen, Maciej Obremski, Mark Simkin
Foundations
In this work we study Invertible Bloom Lookup Tables (IBLTs) with small failure probabilities.
IBLTs are highly versatile data structures that have found applications in set reconciliation protocols, error-correcting codes, and even the design of advanced cryptographic primitives.
For storing $n$ elements and ensuring correctness with probability at least $1 - \delta$, existing IBLT constructions require $\Omega(n(\frac{\log(1/\delta)}{\log(n)}+1))$ space and they crucially rely on fully...
Simplified Modeling of MITM Attacks for Block Ciphers: new (Quantum) Attacks
André Schrottenloher, Marc Stevens
Attacks and cryptanalysis
The meet-in-the-middle (MITM) technique has led to many key-recovery attacks on block ciphers and preimage attacks on hash functions. Nowadays, cryptographers use automatic tools that reduce the search of MITM attacks to an optimization problem. Bao et al. (EUROCRYPT 2021) introduced a low-level modeling based on Mixed Integer Linear Programming (MILP) for MITM attacks on hash functions, which was extended to key-recovery attacks by Dong et al. (CRYPTO 2021). However, the modeling only...
How to Use (Plain) Witness Encryption: Registered ABE, Flexible Broadcast, and More
Cody Freitag, Brent Waters, David J. Wu
Cryptographic protocols
Witness encryption is a generalization of public-key encryption where the public key can be any NP statement x and the associated decryption key is any witness w for x. While early constructions of witness encryption relied on multilinear maps and indistinguishability obfuscation (iO), recent works have provided direct constructions of witness encryption that are more efficient than iO (and also seem unlikely to yield iO). Motivated by this progress, we revisit the possibility of using...
Constant-Round Arguments from One-Way Functions
Noga Amit, Guy Rothblum
Cryptographic protocols
We study the following question: what cryptographic assumptions are needed for obtaining constant-round computationally-sound argument systems? We focus on argument systems with almost-linear verification time for subclasses of $\mathbf{P}$, such as depth-bounded computations.
Kilian's celebrated work [STOC 1992] provides such 4-message arguments for $\mathbf{P}$ (actually, for $\mathbf{NP}$) using collision-resistant hash functions.
We show that $one$-$way\ functions$ suffice for...
Towards High-speed ASIC Implementations of Post-Quantum Cryptography
Malik Imran, Aikata Aikata, Sujoy Sinha Roy, Samuel pagliarini
Implementation
In this brief, we realize different architectural techniques towards improving the performance of post-quantum cryptography (PQC) algorithms when implemented as hardware accelerators on an application-specific integrated circuit (ASIC) platform. Having SABER as a case study, we designed a 256-bit wide architecture geared for high-speed cryptographic applications that incorporates smaller and distributed SRAM memory blocks. Moreover, we have adapted the building blocks of SABER to process...
Exploring Formal Methods for Cryptographic Hash Function Implementations
Nicky Mouha
Implementation
Cryptographic hash functions are used inside many applications that critically rely on their resistance against cryptanalysis attacks and the correctness of their implementations. Nevertheless, vulnerabilities in cryptographic hash function implementations can remain unnoticed for more than a decade, as shown by the recent discovery of a buffer overflow in the implementation of SHA-3 in the eXtended Keccak Code Package (XKCP), impacting Python, PHP, and several other software projects. This...
Algebraic Cryptanalysis of HADES Design Strategy: Application to POSEIDON and Poseidon2
Tomer Ashur, Thomas Buschman, Mohammad Mahzoun
Attacks and cryptanalysis
Arithmetization-Oriented primitives are the building block of advanced cryptographic protocols such as Zero-Knowledge proof systems. One approach to designing such primitives is the HADES design strategy which aims to provide an efficient way to instantiate generalizing substitution-permutation networks to include partial S-box rounds. A notable instance of HADES, introduced by Grassi \emph{et al.} at USENIX Security '21, is Poseidon. Because of its impressive efficiency and low arithmetic...
Lightweight Asynchronous Verifiable Secret Sharing with Optimal Resilience
Victor Shoup, Nigel P. Smart
Cryptographic protocols
We present new protocols for *Asynchronous Verifiable Secret Sharing* for Shamir (i.e., threshold $t<n$) sharing of secrets.
Our protocols:
* Use only "lightweight" cryptographic primitives, such as hash functions;
* Can share secrets over rings such as $\mathbb{Z}_{p^k}$ as well as finite fields $\mathbb{F}_q$;
* Provide *optimal resilience*, in the sense that they tolerate up to $t < n/3$ corruptions, where $n$ is the total number of parties;
* Are *complete*, in the sense that they...
Practical Homomorphic Evaluation of Block-Cipher-Based Hash Functions with Applications
Adda-Akram Bendoukha, Oana Stan, Renaud Sirdey, Nicolas Quero, Luciano Freitas
Applications
Fully homomorphic encryption (FHE) is a powerful cryptographic technique allowing to perform computation directly over encrypted data. Motivated by the overhead induced by the homomorphic ciphertexts during encryption and transmission, the transciphering technique, consisting in switching from a symmetric encryption to FHE encrypted data was investigated in several papers. Different stream and block ciphers were evaluated in terms of their "FHE-friendliness", meaning practical...
An Overview of Hash Based Signatures
Vikas Srivastava, Anubhab Baksi, Sumit Kumar Debnath
Digital signatures are one of the most basic cryptographic building blocks which are utilized to provide attractive security features like authenticity, unforgeability, and undeniability. The security of existing state of the art digital signatures is based on hardness of number theoretic hardness assumptions like discrete logarithm and integer factorization. However, these hard problems are insecure and face a threat in the quantum world. In particular, quantum algorithms like Shor’s...
Machine-Checked Security for $\mathrm{XMSS}$ as in RFC 8391 and $\mathrm{SPHINCS}^{+}$
Manuel Barbosa, François Dupressoir, Benjamin Grégoire, Andreas Hülsing, Matthias Meijers, Pierre-Yves Strub
Public-key cryptography
This work presents a novel machine-checked tight security
proof for $\mathrm{XMSS}$ — a stateful hash-based signature scheme that is (1) standardized in RFC 8391 and NIST SP 800-208, and (2) employed as a primary building block of $\mathrm{SPHINCS}^{+}$, one of the signature schemes recently selected for standardization as a result of NIST’s post-quantum competition.
In 2020, Kudinov, Kiktenko, and Fedoro pointed out a flaw affecting the tight security proofs of $\mathrm{SPHINCS}^{+}$ and...
Hashing to elliptic curves through Cipolla–Lehmer–Müller’s square root algorithm
Dmitrii Koshelev
Implementation
The present article provides a novel hash function $\mathcal{H}$ to any elliptic curve of $j$-invariant $\neq 0, 1728$ over a finite field $\mathbb{F}_{\!q}$ of large characteristic. The unique bottleneck of $\mathcal{H}$ consists in extracting a square root in $\mathbb{F}_{\!q}$ as well as for most hash functions. However, $\mathcal{H}$ is designed in such a way that the root can be found by (Cipolla--Lehmer--)Müller's algorithm in constant time. Violation of this security condition is...
Publicly-Verifiable Deletion via Target-Collapsing Functions
James Bartusek, Dakshita Khurana, Alexander Poremba
Public-key cryptography
We build quantum cryptosystems that support publicly-verifiable deletion from standard cryptographic assumptions. We introduce target-collapsing as a weakening of collapsing for hash functions, analogous to how second preimage resistance weakens collision resistance; that is, target-collapsing requires indistinguishability between superpositions and mixtures of preimages of an honestly sampled image.
We show that target-collapsing hashes enable publicly-verifiable deletion (PVD), proving...
Optimal Security for Keyed Hash Functions: Avoiding Time-Space Tradeoffs for Finding Collisions
Cody Freitag, Ashrujit Ghoshal, Ilan Komargodski
Foundations
Cryptographic hash functions map data of arbitrary size to a fixed size digest, and are one of the most commonly used cryptographic objects. As it is infeasible to design an individual hash function for every input size, variable-input length hash functions are built by designing and bootstrapping a single fixed-input length function that looks sufficiently random. To prevent trivial preprocessing attacks, applications often require not just a single hash function but rather a family of...
Approximate Modeling of Signed Difference and Digraph based Bit Condition Deduction: New Boomerang Attacks on BLAKE
Yonglin Hao, Qingju Wang, Lin Jiao, Xinxin Gong
Attacks and cryptanalysis
The signed difference is a powerful tool for analyzing the Addition, XOR, Rotation (ARX) cryptographic primitives. Currently, solving the accurate model for the signed difference propagation is infeasible.
We propose an approximate MILP modeling method capturing the propagation rules of signed differences. Unlike the accurate signed difference model, the approximate model only focuses on active bits and ignores the possible bit conditions on inactive bits.
To overcome the negative effect...
TS-Hash: a lightweight cryptographic hash family based on Galois LFSRs
Itay Bookstein, Boaz Tsaban
Applications
We study a novel family of cryptographic hash functions based on Galois linear feedback shift registers (LFSRs),
and identify initial guidelines for choosing secure parameters for this family.
These hash functions are extremely simple, efficient, and suitable for implementation in
constrained environments.
Quantum Advantage from One-Way Functions
Tomoyuki Morimae, Takashi Yamakawa
Foundations
Is quantum computing truly faster than classical computing? Demonstrating unconditional quantum computational advantage lies beyond the reach of the current complexity theory, and therefore we have to rely on some complexity assumptions. While various results on quantum advantage have been obtained, all necessitate relatively stronger or less standard assumptions in complexity theory or classical cryptography. In this paper, we show quantum advantage based on several fundamental assumptions,...
On the (Im)plausibility of Public-Key Quantum Money from Collision-Resistant Hash Functions
Prabhanjan Ananth, Zihan Hu, Henry Yuen
Foundations
Public-key quantum money is a cryptographic proposal for using highly entangled quantum states as currency that is publicly verifiable yet resistant to counterfeiting due to the laws of physics. Despite significant interest, constructing provably-secure public-key quantum money schemes based on standard cryptographic assumptions has remained an elusive goal. Even proposing plausibly-secure candidate schemes has been a challenge.
These difficulties call for a deeper and systematic study...
Optimization for SPHINCS+ using Intel Secure Hash Algorithm Extensions
Thomas Hanson, Qian Wang, Santosh Ghosh, Fernando Virdia, Anne Reinders, Manoj R. Sastry
Implementation
SPHINCS+ was selected as a candidate digital signature scheme for standardization by the NIST Post-Quantum Cryptography Standardization Process. It offers security capabilities relying only on the security of cryptographic hash functions. However, it is less efficient than the lattice-based schemes. In this paper, we present an optimized software library for the SPHINCS+ signature scheme, which combines the Intel® Secure Hash Algorithm Extensions (SHA-NI) and AVX2 vector instructions. We...
Area-time Efficient Implementation of NIST Lightweight Hash Functions Targeting IoT Applications
Safiullah Khan, Wai-Kong Lee, Angshuman Karmakar, Jose Maria Bermudo Mera, Abdul Majeed, Seong Oun Hwang
Implementation
To mitigate cybersecurity breaches, secure communication is crucial for the Internet of Things (IoT) environment. Data integrity is one of the most significant characteristics of security, which can be achieved by employing cryptographic hash functions. In view of the demand from IoT applications, the National Institute of Standards and Technology (NIST) initiated a standardization process for lightweight hash functions. This work presents field-programmable gate array (FPGA) implementations...
Obfuscation of Evasive Algebraic Set Membership
Steven D. Galbraith, Trey Li
Public-key cryptography
We define the membership function of a set as the function that determines whether an input is an element of the set. Canetti, Rothblum, and Varia showed how to obfuscate evasive membership functions of hyperplanes over a finite field of order an exponentially large prime, assuming the hardness of a modified decisional Diffie-Hellman problem. Barak, Bitansky, Canetti, Kalai, Paneth, and Sahai extended their work from hyperplanes to hypersurfaces of bounded degree, assuming multilinear maps....
Witness Encryption for Succinct Functional Commitments and Applications
Matteo Campanelli, Dario Fiore, Hamidreza Khoshakhlagh
Public-key cryptography
Witness encryption (WE), introduced by Garg, Gentry, Sahai, and Waters (STOC 2013) allows one to encrypt a message to a statement $\mathsf{x}$ for some NP language $\mathcal{L}$, such that any user holding a witness for $\mathsf{x} \in \mathcal{L}$ can decrypt the ciphertext.
The extreme power of this primitive comes at the cost of its elusiveness: a practical construction from established cryptographic assumptions is currently out of reach.
In this work, we investigate a new notion of...
The Parallel Reversible Pebbling Game: Analyzing the Post-Quantum Security of iMHFs
Jeremiah Blocki, Blake Holman, Seunghoon Lee
Attacks and cryptanalysis
The classical (parallel) black pebbling game is a useful abstraction which allows us to analyze the resources (space, space-time, cumulative space) necessary to evaluate a function $f$ with a static data-dependency graph $G$. Of particular interest in the field of cryptography are data-independent memory-hard functions $f_{G,H}$ which are defined by a directed acyclic graph (DAG) $G$ and a cryptographic hash function $H$. The pebbling complexity of the graph $G$ characterizes the amortized...
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...
Efficient and Universally Composable Non-Interactive Zero-Knowledge Proofs of Knowledge with Security Against Adaptive Corruptions
Anna Lysyanskaya, Leah Namisa Rosenbloom
Foundations
Non-interactive zero-knowledge proofs of knowledge (NIZKPoK) serve as a key building block in many important cryptographic constructions. Achieving universally composable NIZKPoK secure against adaptive corruptions was a long-standing open problem, recently solved by Canetti, Sarkar, and Wang (Asiacrypt'22). This sole known construction requires heavy cryptographic machinery such as correlation-intractable hash functions, and is not ready for use in practice. In this paper, we give...
Cuckoo Hashing in Cryptography: Optimal Parameters, Robustness and Applications
Kevin Yeo
Foundations
Cuckoo hashing is a powerful primitive that enables storing items using small space with efficient querying. At a high level, cuckoo hashing maps $n$ items into $b$ entries storing at most $\ell$ items such that each item is placed into one of $k$ randomly chosen entries. Additionally, there is an overflow stash that can store at most $s$ items. Many cryptographic primitives rely upon cuckoo hashing to privately embed and query data where it is integral to ensure small failure probability...
LaBRADOR: Compact Proofs for R1CS from Module-SIS
Ward Beullens, Gregor Seiler
Cryptographic protocols
The most compact quantum-safe proof systems for large circuits are PCP-type systems such as Ligero, Aurora, and Shockwave, that only use weak cryptographic assumptions, namely hash functions modeled as random oracles. One would expect that by allowing for stronger assumptions, such as the hardness of Module-SIS, it should be possible to design more compact proof systems. But alas, despite considerable progress in lattice-based proofs, no such proof system was known so far. We rectify this...
Hash Gone Bad: Automated discovery of protocol attacks that exploit hash function weaknesses
Vincent Cheval, Cas Cremers, Alexander Dax, Lucca Hirschi, Charlie Jacomme, Steve Kremer
Foundations
Most cryptographic protocols use cryptographic hash functions as a building block. The security analyses of these protocols typically assume that the hash functions are perfect (such as in the random oracle model). However, in practice, most widely deployed hash functions are far from perfect -- and as a result, the analysis may miss attacks that exploit the gap between the model and the actual hash function used.
We develop the first methodology to systematically discover attacks on...
erforming privacy-preserving queries, particularly anonymous authentication, against large-scale datasets presents critical tradeoffs between security, latency, scalability. Existing cryptographic solutions often impose linear computation or communication overheads. This paper introduces a novel, efficient protocol for secure anonymous authentication, uniquely combining matrix partitioning via hash prefixes with Oblivious Pseudorandom Functions in a three-server semi-honest model....
This paper studies the security of key derivation functions (KDFs), a central class of cryptographic algorithms used to derive multiple independent-looking keys (each associated with a particular context) from a single secret. The main security requirement is that these keys are pseudorandom (i.e., the KDF is a pseudorandom function). This paper initiates the study of an additional security property, called key control (KC) security, first informally put forward in a recent update to NIST...
We study several problems in the intersection of cryptography and complexity theory based on the following high-level thesis. 1) Obfuscation can serve as a general-purpose worst-case to average-case reduction, reducing the existence of various forms of cryptography to corresponding worst-case assumptions. 2) We can therefore hope to overcome barriers in cryptography and average-case complexity by (i) making worst-case hardness assumptions beyond $\mathsf{P}\neq \mathsf{NP}$, and...
In this work, we propose a novel systematic approach for obtaining leftover hash lemmas (LHLs) over cyclotomic rings. Such LHLs build a fundamental tool in lattice-based cryptography, both in theoretical reductions as well as in the design of cryptographic primitives. The scattered set of prior works makes it difficult to navigate the landscape and requires a substantial effort to understand the mathematical constraints under which the LHL holds over cyclotomic rings. This is especially...
Onion routing is a popular practical approach to anonymous communication, and the subject of a growing body of foundational theoretical work aiming to design efficient schemes with provable anonymity, the strongest notion of which is full anonymity. Unfortunately, all previous schemes that achieve full anonymity assume the synchronous communication setting, which is unrealistic as real networks may experience message loss and timing attacks that render such schemes insecure. Recently,...
The sponge is a popular construction of hash function design. It operates with a $b$-bit permutation on a $b$-bit state, that is split into a $c$-bit inner part and an $r$-bit outer part. However, the security bounds of the sponge are most often dominated by the capacity $c$: If the length of the digest is $n$ bits, the construction achieves $\min\{n/2,c/2\}$-bit collision resistance and $\min\{n,c/2\}$-bit second preimage resistance (and a slightly more complex but similar bound for...
Poseidon and Poseidon2 are cryptographic hash functions designed for efficient zero-knowledge proof protocols and have been widely adopted in Ethereum applications. To encourage security research, the Ethereum Foundation announced a bounty program in November 2024 for breaking the Poseidon challenges, i.e. solving the CICO (Constrained Input, Constrained Output) problems for round-reduced Poseidon constructions. In this paper, we explain how to apply the Graeffe transform to univariate...
AES has cemented its position as the primary symmetric-key primitive for a wide range of cryptographic applications, which motivates the analysis on the concrete security of AES in practical instantiations, for instance, the collision resistance of AES-based hashing, the key commitment security of AES-based authenticated encryption schemes, and the one-wayness of AES-based one-way functions in ZK and MPC protocols. In this work, we introduce single-color initial structures (SCIS) into...
Truncation of cryptographic outputs is a technique that was recently introduced in Baldimtsi et al. [BCCK22]. The general idea is to try out many inputs to some cryptographic algorithm until the output (e.g. a public-key or some hash value) falls into some sparse set and thus can be compressed: by trying out an expected $2^k$ different inputs one will find an output that starts with $k$ zeros. Using such truncation one can for example save substantial gas fees on Blockchains where...
Constructing and implementing isogeny-based cryptographic primitives is an active research. In particular, performing length-$n$ isogenies walks over quadratic field extensions of $\mathbb{F}_p$ plays an exciting role in some constructions, including Hash functions, Verifiable Delay Functions, Key-Encapsulation Mechanisms, and generic proof systems for isogeny knowledge. Remarkably, many isogeny-based constructions, for efficiency, perform $2$-isogenies through square root...
Johnson and Lindenstrauss (Contemporary Mathematics, 1984) showed that for $n > m$, a scaled random projection $\mathbf{A}$ from $\mathbb{R}^n$ to $\mathbb{R}^m$ is an approximate isometry on any set $S$ of size at most exponential in $m$. If $S$ is larger, however, its points can contract arbitrarily under $\mathbf{A}$. In particular, the hypergrid $([-B, B] \cap \mathbb{Z})^n$ is expected to contain a point that is contracted by a factor of $\kappa_{\mathsf{stat}} = \Theta(B)^{-1/\alpha}$,...
Sanitizable Signature Schemes (SSS) enable a designated party, the sanitizer, to modify predefined parts of a signed message without invalidating the signature, making them useful for applications like pseudonymization and redaction. Since their introduction by Ateniese et al. (ESORICS'05), several classical SSS constructions have been proposed, but none have been instantiated from quantum-resistant assumptions. In this work, we develop the first quantum-secure sanitizable signature schemes...
The Fiat-Shamir transformation underlies numerous non-interactive arguments, with variants that differ in important ways. This paper addresses a gap between variants analyzed by theoreticians and variants implemented (and deployed) by practitioners. Specifically, theoretical analyses typically assume parties have access to random oracles with sufficiently large input and output size, while cryptographic hash functions in practice have fixed input and output sizes (pushing practitioners...
The most fundamental performance metrics of secure multi-party computation (MPC) protocols are related to the number of messages the parties exchange (i.e., round complexity), the size of these messages (i.e., communication complexity), and the overall computational resources required to execute the protocol (i.e., computational complexity). Another quality metric of MPC protocols is related to the black-box or non-black-box use of the underlying cryptographic primitives. Indeed, the design...
Poly1305 is a widely-deployed polynomial hash function. The rationale behind its design was laid out in a series of papers by Bernstein, the last of which dates back to 2005. As computer architectures evolved, some of its design features became less relevant, but implementers found new ways of exploiting these features to boost its performance. However, would we still converge to this same design if we started afresh with today's computer architectures and applications? To answer this...
Trapdoor hash functions (TDHs) are compressing hash functions, with an additional trapdoor functionality: Given a encoding key for a function $f$, a hash on $x$ together with a (small) input encoding allow one to recover $f(x)$. TDHs are a versatile tool and a useful building block for more complex cryptographic protocols. In this work, we propose the first TDH construction assuming the (quasi-polynomial) hardness of the LPN problem with noise rate $\epsilon = O(\log^{1+\beta} n / n)$ for...
We propose the notion of succinct oblivious tensor evaluation (OTE), where two parties compute an additive secret sharing of a tensor product of two vectors $\mathbf{x} \otimes \mathbf{y}$, exchanging two simultaneous messages. Crucially, the size of both messages and of the CRS is independent of the dimension of $\mathbf{x}$. We present a construction of OTE with optimal complexity from the standard learning with errors (LWE) problem. Then we show how this new technical tool enables a...
A Garbling Scheme is a fundamental cryptographic primitive, with numerous theoretical and practical applications. Since its inception by Yao (FOCS'82, '86), optimizing the communication and computation complexities of securely garbling circuits has been an area of active research. One such optimization, and perhaps the most fundamental, is the `Free-XOR' technique (Kolesnikov and Schneider, ICALP'08) which allows XOR gates in a function garbling to not require representation, and therefore...
The concept of Anamorphic Encryption (Persiano, Phan and Yung, Eurocrypt '22), aims to enable private communication in settings where the usage of encryption is heavily controlled by a central authority (henceforth called the dictator) who can obtain users' secret keys. Since then, various works have improved our understanding of AE in several aspects, including its limitations. To this regard, two recent works constructed various Anamorphic-Resistant Encryption (ARE) schemes, i.e., schemes...
Garbling is a fundamental cryptographic primitive, with numerous theoretical and practical applications. Since the first construction by Yao (FOCS’82, ’86), a line of work has concerned itself with reducing the communication and computational complexity of that construction. One of the most efficient garbling schemes presently is the ‘Half Gates’ scheme by Zahur, Rosulek, and Evans (Eurocrypt’15). Despite its widespread adoption, the provable security of this scheme has been based on...
In the last decade, the introduction of advanced cryptographic protocols operating on large finite fields $\mathbb{F}_q$ has raised the need for efficient cryptographic primitives in this setting, commonly referred to as Arithmetization-Oriented (AO). The cryptanalysis of AO hash functions is essentially done through the study of the CICO problem on the underlying permutation. Two recent works at Crypto 2024 and Asiacrypt 2024 managed to solve the CICO problem much more efficiently than...
Cryptographic proof systems enable a verifier to be convinced of a computation's correctness without re-executing it; common efficiency requirements include both succinct proofs and fast verification. In this work we put forth the general study of cryptographic proof systems with \textit{sublinear} proving time (after a preprocessing). Prior work has achieved sublinear proving only for limited computational settings (e.g., vector commitments and lookup arguments), relying on specific...
In modern cryptography, relatively few instantiations of foundational cryptographic primitives are used across most cryptographic protocols. For example, elliptic curve groups are typically instantiated using P-256, P-384, Curve25519, or Curve448, while block ciphers are commonly instantiated with AES, and hash functions with SHA-2, SHA-3, or SHAKE. This limited diversity raises concerns that an adversary with nation-state-level resources could perform a preprocessing attack, generating a...
Arithmetic hash functions defined over prime fields have been actively developed and used in verifiable computation (VC) protocols. Among those, elliptic-curve-based SNARKs require large (256-bit and higher) primes. Such hash functions are notably slow, losing a factor of up to 1000 compared to regular constructions like SHA-2/3. In this paper, we present the hash function Skyscraper-v2, which is aimed at large prime fields and provides major improvements compared to Reinforced Concrete...
With the threat posed by quantum computers on the horizon, systems like Ethereum must transition to cryptographic primitives resistant to quantum attacks. One of the most critical of these primitives is the non-interactive multi-signature scheme used in Ethereum's proof-of-stake consensus, currently implemented with BLS signatures. This primitive enables validators to independently sign blocks, with their signatures then publicly aggregated into a compact aggregate signature. In this...
Postal voting is a frequently used alternative to on-site voting. Traditionally, its security relies on organizational measures, and voters have to trust many entities. In the recent years, several schemes have been proposed to add verifiability properties to postal voting, while preserving vote privacy. Postal voting comes with specific constraints. We conduct a systematic analysis of this setting and we identify a list of generic attacks, highlighting that some attacks seem unavoidable....
A group signatures allows a user to sign a message anonymously on behalf of a group and provides accountability by using an opening authority who can ``open'' a signature and reveal the signer's identity. Group signatures have been widely used in privacy-preserving applications including anonymous attestation and anonymous authentication. Fully dynamic group signatures allow new members to join the group and existing members to be revoked if needed. Symmetric-key based group signature...
Private set intersections are cryptographic protocols that compute the intersection of multiple parties' private sets without revealing elements that are not in the intersection. These protocols become less efficient when the number of parties grows, or the size of the sets increases. For this reason, many protocols are based on Bloom filters, which speed up the protocol by approximating the intersections, introducing false positives with a small but non-negligible probability. These false...
Boolean functions play an important role in designing and analyzing many cryptographic systems, such as block ciphers, stream ciphers, and hash functions, due to their unique cryptographic properties such as nonlinearity, correlation immunity, and algebraic properties. The secure evaluation of Boolean functions or Secure Boolean Evaluation (SBE) is an important area of research. SBE allows parties to jointly compute Boolean functions without exposing their private inputs. SBE finds...
Shoup and Smart (SS24) recently introduced a lightweight asynchronous verifiable secret sharing (AVSS) protocol with optimal resilience directly from cryptographic hash functions (JoC 2024), offering plausible quantum resilience and computational efficiency. However, SS24 AVSS only achieves standard secrecy to keep the secret confidential against $n/3$ corrupted parties \textit{if no honest party publishes its share}. In contrast, from ``heavyweight'' public-key cryptography, one can...
We provide explicit descriptions for radical 2-isogenies in dimensions one, two and three using theta coordinates. These formulas allow us to efficiently navigate in the corresponding isogeny graphs. As an application of this, we implement different versions of the CGL hash func- tion. Notably, the three-dimensional version is fastest, which demonstrates yet another potential of using higher dimensional isogeny graphs in cryptography.
Asynchronous multiparty computation (AMPC) requires an input agreement phase where all participants have a consistent view of the set of private inputs. While the input agreement problem can be precisely addressed by a Byzantine fault-tolerant consensus known as Asynchronous Common Subset (ACS), existing ACS constructions with potential post-quantum security have a large $\widetilde{\mathcal{O}}(n^3)$ communication complexity for a network of $n$ nodes. This poses a bottleneck for AMPC in...
Homomorphic Encryption (HE) enables operations on encrypted data without requiring decryption, thus allowing for secure handling of confidential data within smart contracts. Among the known HE schemes, FHEW and TFHE are particularly notable for use in smart contracts due to their lightweight nature and support for arbitrary logical gates. In contrast, other HE schemes often require several gigabytes of keys and are limited to supporting only addition and multiplication. As a result, there...
Collision-resistant hashing (CRH) is a cornerstone of cryptographic protocols. However, despite decades of research, no construction of a CRH based solely on one-way functions has been found. Moreover, there are black-box limitations that separate these two primitives. Harnik and Naor [HN10] overcame this black-box barrier by introducing the notion of instance compression. Instance compression reduces large NP instances to a size that depends on their witness size while preserving the...
For Password-Based Authenticated Key Exchange (PAKE), an idealized setup such as random oracle (RO) or a trusted setup such as common reference string (CRS) is a must in the universal composability (UC) framework (Canetti, FOCS 2001). Given the potential failure of a CRS or RO setup, it is natural to consider distributing trust among the two setups, resulting a CRS-or-RO-setup (i.e., CoR-setup). However, the infeasibility highlighted by Katz et al. (PODC 2014) suggested that it is...
Proofs of partial knowledge, first considered by Cramer, Damgård and Schoenmakers (CRYPTO'94) and De Santis et al. (FOCS'94), allow for proving the validity of $k$ out of $n$ different statements without revealing which ones those are. In this work, we present a new approach for transforming certain proofs system into new ones that allows for proving partial knowledge. The communication complexity of the resulting proof system only depends logarithmically on the total number of statements...
We present a tweakable wide block cipher called Mystrium and show it as the fastest such primitive on low-end processors that lack dedicated AES or other cryptographic instructions, such as ARM Cortex-A7. Mystrium is based on the provably secure double-decker mode, that requires a doubly extendable cryptographic keyed (deck) function and a universal hash function. We build a new deck function called Xymmer that for its compression part uses Multimixer-128, the fastest universal hash for...
Digital signature is a fundamental cryptographic primitive and is widely used in the real world. Unfortunately, the current digital signature standards like EC-DSA and RSA are not quantum-resistant. Among post-quantum cryptography (PQC), isogeny-based signatures preserve some advantages of elliptic curve cryptosystems, particularly offering small signature sizes. Currently, SQIsign and its variants are the most promising isogeny-based digital signature schemes. In this paper, we propose a...
In recent years a new class of symmetric-key primitives over $\mathbb{F}_p$ that are essential to Multi-Party Computation and Zero-Knowledge Proofs based protocols has emerged. Towards improving the efficiency of such primitives, a number of new block ciphers and hash functions over $\mathbb{F}_p$ were proposed. These new primitives also showed that following alternative design strategies to the classical Substitution-Permutation Network (SPN) and Feistel Networks leads to more efficient...
Redis (Remote Dictionary Server) is a general purpose, in-memory database that supports a rich array of functionality, including various Probabilistic Data Structures (PDS), such as Bloom filters, Cuckoo filters, as well as cardinality and frequency estimators. These PDS typically perform well in the average case. However, given that Redis is intended to be used across a diverse array of applications, it is crucial to evaluate how these PDS perform under worst-case scenarios, i.e., when...
We give the first construction of non-interactive zero-knowledge (NIZK) arguments from post-quantum assumptions other than Learning with Errors. In particular, we achieve NIZK under the polynomial hardness of the Learning Parity with Noise (LPN) assumption, and the exponential hardness of solving random under-determined multivariate quadratic equations (MQ). We also construct NIZK satisfying statistical zero-knowledge assuming a new variant of LPN, Dense-Sparse LPN, introduced by Dao and...
We investigate shift-invariant vectorial Boolean functions on $n$ bits that are lifted from Boolean functions on $k$ bits, for $k\leq n$. We consider vectorial functions that are not necessarily permutations, but are, in some sense, almost bijective. In this context, we define an almost lifting as a Boolean function for which there is an upper bound on the number of collisions of its lifted functions that does not depend on $n$. We show that if a Boolean function with diameter $k$ is an...
The SHA-3 standard consists of four cryptographic hash functions, called SHA3-224, SHA3-256, SHA3-384 and SHA3-512, and two extendable-output functions (XOFs), called SHAKE128 and SHAKE256. In this paper, we study the collision resistance of the SHA-3 instances. By analyzing the nonlinear layer, we introduce the concept of maximum difference density subspace, and develop a new target internal difference algorithm by probabilistic linearization. We also exploit new strategies for optimizing...
The current cryptographic frameworks like RSA, ECC, and AES are potentially under quantum threat. Quantum cryptographic and post-quantum cryptography are being extensively researched for securing future information. The quantum computer and quantum algorithms are still in the early developmental stage and thus lack scalability for practical application. As a result of these challenges, most researched PQC methods are lattice-based, code-based, ECC isogeny, hash-based, and multivariate...
Cryptographic hash functions are said to be the work-horses of modern cryptography. One of the strongest approaches to assess a cryptographic hash function's security is indifferentiability. Informally, indifferentiability measures to what degree the function resembles a random oracle when instantiated with an ideal underlying primitive. However, proving the indifferentiability security of hash functions has been challenging due to complex simulator designs and proof arguments. The Sponge...
$\mathrm{SPHINCS^{+}}$ is a post-quantum signature scheme that, at the time of writing, is being standardized as $\mathrm{SLH\text{-}DSA}$. It is the most conservative option for post-quantum signatures, but the original tight proofs of security were flawed—as reported by Kudinov, Kiktenko and Fedorov in 2020. In this work, we formally prove a tight security bound for $\mathrm{SPHINCS^{+}}$ using the EasyCrypt proof assistant, establishing greater confidence in the general security of the...
We design and implement a novel post-quantum signature scheme based on the Legendre PRF, named Loquat. Prior to this work, efficient approaches for constructing post-quantum signatures with comparable security assumptions mainly used the MPC-in-the-head paradigm or hash trees. Our method departs from these paradigms and, notably, is SNARK-friendly, a feature not commonly found in earlier designs. Loquat requires significantly fewer computational operations for verification than other...
This work resolves the open problem of whether verifiable delay functions (VDFs) can be constructed in the random oracle model.A VDF is a cryptographic primitive that requires a long time to compute (even with parallelization), but produces a unique output that is efficiently and publicly verifiable. We prove that VDFs do not exist in the random oracle model. This also rules out black-box constructions of VDFs from other cryptographic primitives, such as one-way functions, one-way...
Generative pre-trained transformers (GPT's) are a type of large language machine learning model that are unusually adept at producing novel, and coherent, natural language. Notably, these technologies have also been extended to computer programming languages with great success. However, GPT model outputs in general are stochastic and not always correct. For programming languages, the exact specification of the computer code, syntactically and algorithmically, is strictly required in order to...
Byzantine consensus is a fundamental building block in distributed cryptographic problems. Despite decades of research, most existing asynchronous consensus protocols require a strong trusted setup and expensive public-key cryptography. In this paper, we study asynchronous Byzantine consensus protocols that do not rely on a trusted setup and do not use public-key cryptography such as digital signatures. We give an Asynchronous Common Subset (ACS) protocol whose security is only based on...
Quantum computers have the potential to solve hard problems that are nearly impossible to solve by classical computers, this has sparked a surge of research to apply quantum technology and algorithm against the cryptographic systems to evaluate for its quantum resistance. In the process of selecting post-quantum standards, NIST categorizes security levels based on the complexity that quantum computers would require to crack AES encryption (levels 1, 3 and 5) and SHA-2 or SHA-3 (levels 2 and...
Multi-valued Validated Byzantine Agreement (MVBA) is vital for asynchronous distributed protocols like asynchronous BFT consensus and distributed key generation, making performance improvements a long-standing goal. Existing communication-optimal MVBA protocols rely on computationally intensive public-key cryptographic tools, such as non-interactive threshold signatures, which are also vulnerable to quantum attacks. While hash-based MVBA protocols have been proposed to address these...
Two recent proposals by Bernstein and Pornin emphasize the use of deterministic signatures in DSA and its elliptic curve-based variants. Deterministic signatures derive the required ephemeral key value in a deterministic manner from the message to be signed and the secret key instead of using random number generators. The goal is to prevent severe security issues, such as the straight-forward secret key recovery from low quality random numbers. Recent developments have raised skepticism...
Polynomial commitment scheme allows a prover to commit to a polynomial $f \in \mathcal{R}[X]$ of degree $L$, and later prove that the committed function was correctly evaluated at a specified point $x$; in other words $f(x)=u$ for public $x,u \in\mathcal{R}$. Most applications of polynomial commitments, e.g. succinct non-interactive arguments of knowledge (SNARKs), require that (i) both the commitment and evaluation proof are succinct (i.e., polylogarithmic in the degree $L$) - with the...
We study how to construct hash functions that can securely instantiate the Fiat-Shamir transformation against bounded-depth adversaries. The motivation is twofold. First, given the recent fruitful line of research of constructing cryptographic primitives against bounded-depth adversaries under worst-case complexity assumptions, and the rich applications of Fiat-Shamir, instantiating Fiat-Shamir hash functions against bounded-depth adversaries under worst-case complexity assumptions might...
Over the past few decades, we have seen a proliferation of advanced cryptographic primitives with lossy or homomorphic properties built from various assumptions such as Quadratic Residuosity, Decisional Diffie-Hellman, and Learning with Errors. These primitives imply hard problems in the complexity class $\mathcal{SZK}$ (statistical zero-knowledge); as a consequence, they can only be based on assumptions that are broken in $\mathcal{BPP}^{\mathcal{SZK}}$. This poses a barrier for building...
Hashing algorithms are one-way functions that are used in cryptographic protocols as Pseudo Random Functions (PRF), to assess data integrity or to create a Hash-based Message Authentication Code (HMAC). In many cryptographic constructions, secret data is processed with hashing functions. In these cases, recovering the input given to the hashing algorithm allows retrieving secret data. In this paper, we investigate the application of Soft Analytical Side-Channel Attacks (SASCA), based on a...
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...
Class groups of imaginary quadratic fields (class groups for short) have seen a resurgence in cryptography as transparent groups of unknown order. They are a prime candidate for being a trustless alternative to RSA groups because class groups do not need a (distributed) trusted setup to sample a cryptographically secure group of unknown order. Class groups have recently found many applications in verifiable secret sharing, secure multiparty computation, transparent polynomial commitments,...
The existence of "unstructured" hard languages in $\mathsf{NP} \,\cap\,\mathsf{coNP}$ is an intriguing open question. Bennett and Gill (SICOMP, 1981) asked whether $\mathsf{P}$ is separated from $\mathsf{NP} \cap \mathsf{coNP}$ relative to a random oracle, a question that remained open ever since. While a hard language in $\mathsf{NP} \,\cap\,\mathsf{coNP}$ can be constructed in a black-box way from a one-way permutation, for which only few (structured) candidates exist, Bitansky et al....
We introduce protocols for classical verification of quantum depth (CVQD). These protocols enable a classical verifier to differentiate between devices of varying quantum circuit depths, even in the presence of classical computation. The goal is to demonstrate that a classical verifier can reject a device with a quantum circuit depth of no more than $d$, even if the prover employs additional polynomial-time classical computation to deceive. Conversely, the verifier accepts a device with a...
Given a fixed-size block, cryptographic block functions gen- erate outputs by a sequence of bitwise operations. Block functions are widely used in the design of hash functions and stream ciphers. Their correct implementations hence are crucial to computer security. We pro- pose a method that leverages logic equivalence checking to verify assem- bly implementations of cryptographic block functions. Logic equivalence checking is a well-established technique from hardware verification....
Syndrome-based early epidemic warning plays a vital role in preventing and controlling unknown epidemic outbreaks. It monitors the frequency of each syndrome, issues a warning if some frequency is aberrant, identifies potential epidemic outbreaks, and alerts governments as early as possible. Existing systems adopt a cloud-assisted paradigm to achieve cross-facility statistics on the syndrome frequencies. However, in these systems, all symptom data would be directly leaked to the cloud, which...
A backdoored Pseudorandom Generator (PRG) is a PRG which looks pseudorandom to the outside world, but a saboteur can break PRG security by planting a backdoor into a seemingly honest choice of public parameters, $pk$, for the system. Backdoored PRGs became increasingly important due to revelations about NIST’s backdoored Dual EC PRG, and later results about its practical exploitability. Motivated by this, at Eurocrypt'15 Dodis et al. [21] initiated the question of immunizing backdoored...
How could quantum cryptography help us achieve what are not achievable in classical cryptography? In this work we study the classical cryptographic problem that two parties would like to perform secure computations with long outputs. As a basic primitive and example, we first consider the following problem which we call secure function sampling with long outputs: suppose $f:\{0,1\}^n\rightarrow \{0,1\}^m$ is a public, efficient classical function, where $m$ is big; Alice would like to sample...
In the aftermath of the Snowden revelations in 2013, concerns about the integrity and security of cryptographic systems have grown significantly. As adversaries with substantial resources might attempt to subvert cryptographic algorithms and undermine their intended security guarantees, the need for subversion-resilient cryptography has become paramount. Security properties are preserved in subversion-resilient schemes, even if the adversary implements the scheme used in the security...
Extremely Lossy Functions (ELFs) are families of functions that, depending on the choice during key generation, either operate in injective mode or instead have only a polynomial image size. The choice of the mode is indistinguishable to an outsider. ELFs were introduced by Zhandry (Crypto 2016) and have been shown to be very useful in replacing random oracles in a number of applications. One open question is to determine the minimal assumption needed to instantiate ELFs. While all...
Correlation intractability is an emerging cryptographic paradigm that enabled several recent breakthroughs in establishing soundness of the Fiat-Shamir transform and, consequently, basing non-interactive zero-knowledge proofs and succinct arguments on standard cryptographic assumptions. In a nutshell, a hash family is said to be \emph{correlation intractable} for a class of relations $\mathcal{R}$ if, for any relation $R\in\mathcal{R}$, it is hard given a random hash function $h\gets H$ to...
The theory of finite simple groups is a (rather unexplored) area likely to provide interesting computational problems and modelling tools useful in a cryptographic context. In this note, we review some applications of finite non-abelian simple groups to cryptography and discuss different scenarios in which this theory is clearly central, providing the relevant definitions to make the material accessible to both cryptographers and group theorists, in the hope of stimulating further...
In 1993, Benaloh and De Mare introduced cryptographic accumulator, a primitive that allows the representation of a set of values by a short object (the accumulator) and offers the possibility to prove that some input values are in the accumulator. For this purpose, so-called asymmetric accumulators require the creation of an additional cryptographic object, called a witness. Through the years, several instantiations of accumulators were proposed either based on number theoretic assumptions,...
Suppose two parties have hash functions $h_1$ and $h_2$ respectively, but each only trusts the security of their own. We wish to build a hash combiner $C^{h_1, h_2}$ which is secure so long as either one of the underlying hash functions is. This question has been well-studied in the regime of collision resistance. In this case, concatenating the two hash outputs clearly works. Unfortunately, a long series of works (Boneh and Boyen, CRYPTO'06; Pietrzak, Eurocrypt'07; Pietrzak, CRYPTO'08)...
Our research focuses on designing efficient commitment schemes by drawing inspiration from (perfect) information-theoretical secure primitives, e.g., the one-time pad and secret sharing. We use a random input as a mask for the committed value, outputting a function on the random input. Then, couple the output with the committed value xored with folded random input. First, we explore the potential of leveraging the unique properties of the one-time pad to design effective one-way functions....
In this work we study Invertible Bloom Lookup Tables (IBLTs) with small failure probabilities. IBLTs are highly versatile data structures that have found applications in set reconciliation protocols, error-correcting codes, and even the design of advanced cryptographic primitives. For storing $n$ elements and ensuring correctness with probability at least $1 - \delta$, existing IBLT constructions require $\Omega(n(\frac{\log(1/\delta)}{\log(n)}+1))$ space and they crucially rely on fully...
The meet-in-the-middle (MITM) technique has led to many key-recovery attacks on block ciphers and preimage attacks on hash functions. Nowadays, cryptographers use automatic tools that reduce the search of MITM attacks to an optimization problem. Bao et al. (EUROCRYPT 2021) introduced a low-level modeling based on Mixed Integer Linear Programming (MILP) for MITM attacks on hash functions, which was extended to key-recovery attacks by Dong et al. (CRYPTO 2021). However, the modeling only...
Witness encryption is a generalization of public-key encryption where the public key can be any NP statement x and the associated decryption key is any witness w for x. While early constructions of witness encryption relied on multilinear maps and indistinguishability obfuscation (iO), recent works have provided direct constructions of witness encryption that are more efficient than iO (and also seem unlikely to yield iO). Motivated by this progress, we revisit the possibility of using...
We study the following question: what cryptographic assumptions are needed for obtaining constant-round computationally-sound argument systems? We focus on argument systems with almost-linear verification time for subclasses of $\mathbf{P}$, such as depth-bounded computations. Kilian's celebrated work [STOC 1992] provides such 4-message arguments for $\mathbf{P}$ (actually, for $\mathbf{NP}$) using collision-resistant hash functions. We show that $one$-$way\ functions$ suffice for...
In this brief, we realize different architectural techniques towards improving the performance of post-quantum cryptography (PQC) algorithms when implemented as hardware accelerators on an application-specific integrated circuit (ASIC) platform. Having SABER as a case study, we designed a 256-bit wide architecture geared for high-speed cryptographic applications that incorporates smaller and distributed SRAM memory blocks. Moreover, we have adapted the building blocks of SABER to process...
Cryptographic hash functions are used inside many applications that critically rely on their resistance against cryptanalysis attacks and the correctness of their implementations. Nevertheless, vulnerabilities in cryptographic hash function implementations can remain unnoticed for more than a decade, as shown by the recent discovery of a buffer overflow in the implementation of SHA-3 in the eXtended Keccak Code Package (XKCP), impacting Python, PHP, and several other software projects. This...
Arithmetization-Oriented primitives are the building block of advanced cryptographic protocols such as Zero-Knowledge proof systems. One approach to designing such primitives is the HADES design strategy which aims to provide an efficient way to instantiate generalizing substitution-permutation networks to include partial S-box rounds. A notable instance of HADES, introduced by Grassi \emph{et al.} at USENIX Security '21, is Poseidon. Because of its impressive efficiency and low arithmetic...
We present new protocols for *Asynchronous Verifiable Secret Sharing* for Shamir (i.e., threshold $t<n$) sharing of secrets. Our protocols: * Use only "lightweight" cryptographic primitives, such as hash functions; * Can share secrets over rings such as $\mathbb{Z}_{p^k}$ as well as finite fields $\mathbb{F}_q$; * Provide *optimal resilience*, in the sense that they tolerate up to $t < n/3$ corruptions, where $n$ is the total number of parties; * Are *complete*, in the sense that they...
Fully homomorphic encryption (FHE) is a powerful cryptographic technique allowing to perform computation directly over encrypted data. Motivated by the overhead induced by the homomorphic ciphertexts during encryption and transmission, the transciphering technique, consisting in switching from a symmetric encryption to FHE encrypted data was investigated in several papers. Different stream and block ciphers were evaluated in terms of their "FHE-friendliness", meaning practical...
Digital signatures are one of the most basic cryptographic building blocks which are utilized to provide attractive security features like authenticity, unforgeability, and undeniability. The security of existing state of the art digital signatures is based on hardness of number theoretic hardness assumptions like discrete logarithm and integer factorization. However, these hard problems are insecure and face a threat in the quantum world. In particular, quantum algorithms like Shor’s...
This work presents a novel machine-checked tight security proof for $\mathrm{XMSS}$ — a stateful hash-based signature scheme that is (1) standardized in RFC 8391 and NIST SP 800-208, and (2) employed as a primary building block of $\mathrm{SPHINCS}^{+}$, one of the signature schemes recently selected for standardization as a result of NIST’s post-quantum competition. In 2020, Kudinov, Kiktenko, and Fedoro pointed out a flaw affecting the tight security proofs of $\mathrm{SPHINCS}^{+}$ and...
The present article provides a novel hash function $\mathcal{H}$ to any elliptic curve of $j$-invariant $\neq 0, 1728$ over a finite field $\mathbb{F}_{\!q}$ of large characteristic. The unique bottleneck of $\mathcal{H}$ consists in extracting a square root in $\mathbb{F}_{\!q}$ as well as for most hash functions. However, $\mathcal{H}$ is designed in such a way that the root can be found by (Cipolla--Lehmer--)Müller's algorithm in constant time. Violation of this security condition is...
We build quantum cryptosystems that support publicly-verifiable deletion from standard cryptographic assumptions. We introduce target-collapsing as a weakening of collapsing for hash functions, analogous to how second preimage resistance weakens collision resistance; that is, target-collapsing requires indistinguishability between superpositions and mixtures of preimages of an honestly sampled image. We show that target-collapsing hashes enable publicly-verifiable deletion (PVD), proving...
Cryptographic hash functions map data of arbitrary size to a fixed size digest, and are one of the most commonly used cryptographic objects. As it is infeasible to design an individual hash function for every input size, variable-input length hash functions are built by designing and bootstrapping a single fixed-input length function that looks sufficiently random. To prevent trivial preprocessing attacks, applications often require not just a single hash function but rather a family of...
The signed difference is a powerful tool for analyzing the Addition, XOR, Rotation (ARX) cryptographic primitives. Currently, solving the accurate model for the signed difference propagation is infeasible. We propose an approximate MILP modeling method capturing the propagation rules of signed differences. Unlike the accurate signed difference model, the approximate model only focuses on active bits and ignores the possible bit conditions on inactive bits. To overcome the negative effect...
We study a novel family of cryptographic hash functions based on Galois linear feedback shift registers (LFSRs), and identify initial guidelines for choosing secure parameters for this family. These hash functions are extremely simple, efficient, and suitable for implementation in constrained environments.
Is quantum computing truly faster than classical computing? Demonstrating unconditional quantum computational advantage lies beyond the reach of the current complexity theory, and therefore we have to rely on some complexity assumptions. While various results on quantum advantage have been obtained, all necessitate relatively stronger or less standard assumptions in complexity theory or classical cryptography. In this paper, we show quantum advantage based on several fundamental assumptions,...
Public-key quantum money is a cryptographic proposal for using highly entangled quantum states as currency that is publicly verifiable yet resistant to counterfeiting due to the laws of physics. Despite significant interest, constructing provably-secure public-key quantum money schemes based on standard cryptographic assumptions has remained an elusive goal. Even proposing plausibly-secure candidate schemes has been a challenge. These difficulties call for a deeper and systematic study...
SPHINCS+ was selected as a candidate digital signature scheme for standardization by the NIST Post-Quantum Cryptography Standardization Process. It offers security capabilities relying only on the security of cryptographic hash functions. However, it is less efficient than the lattice-based schemes. In this paper, we present an optimized software library for the SPHINCS+ signature scheme, which combines the Intel® Secure Hash Algorithm Extensions (SHA-NI) and AVX2 vector instructions. We...
To mitigate cybersecurity breaches, secure communication is crucial for the Internet of Things (IoT) environment. Data integrity is one of the most significant characteristics of security, which can be achieved by employing cryptographic hash functions. In view of the demand from IoT applications, the National Institute of Standards and Technology (NIST) initiated a standardization process for lightweight hash functions. This work presents field-programmable gate array (FPGA) implementations...
We define the membership function of a set as the function that determines whether an input is an element of the set. Canetti, Rothblum, and Varia showed how to obfuscate evasive membership functions of hyperplanes over a finite field of order an exponentially large prime, assuming the hardness of a modified decisional Diffie-Hellman problem. Barak, Bitansky, Canetti, Kalai, Paneth, and Sahai extended their work from hyperplanes to hypersurfaces of bounded degree, assuming multilinear maps....
Witness encryption (WE), introduced by Garg, Gentry, Sahai, and Waters (STOC 2013) allows one to encrypt a message to a statement $\mathsf{x}$ for some NP language $\mathcal{L}$, such that any user holding a witness for $\mathsf{x} \in \mathcal{L}$ can decrypt the ciphertext. The extreme power of this primitive comes at the cost of its elusiveness: a practical construction from established cryptographic assumptions is currently out of reach. In this work, we investigate a new notion of...
The classical (parallel) black pebbling game is a useful abstraction which allows us to analyze the resources (space, space-time, cumulative space) necessary to evaluate a function $f$ with a static data-dependency graph $G$. Of particular interest in the field of cryptography are data-independent memory-hard functions $f_{G,H}$ which are defined by a directed acyclic graph (DAG) $G$ and a cryptographic hash function $H$. The pebbling complexity of the graph $G$ characterizes the amortized...
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...
Non-interactive zero-knowledge proofs of knowledge (NIZKPoK) serve as a key building block in many important cryptographic constructions. Achieving universally composable NIZKPoK secure against adaptive corruptions was a long-standing open problem, recently solved by Canetti, Sarkar, and Wang (Asiacrypt'22). This sole known construction requires heavy cryptographic machinery such as correlation-intractable hash functions, and is not ready for use in practice. In this paper, we give...
Cuckoo hashing is a powerful primitive that enables storing items using small space with efficient querying. At a high level, cuckoo hashing maps $n$ items into $b$ entries storing at most $\ell$ items such that each item is placed into one of $k$ randomly chosen entries. Additionally, there is an overflow stash that can store at most $s$ items. Many cryptographic primitives rely upon cuckoo hashing to privately embed and query data where it is integral to ensure small failure probability...
The most compact quantum-safe proof systems for large circuits are PCP-type systems such as Ligero, Aurora, and Shockwave, that only use weak cryptographic assumptions, namely hash functions modeled as random oracles. One would expect that by allowing for stronger assumptions, such as the hardness of Module-SIS, it should be possible to design more compact proof systems. But alas, despite considerable progress in lattice-based proofs, no such proof system was known so far. We rectify this...
Most cryptographic protocols use cryptographic hash functions as a building block. The security analyses of these protocols typically assume that the hash functions are perfect (such as in the random oracle model). However, in practice, most widely deployed hash functions are far from perfect -- and as a result, the analysis may miss attacks that exploit the gap between the model and the actual hash function used. We develop the first methodology to systematically discover attacks on...
