(Page 2 of) 2504 results sorted by ID
Hardness of Range Avoidance and Remote Point for Restricted Circuits via Cryptography
Yilei Chen, Jiatu Li
Foundations
A recent line of research has introduced a systematic approach to explore the complexity of explicit construction problems through the use of meta problems, namely, the range avoidance problem (abbrev. $\textsf{Avoid}$) and the remote point problem (abbrev. $\textsf{RPP}$). The upper and lower bounds for these meta problems provide a unified perspective on the complexity of specific explicit construction problems that were previously studied independently. An interesting question largely...
Fully Parallel, One-Cycle Random Shuffling for Efficient Countermeasure in Post-Quantum Cryptography
Jong-Yeon Park, Dongsoo Lee, Seonggyeom Kim, Wonil lee, Bo Gyeong Kang, Kouichi Sakurai
Foundations
Hiding countermeasures are the most widely utilized techniques for thwarting side-channel attacks, and their significance has been further emphasized with the advent of Post Quantum Cryptography (PQC) algorithms, owing to the extensive use of vector operations. Commonly, the Fisher-Yates algorithm is adopted in hiding countermeasures with permuted operation for its security and efficiency in implementation, yet the inherently sequential nature of the algorithm imposes limitations on hardware...
Reverie: an end-to-end accumulation scheme from Cyclefold
Lev Soukhanov
Foundations
Recent advances in SNARK recursion and incrementally-verifiable computation are vast, but most of the efforts seem to be focused on a particular design goal - proving the result of a large computation known completely in advance.
There are other possible applications, requiring different design tradeoffs. Particularly interesting direction is a case with a swarm of collaborating provers, communicating over a peer-to-peer network - which requires to also optimize the amount of data...
B2T: The Third Logical Value of a Bit
Dipesh, Vishesh Mishra, Urbi chatterjee
Foundations
Modern computing systems predominantly operate on the binary number system that accepts only ‘0’ or ‘1’ as logical values leading to computational homogeneity. But this helps in creating leakage patterns that can be exploited by adversaries to carry out hardware and software-level attacks. Recent research has shown that ternary systems, operating on three logical values (‘0′, ‘1', and ‘z') can surpass binary systems in terms of performance and security. In this paper, we first propose a...
Accountable Bulletin Boards: Definition and Provably Secure Implementation
Mike Graf, Ralf Küsters, Daniel Rausch, Simon Egger, Marvin Bechtold, Marcel Flinspach
Foundations
Bulletin boards (BB) are important cryptographic building blocks that, at their core, provide a broadcast channel with
memory. BBs are widely used within many security protocols, including secure multi-party computation protocols, e-voting systems, and electronic auctions. Even though the security of protocols crucially depends on the underlying BB, as also highlighted by recent works, the literature on constructing secure BBs is sparse. The so-far only provably secure BBs require trusted...
Different Flavours of HILL Pseudoentropy and Yao Incompressibility Entropy
Pihla Karanko
Foundations
There are two popular ways to measure computational entropy in cryptography: (HILL) pseudoentropy and (Yao) incompressibility entropy. Both of these computational entropy notions are based on a natural intuition.
- A random variable $X$ has $k$ bits of pseudoentropy if there exists a random variable $Y$ that has $k$ bits 'real' entropy and $Y$ is computationally indistinguishable from $X$.
- A random variable $X$ has $k$ bits of incompressibility entropy if $X$ cannot be efficiently...
A Simple and Efficient Framework of Proof Systems for NP
Yuyu Wang, Chuanjie Su, Jiaxin Pan, Yu Chen
Foundations
In this work, we propose a simple framework of constructing efficient non-interactive zero-knowledge proof (NIZK) systems for all NP. Compared to the state-of-the-art construction by Groth, Ostrovsky, and Sahai (J. ACM, 2012), our resulting NIZK system reduces the proof size and proving and verification cost without any trade-off, i.e., neither increasing computation cost, CRS size nor resorting to stronger assumptions.
Furthermore, we extend our framework to construct a batch argument...
A note on quantum approximate optimization algorithm
Zhengjun Cao
Foundations
The general quantum approximate optimization algorithm (QAOA)
produces approximate solutions for combinatorial optimization problems. The algorithm depends on a positive integer $p$ and the quality of approximation improves as $p$ is increased. In this note, we put some questions about the general QAOA. We also find the recursive QAOA for MaxCut problem is flawed because all quantum gates involved in the algorithm are single qubit gates. No any entangling gate is used, which results in...
Cycle Structure and Observability of Two Types of Galois NFSRs
Xianghan Wang, Jianghua Zhong, Dongdai Lin
Foundations
Nonlinear feedback shift registers (NFSRs) are used in many stream ciphers as their main building blocks. One security criterion for the design of a stream cipher is to assure its keystream has a long period. To meet this criterion, the NFSR used in a stream cipher must have a long state cycle. Further, to simultaneously avoid equivalent keys, the keystream's period is not compressed compared to the NFSR's state cycle length, which can be guaranteed if the NFSR is observable in the sense...
Unconditionally Secure Commitments with Quantum Auxiliary Inputs
Tomoyuki Morimae, Barak Nehoran, Takashi Yamakawa
Foundations
We show the following unconditional results on quantum commitments in two related yet different models:
1. We revisit the notion of quantum auxiliary-input commitments introduced by Chailloux, Kerenidis, and Rosgen (Comput. Complex. 2016) where both the committer and receiver take the same quantum state, which is determined by the security parameter,
as quantum auxiliary inputs. We show that computationally-hiding and statistically-binding quantum auxiliary-input commitments exist...
Unclonable Cryptography with Unbounded Collusions
Alper Çakan, Vipul Goyal
Foundations
Quantum no-cloning theorem gives rise to the intriguing possibility of quantum copy protection where we encode a program in a quantum state such that a user in possession of $k$ such states cannot create $k+1$ working copies. Introduced by Aaronson (CCC'09) over a decade ago, copy protection has proven to be notoriously hard to achieve.
In this work, we construct public-key encryption and functional encryption schemes whose secret keys are copy-protected against unbounded collusions in...
Ring-LWE Hardness Based on Non-invertible Ideals
Charanjit S. Jutla, Chengyu Lin
Foundations
We extend the known pseudorandomness of Ring-LWE to be based on lattices that do not correspond to any ideal of any order in the underlying number field. In earlier works of Lyubashevsky et al (EUROCRYPT 2010) and Peikert et al (STOC 2017), the hardness of RLWE was based on ideal lattices of ring of integers of number fields, which are known to be Dedekind domains. While these works extended Regev's (STOC 2005) quantum polynomial-time reduction for LWE, thus allowing more efficient and more...
Towards Unclonable Cryptography in the Plain Model
Céline Chevalier, Paul Hermouet, Quoc-Huy Vu
Foundations
By leveraging the no-cloning principle of quantum mechanics, unclonable cryptography enables us to achieve novel cryptographic protocols that are otherwise impossible classically. Two most notable examples of unclonable cryptography are quantum copy-protection and unclonable encryption. Most known constructions rely on the quantum random oracle model (as opposed to the plain model), in which all parties have access in superposition to a powerful random oracle.
Despite receiving a lot of...
Beyond MPC-in-the-Head: Black-Box Constructions of Short Zero-Knowledge Proofs
Carmit Hazay, Muthuramakrishnan Venkitasubramaniam, Mor Weiss
Foundations
In their seminal work, Ishai, Kushilevitz, Ostrovsky, and Sahai (STOC`07) presented the MPC-in-the-Head paradigm, which shows how to design Zero-Knowledge Proofs (ZKPs) from secure Multi-Party Computation (MPC) protocols. This paradigm has since then revolutionized and modularized the design of efficient ZKP systems, with far-reaching applications beyond ZKPs. However, to the best of our knowledge, all previous instantiations relied on fully-secure MPC protocols, and have not been able to...
On Instantiating Unleveled Fully-Homomorphic Signatures from Falsifiable Assumptions
Romain Gay, Bogdan Ursu
Foundations
We build the first unleveled fully homomorphic signature scheme in the standard model. Our scheme is not constrained by any a-priori bound on the depth of the functions that can be homomorphically evaluated, and relies on subexponentially-secure indistinguishability obfuscation, fully-homomorphic encryption and a non-interactive zero-knowledge (NIZK) proof system with composable zero-knowledge. Our scheme is also the first to satisfy the strong security notion of context-hiding for an...
PURED: A unified framework for resource-hard functions
Alex Biryukov, Marius Lombard-Platet
Foundations
Algorithm hardness can be described by 5 categories: hardness in computation, in sequential computation, in memory, in energy consumption (or bandwidth), in code size. Similarly, hardness can be a concern for solving or for verifying, depending on the context, and can depend on a secret trapdoor or be universally hard. Two main lines of research investigated such problems: cryptographic puzzles, that gained popularity thanks to blockchain consensus systems (where solving must be moderately...
Sublinear-Communication Secure Multiparty Computation does not require FHE
Elette Boyle, Geoffroy Couteau, Pierre Meyer
Foundations
Secure computation enables mutually distrusting parties to jointly compute a function on their secret inputs, while revealing nothing beyond the function output. A long-running challenge is understanding the required communication complexity of such protocols---in particular, when communication can be sublinear in the circuit representation size of the desired function.
Significant advances have been made affirmatively answering this question within the two-party setting, based on a...
BabySpartan: Lasso-based SNARK for non-uniform computation
Srinath Setty, Justin Thaler
Foundations
Lasso (Setty, Thaler, Wahby, ePrint 2023/1216) is a recent lookup argument that ensures that the prover cryptographically commits to only "small" values. This note describes BabySpartan, a SNARK for a large class of constraint systems that achieves the same property. The SNARK is a simple combination of SuperSpartan and Lasso. The specific class of constraint systems supported is a generalization of so-called Plonkish constraint systems (and a special case of customizable constraint systems...
A Modular Approach to Unclonable Cryptography
Prabhanjan Ananth, Amit Behera
Foundations
We explore a new pathway to designing unclonable cryptographic primitives. We propose a new notion called unclonable puncturable obfuscation (UPO) and study its implications for unclonable cryptography. Using UPO, we present modular (and in some cases, arguably, simple) constructions of many primitives in unclonable cryptography, including, public-key quantum money, quantum copy-protection for many classes of functionalities, unclonable encryption, and single-decryption encryption....
Efficiently Testable Circuits without Conductivity
Mirza Ahad Baig, Suvradip Chakraborty, Stefan Dziembowski, Małgorzata Gałązka, Tomasz Lizurej, Krzysztof Pietrzak
Foundations
The notion of ``efficiently testable circuits'' (ETC) was recently put forward by Baig et al.~(ITCS'23). Informally, an ETC compiler takes as input any Boolean circuit $C$ and outputs a circuit/inputs tuple $(C',\mathbb{T})$ where (completeness) $C'$ is functionally equivalent to $C$
and (security) if $C'$ is tampered in some restricted way, then this can be detected as $C'$ will err on at least one input in the small test set $\mathbb{T}$. The compiler of Baig et al. detects tampering...
An efficient quantum parallel repetition theorem and applications
John Bostanci, Luowen Qian, Nicholas Spooner, Henry Yuen
Foundations
We prove a tight parallel repetition theorem for $3$-message computationally-secure quantum interactive protocols between an efficient challenger and an efficient adversary. We also prove under plausible assumptions that the security of $4$-message computationally secure protocols does not generally decrease under parallel repetition. These mirror the classical results of Bellare, Impagliazzo, and Naor [BIN97]. Finally, we prove that all quantum argument systems can be generically compiled...
A Solution to a Conjecture on the Maps $\chi_n^{(k)}$
Kamil Otal
Foundations
The Boolean map $\chi_n^{(k)}:\mathbb{F}_{2^k}^n\rightarrow \mathbb{F}_{2^k}^n$, $x\mapsto u$ given by $u_i=x_i+(x_{(i+1)\ \mathrm{mod}\ n}+1)x_{(i+2)\ \mathrm{mod}\ n}$ appears in various permutations as a part of cryptographic schemes such as KECCAK-f, ASCON, Xoodoo, Rasta, and Subterranean (2.0). Schoone and Daemen investigated some important algebraic properties of $\chi_n^{(k)}$ in [IACR Cryptology ePrint Archive 2023/1708]. In particular, they showed that $\chi_n^{(k)}$ is not...
Watermarks in the Sand: Impossibility of Strong Watermarking for Generative Models
Hanlin Zhang, Benjamin L. Edelman, Danilo Francati, Daniele Venturi, Giuseppe Ateniese, Boaz Barak
Foundations
Watermarking generative models consists of planting a statistical signal (watermark) in a model’s output so that it can be later verified that the output was generated by the given model. A strong watermarking scheme satisfies the property that a computationally bounded attacker cannot erase the watermark without causing significant quality degradation. In this paper, we study the (im)possibility of strong watermarking schemes. We prove that, under well-specified and natural assumptions,...
Robust Combiners and Universal Constructions for Quantum Cryptography
Taiga Hiroka, Fuyuki Kitagawa, Ryo Nishimaki, Takashi Yamakawa
Foundations
A robust combiner combines many candidates for a cryptographic primitive and generates a new candidate for the same primitive. Its correctness and security hold as long as one of the original candidates satisfies correctness and security. A universal construction is a closely related notion to a robust combiner. A universal construction for a primitive is an explicit construction of the primitive that is correct and secure as long as the primitive exists. It is known that a universal...
Introducing Clapoti(s): Evaluating the isogeny class group action in polynomial time
Aurel Page, Damien Robert
Foundations
In this short note, we present a simplified (but slower) version Clapoti of Clapotis, whose full description will appear later. Let 𝐸/𝔽_𝑞 be an elliptic curve with an effective primitive orientation by a quadratic imaginary order 𝑅 ⊂ End(𝐸). Let 𝔞 be an invertible ideal in 𝑅. Clapoti is a randomized polynomial time algorithm in 𝑂 ((log Δ_𝑅 + log 𝑞)^𝑂(1) ) operations to compute the class group action 𝐸 ↦ 𝐸_𝔞 ≃ 𝐸/𝐸[𝔞].
The Non-Uniform Perebor Conjecture for Time-Bounded Kolmogorov Complexity is False
Noam Mazor, Rafael Pass
Foundations
The Perebor (Russian for “brute-force search”) conjectures, which date back to the 1950s and 1960s are some of the oldest conjectures in complexity theory. The conjectures are a stronger form of the NP ̸ = P conjecture (which they predate) and state that for “meta-complexity” problems, such as the Time-bounded Kolmogorov complexity Problem, and the Minimum Circuit Size Problem, there are no better algorithms than brute force search.
In this paper, we disprove the non-uniform version of...
Adaptively Secure Consensus with Linear Complexity and Constant Round under Honest Majority in the Bare PKI Model, and Separation Bounds from the Idealized Message-Authentication Model
Matthieu Rambaud
Foundations
We consider the mainstream model in secure computation known as the bare PKI setup, also as the {bulletin-board PKI}. It allows players to broadcast once and non-interactively before they receive their inputs and start the execution. A bulletin-board PKI is essentially the minimum setup known so far to implement the model known as {messages-authentication}, i.e., when $P$ is forwarded a signed message, it considers it to be issued by $R$ if and only if $R$ signed it. It is known since...
How to Use Quantum Indistinguishability Obfuscation
Andrea Coladangelo, Sam Gunn
Foundations
Quantum copy protection, introduced by Aaronson, enables giving out a quantum program-description that cannot be meaningfully duplicated. Despite over a decade of study, copy protection is only known to be possible for a very limited class of programs.
As our first contribution, we show how to achieve "best-possible" copy protection for all programs. We do this by introducing quantum state indistinguishability obfuscation (qsiO), a notion of obfuscation for quantum descriptions of...
A Statistical Verification Method of Random Permutations for Hiding Countermeasure Against Side-Channel Attacks
Jong-Yeon Park, Jang-Won Ju, Wonil Lee, Bo-Gyeong Kang, Yasuyuki Kachi, Kouichi Sakurai
Foundations
As NIST is putting the final touches on the standardization of PQC (Post Quantum Cryptography) public key algorithms, it is a racing certainty that peskier cryptographic attacks undeterred by those new PQC algorithms will surface. Such a trend in turn will prompt more follow-up studies of attacks and countermeasures. As things stand, from the attackers’ perspective, one viable form of attack that can be implemented thereupon is the so-called “side-channel attack”. Two best-known...
Explicit Lower Bounds for Communication Complexity of PSM for Concrete Functions
Kazumasa Shinagawa, Koji Nuida
Foundations
Private Simultaneous Messages (PSM) is a minimal model of secure computation, where the input players with shared randomness send messages to the output player simultaneously and only once. In this field, finding upper and lower bounds on communication complexity of PSM protocols is important, and in particular, identifying the optimal one where the upper and lower bounds coincide is the ultimate goal. However, up until now, functions for which the optimal communication complexity has been...
Pseudorandom Isometries
Prabhanjan Ananth, Aditya Gulati, Fatih Kaleoglu, Yao-Ting Lin
Foundations
We introduce a new notion called ${\cal Q}$-secure pseudorandom isometries (PRI). A pseudorandom isometry is an efficient quantum circuit that maps an $n$-qubit state to an $(n+m)$-qubit state in an isometric manner. In terms of security, we require that the output of a $q$-fold PRI on $\rho$, for $ \rho \in {\cal Q}$, for any polynomial $q$, should be computationally indistinguishable from the output of a $q$-fold Haar isometry on $\rho$.
By fine-tuning ${\cal Q}$, we recover many...
Broadcast-Optimal Four-Round MPC in the Plain Model
Michele Ciampi, Ivan Damgård, Divya Ravi, Luisa Siniscalchi, Yu Xia, Sophia Yakoubov
Foundations
Motivated by the fact that broadcast is an expensive, but useful, resource for the realization of multi-party computation protocols (MPC), Cohen, Garay, and Zikas (Eurocrypt 2020), and subsequently Damgård, Magri, Ravi, Siniscalchi and Yakoubov (Crypto 2021), and, Damgård, Ravi, Siniscalchi and Yakoubov (Eurocrypt 2023), focused on 𝘴𝘰-𝘤𝘢𝘭𝘭𝘦𝘥 𝘣𝘳𝘰𝘢𝘥𝘤𝘢𝘴𝘵 𝘰𝘱𝘵𝘪𝘮𝘢𝘭 𝘔𝘗𝘊. In particular, the authors focus on two-round MPC protocols (in the CRS model), and give tight characterizations of which...
Byzantine Agreement Decomposed: Honest Majority Asynchronous Atomic Broadcast from Reliable Broadcast
Simon Holmgaard Kamp, Jesper Buus Nielsen
Foundations
It is well-known that Atomic Broadcast (AB) in asynchronous networks requires randomisation and that at most $t < n/3$ out of $n$ players are Byzantine corrupted. This is opposed to synchronous AB which can tolerate $t < n/2$ corruptions and can be deterministic. We show that these requirements can be conceptually separated by constructing an asynchronous AB protocol which tolerates $t < n/2$ corruptions from blackbox use of Common Coin and Reliable Broadcast (RB). We show the power of this...
On the Security of Succinct Interactive Arguments from Vector Commitments
Alessandro Chiesa, Marcel Dall'Agnol, Ziyi Guan, Nicholas Spooner
Foundations
We study the security of a fundamental family of succinct interactive arguments in the standard model, stemming from the works of Kilian (1992) and Ben-Sasson, Chiesa, and Spooner (``BCS'', 2016). These constructions achieve succinctness by combining probabilistic proofs and vector commitments.
Our first result concerns the succinct interactive argument of Kilian, realized with any probabilistically-checkable proof (PCP) and any vector commitment. We establish the tightest known bounds on...
Exploiting the Symmetry of $\mathbb{Z}^n$: Randomization and the Automorphism Problem
Kaijie Jiang, Anyu Wang, Hengyi Luo, Guoxiao Liu, Yang Yu, Xiaoyun Wang
Foundations
$\mathbb{Z}^n$ is one of the simplest types of lattices, but the computational problems on its rotations, such as $\mathbb{Z}$SVP and $\mathbb{Z}$LIP, have been of great interest in cryptography. Recent advances have been made in building cryptographic primitives based on these problems, as well as in developing new algorithms for solving them. However, the theoretical complexity of $\mathbb{Z}$SVP and $\mathbb{Z}$LIP are still not well understood.
In this work, we study the problems on...
Construction-D lattice from Garcia-Stichtenoth tower code
Elena Kirshanova, Ekaterina Malygina
Foundations
We show an explicit construction of an efficiently decodable family of $n$-dimensional lattices whose minimum distances achieve $\Omega(\sqrt{n} / (\log n)^{\varepsilon+o(1)})$ for $\varepsilon>0$. It improves upon the state-of-the-art construction due to Mook-Peikert (IEEE Trans.\ Inf.\ Theory, no. 68(2), 2022) that provides lattices with minimum distances $\Omega(\sqrt{n/ \log n})$. These lattices are construction-D lattices built from a sequence of BCH codes. We show that replacing BCH...
Few-weight linear codes over $\mathbb{F}_p$ from $t$-to-one mappings
René Rodríguez-Aldama
Foundations
For any prime number $p$, we provide two classes of linear codes with few weights over a $p$-ary alphabet. These codes are based on a well-known generic construction (the defining-set method), stemming on a class of monomials and a class of trinomials over finite fields. The considered monomials are Dembowski-Ostrom monomials $x^{p^{\alpha}+1}$, for a suitable choice of the exponent $\alpha$, so that, when $p>2$ and $n\not\equiv 0 \pmod{4}$, these monomials are planar. We study the...
Towards the Impossibility of Quantum Public Key Encryption with Classical Keys from One-Way Functions
Samuel Bouaziz--Ermann, Alex B. Grilo, Damien Vergnaud, Quoc-Huy Vu
Foundations
There has been a recent interest in proposing quantum protocols whose security relies on weaker computational assumptions than their classical counterparts. Importantly to our work, it has been recently shown that public-key encryption (PKE) from one-way functions (OWF) is possible if we consider quantum public keys. Notice that we do not expect classical PKE from OWF given the impossibility results of Impagliazzo and Rudich (STOC'89).
However, the distribution of quantum public keys is a...
On Parallel Repetition of PCPs
Alessandro Chiesa, Ziyi Guan, Burcu Yıldız
Foundations
Parallel repetition refers to a set of valuable techniques used to reduce soundness error of probabilistic proofs while saving on certain efficiency measures. Parallel repetition has been studied for interactive proofs (IPs) and multi-prover interactive proofs (MIPs). In this paper we initiate the study of parallel repetition for probabilistically checkable proofs (PCPs).
We show that, perhaps surprisingly, parallel repetition of a PCP can increase soundness error, in fact bringing the...
Algebraic properties of the maps $\chi_n$
Jan Schoone, Joan Daemen
Foundations
The Boolean map $\chi_n \colon \mathbb{F}_2^n \to \mathbb{F}_2^n,\ x \mapsto y$ defined by $y_i = x_i + (x_{i+1}+1)x_{i+2}$ (where $i\in \mathbb{Z}/n\mathbb{Z}$) is used in various permutations that are part of cryptographic schemes, e.g., Keccak-f (the SHA-3-permutation), ASCON (the winner of the NIST Lightweight competition), Xoodoo, Rasta and Subterranean (2.0).
In this paper, we study various algebraic properties of this map.
We consider $\chi_n$ (through vectorial isomorphism) as a...
On Quantum Simulation-Soundness
Behzad Abdolmaleki, Céline Chevalier, Ehsan Ebrahimi, Giulio Malavolta, Quoc-Huy Vu
Foundations
Non-interactive zero-knowledge (NIZK) proof systems are a cornerstone of modern cryptography, but their security has received little attention in the quantum settings. Motivated by improving our understanding of this fundamental primitive against quantum adversaries, we propose a new definition of security against quantum adversary. Specifically, we define the notion of quantum simulation soundness
(SS-NIZK), that allows the adversary to access the simulator in superposition. We show a...
Admissible Parameter Sets and Complexity Estimation of Crossbred Algorithm
Shuhei Nakamura
Foundations
The Crossbred algorithm is one of the algorithms for solving a system of polynomial equations, proposed by Joux and Vitse in 2017. It has been implemented in Fukuoka MQ challenge, which is related to the security of multivariate crytography, and holds several records. A framework for estimating the complexity has already been provided by Chen et al. in 2017. However, it is generally unknown which parameters are actually available. This paper investigates how to select available parameters...
The Quantum Decoding Problem
André Chailloux, Jean-Pierre Tillich
Foundations
One of the founding results of lattice based cryptography is a quantum reduction from the Short Integer Solution problem to the Learning with Errors problem introduced by Regev. It has recently been pointed out by Chen, Liu and Zhandry that this reduction can be made more powerful by replacing the learning with errors problem with a quantum equivalent, where the errors are given in quantum superposition. In the context of codes, this can be adapted to a reduction from finding short...
$\Pi$: A Unified Framework for Verifiable Secret Sharing
Karim Baghery
Foundations
An $(n, t)$-Non-Interactive Verifiable Secret Sharing (NI-VSS) scheme allows a dealer to share a secret among $n$ parties, s.t. all the parties can verify the validity of their shares and only a set of them, i.e., more than $t$, can access the secret. In this paper, we present $\Pi$, as a unified framework for building NI-VSS schemes in the majority honest setting. Notably, $\Pi$ does not rely on homomorphic commitments; instead requires a Random Oracle (RO) and any commitment scheme that...
Approximate Lower Bound Arguments
Pyrros Chaidos, Aggelos Kiayias, Leonid Reyzin, Anatoliy Zinovyev
Foundations
Suppose a prover, in possession of a large body of valuable evidence, wants to quickly convince a verifier by presenting only a small portion of the evidence.
We define an Approximate Lower Bound Argument, or ALBA, which allows the prover to do just that: to succinctly prove knowledge of a large number of elements satisfying a predicate (or, more generally, elements of a sufficient total weight when a predicate is generalized to a weight function). The argument is approximate because...
On Gaussian sampling, smoothing parameter and application to signatures
Thomas Espitau, Alexandre Wallet, Yang Yu
Foundations
We present a general framework for polynomial-time lattice Gaussian
sampling. It revolves around a systematic study of the discrete
Gaussian measure and its samplers under extensions of lattices;
we first show that given lattices $\Lambda'\subset \Lambda$ we can sample
efficiently in $\Lambda$ if we know how to do so in $\Lambda'$ and the
quotient $\Lambda/\Lambda'$, \emph{regardless} of the primitivity of
$\Lambda'$. As a direct application, we...
Security Bounds for Proof-Carrying Data from Straightline Extractors
Alessandro Chiesa, Ziyi Guan, Shahar Samocha, Eylon Yogev
Foundations
Proof-carrying data (PCD) is a powerful cryptographic primitive that allows mutually distrustful parties to perform distributed computation in an efficiently verifiable manner. Real-world deployments of PCD have sparked keen interest within the applied community and industry.
Known constructions of PCD are obtained by recursively-composing SNARKs or related primitives. Unfortunately, known security analyses incur expensive blowups, which practitioners have disregarded as the analyses...
Quantum Key Leasing for PKE and FHE with a Classical Lessor
Orestis Chardouvelis, Vipul Goyal, Aayush Jain, Jiahui Liu
Foundations
In this work, we consider the problem of secure key leasing, also known as revocable cryptography (Agarwal et. al. Eurocrypt' 23, Ananth et. al. TCC' 23), as a strengthened security notion of its predecessor put forward in Ananth et. al. Eurocrypt' 21. This problem aims to leverage unclonable nature of quantum information to allow a lessor to lease a quantum key with reusability for evaluating a classical functionality. Later, the lessor can request the lessee to provably delete the key and...
On Decompositions of Permutations in Quadratic Functions
Samuele Andreoli, Enrico Piccione, Lilya Budaghyan, Pantelimon Stănică, Svetla Nikova
Foundations
The algebraic degree of a vectorial Boolean function is one of the main parameters driving the cost of its hardware implementation.
Thus, finding decompositions of functions into sequences of functions of lower algebraic degrees has been explored to reduce the cost of implementations. In this paper, we consider such decompositions of permutations over $\mathbb{F}_{2^n}$.
We prove the existence of decompositions using quadratic and linear power permutations for all permutations when...
Commitments from Quantum One-Wayness
Dakshita Khurana, Kabir Tomer
Foundations
One-way functions are central to classical cryptography. They are both necessary for the existence of non-trivial classical cryptosystems, and sufficient to realize meaningful primitives including commitments, pseudorandom generators and digital signatures. At the same time, a mounting body of evidence suggests that assumptions even weaker than one-way functions may suffice for many cryptographic tasks of interest in a quantum world, including bit commitments and secure multi-party...
Power circuits: a new arithmetization for GKR-styled sumcheck
Lev Soukhanov
Foundations
Goldwasser-Kalai-Rothblum protocol (GKR) for layered circuits is a sumcheck-based argument of knowledge for layered circuits, running in $\sim 2\mu \ell$ amount of rounds, where $\ell$ is the amount of layers and $\mu$ is the average layer logsize.
For a layer $i$ of size $2^{\mu_i}$ the main work consists of running a sumcheck protocol of the form \[\underset{x,y}{\sum} \text{Add}_i(x,y,z)(f(x)+f(y)) + \text{Mul}_i(x,y,z)f(x)f(y)\] over a $2^{2\mu_i}$-dimensional cube, where...
How to Prove Statements Obliviously?
Sanjam Garg, Aarushi Goel, Mingyuan Wang
Foundations
Cryptographic applications often require proving statements about hidden secrets satisfying certain circuit relations. Moreover, these proofs must often be generated obliviously, i.e., without knowledge of the secret. This work presents a new technique called --- FRI on hidden values --- for efficiently proving such statements.
This technique enables a polynomial commitment scheme for values hidden inside linearly homomorphic primitives, such as linearly homomorphic encryption, linearly...
A one-query lower bound for unitary synthesis and breaking quantum cryptography
Alex Lombardi, Fermi Ma, John Wright
Foundations
The Unitary Synthesis Problem (Aaronson-Kuperberg 2007) asks whether any $n$-qubit unitary $U$ can be implemented by an efficient quantum algorithm $A$ augmented with an oracle that computes an arbitrary Boolean function $f$. In other words, can the task of implementing any unitary be efficiently reduced to the task of implementing any Boolean function?
In this work, we prove a one-query lower bound for unitary synthesis. We show that there exist unitaries $U$ such that no...
The Uber-Knowledge Assumption: A Bridge to the AGM
Balthazar Bauer, Pooya Farshim, Patrick Harasser, Markulf Kohlweiss
Foundations
The generic-group model (GGM) and the algebraic-group model (AGM) have been exceptionally successful in proving the security of many classical and modern cryptosystems. These models, however, come with standard-model uninstantiability results, raising the question whether the schemes analyzed under them can be based on firmer standard-model footing.
We formulate the uber-knowledge (UK) assumption, a standard-model assumption that naturally extends the uber-assumption family to...
One-way Functions and Hardness of (Probabilistic) Time-Bounded Kolmogorov Complexity w.r.t. Samplable Distributions
Yanyi Liu, Rafael Pass
Foundations
Consider the recently introduced notion of \emph{probabilistic
time-bounded Kolmogorov Complexity}, pK^t (Goldberg et al,
CCC'22), and let MpK^tP denote the language of pairs (x,k) such that pK^t(x) \leq k.
We show the equivalence of the following:
- MpK^{poly}P is (mildly) hard-on-average w.r.t. \emph{any} samplable
distribution D;
- MpK^{poly}P is (mildly) hard-on-average w.r.t. the
\emph{uniform} distribution;
- Existence of one-way functions.
As far as we know, this...
On the Round Complexity of Asynchronous Crusader Agreement
Ittai Abraham, Naama Ben-David, Gilad Stern, Sravya Yandamuri
Foundations
We present new lower and upper bounds on the number of communication rounds required for asynchronous Crusader Agreement (CA) and Binding Crusader Agreement (BCA), two primitives that are used for solving binary consensus. We show results for the information theoretic and authenticated settings. In doing so, we present a generic model for proving round complexity lower bounds in the asynchronous setting.
In some settings, our attempts to prove lower bounds on round complexity fail....
How to Garble Mixed Circuits that Combine Boolean and Arithmetic Computations
Hanjun Li, Tianren Liu
Foundations
The study of garbling arithmetic circuits is initiated by Applebaum, Ishai, and Kushilevitz [FOCS'11], which can be naturally extended to mixed circuits. The basis of mixed circuits includes Boolean operations, arithmetic operations over a large ring and bit-decomposition that converts an arithmetic value to its bit representation. We construct efficient garbling schemes for mixed circuits.
In the random oracle model, we construct two garbling schemes:
$\bullet$ The first scheme...
Towards Optimally Small Smoothness Bounds for Cryptographic-Sized Twin Smooth Integers and their Isogeny-based Applications
Bruno Sterner
Foundations
We give a new approach for finding large smooth twins. Those twins whose sum is a prime are of interest in the parameter setup of certain isogeny-based cryptosystems such as SQIsign. The approach to find such twins is to find two polynomials in $\mathbb{Q}[x]$ that split into a product of small degree factors and differ by $1$. Then evaluate them on a particular smooth integer. This was first explored by Costello, Meyer and Naehrig at EUROCRYPT'21 using polynomials that split completely into...
Unclonable Commitments and Proofs
Vipul Goyal, Giulio Malavolta, Justin Raizes
Foundations
Non-malleable cryptography, proposed by Dolev, Dwork, and Naor (SICOMP '00), has numerous applications in protocol composition. In the context of proofs, it guarantees that an adversary who receives a proof cannot maul it into another valid proof. However, non-malleable cryptography (particularly in the non-interactive setting) suffers from an important limitation: An attacker can always copy the proof and resubmit it to another verifier (or even multiple verifiers).
In this work, we...
A reduced set of submatrices for a faster evaluation of the MDS property of a circulant matrix with entries that are powers of two
Dragan Lambić
Foundations
In this paper a reduced set of submatrices for a faster evaluation of the MDS property of a circulant matrix, with entries that are powers of two, is proposed. A proposition is made that under the condition that all entries of a t × t circulant matrix are powers of 2, it is sufficient to check only its 2x2 submatrices in order to evaluate the MDS property in a prime field. Although there is no theoretical proof to support this proposition at this point, the experimental results conducted on...
Leakage-Free Probabilistic Jasmin Programs
José Bacelar Almeida, Denis Firsov, Tiago Oliveira, Dominique Unruh
Foundations
We give a semantic characterization of leakage-freeness through timing side-channels for Jasmin programs. Our characterization also covers probabilistic Jasmin programs that are not constant-time. In addition, we provide a characterization in terms of probabilistic relational Hoare logic and prove equivalence of both definitions. We also prove that our new characterizations are compositional. Finally, we relate new definitions to the existing ones from prior work which only apply to...
Lower bound of costs of formulas to compute image curves of $3$-isogenies in the framework of generalized Montgomery coordinates
Tomoki Moriya, Hiroshi Onuki, Yusuke Aikawa, Tsuyoshi Takagi
Foundations
In 2022, Moriya, Onuki, Aikawa, and Takagi proposed a new framework named generalized Montgomery coordinates to treat one-coordinate type formulas to compute isogenies. This framework generalizes some already known one-coordinate type formulas of elliptic curves. Their result shows that a formula to compute image points under isogenies is unique in the framework of generalized Montogmery coordinates; however, a formula to compute image curves is not unique. Therefore, we have a question:...
Algebraic Group Model with Oblivious Sampling
Helger Lipmaa, Roberto Parisella, Janno Siim
Foundations
In the algebraic group model (AGM), an adversary has to return with each group element a linear representation with respect to input group elements. In many groups, it is easy to sample group elements obliviously without knowing such linear representations. Since the AGM does not model this, it can be used to prove the security of spurious knowledge assumptions. We show several well-known zk-SNARKs use such assumptions. We propose AGM with oblivious sampling (AGMOS), an AGM variant where...
Space-Efficient and Noise-Robust Quantum Factoring
Seyoon Ragavan, Vinod Vaikuntanathan
Foundations
We provide two improvements to Regev's recent quantum factoring algorithm (arXiv:2308.06572), addressing its space efficiency and its noise-tolerance.
Our first contribution is to improve the quantum space efficiency of Regev's algorithm while keeping the circuit size the same. Our main result constructs a quantum factoring circuit using $O(n \log n)$ qubits and $O(n^{3/2} \log n)$ gates. We achieve the best of Shor and Regev (upto a logarithmic factor in the space complexity): on...
Holographic SNARGs for P and Batch-NP from (Polynomially Hard) Learning with Errors
Susumu Kiyoshima
Foundations
A succinct non-interactive argument (SNARG) is called holographic if the verifier runs in time sub-linear in the input length when given oracle access to an encoding of the input. We present holographic SNARGs for P and Batch-NP under the learning with errors (LWE) assumption. Our holographic SNARG for P has a verifier that runs in time $\mathsf{poly}(\lambda, \log T, \log n)$ for $T$-time computations and $n$-bit inputs ($\lambda$ is the security parameter), while our holographic SNARG for...
On the Hardness of $\sf{S|LWE\rangle}$ with Gaussian and Other Amplitudes
Yilei Chen, Zihan Hu, Qipeng Liu, Han Luo, Yaxin Tu
Foundations
The learning with errors problem (LWE) is one of the most important building blocks for post-quantum cryptography. To better understand the quantum hardness of LWE, it is crucial to explore quantum variants of LWE, show quantum algorithms for those variants, or prove they are as hard as standard LWE.
To this end, Chen, Liu, and Zhandry [Eurocrypt 2022] define the $\sf{S|LWE\rangle}$ problem, which encodes the error of LWE samples into quantum amplitudes. They then show efficient quantum...
Measuring the Concentration of Control in Contemporary Ethereum
Simon Brown
Foundations
Ethereum is undergoing significant changes to its architecture as it evolves. These changes include its switch to PoS consensus and the introduction of significant infrastructural changes that do not require a change to the core protocol, but that fundamentally affect the way users interact with the network. These changes represent an evolution toward a more modular architecture, in which there exists new exogenous vectors for centralization. This paper builds on previous studies of...
Lower Bounds on Anonymous Whistleblowing
Willy Quach, LaKyah Tyner, Daniel Wichs
Foundations
Anonymous transfer, recently introduced by Agrikola, Couteau and Maier [ACM22] (TCC '22), allows a sender to leak a message anonymously by participating in a public non-anonymous discussion where everyone knows who said what. This opens up the intriguing possibility of using cryptography to ensure strong anonymity guarantees in a seemingly non-anonymous environment.
The work of [ACM22] presented a lower bound on anonymous transfer, ruling out constructions with strong anonymity guarantees...
Succinct Proofs and Linear Algebra
Alex Evans, Guillermo Angeris
Foundations
The intuitions behind succinct proof systems are often difficult to separate from some of the deep cryptographic techniques that are used in their construction. In this paper, we show that, using some simple abstractions, a number of commonly-used tools used in the construction of succinct proof systems may be viewed as basic consequences of linear algebra over finite fields. We introduce notation which considerably simplifies these constructions and slowly build a toolkit of useful...
Auditable Obfuscation
Shalini Banerjee, Steven D. Galbraith
Foundations
We introduce a new variant of malicious obfuscation. Our formalism is incomparable to the existing definitions by Canetti and Varia (TCC 2010), Canetti et al. (EUROCRYPT 2022) and Badrinarayanan et al. (ASIACRYPT 2016). We show that this concept is natural and applicable to obfuscation-as-a-service platforms. We next define a new notion called auditable obfuscation which provides security against malicious obfuscation. Finally, we construct a proof of concept of the developed notions based...
On Black-Box Verifiable Outsourcing
Amit Agarwal, Navid Alamati, Dakshita Khurana, Srinivasan Raghuraman, Peter Rindal
Foundations
We study verifiable outsourcing of computation in a model where the verifier has black-box access to the function being computed. We introduce the problem of oracle-aided batch verification of computation (OBVC) for a function class $\mathcal{F}$. This allows a verifier to efficiently verify the correctness of any $f \in \mathcal{F}$ evaluated on a batch of $n$ instances $x_1, \ldots, x_n$, while only making $\lambda$ calls to an oracle for $f$ (along with $O(n \lambda)$ calls to...
Round-Robin is Optimal: Lower Bounds for Group Action Based Protocols
Daniele Cozzo, Emanuele Giunta
Foundations
An hard homogeneous space (HHS) is a finite group acting on a set with
the group action being hard to invert and the set lacking any algebraic
structure.
As such HHS could potentially replace finite groups where the discrete logarithm is hard for building cryptographic primitives and protocols in a post-quantum world.
Threshold HHS-based primitives typically require parties to compute the group action of a secret-shared input on a public set element.
On one hand this could be done...
A Further Study of Vectorial Dual-Bent Functions
Jiaxin Wang, Fang-Wei Fu, Yadi Wei, Jing Yang
Foundations
Vectorial dual-bent functions have recently attracted some researchers' interest as they play a significant role in constructing partial difference sets, association schemes, bent partitions and linear codes. In this paper, we further study vectorial dual-bent functions $F: V_{n}^{(p)}\rightarrow V_{m}^{(p)}$, where $2\leq m \leq \frac{n}{2}$, $V_{n}^{(p)}$ denotes an $n$-dimensional vector space over the prime field $\mathbb{F}_{p}$. We give new characterizations of certain vectorial...
Counting Unpredictable Bits: A Simple PRG from One-way Functions
Noam Mazor, Rafael Pass
Foundations
A central result in the theory of Cryptography, by Hastad, Imagliazzo, Luby and Levin [SICOMP’99], demonstrates that the existence one-way functions (OWF) implies the existence of pseudo-random generators (PRGs). Despite the fundamental importance of this result, and several elegant improvements/simplifications, analyses of constructions of PRGs from OWFs remain complex (both conceptually and technically).
Our goal is to provide a construction of a PRG from OWFs with a simple proof of...
On Time-Space Lower Bounds for Finding Short Collisions in Sponge Hash Functions
Akshima, Xiaoqi Duan, Siyao Guo, Qipeng Liu
Foundations
Sponge paradigm, used in the design of SHA-3, is an alternative hashing technique to the popular Merkle-Damgård paradigm. We revisit the problem of finding $B$-block-long collisions in sponge hash functions in the auxiliary-input random permutation model, in which an attacker gets a piece of $S$-bit advice about the random permutation and makes $T$ (forward or inverse) oracle queries to the random permutation.
Recently, significant progress has been made in the Merkle-Damgård setting and...
Security with Functional Re-Encryption from CPA
Yevgeniy Dodis, Shai Halevi, Daniel Wichs
Foundations
The notion of functional re-encryption security (funcCPA) for public-key encryption schemes was recently introduced by Akavia et al. (TCC'22), in the context of homomorphic encryption. This notion lies in between CPA security and CCA security: we give the attacker a functional re-encryption oracle instead of the decryption oracle of CCA security. This oracle takes a ciphertext $c$ and a function $f$, and returns fresh encryption of the output of $f$ applied to the decryption of $c$; in...
Rogue-Instance Security for Batch Knowledge Proofs
Gil Segev, Amit Sharabi, Eylon Yogev
Foundations
We propose a new notion of knowledge soundness, denoted rogue-instance security, for interactive and non-interactive batch knowledge proofs. Our notion, inspired by the standard notion of rogue-key security for multi-signature schemes, considers a setting in which a malicious prover is provided with an honestly-generated instance $x_1$, and may then be able to maliciously generate related "rogue" instances $x_2,\ldots,x_k$ for convincing a verifier in a batch knowledge proof of corresponding...
Algebraic isomorphic spaces of ideal lattices, reduction of Ring-SIS problem, and new reduction of Ring-LWE problem
Zhuang Shan, Leyou Zhang, Qing Wu, Qiqi Lai
Foundations
This paper mainly studies an open problem in modern cryptography, namely the Ring-SIS reduction problem. In order to prove the hardness of the Ring-SIS problem, this paper introduces the concepts of the one-dimensional SIS problem, the Ring-SIS$|_{x=0}$ problem, and the variant knapsack problem. The equivalence relations between the three are first established, on which the connection between the Ring-SIS$|_{x=0}$ problem and the Ring-SIS problem is built. This proves that the hardness of...
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...
Fully Homomorphic Encryption: A Mathematical Introduction
Sara Logsdon
Foundations
This paper offers a mathematical introduction to fully homomorphic encryption, a concept that enables computation on encrypted data. We trace the historical development of FHE, describe Fully Homomorphic Encryption over the Torus (TFHE) and how it performs certain mathematical operations, and explore bootstrapping and the possibility for adjusting computational depth. This paper equips readers with a brief understanding of FHE's evolution and the essential mechanisms facilitating practical...
Bootstrapping Homomorphic Encryption via Functional Encryption
Nir bitansky, Tomer Solomon
Foundations
Homomorphic encryption is a central object in modern cryptography, with far-reaching applications. Constructions supporting homomorphic evaluation of arbitrary Boolean circuits have been known for over a decade, based on standard lattice assumptions. However, these constructions are leveled, meaning that they only support circuits up to some a-priori bounded depth. These leveled constructions can be bootstrapped into fully homomorphic ones, but this requires additional circular security...
On Weighted-Sum Orthogonal Latin Squares and Secret Sharing
Koji Nuida, Tomoko Adachi
Foundations
Latin squares are a classical and well-studied topic of discrete mathematics, and recently Takeuti and Adachi (IACR ePrint, 2023) proposed (2,n)-threshold secret sharing based on mutually orthogonal Latin squares (MOLS). Hence efficient constructions of as large sets of MOLS as possible are also important from practical viewpoints. In this letter, we determine the maximum number of MOLS among a known class of Latin squares defined by weighted sums. We also mention some known property of...
Reframing And Extending The Random Probing Expandibility To Make Probing-Secure Compilers Tolerate A Constant Noise
Giuseppe Manzoni
Foundations
In the context of circuits leaking the internal state, there are various models to analyze what the adversary can see, like the $p$-random probing model in which the adversary can see the value of each wire with probability $p$. In this model, for a fixed $p$, it's possible to reach an arbitrary security by 'expanding' a stateless circuit via iterated compilation, reaching a security of $2^{-\kappa}$ with a polynomial size in $\kappa$.
The existing proofs of the expansion work by first...
Oracle Recording for Non-Uniform Random Oracles, and its Applications
Minki Hhan, Aaram Yun
Foundations
In Crypto 2019, Zhandry showed how to define compressed oracles, which record quantum superposition queries to the quantum random oracle. In this paper, we extend Zhandry's compressed oracle technique to non-uniformly distributed functions with independently sampled outputs. We define two quantum oracles $\mathsf{CStO}_D$ and $\mathsf{CPhsO}_D$, which are indistinguishable to the non-uniform quantum random oracle where quantum access is given to a random function $H$ whose images $H(x)$...
Ideal-SVP is Hard for Small-Norm Uniform Prime Ideals
Joël Felderhoff, Alice Pellet-Mary, Damien Stehlé, Benjamin Wesolowski
Foundations
The presumed hardness of the Shortest Vector Problem for ideal lattices (Ideal-SVP) has been a fruitful assumption to understand other assumptions on algebraic lattices and as a security foundation of cryptosystems. Gentry [CRYPTO'10] proved that Ideal-SVP enjoys a worst-case to average-case reduction, where the average-case distribution is the uniform distribution over the set of inverses of prime ideals of small algebraic norm (below $d^{O(d)}$ for cyclotomic fields, here $d$ refers to...
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...
Communication Lower Bounds of Key-Agreement Protocols via Density Increment Arguments
Mi-Ying (Miryam) Huang, Xinyu Mao, Guangxu Yang, Jiapeng Zhang
Foundations
Constructing key-agreement protocols in the random oracle model (ROM) is a viable method to assess the feasibility of developing public-key cryptography within Minicrypt. Unfortunately, as shown by Impagliazzo and Rudich (STOC 1989) and Barak and Mahmoody (Crypto 2009), such protocols can only guarantee limited security: any $\ell$-query protocol can be attacked by an $O(\ell^2)$-query adversary. This quadratic gap matches the key-agreement protocol proposed by Merkle (CACM 78), known as ...
Layered Symbolic Security Analysis in DY$^\star$
Karthikeyan Bhargavan, Abhishek Bichhawat, Pedram Hosseyni, Ralf Kuesters, Klaas Pruiksma, Guido Schmitz, Clara Waldmann, Tim Würtele
Foundations
While cryptographic protocols are often analyzed in isolation, they are typically deployed within a stack of protocols, where each layer relies on the security guarantees provided by the protocol layer below it, and in turn provides its own security functionality to the layer above. Formally analyzing the whole stack in one go is infeasible even for semi-automated verification tools, and impossible for pen-and-paper proofs. The DY$^\star$ protocol verification framework offers a modular and...
Optimizing HE operations via Level-aware Key-switching Framework
Intak Hwang, Jinyeong Seo, Yongsoo Song
Foundations
In lattice-based Homomorphic Encryption (HE) schemes, the key-switching procedure is a core building block of non-linear operations but also a major performance bottleneck.
The computational complexity of the operation is primarily determined by the so-called gadget decomposition, which transforms a ciphertext entry into a tuple of small polynomials before being multiplied with the corresponding evaluation key.
However, the previous studies such as Halevi et al. (CT-RSA 2019) and Han and...
Fine-Grained Secure Attribute-Based Encryption
Yuyu Wang, Jiaxin Pan, Yu Chen
Foundations
Fine-grained cryptography is constructing cryptosystems in a setting where an adversary’s resource is a-prior bounded and an honest party has less resource than an adversary. Currently, only simple form of encryption schemes, such as secret-key and public-key encryption, are constructed in this setting.
In this paper, we enrich the available tools in fine-grained cryptography by proposing the first fine-grained secure attribute-based encryption (ABE) scheme. Our construction is adaptively...
On the Black-Box Separation Between Ring Signatures and Public Key Encryptions
Kyosuke Yamashita, Keisuke Hara
Foundations
In this paper, we show that it is impossible to construct a public key encryption scheme (PKE) from a ring signature scheme in a black-box fashion in the standard model. Such an impossibility is highly non-trivial because, to the best of our knowledge, known generic constructions of ring signature scheme are based on public key cryptosystems or in the random oracle model. Technically, we introduce a new cryptographic primitive named indistinguishable multi-designated verifiers signature...
An erf Analog for Discrete Gaussian Sampling
Nicolas Gama, Anand Kumar Narayanan, Ryder LiuLin, Dongze Yue
Foundations
Most of the current lattice-based cryptosystems rely on finding Gaussian Samples from a lattice that are close to a given target. To that end, two popular distributions have been historically defined and studied: the Rounded Gaussian distribution and the Discrete Gaussian distribution.
The first one is nearly trivial to sample: simply round the coordinates of continuous Gaussian samples to their nearest integer. Unfortunately, the security of resulting cryptosystems are not as well...
Proof-Carrying Data from Multi-folding Schemes
Zibo Zhou, Zongyang Zhang, Jin Dong
Foundations
Proof-carrying data (PCD) is a powerful cryptographic primitive that allows mutually distrustful parties to perform distributed computation defined on directed acyclic graphs in an efficiently verifiable manner. Important efficiency parameters include prover's cost at each step and the recursion overhead that measures the additional cost apart from proving the computation.
In this paper, we construct a PCD scheme having the smallest prover's cost and recursion overhead in the literature....
Key-Agreement with Perfect Completeness from Random Oracles
Noam Mazor
Foundations
In the Random Oracle Model (ROM) all parties have oracle access to a common random function, and the parties are limited in the number of queries they can make to the oracle. The Merkle’s Puzzles protocol, introduced by Merkle [CACM ’78], is a key-agreement protocol in the ROM with a quadratic gap between the query complexity of the honest parties and the eavesdropper. This quadratic gap is known to be optimal, by the works of Impagliazzo and Rudich [STOC ’89] and Barak and Mahmoody [Crypto...
Ordering Transactions with Bounded Unfairness: Definitions, Complexity and Constructions
Aggelos Kiayias, Nikos Leonardos, Yu Shen
Foundations
An important consideration in the context of distributed ledger protocols is fairness in terms of transaction ordering. Recent work [Crypto 2020] revealed a connection of (receiver) order fairness to social choice theory and related impossibility results arising from the Condorcet paradox. As a result of the impossibility, various relaxations of order fairness were proposed in prior works. Given that distributed ledger protocols, especially those processing smart contracts, must serialize...
On the Black-Box Impossibility of Multi-Designated Verifiers Signature Schemes from Ring Signature Schemes
Kyosuke Yamashita, Keisuke Hara
Foundations
From the work by Laguillaumie and Vergnaud in ICICS'04, it has been widely believed that multi-designated verifier signature schemes (MDVS) can be constructed from ring signature schemes in general.
However in this paper, somewhat surprisingly, we prove that it is impossible to construct an MDVS scheme from a ring signature scheme in a black-box sense (in the standard model).
The impossibility stems from the difference between the definitions of unforgeability.
To the best of our...
Automated Analysis of Protocols that use Authenticated Encryption: How Subtle AEAD Differences can impact Protocol Security
Cas Cremers, Alexander Dax, Charlie Jacomme, Mang Zhao
Foundations
Many modern security protocols such as TLS, WPA2, WireGuard, and Signal use a cryptographic primitive called Authenticated Encryption (optionally with Authenticated Data), also known as an AEAD scheme. AEAD is a variant of symmetric encryption that additionally provides authentication. While authentication may seem to be a straightforward additional requirement, it has in fact turned out to be complex: many different security notions for AEADs are still being proposed, and several recent...
Unlocking the lookup singularity with Lasso
Srinath Setty, Justin Thaler, Riad Wahby
Foundations
This paper introduces Lasso, a new family of lookup arguments, which allow an untrusted prover to commit to a vector $a \in \mathbb{F}^m$ and prove that all entries of a reside in some predetermined table $t \in \mathbb{F}^n$. Lasso’s performance characteristics unlock the so-called "lookup singularity". Lasso works with any multilinear polynomial commitment scheme, and provides the following efficiency properties.
For $m$ lookups into a table of size $n$, Lasso’s prover commits to just...
Infinite families of minimal binary codes via Krawtchouk polynomials
Xiaoni Du, René Rodríguez, Hao Wu
Foundations
Linear codes play a crucial role in various fields of engineering and mathematics, including data storage, communication, cryptography, and combinatorics. Minimal linear codes, a subset of linear codes, are particularly essential for designing effective secret sharing schemes. In this paper, we introduce several classes of minimal binary linear codes by carefully selecting appropriate Boolean functions. These functions belong to a renowned class of Boolean functions, the general...
Extension of Shannon's theory of ciphers based on Latin rectangles
Karel BURDA
Foundations
The paper extends Shannon's classical theory of ciphers. Here ciphers are modeled by Latin rectangles and their resistance to brute force attack is assessed through the valence of cryptograms. The valence of a cryptogram is defined as the number of all meaningful messages produced by decrypting the cryptogram with all possible keys. In this paper, the mean cryptogram valence of an arbitrary modern cipher with K keys, N outputs and N inputs, of which M inputs are messages, is derived....
-
« Previous
-
1
- 2
- 3
- ...
- 26
-
Next »
A recent line of research has introduced a systematic approach to explore the complexity of explicit construction problems through the use of meta problems, namely, the range avoidance problem (abbrev. $\textsf{Avoid}$) and the remote point problem (abbrev. $\textsf{RPP}$). The upper and lower bounds for these meta problems provide a unified perspective on the complexity of specific explicit construction problems that were previously studied independently. An interesting question largely...
Hiding countermeasures are the most widely utilized techniques for thwarting side-channel attacks, and their significance has been further emphasized with the advent of Post Quantum Cryptography (PQC) algorithms, owing to the extensive use of vector operations. Commonly, the Fisher-Yates algorithm is adopted in hiding countermeasures with permuted operation for its security and efficiency in implementation, yet the inherently sequential nature of the algorithm imposes limitations on hardware...
Recent advances in SNARK recursion and incrementally-verifiable computation are vast, but most of the efforts seem to be focused on a particular design goal - proving the result of a large computation known completely in advance. There are other possible applications, requiring different design tradeoffs. Particularly interesting direction is a case with a swarm of collaborating provers, communicating over a peer-to-peer network - which requires to also optimize the amount of data...
Modern computing systems predominantly operate on the binary number system that accepts only ‘0’ or ‘1’ as logical values leading to computational homogeneity. But this helps in creating leakage patterns that can be exploited by adversaries to carry out hardware and software-level attacks. Recent research has shown that ternary systems, operating on three logical values (‘0′, ‘1', and ‘z') can surpass binary systems in terms of performance and security. In this paper, we first propose a...
Bulletin boards (BB) are important cryptographic building blocks that, at their core, provide a broadcast channel with memory. BBs are widely used within many security protocols, including secure multi-party computation protocols, e-voting systems, and electronic auctions. Even though the security of protocols crucially depends on the underlying BB, as also highlighted by recent works, the literature on constructing secure BBs is sparse. The so-far only provably secure BBs require trusted...
There are two popular ways to measure computational entropy in cryptography: (HILL) pseudoentropy and (Yao) incompressibility entropy. Both of these computational entropy notions are based on a natural intuition. - A random variable $X$ has $k$ bits of pseudoentropy if there exists a random variable $Y$ that has $k$ bits 'real' entropy and $Y$ is computationally indistinguishable from $X$. - A random variable $X$ has $k$ bits of incompressibility entropy if $X$ cannot be efficiently...
In this work, we propose a simple framework of constructing efficient non-interactive zero-knowledge proof (NIZK) systems for all NP. Compared to the state-of-the-art construction by Groth, Ostrovsky, and Sahai (J. ACM, 2012), our resulting NIZK system reduces the proof size and proving and verification cost without any trade-off, i.e., neither increasing computation cost, CRS size nor resorting to stronger assumptions. Furthermore, we extend our framework to construct a batch argument...
The general quantum approximate optimization algorithm (QAOA) produces approximate solutions for combinatorial optimization problems. The algorithm depends on a positive integer $p$ and the quality of approximation improves as $p$ is increased. In this note, we put some questions about the general QAOA. We also find the recursive QAOA for MaxCut problem is flawed because all quantum gates involved in the algorithm are single qubit gates. No any entangling gate is used, which results in...
Nonlinear feedback shift registers (NFSRs) are used in many stream ciphers as their main building blocks. One security criterion for the design of a stream cipher is to assure its keystream has a long period. To meet this criterion, the NFSR used in a stream cipher must have a long state cycle. Further, to simultaneously avoid equivalent keys, the keystream's period is not compressed compared to the NFSR's state cycle length, which can be guaranteed if the NFSR is observable in the sense...
We show the following unconditional results on quantum commitments in two related yet different models: 1. We revisit the notion of quantum auxiliary-input commitments introduced by Chailloux, Kerenidis, and Rosgen (Comput. Complex. 2016) where both the committer and receiver take the same quantum state, which is determined by the security parameter, as quantum auxiliary inputs. We show that computationally-hiding and statistically-binding quantum auxiliary-input commitments exist...
Quantum no-cloning theorem gives rise to the intriguing possibility of quantum copy protection where we encode a program in a quantum state such that a user in possession of $k$ such states cannot create $k+1$ working copies. Introduced by Aaronson (CCC'09) over a decade ago, copy protection has proven to be notoriously hard to achieve. In this work, we construct public-key encryption and functional encryption schemes whose secret keys are copy-protected against unbounded collusions in...
We extend the known pseudorandomness of Ring-LWE to be based on lattices that do not correspond to any ideal of any order in the underlying number field. In earlier works of Lyubashevsky et al (EUROCRYPT 2010) and Peikert et al (STOC 2017), the hardness of RLWE was based on ideal lattices of ring of integers of number fields, which are known to be Dedekind domains. While these works extended Regev's (STOC 2005) quantum polynomial-time reduction for LWE, thus allowing more efficient and more...
By leveraging the no-cloning principle of quantum mechanics, unclonable cryptography enables us to achieve novel cryptographic protocols that are otherwise impossible classically. Two most notable examples of unclonable cryptography are quantum copy-protection and unclonable encryption. Most known constructions rely on the quantum random oracle model (as opposed to the plain model), in which all parties have access in superposition to a powerful random oracle. Despite receiving a lot of...
In their seminal work, Ishai, Kushilevitz, Ostrovsky, and Sahai (STOC`07) presented the MPC-in-the-Head paradigm, which shows how to design Zero-Knowledge Proofs (ZKPs) from secure Multi-Party Computation (MPC) protocols. This paradigm has since then revolutionized and modularized the design of efficient ZKP systems, with far-reaching applications beyond ZKPs. However, to the best of our knowledge, all previous instantiations relied on fully-secure MPC protocols, and have not been able to...
We build the first unleveled fully homomorphic signature scheme in the standard model. Our scheme is not constrained by any a-priori bound on the depth of the functions that can be homomorphically evaluated, and relies on subexponentially-secure indistinguishability obfuscation, fully-homomorphic encryption and a non-interactive zero-knowledge (NIZK) proof system with composable zero-knowledge. Our scheme is also the first to satisfy the strong security notion of context-hiding for an...
Algorithm hardness can be described by 5 categories: hardness in computation, in sequential computation, in memory, in energy consumption (or bandwidth), in code size. Similarly, hardness can be a concern for solving or for verifying, depending on the context, and can depend on a secret trapdoor or be universally hard. Two main lines of research investigated such problems: cryptographic puzzles, that gained popularity thanks to blockchain consensus systems (where solving must be moderately...
Secure computation enables mutually distrusting parties to jointly compute a function on their secret inputs, while revealing nothing beyond the function output. A long-running challenge is understanding the required communication complexity of such protocols---in particular, when communication can be sublinear in the circuit representation size of the desired function. Significant advances have been made affirmatively answering this question within the two-party setting, based on a...
Lasso (Setty, Thaler, Wahby, ePrint 2023/1216) is a recent lookup argument that ensures that the prover cryptographically commits to only "small" values. This note describes BabySpartan, a SNARK for a large class of constraint systems that achieves the same property. The SNARK is a simple combination of SuperSpartan and Lasso. The specific class of constraint systems supported is a generalization of so-called Plonkish constraint systems (and a special case of customizable constraint systems...
We explore a new pathway to designing unclonable cryptographic primitives. We propose a new notion called unclonable puncturable obfuscation (UPO) and study its implications for unclonable cryptography. Using UPO, we present modular (and in some cases, arguably, simple) constructions of many primitives in unclonable cryptography, including, public-key quantum money, quantum copy-protection for many classes of functionalities, unclonable encryption, and single-decryption encryption....
The notion of ``efficiently testable circuits'' (ETC) was recently put forward by Baig et al.~(ITCS'23). Informally, an ETC compiler takes as input any Boolean circuit $C$ and outputs a circuit/inputs tuple $(C',\mathbb{T})$ where (completeness) $C'$ is functionally equivalent to $C$ and (security) if $C'$ is tampered in some restricted way, then this can be detected as $C'$ will err on at least one input in the small test set $\mathbb{T}$. The compiler of Baig et al. detects tampering...
We prove a tight parallel repetition theorem for $3$-message computationally-secure quantum interactive protocols between an efficient challenger and an efficient adversary. We also prove under plausible assumptions that the security of $4$-message computationally secure protocols does not generally decrease under parallel repetition. These mirror the classical results of Bellare, Impagliazzo, and Naor [BIN97]. Finally, we prove that all quantum argument systems can be generically compiled...
The Boolean map $\chi_n^{(k)}:\mathbb{F}_{2^k}^n\rightarrow \mathbb{F}_{2^k}^n$, $x\mapsto u$ given by $u_i=x_i+(x_{(i+1)\ \mathrm{mod}\ n}+1)x_{(i+2)\ \mathrm{mod}\ n}$ appears in various permutations as a part of cryptographic schemes such as KECCAK-f, ASCON, Xoodoo, Rasta, and Subterranean (2.0). Schoone and Daemen investigated some important algebraic properties of $\chi_n^{(k)}$ in [IACR Cryptology ePrint Archive 2023/1708]. In particular, they showed that $\chi_n^{(k)}$ is not...
Watermarking generative models consists of planting a statistical signal (watermark) in a model’s output so that it can be later verified that the output was generated by the given model. A strong watermarking scheme satisfies the property that a computationally bounded attacker cannot erase the watermark without causing significant quality degradation. In this paper, we study the (im)possibility of strong watermarking schemes. We prove that, under well-specified and natural assumptions,...
A robust combiner combines many candidates for a cryptographic primitive and generates a new candidate for the same primitive. Its correctness and security hold as long as one of the original candidates satisfies correctness and security. A universal construction is a closely related notion to a robust combiner. A universal construction for a primitive is an explicit construction of the primitive that is correct and secure as long as the primitive exists. It is known that a universal...
In this short note, we present a simplified (but slower) version Clapoti of Clapotis, whose full description will appear later. Let 𝐸/𝔽_𝑞 be an elliptic curve with an effective primitive orientation by a quadratic imaginary order 𝑅 ⊂ End(𝐸). Let 𝔞 be an invertible ideal in 𝑅. Clapoti is a randomized polynomial time algorithm in 𝑂 ((log Δ_𝑅 + log 𝑞)^𝑂(1) ) operations to compute the class group action 𝐸 ↦ 𝐸_𝔞 ≃ 𝐸/𝐸[𝔞].
The Perebor (Russian for “brute-force search”) conjectures, which date back to the 1950s and 1960s are some of the oldest conjectures in complexity theory. The conjectures are a stronger form of the NP ̸ = P conjecture (which they predate) and state that for “meta-complexity” problems, such as the Time-bounded Kolmogorov complexity Problem, and the Minimum Circuit Size Problem, there are no better algorithms than brute force search. In this paper, we disprove the non-uniform version of...
We consider the mainstream model in secure computation known as the bare PKI setup, also as the {bulletin-board PKI}. It allows players to broadcast once and non-interactively before they receive their inputs and start the execution. A bulletin-board PKI is essentially the minimum setup known so far to implement the model known as {messages-authentication}, i.e., when $P$ is forwarded a signed message, it considers it to be issued by $R$ if and only if $R$ signed it. It is known since...
Quantum copy protection, introduced by Aaronson, enables giving out a quantum program-description that cannot be meaningfully duplicated. Despite over a decade of study, copy protection is only known to be possible for a very limited class of programs. As our first contribution, we show how to achieve "best-possible" copy protection for all programs. We do this by introducing quantum state indistinguishability obfuscation (qsiO), a notion of obfuscation for quantum descriptions of...
As NIST is putting the final touches on the standardization of PQC (Post Quantum Cryptography) public key algorithms, it is a racing certainty that peskier cryptographic attacks undeterred by those new PQC algorithms will surface. Such a trend in turn will prompt more follow-up studies of attacks and countermeasures. As things stand, from the attackers’ perspective, one viable form of attack that can be implemented thereupon is the so-called “side-channel attack”. Two best-known...
Private Simultaneous Messages (PSM) is a minimal model of secure computation, where the input players with shared randomness send messages to the output player simultaneously and only once. In this field, finding upper and lower bounds on communication complexity of PSM protocols is important, and in particular, identifying the optimal one where the upper and lower bounds coincide is the ultimate goal. However, up until now, functions for which the optimal communication complexity has been...
We introduce a new notion called ${\cal Q}$-secure pseudorandom isometries (PRI). A pseudorandom isometry is an efficient quantum circuit that maps an $n$-qubit state to an $(n+m)$-qubit state in an isometric manner. In terms of security, we require that the output of a $q$-fold PRI on $\rho$, for $ \rho \in {\cal Q}$, for any polynomial $q$, should be computationally indistinguishable from the output of a $q$-fold Haar isometry on $\rho$. By fine-tuning ${\cal Q}$, we recover many...
Motivated by the fact that broadcast is an expensive, but useful, resource for the realization of multi-party computation protocols (MPC), Cohen, Garay, and Zikas (Eurocrypt 2020), and subsequently Damgård, Magri, Ravi, Siniscalchi and Yakoubov (Crypto 2021), and, Damgård, Ravi, Siniscalchi and Yakoubov (Eurocrypt 2023), focused on 𝘴𝘰-𝘤𝘢𝘭𝘭𝘦𝘥 𝘣𝘳𝘰𝘢𝘥𝘤𝘢𝘴𝘵 𝘰𝘱𝘵𝘪𝘮𝘢𝘭 𝘔𝘗𝘊. In particular, the authors focus on two-round MPC protocols (in the CRS model), and give tight characterizations of which...
It is well-known that Atomic Broadcast (AB) in asynchronous networks requires randomisation and that at most $t < n/3$ out of $n$ players are Byzantine corrupted. This is opposed to synchronous AB which can tolerate $t < n/2$ corruptions and can be deterministic. We show that these requirements can be conceptually separated by constructing an asynchronous AB protocol which tolerates $t < n/2$ corruptions from blackbox use of Common Coin and Reliable Broadcast (RB). We show the power of this...
We study the security of a fundamental family of succinct interactive arguments in the standard model, stemming from the works of Kilian (1992) and Ben-Sasson, Chiesa, and Spooner (``BCS'', 2016). These constructions achieve succinctness by combining probabilistic proofs and vector commitments. Our first result concerns the succinct interactive argument of Kilian, realized with any probabilistically-checkable proof (PCP) and any vector commitment. We establish the tightest known bounds on...
$\mathbb{Z}^n$ is one of the simplest types of lattices, but the computational problems on its rotations, such as $\mathbb{Z}$SVP and $\mathbb{Z}$LIP, have been of great interest in cryptography. Recent advances have been made in building cryptographic primitives based on these problems, as well as in developing new algorithms for solving them. However, the theoretical complexity of $\mathbb{Z}$SVP and $\mathbb{Z}$LIP are still not well understood. In this work, we study the problems on...
We show an explicit construction of an efficiently decodable family of $n$-dimensional lattices whose minimum distances achieve $\Omega(\sqrt{n} / (\log n)^{\varepsilon+o(1)})$ for $\varepsilon>0$. It improves upon the state-of-the-art construction due to Mook-Peikert (IEEE Trans.\ Inf.\ Theory, no. 68(2), 2022) that provides lattices with minimum distances $\Omega(\sqrt{n/ \log n})$. These lattices are construction-D lattices built from a sequence of BCH codes. We show that replacing BCH...
For any prime number $p$, we provide two classes of linear codes with few weights over a $p$-ary alphabet. These codes are based on a well-known generic construction (the defining-set method), stemming on a class of monomials and a class of trinomials over finite fields. The considered monomials are Dembowski-Ostrom monomials $x^{p^{\alpha}+1}$, for a suitable choice of the exponent $\alpha$, so that, when $p>2$ and $n\not\equiv 0 \pmod{4}$, these monomials are planar. We study the...
There has been a recent interest in proposing quantum protocols whose security relies on weaker computational assumptions than their classical counterparts. Importantly to our work, it has been recently shown that public-key encryption (PKE) from one-way functions (OWF) is possible if we consider quantum public keys. Notice that we do not expect classical PKE from OWF given the impossibility results of Impagliazzo and Rudich (STOC'89). However, the distribution of quantum public keys is a...
Parallel repetition refers to a set of valuable techniques used to reduce soundness error of probabilistic proofs while saving on certain efficiency measures. Parallel repetition has been studied for interactive proofs (IPs) and multi-prover interactive proofs (MIPs). In this paper we initiate the study of parallel repetition for probabilistically checkable proofs (PCPs). We show that, perhaps surprisingly, parallel repetition of a PCP can increase soundness error, in fact bringing the...
The Boolean map $\chi_n \colon \mathbb{F}_2^n \to \mathbb{F}_2^n,\ x \mapsto y$ defined by $y_i = x_i + (x_{i+1}+1)x_{i+2}$ (where $i\in \mathbb{Z}/n\mathbb{Z}$) is used in various permutations that are part of cryptographic schemes, e.g., Keccak-f (the SHA-3-permutation), ASCON (the winner of the NIST Lightweight competition), Xoodoo, Rasta and Subterranean (2.0). In this paper, we study various algebraic properties of this map. We consider $\chi_n$ (through vectorial isomorphism) as a...
Non-interactive zero-knowledge (NIZK) proof systems are a cornerstone of modern cryptography, but their security has received little attention in the quantum settings. Motivated by improving our understanding of this fundamental primitive against quantum adversaries, we propose a new definition of security against quantum adversary. Specifically, we define the notion of quantum simulation soundness (SS-NIZK), that allows the adversary to access the simulator in superposition. We show a...
The Crossbred algorithm is one of the algorithms for solving a system of polynomial equations, proposed by Joux and Vitse in 2017. It has been implemented in Fukuoka MQ challenge, which is related to the security of multivariate crytography, and holds several records. A framework for estimating the complexity has already been provided by Chen et al. in 2017. However, it is generally unknown which parameters are actually available. This paper investigates how to select available parameters...
One of the founding results of lattice based cryptography is a quantum reduction from the Short Integer Solution problem to the Learning with Errors problem introduced by Regev. It has recently been pointed out by Chen, Liu and Zhandry that this reduction can be made more powerful by replacing the learning with errors problem with a quantum equivalent, where the errors are given in quantum superposition. In the context of codes, this can be adapted to a reduction from finding short...
An $(n, t)$-Non-Interactive Verifiable Secret Sharing (NI-VSS) scheme allows a dealer to share a secret among $n$ parties, s.t. all the parties can verify the validity of their shares and only a set of them, i.e., more than $t$, can access the secret. In this paper, we present $\Pi$, as a unified framework for building NI-VSS schemes in the majority honest setting. Notably, $\Pi$ does not rely on homomorphic commitments; instead requires a Random Oracle (RO) and any commitment scheme that...
Suppose a prover, in possession of a large body of valuable evidence, wants to quickly convince a verifier by presenting only a small portion of the evidence. We define an Approximate Lower Bound Argument, or ALBA, which allows the prover to do just that: to succinctly prove knowledge of a large number of elements satisfying a predicate (or, more generally, elements of a sufficient total weight when a predicate is generalized to a weight function). The argument is approximate because...
We present a general framework for polynomial-time lattice Gaussian sampling. It revolves around a systematic study of the discrete Gaussian measure and its samplers under extensions of lattices; we first show that given lattices $\Lambda'\subset \Lambda$ we can sample efficiently in $\Lambda$ if we know how to do so in $\Lambda'$ and the quotient $\Lambda/\Lambda'$, \emph{regardless} of the primitivity of $\Lambda'$. As a direct application, we...
Proof-carrying data (PCD) is a powerful cryptographic primitive that allows mutually distrustful parties to perform distributed computation in an efficiently verifiable manner. Real-world deployments of PCD have sparked keen interest within the applied community and industry. Known constructions of PCD are obtained by recursively-composing SNARKs or related primitives. Unfortunately, known security analyses incur expensive blowups, which practitioners have disregarded as the analyses...
In this work, we consider the problem of secure key leasing, also known as revocable cryptography (Agarwal et. al. Eurocrypt' 23, Ananth et. al. TCC' 23), as a strengthened security notion of its predecessor put forward in Ananth et. al. Eurocrypt' 21. This problem aims to leverage unclonable nature of quantum information to allow a lessor to lease a quantum key with reusability for evaluating a classical functionality. Later, the lessor can request the lessee to provably delete the key and...
The algebraic degree of a vectorial Boolean function is one of the main parameters driving the cost of its hardware implementation. Thus, finding decompositions of functions into sequences of functions of lower algebraic degrees has been explored to reduce the cost of implementations. In this paper, we consider such decompositions of permutations over $\mathbb{F}_{2^n}$. We prove the existence of decompositions using quadratic and linear power permutations for all permutations when...
One-way functions are central to classical cryptography. They are both necessary for the existence of non-trivial classical cryptosystems, and sufficient to realize meaningful primitives including commitments, pseudorandom generators and digital signatures. At the same time, a mounting body of evidence suggests that assumptions even weaker than one-way functions may suffice for many cryptographic tasks of interest in a quantum world, including bit commitments and secure multi-party...
Goldwasser-Kalai-Rothblum protocol (GKR) for layered circuits is a sumcheck-based argument of knowledge for layered circuits, running in $\sim 2\mu \ell$ amount of rounds, where $\ell$ is the amount of layers and $\mu$ is the average layer logsize. For a layer $i$ of size $2^{\mu_i}$ the main work consists of running a sumcheck protocol of the form \[\underset{x,y}{\sum} \text{Add}_i(x,y,z)(f(x)+f(y)) + \text{Mul}_i(x,y,z)f(x)f(y)\] over a $2^{2\mu_i}$-dimensional cube, where...
Cryptographic applications often require proving statements about hidden secrets satisfying certain circuit relations. Moreover, these proofs must often be generated obliviously, i.e., without knowledge of the secret. This work presents a new technique called --- FRI on hidden values --- for efficiently proving such statements. This technique enables a polynomial commitment scheme for values hidden inside linearly homomorphic primitives, such as linearly homomorphic encryption, linearly...
The Unitary Synthesis Problem (Aaronson-Kuperberg 2007) asks whether any $n$-qubit unitary $U$ can be implemented by an efficient quantum algorithm $A$ augmented with an oracle that computes an arbitrary Boolean function $f$. In other words, can the task of implementing any unitary be efficiently reduced to the task of implementing any Boolean function? In this work, we prove a one-query lower bound for unitary synthesis. We show that there exist unitaries $U$ such that no...
The generic-group model (GGM) and the algebraic-group model (AGM) have been exceptionally successful in proving the security of many classical and modern cryptosystems. These models, however, come with standard-model uninstantiability results, raising the question whether the schemes analyzed under them can be based on firmer standard-model footing. We formulate the uber-knowledge (UK) assumption, a standard-model assumption that naturally extends the uber-assumption family to...
Consider the recently introduced notion of \emph{probabilistic time-bounded Kolmogorov Complexity}, pK^t (Goldberg et al, CCC'22), and let MpK^tP denote the language of pairs (x,k) such that pK^t(x) \leq k. We show the equivalence of the following: - MpK^{poly}P is (mildly) hard-on-average w.r.t. \emph{any} samplable distribution D; - MpK^{poly}P is (mildly) hard-on-average w.r.t. the \emph{uniform} distribution; - Existence of one-way functions. As far as we know, this...
We present new lower and upper bounds on the number of communication rounds required for asynchronous Crusader Agreement (CA) and Binding Crusader Agreement (BCA), two primitives that are used for solving binary consensus. We show results for the information theoretic and authenticated settings. In doing so, we present a generic model for proving round complexity lower bounds in the asynchronous setting. In some settings, our attempts to prove lower bounds on round complexity fail....
The study of garbling arithmetic circuits is initiated by Applebaum, Ishai, and Kushilevitz [FOCS'11], which can be naturally extended to mixed circuits. The basis of mixed circuits includes Boolean operations, arithmetic operations over a large ring and bit-decomposition that converts an arithmetic value to its bit representation. We construct efficient garbling schemes for mixed circuits. In the random oracle model, we construct two garbling schemes: $\bullet$ The first scheme...
We give a new approach for finding large smooth twins. Those twins whose sum is a prime are of interest in the parameter setup of certain isogeny-based cryptosystems such as SQIsign. The approach to find such twins is to find two polynomials in $\mathbb{Q}[x]$ that split into a product of small degree factors and differ by $1$. Then evaluate them on a particular smooth integer. This was first explored by Costello, Meyer and Naehrig at EUROCRYPT'21 using polynomials that split completely into...
Non-malleable cryptography, proposed by Dolev, Dwork, and Naor (SICOMP '00), has numerous applications in protocol composition. In the context of proofs, it guarantees that an adversary who receives a proof cannot maul it into another valid proof. However, non-malleable cryptography (particularly in the non-interactive setting) suffers from an important limitation: An attacker can always copy the proof and resubmit it to another verifier (or even multiple verifiers). In this work, we...
In this paper a reduced set of submatrices for a faster evaluation of the MDS property of a circulant matrix, with entries that are powers of two, is proposed. A proposition is made that under the condition that all entries of a t × t circulant matrix are powers of 2, it is sufficient to check only its 2x2 submatrices in order to evaluate the MDS property in a prime field. Although there is no theoretical proof to support this proposition at this point, the experimental results conducted on...
We give a semantic characterization of leakage-freeness through timing side-channels for Jasmin programs. Our characterization also covers probabilistic Jasmin programs that are not constant-time. In addition, we provide a characterization in terms of probabilistic relational Hoare logic and prove equivalence of both definitions. We also prove that our new characterizations are compositional. Finally, we relate new definitions to the existing ones from prior work which only apply to...
In 2022, Moriya, Onuki, Aikawa, and Takagi proposed a new framework named generalized Montgomery coordinates to treat one-coordinate type formulas to compute isogenies. This framework generalizes some already known one-coordinate type formulas of elliptic curves. Their result shows that a formula to compute image points under isogenies is unique in the framework of generalized Montogmery coordinates; however, a formula to compute image curves is not unique. Therefore, we have a question:...
In the algebraic group model (AGM), an adversary has to return with each group element a linear representation with respect to input group elements. In many groups, it is easy to sample group elements obliviously without knowing such linear representations. Since the AGM does not model this, it can be used to prove the security of spurious knowledge assumptions. We show several well-known zk-SNARKs use such assumptions. We propose AGM with oblivious sampling (AGMOS), an AGM variant where...
We provide two improvements to Regev's recent quantum factoring algorithm (arXiv:2308.06572), addressing its space efficiency and its noise-tolerance. Our first contribution is to improve the quantum space efficiency of Regev's algorithm while keeping the circuit size the same. Our main result constructs a quantum factoring circuit using $O(n \log n)$ qubits and $O(n^{3/2} \log n)$ gates. We achieve the best of Shor and Regev (upto a logarithmic factor in the space complexity): on...
A succinct non-interactive argument (SNARG) is called holographic if the verifier runs in time sub-linear in the input length when given oracle access to an encoding of the input. We present holographic SNARGs for P and Batch-NP under the learning with errors (LWE) assumption. Our holographic SNARG for P has a verifier that runs in time $\mathsf{poly}(\lambda, \log T, \log n)$ for $T$-time computations and $n$-bit inputs ($\lambda$ is the security parameter), while our holographic SNARG for...
The learning with errors problem (LWE) is one of the most important building blocks for post-quantum cryptography. To better understand the quantum hardness of LWE, it is crucial to explore quantum variants of LWE, show quantum algorithms for those variants, or prove they are as hard as standard LWE. To this end, Chen, Liu, and Zhandry [Eurocrypt 2022] define the $\sf{S|LWE\rangle}$ problem, which encodes the error of LWE samples into quantum amplitudes. They then show efficient quantum...
Ethereum is undergoing significant changes to its architecture as it evolves. These changes include its switch to PoS consensus and the introduction of significant infrastructural changes that do not require a change to the core protocol, but that fundamentally affect the way users interact with the network. These changes represent an evolution toward a more modular architecture, in which there exists new exogenous vectors for centralization. This paper builds on previous studies of...
Anonymous transfer, recently introduced by Agrikola, Couteau and Maier [ACM22] (TCC '22), allows a sender to leak a message anonymously by participating in a public non-anonymous discussion where everyone knows who said what. This opens up the intriguing possibility of using cryptography to ensure strong anonymity guarantees in a seemingly non-anonymous environment. The work of [ACM22] presented a lower bound on anonymous transfer, ruling out constructions with strong anonymity guarantees...
The intuitions behind succinct proof systems are often difficult to separate from some of the deep cryptographic techniques that are used in their construction. In this paper, we show that, using some simple abstractions, a number of commonly-used tools used in the construction of succinct proof systems may be viewed as basic consequences of linear algebra over finite fields. We introduce notation which considerably simplifies these constructions and slowly build a toolkit of useful...
We introduce a new variant of malicious obfuscation. Our formalism is incomparable to the existing definitions by Canetti and Varia (TCC 2010), Canetti et al. (EUROCRYPT 2022) and Badrinarayanan et al. (ASIACRYPT 2016). We show that this concept is natural and applicable to obfuscation-as-a-service platforms. We next define a new notion called auditable obfuscation which provides security against malicious obfuscation. Finally, we construct a proof of concept of the developed notions based...
We study verifiable outsourcing of computation in a model where the verifier has black-box access to the function being computed. We introduce the problem of oracle-aided batch verification of computation (OBVC) for a function class $\mathcal{F}$. This allows a verifier to efficiently verify the correctness of any $f \in \mathcal{F}$ evaluated on a batch of $n$ instances $x_1, \ldots, x_n$, while only making $\lambda$ calls to an oracle for $f$ (along with $O(n \lambda)$ calls to...
An hard homogeneous space (HHS) is a finite group acting on a set with the group action being hard to invert and the set lacking any algebraic structure. As such HHS could potentially replace finite groups where the discrete logarithm is hard for building cryptographic primitives and protocols in a post-quantum world. Threshold HHS-based primitives typically require parties to compute the group action of a secret-shared input on a public set element. On one hand this could be done...
Vectorial dual-bent functions have recently attracted some researchers' interest as they play a significant role in constructing partial difference sets, association schemes, bent partitions and linear codes. In this paper, we further study vectorial dual-bent functions $F: V_{n}^{(p)}\rightarrow V_{m}^{(p)}$, where $2\leq m \leq \frac{n}{2}$, $V_{n}^{(p)}$ denotes an $n$-dimensional vector space over the prime field $\mathbb{F}_{p}$. We give new characterizations of certain vectorial...
A central result in the theory of Cryptography, by Hastad, Imagliazzo, Luby and Levin [SICOMP’99], demonstrates that the existence one-way functions (OWF) implies the existence of pseudo-random generators (PRGs). Despite the fundamental importance of this result, and several elegant improvements/simplifications, analyses of constructions of PRGs from OWFs remain complex (both conceptually and technically). Our goal is to provide a construction of a PRG from OWFs with a simple proof of...
Sponge paradigm, used in the design of SHA-3, is an alternative hashing technique to the popular Merkle-Damgård paradigm. We revisit the problem of finding $B$-block-long collisions in sponge hash functions in the auxiliary-input random permutation model, in which an attacker gets a piece of $S$-bit advice about the random permutation and makes $T$ (forward or inverse) oracle queries to the random permutation. Recently, significant progress has been made in the Merkle-Damgård setting and...
The notion of functional re-encryption security (funcCPA) for public-key encryption schemes was recently introduced by Akavia et al. (TCC'22), in the context of homomorphic encryption. This notion lies in between CPA security and CCA security: we give the attacker a functional re-encryption oracle instead of the decryption oracle of CCA security. This oracle takes a ciphertext $c$ and a function $f$, and returns fresh encryption of the output of $f$ applied to the decryption of $c$; in...
We propose a new notion of knowledge soundness, denoted rogue-instance security, for interactive and non-interactive batch knowledge proofs. Our notion, inspired by the standard notion of rogue-key security for multi-signature schemes, considers a setting in which a malicious prover is provided with an honestly-generated instance $x_1$, and may then be able to maliciously generate related "rogue" instances $x_2,\ldots,x_k$ for convincing a verifier in a batch knowledge proof of corresponding...
This paper mainly studies an open problem in modern cryptography, namely the Ring-SIS reduction problem. In order to prove the hardness of the Ring-SIS problem, this paper introduces the concepts of the one-dimensional SIS problem, the Ring-SIS$|_{x=0}$ problem, and the variant knapsack problem. The equivalence relations between the three are first established, on which the connection between the Ring-SIS$|_{x=0}$ problem and the Ring-SIS problem is built. This proves that the hardness of...
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...
This paper offers a mathematical introduction to fully homomorphic encryption, a concept that enables computation on encrypted data. We trace the historical development of FHE, describe Fully Homomorphic Encryption over the Torus (TFHE) and how it performs certain mathematical operations, and explore bootstrapping and the possibility for adjusting computational depth. This paper equips readers with a brief understanding of FHE's evolution and the essential mechanisms facilitating practical...
Homomorphic encryption is a central object in modern cryptography, with far-reaching applications. Constructions supporting homomorphic evaluation of arbitrary Boolean circuits have been known for over a decade, based on standard lattice assumptions. However, these constructions are leveled, meaning that they only support circuits up to some a-priori bounded depth. These leveled constructions can be bootstrapped into fully homomorphic ones, but this requires additional circular security...
Latin squares are a classical and well-studied topic of discrete mathematics, and recently Takeuti and Adachi (IACR ePrint, 2023) proposed (2,n)-threshold secret sharing based on mutually orthogonal Latin squares (MOLS). Hence efficient constructions of as large sets of MOLS as possible are also important from practical viewpoints. In this letter, we determine the maximum number of MOLS among a known class of Latin squares defined by weighted sums. We also mention some known property of...
In the context of circuits leaking the internal state, there are various models to analyze what the adversary can see, like the $p$-random probing model in which the adversary can see the value of each wire with probability $p$. In this model, for a fixed $p$, it's possible to reach an arbitrary security by 'expanding' a stateless circuit via iterated compilation, reaching a security of $2^{-\kappa}$ with a polynomial size in $\kappa$. The existing proofs of the expansion work by first...
In Crypto 2019, Zhandry showed how to define compressed oracles, which record quantum superposition queries to the quantum random oracle. In this paper, we extend Zhandry's compressed oracle technique to non-uniformly distributed functions with independently sampled outputs. We define two quantum oracles $\mathsf{CStO}_D$ and $\mathsf{CPhsO}_D$, which are indistinguishable to the non-uniform quantum random oracle where quantum access is given to a random function $H$ whose images $H(x)$...
The presumed hardness of the Shortest Vector Problem for ideal lattices (Ideal-SVP) has been a fruitful assumption to understand other assumptions on algebraic lattices and as a security foundation of cryptosystems. Gentry [CRYPTO'10] proved that Ideal-SVP enjoys a worst-case to average-case reduction, where the average-case distribution is the uniform distribution over the set of inverses of prime ideals of small algebraic norm (below $d^{O(d)}$ for cyclotomic fields, here $d$ refers to...
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...
Constructing key-agreement protocols in the random oracle model (ROM) is a viable method to assess the feasibility of developing public-key cryptography within Minicrypt. Unfortunately, as shown by Impagliazzo and Rudich (STOC 1989) and Barak and Mahmoody (Crypto 2009), such protocols can only guarantee limited security: any $\ell$-query protocol can be attacked by an $O(\ell^2)$-query adversary. This quadratic gap matches the key-agreement protocol proposed by Merkle (CACM 78), known as ...
While cryptographic protocols are often analyzed in isolation, they are typically deployed within a stack of protocols, where each layer relies on the security guarantees provided by the protocol layer below it, and in turn provides its own security functionality to the layer above. Formally analyzing the whole stack in one go is infeasible even for semi-automated verification tools, and impossible for pen-and-paper proofs. The DY$^\star$ protocol verification framework offers a modular and...
In lattice-based Homomorphic Encryption (HE) schemes, the key-switching procedure is a core building block of non-linear operations but also a major performance bottleneck. The computational complexity of the operation is primarily determined by the so-called gadget decomposition, which transforms a ciphertext entry into a tuple of small polynomials before being multiplied with the corresponding evaluation key. However, the previous studies such as Halevi et al. (CT-RSA 2019) and Han and...
Fine-grained cryptography is constructing cryptosystems in a setting where an adversary’s resource is a-prior bounded and an honest party has less resource than an adversary. Currently, only simple form of encryption schemes, such as secret-key and public-key encryption, are constructed in this setting. In this paper, we enrich the available tools in fine-grained cryptography by proposing the first fine-grained secure attribute-based encryption (ABE) scheme. Our construction is adaptively...
In this paper, we show that it is impossible to construct a public key encryption scheme (PKE) from a ring signature scheme in a black-box fashion in the standard model. Such an impossibility is highly non-trivial because, to the best of our knowledge, known generic constructions of ring signature scheme are based on public key cryptosystems or in the random oracle model. Technically, we introduce a new cryptographic primitive named indistinguishable multi-designated verifiers signature...
Most of the current lattice-based cryptosystems rely on finding Gaussian Samples from a lattice that are close to a given target. To that end, two popular distributions have been historically defined and studied: the Rounded Gaussian distribution and the Discrete Gaussian distribution. The first one is nearly trivial to sample: simply round the coordinates of continuous Gaussian samples to their nearest integer. Unfortunately, the security of resulting cryptosystems are not as well...
Proof-carrying data (PCD) is a powerful cryptographic primitive that allows mutually distrustful parties to perform distributed computation defined on directed acyclic graphs in an efficiently verifiable manner. Important efficiency parameters include prover's cost at each step and the recursion overhead that measures the additional cost apart from proving the computation. In this paper, we construct a PCD scheme having the smallest prover's cost and recursion overhead in the literature....
In the Random Oracle Model (ROM) all parties have oracle access to a common random function, and the parties are limited in the number of queries they can make to the oracle. The Merkle’s Puzzles protocol, introduced by Merkle [CACM ’78], is a key-agreement protocol in the ROM with a quadratic gap between the query complexity of the honest parties and the eavesdropper. This quadratic gap is known to be optimal, by the works of Impagliazzo and Rudich [STOC ’89] and Barak and Mahmoody [Crypto...
An important consideration in the context of distributed ledger protocols is fairness in terms of transaction ordering. Recent work [Crypto 2020] revealed a connection of (receiver) order fairness to social choice theory and related impossibility results arising from the Condorcet paradox. As a result of the impossibility, various relaxations of order fairness were proposed in prior works. Given that distributed ledger protocols, especially those processing smart contracts, must serialize...
From the work by Laguillaumie and Vergnaud in ICICS'04, it has been widely believed that multi-designated verifier signature schemes (MDVS) can be constructed from ring signature schemes in general. However in this paper, somewhat surprisingly, we prove that it is impossible to construct an MDVS scheme from a ring signature scheme in a black-box sense (in the standard model). The impossibility stems from the difference between the definitions of unforgeability. To the best of our...
Many modern security protocols such as TLS, WPA2, WireGuard, and Signal use a cryptographic primitive called Authenticated Encryption (optionally with Authenticated Data), also known as an AEAD scheme. AEAD is a variant of symmetric encryption that additionally provides authentication. While authentication may seem to be a straightforward additional requirement, it has in fact turned out to be complex: many different security notions for AEADs are still being proposed, and several recent...
This paper introduces Lasso, a new family of lookup arguments, which allow an untrusted prover to commit to a vector $a \in \mathbb{F}^m$ and prove that all entries of a reside in some predetermined table $t \in \mathbb{F}^n$. Lasso’s performance characteristics unlock the so-called "lookup singularity". Lasso works with any multilinear polynomial commitment scheme, and provides the following efficiency properties. For $m$ lookups into a table of size $n$, Lasso’s prover commits to just...
Linear codes play a crucial role in various fields of engineering and mathematics, including data storage, communication, cryptography, and combinatorics. Minimal linear codes, a subset of linear codes, are particularly essential for designing effective secret sharing schemes. In this paper, we introduce several classes of minimal binary linear codes by carefully selecting appropriate Boolean functions. These functions belong to a renowned class of Boolean functions, the general...
The paper extends Shannon's classical theory of ciphers. Here ciphers are modeled by Latin rectangles and their resistance to brute force attack is assessed through the valence of cryptograms. The valence of a cryptogram is defined as the number of all meaningful messages produced by decrypting the cryptogram with all possible keys. In this paper, the mean cryptogram valence of an arbitrary modern cipher with K keys, N outputs and N inputs, of which M inputs are messages, is derived....
- « Previous
- 1
- 2
- 3
- ...
- 26
- Next »
