Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top

2022 | Book

Multitarget Decryption Failure Attacks and Their Application to Saber and Kyber Read chapter Read first chapter

Public-Key Cryptography – PKC 2022

25th IACR International Conference on Practice and Theory of Public-Key Cryptography, Virtual Event, March 8–11, 2022, Proceedings, Part I

Editors: Dr. Goichiro Hanaoka, Junji Shikata, Yohei Watanabe

Publisher: Springer International Publishing

Book Series : Lecture Notes in Computer Science

Part of: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Login to get access
insite
SEARCH

About this book

The two-volume proceedings set LNCS 13177 and 13178 constitutes the proceedings of the 25th IACR International Conference on Practice and Theory of Public Key Cryptography, PKC 2022, which took place virtually during March 7-11, 2022. The conference was originally planned to take place in Yokohama, Japan, but had to change to an online format due to the COVID-19 pandemic.

The 40 papers included in these proceedings were carefully reviewed and selected from 137 submissions. They focus on all aspects of public-key cryptography, covering cryptanalysis; MPC and secret sharing; cryptographic protocols; tools; SNARKs and NIZKs; key exchange; theory; encryption; and signatures.

Table of Contents

Frontmatter

Cryptanalysis

Frontmatter
Multitarget Decryption Failure Attacks and Their Application to Saber and Kyber
Abstract
Many lattice-based encryption schemes are subject to a very small probability of decryption failures. It has been shown that an adversary can efficiently recover the secret key using a number of ciphertexts that cause such a decryption failure. In PKC 2019, D’Anvers et al. introduced ‘failure boosting’, a technique to speed up the search for decryption failures. In this work we first improve the state-of-the-art multitarget failure boosting attacks. We then improve the cost calculation of failure boosting and extend the applicability of these calculations to permit cost calculations of real-world schemes. Using our newly developed methodologies we determine the multitarget decryption failure attack cost for all parameter sets of Saber and Kyber, showing among others that the quantum security of Saber can theoretically be reduced from 172 bits to 145 bits in specific circumstances. We then discuss the applicability of decryption failure attacks in real-world scenarios, showing that an attack might not be practical to execute.
Jan-Pieter D’Anvers, Senne Batsleer
Post-quantum Security of Plain OAEP Transform
Abstract
In this paper, we show that OAEP transform is indistinguishable under chosen ciphertext attack in the quantum random oracle model if the underlying trapdoor permutation is quantum partial-domain one-way. The existing post-quantum security of OAEP (TCC 2016-B [14]) requires a modification to the OAEP transform using an extra hash function. We prove the security of the OAEP transform without any modification and this answers an open question in one of the finalists of NIST competition, NTRU submission [6], affirmatively.
Ehsan Ebrahimi
On the Security of OSIDH
Abstract
The Oriented Supersingular Isogeny Diffie–Hellman is a post-quantum key exchange scheme recently introduced by Colò and Kohel. It is based on the group action of an ideal class group of a quadratic imaginary order on a subset of supersingular elliptic curves, and in this sense it can be viewed as a generalization of the popular isogeny based key exchange CSIDH. From an algorithmic standpoint, however, OSIDH is quite different from CSIDH. In a sense, OSIDH uses class groups which are more structured than in CSIDH, creating a potential weakness that was already recognized by Colò and Kohel. To circumvent the weakness, they proposed an ingenious way to realize a key exchange by exchanging partial information on how the class group acts in the neighborhood of the public curves, and conjectured that this additional information would not impact security.
In this work we revisit the security of OSIDH by presenting a new attack, building upon previous work of Onuki. Our attack has exponential complexity, but it practically breaks Colò and Kohel’s parameters unlike Onuki’s attack. We also discuss countermeasures to our attack, and analyze their impact on OSIDH, both from an efficiency and a functionality point of view.
Pierrick Dartois, Luca De Feo
Time-Memory Tradeoffs for Large-Weight Syndrome Decoding in Ternary Codes
Abstract
We propose new algorithms for solving a class of large-weight syndrome decoding problems in random ternary codes. This is the main generic problem underlying the security of the recent Wave signature scheme (Debris-Alazard et al. 2019), and it has so far received limited attention. At SAC 2019 Bricout et al. proposed a reduction to a binary subset sum problem requiring many solutions, and used it to obtain the fastest known algorithm. However —as is often the case in the coding theory literature— its memory cost is proportional to its time cost, which makes it unattractive in most applications.
In this work we propose a range of memory-efficient algorithms for this problem, which describe a near-continuous time-memory tradeoff curve. Those are obtained by using the same reduction as Bricout et al. and carefully instantiating the derived subset sum problem with exhaustive-search algorithms from the literature, in particular dissection (Dinur et al. 2012) and dissection in tree (Dinur 2019). We also spend significant effort adapting those algorithms to decrease their granularity, thereby allowing them to be smoothly used in a syndrome decoding context when not all the solutions to the subset sum problem are required. For a proposed parameter set for Wave, one of our best instantiations is estimated to cost \(2^{177}\) bit operations and requiring \(2^{88.5}\) bits of storage, while we estimate this to be \(2^{152}\) and \(2^{144}\) for the best algorithm from Bricout et al..
Pierre Karpman, Charlotte Lefevre
Syndrome Decoding Estimator
Abstract
The selection of secure parameter sets requires an estimation of the attack cost to break the respective cryptographic scheme instantiated under these parameters. The current NIST standardization process for post-quantum schemes makes this an urgent task, especially considering the announcement to select final candidates by the end of 2021. For code-based schemes, recent estimates seemed to contradict the claimed security of most proposals, leading to a certain doubt about the correctness of those estimates. Furthermore, none of the available estimates include most recent algorithmic improvements on decoding linear codes, which are based on information set decoding (ISD) in combination with nearest neighbor search. In this work we observe that all major ISD improvements are build on nearest neighbor search, explicitly or implicitly. This allows us to derive a framework from which we obtain practical variants of all relevant ISD algorithms including the most recent improvements. We derive formulas for the practical attack costs and make those online available in an easy to use estimator tool written in python and C. Eventually, we provide classical and quantum estimates for the bit security of all parameter sets of current code-based NIST proposals.
Andre Esser, Emanuele Bellini
On the Isogeny Problem with Torsion Point Information
Abstract
It has recently been rigorously proven (and was previously known under certain heuristics) that the general supersingular isogeny problem reduces to the supersingular endomorphism ring computation problem. However, in order to attack SIDH-type schemes, one requires a particular isogeny which is usually not returned by the general reduction. At Asiacrypt 2016, Galbraith, Petit, Shani and Ti presented a polynomial-time reduction of the problem of finding the secret isogeny in SIDH to the problem of computing the endomorphism ring of a supersingular elliptic curve. Their method exploits the fact that secret isogenies in SIDH are of degree approximately \(p^{1/2}\). The method does not extend to other SIDH-type schemes, where secret isogenies of larger degree are used and this condition is not fulfilled.
We present a more general reduction algorithm that generalises to all SIDH-type schemes. The main idea of our algorithm is to exploit available torsion point images together with the KLPT algorithm to obtain a linear system of equations over a certain residue class ring. We show that this system will have a unique solution that can be lifted to the integers if some mild conditions on the parameters are satisfied. This lift then yields the secret isogeny. One consequence of this work is that the choice of the prime p in B-SIDH is tight.
Tako Boris Fouotsa, Péter Kutas, Simon-Philipp Merz, Yan Bo Ti

