IACR News
Updates on the COVID-19 situation are on the
Announcement channel.
Here you can see all recent updates to the IACR webpage. These updates are also available:
14 October 2022
David Balbás, Dario Catalano, Dario Fiore, Russell W. F. Lai
A functional commitment (FC) scheme allows one to commit to a vector $\vec{x}$ and later produce a short opening proof of $(f, f(\vec{x}))$ for any admissible function $f$. The security of FC schemes, called evaluation binding, ensures that it is hard to open the commitment to the same function $f$ and different outputs $y \neq y'$. Unlike succinct non-interactive arguments (SNARG) which provide a stronger soundness guarantee but typically require non-falsifiable assumptions, the evaluation binding of FC schemes can often be based on falsifiable assumptions and is sufficient for certain applications such as constructing homomorphic signatures (HS).
Since their inception, FC schemes supporting ever more expressive classes of functions have been proposed, with the state-of-the-art supporting low-degree polynomial maps.
In this work we construct the first FC schemes for circuits, based on either pairing-based or lattice-based falsifiable assumptions. Our FCs require to fix a-priori only the maximal width of the circuit to be evaluated, and have opening proofs whose size only depends on the depth of the circuit. We obtain our results in two steps. First, we introduce a new tool which we call chainable functional commitment (CFC), and show that CFCs for quadratic polynomial maps generically imply an FC for bounded-width circuits. Then, we show how to efficiently instantiate CFCs for quadratic polynomial maps over either pairing groups or lattices.
Using a recent transformation from FC to HS, we obtain the first pairing- and lattice-based constructions of HS for bounded-width, but unbounded-depth, circuits. Prior to this work, the only HS for general circuits is lattice-based and requires bounding the circuit depth at setup time.
In this work we construct the first FC schemes for circuits, based on either pairing-based or lattice-based falsifiable assumptions. Our FCs require to fix a-priori only the maximal width of the circuit to be evaluated, and have opening proofs whose size only depends on the depth of the circuit. We obtain our results in two steps. First, we introduce a new tool which we call chainable functional commitment (CFC), and show that CFCs for quadratic polynomial maps generically imply an FC for bounded-width circuits. Then, we show how to efficiently instantiate CFCs for quadratic polynomial maps over either pairing groups or lattices.
Using a recent transformation from FC to HS, we obtain the first pairing- and lattice-based constructions of HS for bounded-width, but unbounded-depth, circuits. Prior to this work, the only HS for general circuits is lattice-based and requires bounding the circuit depth at setup time.
Robin Geelen, Ilia Iliashenko, Jiayi Kang, Frederik Vercauteren
In this paper, we perform a systematic study of functions $f: \mathbb{Z}_{p^e} \to \mathbb{Z}_{p^e}$ and categorize those functions that can be represented by a polynomial with integer coefficients. More specifically, we cover the following properties: necessary and sufficient conditions for the existence of an integer polynomial representation; computation of such a representation; and the complete set of equivalent polynomials that represent a given function.
As an application, we use the newly developed theory to speed up bootstrapping for the BGV and BFV homomorphic encryption schemes. The crucial ingredient underlying our improvements is the existence of null polynomials, i.e. non-zero polynomials that evaluate to zero in every point. We exploit the rich algebraic structure of these null polynomials to find better representations of the digit extraction function, which is the main bottleneck in bootstrapping. As such, we obtain sparse polynomials that have 50% fewer coefficients than the original ones. In addition, we propose a new method to decompose digit extraction as a series of polynomial evaluations. This lowers the time complexity from $\mathcal{O}(\sqrt{pe})$ to $\mathcal{O}(\sqrt{p}\sqrt[^4]{e})$ for digit extraction modulo $p^e$, at the cost of a slight increase in multiplicative depth. Overall, our implementation in HElib shows a significant speedup of a factor up to 2.6 over the state-of-the-art.
As an application, we use the newly developed theory to speed up bootstrapping for the BGV and BFV homomorphic encryption schemes. The crucial ingredient underlying our improvements is the existence of null polynomials, i.e. non-zero polynomials that evaluate to zero in every point. We exploit the rich algebraic structure of these null polynomials to find better representations of the digit extraction function, which is the main bottleneck in bootstrapping. As such, we obtain sparse polynomials that have 50% fewer coefficients than the original ones. In addition, we propose a new method to decompose digit extraction as a series of polynomial evaluations. This lowers the time complexity from $\mathcal{O}(\sqrt{pe})$ to $\mathcal{O}(\sqrt{p}\sqrt[^4]{e})$ for digit extraction modulo $p^e$, at the cost of a slight increase in multiplicative depth. Overall, our implementation in HElib shows a significant speedup of a factor up to 2.6 over the state-of-the-art.
Robin Geelen, Frederik Vercauteren
We unify the state-of-the-art bootstrapping algorithms for BGV and BFV in a single framework, and show that BGV and BFV can be bootstrapped with identical complexity. This result corrects a claim by Chen and Han (Eurocrypt 2018) that BFV is more efficient to bootstrap than BGV. We also fix an error in their optimized procedure for power-of-two cyclotomics, which occurs for some parameter sets.
Our analysis is simpler, yet more general than earlier work, in that it simultaneously covers both BGV and BFV. Furthermore, we also design and implement a high-level open source software library for bootstrapping in the Magma Computer Algebra System. It is the first library to support both BGV and BFV bootstrapping in full generality, with all recent techniques (including the above fixes) and trade-offs.
Our analysis is simpler, yet more general than earlier work, in that it simultaneously covers both BGV and BFV. Furthermore, we also design and implement a high-level open source software library for bootstrapping in the Magma Computer Algebra System. It is the first library to support both BGV and BFV bootstrapping in full generality, with all recent techniques (including the above fixes) and trade-offs.
Samuel Jaques, Michael Lodder, Hart Montgomery
A cryptographic accumulator is a space- and time-efficient data structure with associated algorithms used for secure membership testing. In the growing space of digital credentials, accumulators found in managing a set of valid credentials, giving efficient and anonymous methods for credential holders to prove their validity. Unlike traditional credentials like digital signatures, one can easily revoke credentials with an accumulator; however, each revocation forces existing credential holders to engage in an expensive update process. Previous works make this faster and easier by sacrificing anonymity. To improve performance without compromising privacy, we present ALLOSAUR, a multi-party accumulator based on pairings. In ALLOSAUR, we eliminate the cost of accumulating new credentials, let "credential managers" manage the accumulator values with secure multiparty computation, and allow anonymous credential updates with a square-root reduction in communication costs as compared to existing work.
A deployed digital credential system is a vast and complicated system, and existing formalisms do not fully address the scope or power of a real-world adversary. We develop a thorough UC-style formalism that allows arbitrary malicious behaviour from an adversary controlling a minority of credential managers and arbitrary numbers of users, credentials, and verifiers. In our new formalism we present a novel definition of privacy that captures as much anonymity as possible while accounting for inevitable losses from interaction with the system. The detail in our formalism reveals real-world issues in existing accumulator constructions, all of which ALLOSAUR avoids.
Our proof-of-concept implementation can update over 1000 revocations with less than half a second of total computation and 16 kB communication, at least a 5x improvement over the previous state-of-the-art in both metrics.
A deployed digital credential system is a vast and complicated system, and existing formalisms do not fully address the scope or power of a real-world adversary. We develop a thorough UC-style formalism that allows arbitrary malicious behaviour from an adversary controlling a minority of credential managers and arbitrary numbers of users, credentials, and verifiers. In our new formalism we present a novel definition of privacy that captures as much anonymity as possible while accounting for inevitable losses from interaction with the system. The detail in our formalism reveals real-world issues in existing accumulator constructions, all of which ALLOSAUR avoids.
Our proof-of-concept implementation can update over 1000 revocations with less than half a second of total computation and 16 kB communication, at least a 5x improvement over the previous state-of-the-art in both metrics.
Rafael Carrera Rodriguez, Florent Bruguier, Emanuele Valea, Pascal Benoit
Post-quantum cryptography represents a category of cryptosystems resistant to quantum algorithms. Recently, NIST launched a process to standardize one or more of such algorithms in the key encapsulation mechanism and signature categories. Such schemes are under the scrutiny of their mathematical security, but they are not side-channel secure at the algorithm level. That is why their side-channel vulnerabilities must be assessed by the research community. In this paper, we present a non-profiled correlation electromagnetic analysis against an FPGA implementation of the chosen NIST key-encapsulation mechanism standard, CRYSTALS-Kyber. The attack correlates an electromagnetic radiation model of the polynomial multiplication execution with the captured traces. With 166,620 traces, this attack correctly recovers 100% of the subkeys. Furthermore, a countermeasure is presented for securing the target implementation against the presented attack.
Jiangshan Long, Chenxu Wang, Changhai Ou, Zhu Wang, Yongbin Zhou, Ming Tang
Success Rate (SR) is empirically and theoretically a common metric for evaluating the performance of side-channel attacks. Intuitive expressions of success rate are desirable since they reveal and explain the functional dependence on relevant parameters, such as number of measurements and Signal-to-Noise Ratio (SNR), in a straightforward manner. Meanwhile, existing works more or less expose unsolved fundamental problems, such as strong leakage assumption, difficulty in interpretation of principle, inaccurate evaluation, and inconsideration of high-order SR. In this paper, we first provide an intuitive framework that statistical tests embedded in different univariate DPA attacks are unified as analyzing and comparing visualized vectors in a Euclidean space by using different easy-to-understand metrics. Then, we establish a unified framework to abstract and convert the security evaluations to the problem of finding a boundary in the Euclidean space. With expressions of the boundary, judging whether a DPA attack succeeds in sense of $o^{th}$-order becomes fairly efficient and intuitive, and the corresponding SR can be calculated theoretically by integral. Finally, we propose an algorithm that is capable of estimating arbitrary order of SR effectively. Our experimental results verify the theory and highlight the superiority. We believe our research raises many new perspectives for comparing and evaluating side-channel attacks, countermeasures and implementations.
Haruhisa Kosuge, Keita Xagawa
A hash-and-sign signature based on preimage-sampleable function (PSF) (Gentry et al. [STOC 2008]) is secure in the Quantum Random Oracle Model (QROM) if the PSF is collision-resistant (Boneh et al. [ASIACRYPT 2011]) or one-way (Zhandry [CRYPTO 2012]). However, trapdoor functions (TDFs) in code-based and multivariate-quadratic-based (MQ-based) signatures are not PSFs; for example, underlying TDFs of the Courtois-Finiasz-Sendrier (CFS), Unbalanced Oil and Vinegar (UOV), and Hidden Field Equations (HFE) signatures are not surjection. Thus, such signature schemes adopt probabilistic hash-and-sign with retry. This paradigm is secure in the (classical) Random Oracle Model (ROM), assuming that the underlying TDF is non-invertible; that is, it is hard to find a preimage of a given random value in the range (e.g., Sakumoto et al. [PQCRYPTO 2011] for the modified UOV/HFE signatures). Unfortunately, there is no known security proof for the probabilistic hash-and-sign with retry in the QROM.
We give the first security proof for the probabilistic hash-and-sign with retry in the QROM, assuming that the underlying non-PSF TDF is non-invertible. Our reduction from the non-invertibility is tighter than the existing ones that apply to only signature schemes based on PSFs. We apply the security proof to code-based and MQ-based signatures. Moreover, we extend the proof into the multi-key setting by using prefix hashing (Duman et al. [ACM CCS 2021]).
Sam Gunn, Nathan Ju, Fermi Ma, Mark Zhandry
What does it mean to commit to a quantum state? In this work, we propose a simple answer: a commitment to quantum messages is binding if, after the commit phase, the committed state is hidden from the sender's view. We accompany this new definition with several instantiations. We build the first non-interactive succinct quantum state commitments, which can be seen as an analogue of collision-resistant hashing for quantum messages. We also show that hiding quantum state commitments (QSCs) are implied by any commitment scheme for classical messages. All of our constructions can be based on quantum-cryptographic assumptions that are implied by but are potentially weaker than one-way functions.
Commitments to quantum states open the door to many new cryptographic possibilities. Our flagship application of a succinct QSC is a quantum-communication version of Kilian's succinct arguments for any language that has quantum PCPs with constant error and polylogarithmic locality. Plugging in the PCP theorem, this yields succinct arguments for NP under significantly weaker assumptions than required classically; moreover, if the quantum PCP conjecture holds, this extends to QMA. At the heart of our security proof is a new rewinding technique for extracting quantum information.
Commitments to quantum states open the door to many new cryptographic possibilities. Our flagship application of a succinct QSC is a quantum-communication version of Kilian's succinct arguments for any language that has quantum PCPs with constant error and polylogarithmic locality. Plugging in the PCP theorem, this yields succinct arguments for NP under significantly weaker assumptions than required classically; moreover, if the quantum PCP conjecture holds, this extends to QMA. At the heart of our security proof is a new rewinding technique for extracting quantum information.
Mingxun Zhou, Elaine Shi, T-H. Hubert Chan, Shir Maimon
Differential obliviousness (DO) access pattern privacy is a privacy notion which guarantees that the access patterns of a program satisfy differential privacy. Differential obliviousness was studied in a sequence of recent works as a relaxation of full obliviousness. Earlier works showed that DO not only allows us to circumvent the logarithmic-overhead barrier of fully oblivious algorithms, in many cases, it also allows us to achieve polynomial speedup over full obliviousness, since it avoids "padding to the worst-case" behavior of fully oblivious algorithms.
Despite the promises of differential obliviousness (DO), a significant barrier that hinders its broad application is the lack of composability. In particular, when we apply one DO algorithm to the output of another DO algorithm, the composed algorithm may no longer be DO (with reasonable parameters). More specifically, the outputs of the first DO algorithm on two neighboring inputs may no longer be neighboring, and thus we cannot directly benefit from the DO guarantee of the second algorithm.
In this work, we are the first to explore a theory of composition for differentially oblivious algorithms. We propose a refinement of the DO notion called $(\epsilon, \delta)$-neighbor-preserving-DO, or $(\epsilon, \delta)$-NPDO for short, and we prove that our new notion indeed provides nice compositional guarantees. In this way, the algorithm designer can easily track the privacy loss when composing multiple DO algorithms.
We give several example applications to showcase the power and expressiveness of our new NPDO notion. One of these examples is a result of independent interest: we use the compositional framework to prove an optimal privacy amplification theorem for the differentially oblivious shuffle model. In other words, we show that for a class of distributed differentially private mechanisms in the shuffle-model, one can replace the perfectly secure shuffler with a DO shuffler, and nonetheless enjoy almost the same privacy amplification enabled by a shuffler.
Despite the promises of differential obliviousness (DO), a significant barrier that hinders its broad application is the lack of composability. In particular, when we apply one DO algorithm to the output of another DO algorithm, the composed algorithm may no longer be DO (with reasonable parameters). More specifically, the outputs of the first DO algorithm on two neighboring inputs may no longer be neighboring, and thus we cannot directly benefit from the DO guarantee of the second algorithm.
In this work, we are the first to explore a theory of composition for differentially oblivious algorithms. We propose a refinement of the DO notion called $(\epsilon, \delta)$-neighbor-preserving-DO, or $(\epsilon, \delta)$-NPDO for short, and we prove that our new notion indeed provides nice compositional guarantees. In this way, the algorithm designer can easily track the privacy loss when composing multiple DO algorithms.
We give several example applications to showcase the power and expressiveness of our new NPDO notion. One of these examples is a result of independent interest: we use the compositional framework to prove an optimal privacy amplification theorem for the differentially oblivious shuffle model. In other words, we show that for a class of distributed differentially private mechanisms in the shuffle-model, one can replace the perfectly secure shuffler with a DO shuffler, and nonetheless enjoy almost the same privacy amplification enabled by a shuffler.
Gabrielle De Micheli, Daniele Micciancio
The celebrated LLL algorithm for Euclidean lattices is central to cryptanalysis of well- known and deployed protocols as it provides approximate solutions to the Shortest Vector Problem (SVP). Recent interest in algebrically structured lattices (e.g., for the efficient implementation of lattice- based cryptography) has prompted adapations of LLL to such structured lattices, and, in particular, to module lattices, i.e., lattices that are modules over algebraic ring extensions of the integers. One of these adaptations is a quantum algorithm proposed by Lee, Pellet-Mary, Stehlé and Wallet (Asiacrypt 2019). In this work, we dequantize the algorithm of Lee et al., and provide a fully classical LLL-type algorithm for arbitrary module lattices that achieves same SVP approximation factors, single exponential in the rank of the input module. Just like the algorithm of Lee et al., our algorithm runs in polynomial time given an oracle that solves the Closest Vector Problem (CVP) in a certain, fixed lattice L_K that depends only on the number field K.
Binyi Chen, Benedikt Bünz, Dan Boneh, Zhenfei Zhang
Plonk is a widely used succinct non-interactive proof system that uses univariate polynomial commitments. Plonk is quite flexible: it supports circuits with low-degree ``custom'' gates as well as circuits with lookup gates (a lookup gate ensures that its input is contained in a predefined table). For large circuits, the bottleneck in generating a Plonk proof is the need for computing a large FFT.
We present HyperPlonk, an adaptation of Plonk to the boolean hypercube, using multilinear polynomial commitments. HyperPlonk retains the flexibility of Plonk but provides several additional benefits. First, it avoids the need for an FFT during proof generation. Second, and more importantly, it supports custom gates of much higher degree than Plonk without harming the running time of the prover. Both of these can dramatically speed up the prover's running time. Since HyperPlonk relies on multilinear polynomial commitments, we revisit two elegant constructions: one from Orion and one from Virgo. We show how to reduce the Orion opening proof size to less than 10kb (an almost factor 1000 improvement) and show how to make the Virgo FRI-based opening proof simpler and shorter.
We present HyperPlonk, an adaptation of Plonk to the boolean hypercube, using multilinear polynomial commitments. HyperPlonk retains the flexibility of Plonk but provides several additional benefits. First, it avoids the need for an FFT during proof generation. Second, and more importantly, it supports custom gates of much higher degree than Plonk without harming the running time of the prover. Both of these can dramatically speed up the prover's running time. Since HyperPlonk relies on multilinear polynomial commitments, we revisit two elegant constructions: one from Orion and one from Virgo. We show how to reduce the Orion opening proof size to less than 10kb (an almost factor 1000 improvement) and show how to make the Virgo FRI-based opening proof simpler and shorter.
Marijn F. Stollenga
Cryptocurrencies have become tremendously popular since the creation of Bitcoin. However, its central Proof-of-Work consensus mechanism is very power hungry. As an alternative, Proof-of-Space (PoS) was introduced that uses storage instead of computations to create a consensus. However, current PoS implementations are complex and sensitive to the Nothing-at-Stake problem, and use mitigations that affect their permissionless and decentralised nature.
We introduce Proof-of-Space Search (PoSS) which embraces Hellman's time-memory trade-off to create a much simpler algorithm that avoids the Nothing-at-Stake problem. Additionally, we greatly stabilise block-times using a novel dynamic Logarithmic Embargo (LE) rule. Combined, we show that PoSSLE is a simple and stable alternative to PoW with many of its properties, while being an estimated 10 times more energy efficient and sustaining consistent block times.
We introduce Proof-of-Space Search (PoSS) which embraces Hellman's time-memory trade-off to create a much simpler algorithm that avoids the Nothing-at-Stake problem. Additionally, we greatly stabilise block-times using a novel dynamic Logarithmic Embargo (LE) rule. Combined, we show that PoSSLE is a simple and stable alternative to PoW with many of its properties, while being an estimated 10 times more energy efficient and sustaining consistent block times.
Paul Bunn, Eyal Kushilevitz, Rafail Ostrovsky
The Non-Interactive Anonymous Router (NIAR) model was introduced by Shi and Wu [SW21] as an alternative to conventional solutions to the anonymous routing problem, in which a set of senders wish to send messages to a set of receivers. In contrast to most known approaches to support anonymous routing (e.g. mix-nets, DC-nets, etc.) which rely on a network of routers communicating with users via interactive protocols, the NIAR model assumes a $single$ router and is inherently $non$-$interactive$ (after an initial setup phase). In addition to being non-interactive, the NIAR model is compelling due to the security it provides: instead of relying on the honesty of some subset of the routers, the NIAR model requires anonymity even if the router (as well as an arbitrary subset of senders/receivers) is corrupted.
In this paper, we present a protocol for the NIAR model that improves upon the results from [SW21] in two ways:
- Improved computational efficiency (quadratic to near linear): Our protocol matches the communication complexity of [SW21] for each sender/receiver, while reducing the computational overhead for the router to polylog overhead instead of linear overhead.
- Relaxation of assumptions: Security of the protocol in [SW21] relies on the Decisional Linear assumption in bilinear groups; while security for our protocol follows from the existence of any rate-1 oblivious transfer (OT) protocol (instantiations of this primitive are known to exist under DDH, QR and LWE [DGI19,GHO20]).
In this paper, we present a protocol for the NIAR model that improves upon the results from [SW21] in two ways:
- Improved computational efficiency (quadratic to near linear): Our protocol matches the communication complexity of [SW21] for each sender/receiver, while reducing the computational overhead for the router to polylog overhead instead of linear overhead.
- Relaxation of assumptions: Security of the protocol in [SW21] relies on the Decisional Linear assumption in bilinear groups; while security for our protocol follows from the existence of any rate-1 oblivious transfer (OT) protocol (instantiations of this primitive are known to exist under DDH, QR and LWE [DGI19,GHO20]).
Miguel Ambrona, Marc Beunardeau, Anne-Laure Schmitt, Raphaël R. Toledo
PlonK is a prominent universal and updatable zk-SNARK for general circuit satisfiability. We present aPlonK, a variant of PlonK that reduces the proof size and verification time when multiple statements are proven in a batch. Both the aggregated proof size and the verification complexity of aPlonK are logarithmic in the number of aggregated statements. Our main building block, inspired by the techniques developed in SnarkPack (Gailly, Maller, Nitulescu, FC 2022), is a multi-polynomial commitment scheme, a new primitive that generalizes polynomial commitment schemes. Our techniques also include a mechanism for involving committed data into PlonK statements very efficiently, which can be of independent interest.
We also implement an open-source industrial-grade library for zero-knowledge PlonK proofs with support for aPlonK. Our experimental results show that our techniques are suitable for real-world applications (such as blockchain rollups), achieving significant performance improvements in proof size and verification time.
Christina Boura, Nicolas David, Rachelle Heim Boissier, Maria Naya-Plasencia
Differential attacks are among the most important families of cryptanalysis against symmetric primitives. Since their introduction in 1990, several improvements to the basic technique as well as many dedicated attacks against symmetric primitives have been proposed. Most of the proposed improvements concern the key-recovery part. However, when designing a new primitive, the security analysis regarding differential attacks is often limited to finding the best trails over a limited number of rounds with branch and bound techniques, and a poor heuristic is then applied to deduce the total number of rounds a differential attack could reach. In this work we analyze the security of the SPEEDY family of block ciphers against differential cryptanalysis and show how to optimize many of the steps of the key-recovery procedure for this type of attacks. For this, we implemented a search for finding optimal trails for this cipher and their associated multiple probabilities under some constraints and applied non-trivial techniques to obtain optimal data and key-sieving. This permitted us to fully break SPEEDY-7-192, the 7-round variant of SPEEDY supposed to provide 192-bit security. Our work demonstrates among others the need to better understand the subtleties of differential cryptanalysis in order to get meaningful estimates on the security offered by a cipher against these attacks.
Lucjan Hanzlik, Julian Loss, Benedikt Wagner
Blind signatures are a fundamental tool for privacy-preserving applications.
Known constructions of concurrently secure blind signature schemes either are prohibitively inefficient or rely on non-standard assumptions, even in the random oracle model.
A recent line of work (ASIACRYPT `21, CRYPTO `22) initiated the study of concretely efficient schemes based on well-understood assumptions in the random oracle model.
However, these schemes still have several major drawbacks:
1) The signer is required to keep state; 2) The computation grows linearly with the number of signing interactions, making the schemes impractical; 3) The schemes require at least five moves of interaction.
In this paper, we introduce a blind signature scheme that eliminates all of the above drawbacks at the same time. Namely, we show a round-optimal, concretely efficient, concurrently secure, and stateless blind signature scheme in which communication and computation are independent of the number of signing interactions. Our construction also naturally generalizes to the partially blind signature setting.
Our scheme is based on the CDH assumption in the asymmetric pairing setting and can be instantiated using a standard BLS curve. We obtain signature and communication sizes of 9KB and 36KB, respectively. To further improve the efficiency of our scheme, we show how to obtain a scheme with better amortized communication efficiency. Our approach batches the issuing of signatures for multiple messages.
In this paper, we introduce a blind signature scheme that eliminates all of the above drawbacks at the same time. Namely, we show a round-optimal, concretely efficient, concurrently secure, and stateless blind signature scheme in which communication and computation are independent of the number of signing interactions. Our construction also naturally generalizes to the partially blind signature setting.
Our scheme is based on the CDH assumption in the asymmetric pairing setting and can be instantiated using a standard BLS curve. We obtain signature and communication sizes of 9KB and 36KB, respectively. To further improve the efficiency of our scheme, we show how to obtain a scheme with better amortized communication efficiency. Our approach batches the issuing of signatures for multiple messages.
Xiutao Feng, Xiaoshan GAO, Zhangyi WANG, Xiangyong ZENG
The invertibility of a random function (IRF, in short) is an important problem and has wide applications in cryptography. For ex- ample, searching a preimage of Hash functions, recovering a key of block ciphers under the known-plaintext-attack model, solving discrete loga- rithms over a prime field with large prime, and so on, can be viewed as its instances. In this work we describe the invertibility of multiple random functions (IMRF, in short), which is a generalization of the IRF. In order to solve the IMRF, we generalize the birthday theorem. Based on the generalized birthday theorem and time-memory tradeoff (TMTO, in short) method, we present an efficient TMTO method of solving an IMRF, which can be viewed as a generalization of three main TMTO attacks, that is, Hellman’s attack, Biryukov and Shamir’s attack with BSW sampling, and Biryukov, Mukhopadhyay and Sarkar’s time- memory-key tradeoff attack. Our method is highly parallel and suitable for distributed computing environments. As a generalization of Hellman’s attack, our method overcomes its shortcoming of using only one pair of known plaintext and ciphertext and first admits more than one datum in a TMTO on block ciphers at the single key scenario. As a generaliza- tion of Biryukov and Shamir’s attack with BSW sampling, our method overcomes its shortcoming of using only a few data with specific prefix in stream ciphers and can utilize all data without any waste. As appli- cations, we get two new tradeoff curves: N2 = TM2D3, N = PD and D=τforblockciphers,andN2 =τ3TM2D2,N=τPDandD≥τ for stream ciphers, where τ is the number of random functions, that is, the number of independent computing units available to an attacker, N is the size of key space (for block ciphers) or state (for stream ci- phers) space, D the number of data captured by the attacker, and T, M, P the time/memory/precomputation cost consumed at each computing unit respectively. As examples, assume that 4096 computing units can be available for the attacker. Denote by 5-tuple (τ, T, M, D, P ) the costof our method. Then the cost of breaking DES, AES-128 and A5/1 is (212, 225.3, 225.3, 212, 244), (212, 273.3, 273.3, 212, 2116) and (212, 222.7, 217.3,217.3, 234.7) respectively
Hoeteck Wee
We present a new public-key ABE for DFA based on the LWE assumption, achieving security against collusions of a-priori bounded size. Our scheme achieves ciphertext size $\tilde{O}(\ell + B)$ for attributes of length $\ell$ and collusion size $B$. Prior LWE-based schemes has either larger ciphertext size $\tilde{O}(\ell \cdot B)$, or are limited to the secret-key setting. Along the way, we introduce a new technique for lattice trapdoor sampling, which we believe would be of independent interest. Finally, we present a simple candidate public-key ABE for DFA for the unbounded collusion setting.
Shweta Agrawal, Simran Kumari, Anshu Yadav, Shota Yamada
A trace and revoke ($\sf{TR}$) scheme is an $N$ user traitor tracing scheme which additionally enables the encryptor to specify a list $L \subseteq$ of revoked users so that these users can no longer decrypt ciphertexts. The ``holy grail'' of this line of work is a construction which resists unbounded collusions, achieves ciphertext, public and secret key sizes independent (ignoring logarithmic dependencies) of $|L|$ and $|N|$, and is based on polynomial hardness assumptions. In this work we make the following contributions:
1. Public Trace Setting: We provide a construction which (i) achieves optimal parameters, (ii) supports embedding identities (from an exponential space) in user secret keys, (iii) relies on polynomial hardness assumptions, namely compact functional encryption (${\sf FE}$) and a key-policy attribute based encryption (${\sf ABE}$) with special efficiency properties constructed by Boneh et al. (Eurocrypt 2014) from Learning With Errors (${\sf LWE}$), and (iv) enjoys adaptive security with respect to the revocation list. The previous best known construction by Nishimaki, Wichs and Zhandry (Eurocrypt 2016) which achieved optimal parameters and embedded identities, relied on indistinguishability obfuscation, which is considered an inherently subexponential assumption and achieved only selective security with respect to the revocation list. 2. Secret Trace Setting: We provide the first construction with optimal ciphertext, public and secret key sizes and embedded identities from any assumption outside Obfustopia. In detail, our construction relies on Lockable Obfuscation which can be constructed using ${\sf LWE}$ (Goyal, Koppula, Waters and Wichs, Zirdelis, Focs 2017) and two ${\sf ABE}$ schemes: (i) the key-policy scheme with special efficiency properties by Boneh et al. (Eurocrypt 2014) and (ii) a ciphertext-policy ${\sf ABE}$ for ${\sf P}$ which was recently constructed by Wee (Eurocrypt 2022) using a new assumption called evasive and tensor ${\sf LWE}$. This assumption, introduced to build an ${\sf ABE}$, is believed to be much weaker than lattice based assumptions underlying ${\sf FE}$ or ${\sf iO}$ -- in particular it is required even for lattice based broadcast, without trace.
Moreover, by relying on subexponential security of ${\sf LWE}$, both our constructions can also support a super-polynomial sized revocation list, so long as it allows efficient representation and membership testing. Ours is the first work to achieve this, to the best of our knowledge.
1. Public Trace Setting: We provide a construction which (i) achieves optimal parameters, (ii) supports embedding identities (from an exponential space) in user secret keys, (iii) relies on polynomial hardness assumptions, namely compact functional encryption (${\sf FE}$) and a key-policy attribute based encryption (${\sf ABE}$) with special efficiency properties constructed by Boneh et al. (Eurocrypt 2014) from Learning With Errors (${\sf LWE}$), and (iv) enjoys adaptive security with respect to the revocation list. The previous best known construction by Nishimaki, Wichs and Zhandry (Eurocrypt 2016) which achieved optimal parameters and embedded identities, relied on indistinguishability obfuscation, which is considered an inherently subexponential assumption and achieved only selective security with respect to the revocation list. 2. Secret Trace Setting: We provide the first construction with optimal ciphertext, public and secret key sizes and embedded identities from any assumption outside Obfustopia. In detail, our construction relies on Lockable Obfuscation which can be constructed using ${\sf LWE}$ (Goyal, Koppula, Waters and Wichs, Zirdelis, Focs 2017) and two ${\sf ABE}$ schemes: (i) the key-policy scheme with special efficiency properties by Boneh et al. (Eurocrypt 2014) and (ii) a ciphertext-policy ${\sf ABE}$ for ${\sf P}$ which was recently constructed by Wee (Eurocrypt 2022) using a new assumption called evasive and tensor ${\sf LWE}$. This assumption, introduced to build an ${\sf ABE}$, is believed to be much weaker than lattice based assumptions underlying ${\sf FE}$ or ${\sf iO}$ -- in particular it is required even for lattice based broadcast, without trace.
Moreover, by relying on subexponential security of ${\sf LWE}$, both our constructions can also support a super-polynomial sized revocation list, so long as it allows efficient representation and membership testing. Ours is the first work to achieve this, to the best of our knowledge.
Trey Li
This paper provides a cryptographic application to our previous paper [Li22h], where we considered noisy systems of discrete exponential equations over a land, which is a monoid without the requirement of associativity. In this paper we give a general methodology for signature scheme construction from noisy systems.