MPC and Secret Sharing

Frontmatter
Reusable Two-Round MPC from LPN
Abstract
We present a new construction of maliciously-secure, two-round multiparty computation (MPC) in the CRS model, where the first message is reusable an unbounded number of times. The security of the protocol relies on the Learning Parity with Noise (LPN) assumption with inverse polynomial noise rate \(1/n^{1-\epsilon }\) for small enough constant \(\epsilon \), where n is the LPN dimension. Prior works on reusable two-round MPC required assumptions such as DDH or LWE that imply some flavor of homomorphic computation. We obtain our result in two steps:
  • In the first step, we construct a two-round MPC protocol in the silent pre-processing model (Boyle et al. Crypto 2019). Specifically, the parties engage in a computationally inexpensive setup procedure that generates some correlated random strings. Then, the parties commit to their inputs. Finally, each party sends a message depending on the function to be computed, and these messages can be decoded to obtain the output. Crucially, the complexity of the pre-processing phase and the input commitment phase do not grow with the size of the circuit to be computed. We call this multiparty silent NISC (msNISC), generalizing the notion of two-party silent NISC of Boyle et al. (CCS 2019). We provide a construction of msNISC from LPN in the random oracle model.
  • In the second step, we give a transformation that removes the pre-processing phase and use of random oracle from the previous protocol. This transformation additionally adds (unbounded) reusability of the first round message, giving the first construction of reusable two-round MPC from the LPN assumption. This step makes novel use of randomized encoding of circuits (Applebaum et al., FOCS 2004) and a variant of the “tree of MPC messages” technique of Ananth et al. and Bartusek et al. (TCC 2020).
James Bartusek, Sanjam Garg, Akshayaram Srinivasan, Yinuo Zhang
On the Bottleneck Complexity of MPC with Correlated Randomness
Abstract
At ICALP 2018, Boyle et al. introduced the notion of the bottleneck complexity of a secure multi-party computation (MPC) protocol. This measures the maximum communication complexity of any one party in the protocol, aiming to improve load-balancing among the parties.
In this work, we study the bottleneck complexity of MPC in the preprocessing model, where parties are given correlated randomness ahead of time. We present two constructions of bottleneck-efficient MPC protocols, whose bottleneck complexity is independent of the number of parties:
1.
A protocol for computing abelian programs, based only on one-way functions.
 
2.
A protocol for selection functions, based on any linearly homomorphic encryption scheme.
 
Compared with previous bottleneck-efficient constructions, our protocols can be based on a wider range of assumptions, and avoid the use of fully homomorphic encryption.
Claudio Orlandi, Divya Ravi, Peter Scholl
Low-Communication Multiparty Triple Generation for SPDZ from Ring-LPN
Abstract
The SPDZ protocol for multi-party computation relies on a correlated randomness setup consisting of authenticated, multiplication triples. A recent line of work by Boyle et al. (Crypto 2019, Crypto 2020) has investigated the possibility of producing this correlated randomness in a silent preprocessing phase, which involves a “small” setup protocol with less communication than the total size of the triples being produced. These works do this using a tool called a pseudorandom correlation generator (PCG), which allows a large batch of correlated randomness to be compressed into a set of smaller, correlated seeds. However, existing methods for compressing SPDZ triples only apply to the 2-party setting.
In this work, we construct a PCG for producing SPDZ triples over large prime fields in the multi-party setting. The security of our PCG is based on the ring-LPN assumption over fields, similar to the work of Boyle et al. (Crypto 2020) in the 2-party setting. We also present a corresponding, actively secure setup protocol, which can be used to generate the PCG seeds and instantiate SPDZ with a silent preprocessing phase. As a building block, which may be of independent interest, we construct a new type of 3-party distributed point function supporting outputs over arbitrary groups (including large prime order), as well as an efficient protocol for setting up our DPF keys with active security.
Damiano Abram, Peter Scholl
Storing and Retrieving Secrets on a Blockchain
Abstract
A secret sharing scheme enables one party to distribute shares of a secret to n parties and ensures that an adversary in control of t out of n parties will learn no information about the secret. However, traditional secret sharing schemes are often insufficient, especially for applications in which the set of parties who hold the secret shares might change over time. To achieve security in this setting, dynamic proactive secret sharing (DPSS) is used. DPSS schemes proactively update the secret shares held by the parties and allow changes to the set of parties holding the secrets. We propose FaB-DPSS (FAst Batched DPSS) – a new and highly optimized batched DPSS scheme. While previous work on batched DPSS [BDLO15] focuses on a single client submitting a batch of secrets and does not allow storing and releasing secrets independently, we allow multiple different clients to dynamically share and release secrets. FaB-DPSS is the most efficient robust DPSS scheme that supports the highest possible adversarial threshold of \(\frac{1}{2}\). We prove FaB-DPSS secure and implement it. All operations complete in seconds, and we outperform a prior state-of-the-art DPSS scheme [MZW+19] by over \(6\times \).
Additionally, we propose new applications of DPSS in the context of blockchains. Specifically, we propose a protocol that uses blockchains and FaB-DPSS to provide conditional secret storage. The protocol allows parties to store secrets along with a release condition, and once a (possibly different) party satisfies this release condition, the secret is privately released to that party. This functionality is similar to extractable witness encryption. While there are numerous compelling applications (e.g., time-lock encryption, one-time programs, and fair multi-party computation) which rely on extractable witness encryption, there are no known efficient constructions (or even constructions based on any well-studied assumptions) of extractable witness encryption. However, by utilizing blockchains and FaB-DPSS, we can easily build all those applications. We provide an implementation of our conditional secret storage protocol as well as several applications building on top of it.
Vipul Goyal, Abhiram Kothapalli, Elisaweta Masserova, Bryan Parno, Yifan Song
CNF-FSS and Its Applications
Abstract
Function Secret Sharing (FSS), introduced by Boyle, Gilboa and Ishai [BGI15], extends the classical notion of secret-sharing a value to secret sharing a function. Namely, for a secret function f (from a class \(\mathcal F\)), FSS provides a sharing of f whereby succinct shares (“keys”) are distributed to a set of parties, so that later the parties can non-interactively compute an additive sharing of f(x), for any input x in the domain of f. Previous work on FSS concentrated mostly on the two-party case, where highly efficient schemes are obtained for some simple, yet extremely useful, classes \(\mathcal F\) (in particular, FSS for the class of point functions, a task referred to as DPF – Distributed Point Functions [GI14, BGI15]).
In this paper, we concentrate on the multi-party case, with \(p\ge 3\) parties and t-security (\(1\le t<p\)). First, we introduce the notion of CNF-DPF (or, more generally, CNF-FSS), where the scheme uses the CNF version of secret sharing (rather than additive sharing) to share each value f(x). We then demonstrate the utility of CNF-DPF by providing several applications. Our main result shows how CNF-DPF can be used to achieve substantial asymptotic improvement in communication complexity when using it as a building block for constructing standard (t, p)-DPF protocols that tolerate \(t>1\) (semi-honest) corruptions (of the p parties). For example, we build a 2-out-of-5 secure (standard) DPF scheme of communication complexity \(O(N^{1/4})\), where N is the domain size of f (compared with the current best-known of \(O(N^{1/2})\) for (2, 5)-DPF). More generally, with \(p>dt\) parties, we give a (t, p)-DPF whose communication grows as \(O(N^{1/2d})\) (rather than \(O(\sqrt{N})\) that follows from the \((p-1,p)\)-DPF scheme of [BGI15]). (We ignore here terms that depend on the number of parties, p, the security parameter, etc. See precise statements in the main body of the paper below)
We also present a 1-out-of-3 secure CNF-DPF scheme, in which each party holds two of the three keys, with poly-logarithmic communication complexity. These results have immediate implications to scenarios where (multi-server) DPF was shown to be applicable. For example, we show how to use such a scheme to obtain asymptotic improvement (\(O(\log ^2N)\) versus \(O(\sqrt{N})\)) in communication complexity over the 3-party protocol of [BKKO20].
Paul Bunn, Eyal Kushilevitz, Rafail Ostrovsky

Cryptographic Protocols

Frontmatter
Efficient Verifiable Partially-Decryptable Commitments from Lattices and Applications
Abstract
We introduce verifiable partially-decryptable commitments (VPDC), as a building block for constructing efficient privacy-preserving protocols supporting auditability by a trusted party. A VPDC is an extension of a commitment along with an accompanying proof, convincing a verifier that (i) the given commitment is well-formed and (ii) a certain part of the committed message can be decrypted using a (secret) trapdoor known to a trusted party.
We first formalize VPDCs and then introduce a general decryption feasibility result that overcomes the challenges in relaxed proofs arising in the lattice setting. Our general result can be applied to a wide class of Fiat-Shamir based protocols and may be of independent interest.
Next, we show how to extend the commonly used lattice-based ‘Hashed-Message Commitment’ (HMC) scheme into a succinct and efficient VPDC. In particular, we devise a novel ‘gadget’-based Regev-style (partial) decryption method, compatible with efficient relaxed lattice-based zero-knowledge proofs. We prove the soundness of our VPDC in the setting of adversarial proofs, where a prover tries to create a valid VPDC output that fails in decryption.
To demonstrate the effectiveness of our results, we extend a private blockchain payment protocol, MatRiCT, by Esgin et al. (ACM CCS ’19) into a formally auditable construction, which we call MatRiCT-Au, with very low communication and computation overheads over MatRiCT.
Muhammed F. Esgin, Ron Steinfeld, Raymond K. Zhao
Making Private Function Evaluation Safer, Faster, and Simpler
Abstract
In the problem of two-party private function evaluation (PFE), one party \(\mathsf {P}_{\mathsf {A}}\) holds a private function f and (optionally) a private input \(x_A\), while the other party \(\mathsf {P}_{\mathsf {B}}\) possesses a private input \(x_B\). Their goal is to evaluate f on \(x_A\) and \(x_B\), and one or both parties may obtain the evaluation result \(f(x_A, x_B)\) while no other information beyond \(f(x_A, x_B)\) is revealed.
In this paper, we revisit the two-party PFE problem and provide several enhancements. We propose the first constant-round actively secure PFE protocol with linear complexity. Based on this result, we further provide the first constant-round publicly verifiable covertly (PVC) secure PFE protocol with linear complexity to gain better efficiency. For instance, when the deterrence factor is \(\epsilon = 1/2\), compared to the passively secure protocol, its communication cost is very close and its computation cost is around \(2.6\times \). In our constructions, as a by-product, we design a specific protocol for proving that a list of ElGamal ciphertexts is derived from an extended permutation performed on a given list of elements. It should be noted that this protocol greatly improves the previous result and may be of independent interest. In addition, a reusability property is added to our two PFE protocols. Namely, if the same function f is involved in multiple executions of the protocol between \(\mathsf {P}_{\mathsf {A}}\) and \(\mathsf {P}_{\mathsf {B}}\), then the protocol could be executed more efficiently from the second execution. Moreover, we further extend this property to be global, such that it supports multiple executions for the same f in a reusable fashion between \(\mathsf {P}_{\mathsf {A}}\) and arbitrary parties playing the role of \(\mathsf {P}_{\mathsf {B}}\).
Yi Liu, Qi Wang, Siu-Ming Yiu
Two-Round Oblivious Linear Evaluation from Learning with Errors
Abstract
Oblivious Linear Evaluation (OLE) is the arithmetic analogue of the well-know oblivious transfer primitive. It allows a sender, holding an affine function \(f(x)=a+bx\) over a finite field or ring, to let a receiver learn f(w) for a w of the receiver’s choice. In terms of security, the sender remains oblivious of the receiver’s input w, whereas the receiver learns nothing beyond f(w) about f. In recent years, OLE has emerged as an essential building block to construct efficient, reusable and maliciously-secure two-party computation.
In this work, we present efficient two-round protocols for OLE over large fields based on the Learning with Errors (LWE) assumption, providing a full arithmetic generalization of the oblivious transfer protocol of Peikert, Vaikuntanathan and Waters (CRYPTO 2008). At the technical core of our work is a novel extraction technique which allows to determine if a non-trivial multiple of some vector is close to a q-ary lattice.
Pedro Branco, Nico Döttling, Paulo Mateus
Improved Constructions of Anonymous Credentials from Structure-Preserving Signatures on Equivalence Classes
Abstract
Anonymous attribute-based credentials (ABCs) are a powerful tool allowing users to authenticate while maintaining privacy. When instantiated from structure-preserving signatures on equivalence classes (SPS-EQ) we obtain a controlled form of malleability, and hence increased functionality and privacy for the user. Existing constructions consider equivalence classes on the message space, allowing the joint randomization of credentials and the corresponding signatures on them.
In this work, we additionally consider equivalence classes on the signing-key space. In this regard, we obtain a signer-hiding notion, where the issuing organization is not revealed when a user shows a credential. To achieve this, we instantiate the ABC framework of Fuchsbauer, Hanser, and Slamanig (FHS, Journal of Cryptology ’19) with a recent SPS-EQ scheme (ASIACRYPT ’19) modified to support a fully adaptive NIZK from the framework of Couteau and Hartmann (CRYPTO ’20). We also show how to obtain Mercurial Signatures (CT-RSA, 2019), extending the application of our construction to anonymous delegatable credentials.
To further increase functionality and efficiency, we augment the set-commitment scheme of FHS19 to support openings on attribute sets disjoint from those possessed by the user, while integrating a proof of exponentiation to allow for a more efficient verifier. Instantiating in the CRS model, we obtain an efficient credential system, anonymous under malicious organization keys, with increased expressiveness and privacy, proven secure in the standard model.
Aisling Connolly, Pascal Lafourcade, Octavio Perez Kempner
Traceable PRFs: Full Collusion Resistance and Active Security
Abstract
The main goal of traceable cryptography is to protect against unauthorized redistribution of cryptographic functionalities. Such schemes provide a way to embed identities (i.e., a “mark”) within cryptographic objects (e.g., decryption keys in an encryption scheme, signing keys in a signature scheme). In turn, the tracing guarantee ensures that any “pirate device” that successfully replicates the underlying functionality can be successfully traced to the set of identities used to build the device.
In this work, we study traceable pseudorandom functions (PRFs). As PRFs are the workhorses of symmetric cryptography, traceable PRFs are useful for augmenting symmetric cryptographic primitives with strong traceable security guarantees. However, existing constructions of traceable PRFs either rely on strong notions like indistinguishability obfuscation or satisfy weak security guarantees like single-key security (i.e., tracing only works against adversaries that possess a single marked key).
In this work, we show how to use fingerprinting codes to upgrade a single-key traceable PRF into a fully collusion resistant traceable PRF, where security holds regardless of how many keys the adversary possesses. We additionally introduce a stronger notion of security where tracing security holds even against active adversaries that have oracle access to the tracing algorithm. In conjunction with known constructions of single-key traceable PRFs, we obtain the first fully collusion resistant traceable PRF from standard lattice assumptions. Our traceable PRFs directly imply new lattice-based secret-key traitor tracing schemes that are CCA-secure and where tracing security holds against active adversaries that have access to the tracing oracle.
Sarasij Maitra, David J. Wu

Tools

Frontmatter
Radical Isogenies on Montgomery Curves
Abstract
We work on some open problems in radical isogenies. Radical isogenies are formulas to compute chains of N-isogenies for small N and proposed by Castryck, Decru, and Vercauteren in Asiacrypt 2020. These formulas do not need to generate a point of order N generating the kernel and accelerate some isogeny-based cryptosystems like CSIDH. On the other hand, since these formulas use Tate normal forms, these need to transform Tate normal forms to curves with efficient arithmetic, e.g., Montgomery curves. In this paper, we propose radical-isogeny formulas of degrees 3 and 4 on Montgomery curves. Our formulas compute some values determining Montgomery curves, from which one can efficiently recover Montgomery coefficients. And our formulas are more efficient for some cryptosystems than the original radical isogenies. In addition, we prove a conjecture left open by Castryck et al. that relates to radical isogenies of degree 4.
Hiroshi Onuki, Tomoki Moriya
Towards a Simpler Lattice Gadget Toolkit
Abstract
As a building block, gadgets and associated algorithms are widely used in advanced lattice cryptosystems. The gadget algorithms for power-of-base moduli are very efficient and simple, however the current algorithms for arbitrary moduli are still complicated and practically more costly despite several efforts. Considering the necessity of arbitrary moduli, developing simpler and more practical gadget algorithms for arbitrary moduli is crucial to improving the practical performance of lattice based applications.
In this work, we propose two new gadget sampling algorithms for arbitrary moduli. Our first algorithm is for gadget Gaussian sampling. It is simple and efficient. One distinguishing feature of our Gaussian sampler is that it does not need floating-point arithmetic, which makes it better compatible with constrained environments. Our second algorithm is for gadget subgaussian sampling. Compared with the existing algorithm, it is simpler, faster, and requires asymptotically less randomness. In addition, our subgaussian sampler achieves an almost equal quality for different practical parameters. Overall these two algorithms provide simpler options for gadget algorithms and enhance the practicality of the gadget toolkit.
Shiduo Zhang, Yang Yu

SNARKs and NIZKs

Frontmatter
Polynomial IOPs for Linear Algebra Relations
Abstract
This paper proposes new Polynomial IOPs for arithmetic circuits. They rely on the monomial coefficient basis to represent the matrices and vectors arising from the arithmetic constraint satisfaction system, and build on new protocols for establishing the correct computation of linear algebra relations such as matrix-vector products and Hadamard products. Our protocols give rise to concrete proof systems with succinct verification when compiled down with a cryptographic compiler whose role is abstracted away in this paper. Depending only on the compiler, the resulting SNARKs are either transparent or rely on a trusted setup.
Alan Szepieniec, Yuncong Zhang
A Unified Framework for Non-universal SNARKs
Abstract
We propose a general framework for non-universal SNARKs. It contains (1) knowledge-sound and non-black-box any-simulation-extractable (ASE), (2) zero-knowledge and subversion-zero knowledge SNARKs for the well-known QAP, SAP, QSP, and QSP constraint languages that all by design have relatively simple security proofs. The knowledge-sound zero-knowledge SNARK is similar to Groth’s SNARK from EUROCRYPT 2016, except having fewer trapdoors, while the ASE subversion-zero knowledge SNARK relies on few additional conditions. We prove security in a weaker, more realistic version of the algebraic group model. We characterize SAP, SSP, and QSP in terms of QAP; this allows one to use a SNARK for QAP directly for other languages. Our results allow us to construct a family of SNARKs for different languages and with different security properties following the same proof template. Some of the new SNARKs are more efficient than prior ones. In other cases, the new SNARKs cover gaps in the landscape, e.g., there was no previous ASE or Sub-ZK SNARK for SSP or QSP.
Helger Lipmaa
ECLIPSE: Enhanced Compiling Method for Pedersen-Committed zkSNARK Engines
Abstract
We advance the state-of-the art for zero-knowledge commit-and-prove SNARKs (CP-SNARKs). CP-SNARKs are an important class of SNARKs which, using commitments as “glue”, allow to efficiently combine proof systems—e.g., general-purpose SNARKs (an efficient way to prove statements about circuits) and \(\varSigma \)-protocols (an efficient way to prove statements about group operations). Thus, CP-SNARKs allow to efficiently provide zero-knowledge proofs for composite statements such as \(h=H(g^{x})\) for some hash-function H.
Our main contribution is providing the first construction of CP-SNARKs where the proof size is succinct in the number of commitments.
We achieve our result by providing a general technique to compile Algebraic Holographic Proofs (AHP) (an underlying abstraction used in many modern SNARKs) with special “decomposition” properties into an efficient CP-SNARK. We then show that some of the most efficient AHP constructions—Marlin, PLONK, and Sonic—satisfy our compilation requirements.
Our resulting SNARKs achieve universal and updatable reference strings, which are highly desirable features as they greatly reduce the trust needed in the SNARK setup phase.
Diego F. Aranha, Emil Madsen Bennedsen, Matteo Campanelli, Chaya Ganesh, Claudio Orlandi, Akira Takahashi
Rational Modular Encoding in the DCR Setting: Non-interactive Range Proofs and Paillier-Based Naor-Yung in the Standard Model
Abstract
Range proofs allow a sender to convince a verifier that committed integers belong to an interval without revealing anything else. So far, all known non-interactive range proofs in the standard model rely on groups endowed with a bilinear map. Moreover, they either require the group order to be larger than the range of any proven statement or they suffer from a wasteful rate. Recently (Eurocrypt’21), Couteau et al. introduced a new approach to efficiently prove range membership by encoding integers as a modular ratio between small integers. We show that their technique can be transposed in the standard model under the Composite Residuosity (\(\mathsf {DCR}\)) assumption. Interestingly, with this modification, the size of ranges is not a priori restricted by the common reference string. It also gives a constant ratio between the size of ranges and proofs. Moreover, we show that their technique of encoding messages as bounded rationals provides a secure standard model instantiation of the Naor-Yung CCA2 encryption paradigm under the \(\mathsf {DCR}\) assumption.
Julien Devevey, Benoît Libert, Thomas Peters
Backmatter
Metadata
Title
Public-Key Cryptography – PKC 2022
Editors
Dr. Goichiro Hanaoka
Junji Shikata
Yohei Watanabe
Copyright Year
2022
Electronic ISBN
978-3-030-97121-2
Print ISBN
978-3-030-97120-5
DOI
https://doi.org/10.1007/978-3-030-97121-2

Premium Partner

    Image Credits