Научный семинар по криптографии (заседание 9) (Астана)
https://cryptography.kz/ru/%D0%BD%D0%B0%D1%83%D1%87%D0%BD%D1%8B%D0%B9-%D1%81%D0%B5%D0%BC%D0%B8%D0%BD%D0%B0%D1%80-%D0%BF%D0%BE-%D0%BA%D1%80%D0%B8%D0%BF%D1%82%D0%BE%D0%B3%D1%80%D0%B0%D1%84%D0%B8%D0%B8-(%D0%B7%D0%B0%D1%81%D0%B5%D0%B4%D0%B0%D0%BD%D0%B8%D0%B5-9)-(%D0%B0%D1%81%D1%82%D0%B0%D0%BD%D0%B0).html
https://cryptography.kz/ru/%D0%BD%D0%B0%D1%83%D1%87%D0%BD%D1%8B%D0%B9-%D1%81%D0%B5%D0%BC%D0%B8%D0%BD%D0%B0%D1%80-%D0%BF%D0%BE-%D0%BA%D1%80%D0%B8%D0%BF%D1%82%D0%BE%D0%B3%D1%80%D0%B0%D1%84%D0%B8%D0%B8-(%D0%B7%D0%B0%D1%81%D0%B5%D0%B4%D0%B0%D0%BD%D0%B8%D0%B5-9)-(%D0%B0%D1%81%D1%82%D0%B0%D0%BD%D0%B0).html
cryptography.kz
Cryptography - Научный семинар по криптографии (заседание 9) (Астана)
Improved Conditional Cube Attacks on Ascon AEADs in Nonce-Respecting Settings -- with a Break-Fix Strategy
https://iacr.org/news/item/23142
ePrint Report: Improved Conditional Cube Attacks on Ascon AEADs in Nonce-Respecting Settings -- with a Break-Fix Strategy
Kai Hu
The best-known distinguisher on 7-round Ascon-128 and Ascon-128a AEAD uses a 60-dimensional cube where the nonce bits are set to be equal in the third and fourth rows of the Ascon state during initialization (Rohit et al. ToSC 2021/1).
It was not known how to use this distinguisher to mount key-recovery attacks.
In this paper, we investigate this problem using a new strategy called \textit{break-fix} for the conditional cube attack. The idea is to introduce slightly-modified cubes which increase the degrees of 7-round output bits to be more than 59 (break phase) and then find key conditions which can bring the degree back to 59 (fix phase).
Using this idea, key-recovery attacks on 7-round Ascon-128, Ascon-128a and Ascon-80pq are proposed.
The attacks have better time/memory complexities than the existing attacks, and in some cases improve the weak-key attacks as well.
https://iacr.org/news/item/23142
ePrint Report: Improved Conditional Cube Attacks on Ascon AEADs in Nonce-Respecting Settings -- with a Break-Fix Strategy
Kai Hu
The best-known distinguisher on 7-round Ascon-128 and Ascon-128a AEAD uses a 60-dimensional cube where the nonce bits are set to be equal in the third and fourth rows of the Ascon state during initialization (Rohit et al. ToSC 2021/1).
It was not known how to use this distinguisher to mount key-recovery attacks.
In this paper, we investigate this problem using a new strategy called \textit{break-fix} for the conditional cube attack. The idea is to introduce slightly-modified cubes which increase the degrees of 7-round output bits to be more than 59 (break phase) and then find key conditions which can bring the degree back to 59 (fix phase).
Using this idea, key-recovery attacks on 7-round Ascon-128, Ascon-128a and Ascon-80pq are proposed.
The attacks have better time/memory complexities than the existing attacks, and in some cases improve the weak-key attacks as well.
Efficient Universally-Verifiable Electronic Voting with Everlasting Privacy
https://iacr.org/news/item/23141
ePrint Report: Efficient Universally-Verifiable Electronic Voting with Everlasting Privacy
David Pointcheval
Universal verifiability is a must-to-have for electronic voting schemes. It is essential to ensure honest behavior of all the players during the whole process, together with the eligibility. However, it should not endanger the privacy of the individual votes, which is another major requirement.
Whereas the first property prevents attacks during the voting process, privacy of the votes should hold forever, which has been called everlasting privacy.
A classical approach for universal verifiability is to add some proofs together with the encrypted votes, which requires publication of the latter, while eligibility needs a link between the votes and the voters: it definitely excludes long-term privacy. An alternative is the use of perfectly-hiding commitments, on which proofs are published, while ciphertexts are kept private for computing the tally.
In this paper, we show how recent linearly-homomorphic signatures can be exploited for all the proofs, leading to very efficient procedures towards universal verifiability with both strong receipt-freeness and everlasting privacy.
Privacy will indeed be unconditional, after the publication of the results and the proofs, whereas the soundness of the proofs holds in the algebraic group model and the random oracle model.
https://iacr.org/news/item/23141
ePrint Report: Efficient Universally-Verifiable Electronic Voting with Everlasting Privacy
David Pointcheval
Universal verifiability is a must-to-have for electronic voting schemes. It is essential to ensure honest behavior of all the players during the whole process, together with the eligibility. However, it should not endanger the privacy of the individual votes, which is another major requirement.
Whereas the first property prevents attacks during the voting process, privacy of the votes should hold forever, which has been called everlasting privacy.
A classical approach for universal verifiability is to add some proofs together with the encrypted votes, which requires publication of the latter, while eligibility needs a link between the votes and the voters: it definitely excludes long-term privacy. An alternative is the use of perfectly-hiding commitments, on which proofs are published, while ciphertexts are kept private for computing the tally.
In this paper, we show how recent linearly-homomorphic signatures can be exploited for all the proofs, leading to very efficient procedures towards universal verifiability with both strong receipt-freeness and everlasting privacy.
Privacy will indeed be unconditional, after the publication of the results and the proofs, whereas the soundness of the proofs holds in the algebraic group model and the random oracle model.
A Deniability Analysis of Signal's Initial Handshake PQXDH
https://iacr.org/news/item/23140
ePrint Report: A Deniability Analysis of Signal's Initial Handshake PQXDH
Rune Fiedler, Christian Janson
Many use messaging apps such as Signal to exercise their right to private communication. To cope with the advent of quantum computing, Signal employs a new initial handshake protocol called PQXDH for post-quantum confidentiality, yet keeps guarantees of authenticity and deniability classical. Compared to its predecessor X3DH, PQXDH includes a KEM encapsulation and a signature on the ephemeral key. In this work we show that PQXDH does not meet the same deniability guarantees as X3DH due to the signature on the ephemeral key. Our analysis relies on plaintext awareness of the KEM, which Signal's implementation of PQXDH does not provide. As for X3DH, both parties (initiator and responder) obtain different deniability guarantees due to the asymmetry of the protocol.
For our analysis of PQXDH, we introduce a new model for deniability of key exchange that allows a more fine-grained analysis. Our deniability model picks up on the ideas of prior work and facilitates new combinations of deniability notions, such as deniability against malicious adversaries in the big brother model, i.e. where the distinguisher knows all secret keys. Our model may be of independent interest.
https://iacr.org/news/item/23140
ePrint Report: A Deniability Analysis of Signal's Initial Handshake PQXDH
Rune Fiedler, Christian Janson
Many use messaging apps such as Signal to exercise their right to private communication. To cope with the advent of quantum computing, Signal employs a new initial handshake protocol called PQXDH for post-quantum confidentiality, yet keeps guarantees of authenticity and deniability classical. Compared to its predecessor X3DH, PQXDH includes a KEM encapsulation and a signature on the ephemeral key. In this work we show that PQXDH does not meet the same deniability guarantees as X3DH due to the signature on the ephemeral key. Our analysis relies on plaintext awareness of the KEM, which Signal's implementation of PQXDH does not provide. As for X3DH, both parties (initiator and responder) obtain different deniability guarantees due to the asymmetry of the protocol.
For our analysis of PQXDH, we introduce a new model for deniability of key exchange that allows a more fine-grained analysis. Our deniability model picks up on the ideas of prior work and facilitates new combinations of deniability notions, such as deniability against malicious adversaries in the big brother model, i.e. where the distinguisher knows all secret keys. Our model may be of independent interest.
Multi-Client Functional Encryption with Public Inputs and Strong Security
https://iacr.org/news/item/23139
ePrint Report: Multi-Client Functional Encryption with Public Inputs and Strong Security
Ky Nguyen, Duong Hieu Phan, David Pointcheval
Recent years have witnessed a significant development for functional encryption (FE) in the multi-user setting, particularly with multi-client functional encryption (MCFE). The challenge becomes more important when combined with access control, such as attribute-based encryption (ABE), which was actually not covered by the FE and MCFE frameworks. On the other hand, as for complex primitives, many works have studied the admissibility of adversaries to ensure that the security model encompasses all real threats of attacks.
In this paper, adding a public input to FE/MCFE, we cover many previous primitives, notably attribute-based function classes. Furthermore, with the strongest admissibility for inner-product functionality, our framework is quite versatile, as it encrypts multiple sub-vectors, allows repetitions and corruptions, and eventually also encompasses public-key FE and classical ABE, bridging the private setting of MCFE with the public setting of FE and ABE.
Finally, we propose an MCFE with public inputs with the class of functions that combines inner-products (on private inputs) and attribute-based access-control (on public inputs) for LSSS policies. We achieve the first AB-MCFE for inner-products with strong admissibility and with adaptive security. This also leads to MIFE for inner products, public-key single-input inner-product FE with LSSS key-policy and KPABE for LSSS, with adaptive security while the previous AB-MCFE construction of Agrawal et al. from CRYPTO '23 considers a slightly larger functionality of average weighted sum but with selective security only.
https://iacr.org/news/item/23139
ePrint Report: Multi-Client Functional Encryption with Public Inputs and Strong Security
Ky Nguyen, Duong Hieu Phan, David Pointcheval
Recent years have witnessed a significant development for functional encryption (FE) in the multi-user setting, particularly with multi-client functional encryption (MCFE). The challenge becomes more important when combined with access control, such as attribute-based encryption (ABE), which was actually not covered by the FE and MCFE frameworks. On the other hand, as for complex primitives, many works have studied the admissibility of adversaries to ensure that the security model encompasses all real threats of attacks.
In this paper, adding a public input to FE/MCFE, we cover many previous primitives, notably attribute-based function classes. Furthermore, with the strongest admissibility for inner-product functionality, our framework is quite versatile, as it encrypts multiple sub-vectors, allows repetitions and corruptions, and eventually also encompasses public-key FE and classical ABE, bridging the private setting of MCFE with the public setting of FE and ABE.
Finally, we propose an MCFE with public inputs with the class of functions that combines inner-products (on private inputs) and attribute-based access-control (on public inputs) for LSSS policies. We achieve the first AB-MCFE for inner-products with strong admissibility and with adaptive security. This also leads to MIFE for inner products, public-key single-input inner-product FE with LSSS key-policy and KPABE for LSSS, with adaptive security while the previous AB-MCFE construction of Agrawal et al. from CRYPTO '23 considers a slightly larger functionality of average weighted sum but with selective security only.
BGJ15 Revisited: Sieving with Streamed Memory Access
https://iacr.org/news/item/23138
ePrint Report: BGJ15 Revisited: Sieving with Streamed Memory Access
Ziyu Zhao, Jintai Ding, Bo-Yin Yang
The focus of this paper is to tackle the issue of memory access within sieving algorithms for lattice problems. We have conducted an in-depth analysis of an optimized BGJ sieve (Becker-Gama-Joux 2015), and our findings suggest that its inherent structure is significantly more memory-efficient compared to the asymptotically fastest BDGL sieve (Becker-Ducas-Gama-Laarhoven 2016). Specifically, it necessitates merely $2^{0.2075n + o(n)}$ streamed (non-random) main memory accesses for the execution of an $n$-dimensional sieving. We also provide evidence that the time complexity of this refined BGJ sieve could potentially be $2^{0.292n + o(n)}$, or at least something remarkably close to it. Actually, it outperforms the BDGL sieve in all dimensions that are practically achievable. We hope that this study will contribute to the resolution of the ongoing debate regarding the measurement of RAM access overhead in large-scale, sieving-based lattice attacks.
The concept above is also supported by our implementation. Actually, we provide a highly efficient, both in terms of time and memory, CPU-based implementation of the refined BGJ sieve within an optimized sieving framework. This implementation results in approximately 40% savings in RAM usage and is at least $2^{4.5}$ times more efficient in terms of gate count compared to the previous 4-GPU implementation (Ducas-Stevens-Woerden 2021). Notably, we have successfully solved the 183-dimensional SVP Darmstadt Challenge in 30 days using a 112-core server and approximately 0.87TB of RAM. The majority of previous sieving-based SVP computations relied on the HK3-sieve (Herold-Kirshanova 2017), hence this implementation could offer further insights into the behavior of these asymptotically faster sieving algorithms when applied to large-scale problems. Moreover, our refined cost estimation of SVP based on this implementation suggests that some of the NIST PQC candidates, such as Falcon-512, are unlikely to achieve NIST's security requirements.
https://iacr.org/news/item/23138
ePrint Report: BGJ15 Revisited: Sieving with Streamed Memory Access
Ziyu Zhao, Jintai Ding, Bo-Yin Yang
The focus of this paper is to tackle the issue of memory access within sieving algorithms for lattice problems. We have conducted an in-depth analysis of an optimized BGJ sieve (Becker-Gama-Joux 2015), and our findings suggest that its inherent structure is significantly more memory-efficient compared to the asymptotically fastest BDGL sieve (Becker-Ducas-Gama-Laarhoven 2016). Specifically, it necessitates merely $2^{0.2075n + o(n)}$ streamed (non-random) main memory accesses for the execution of an $n$-dimensional sieving. We also provide evidence that the time complexity of this refined BGJ sieve could potentially be $2^{0.292n + o(n)}$, or at least something remarkably close to it. Actually, it outperforms the BDGL sieve in all dimensions that are practically achievable. We hope that this study will contribute to the resolution of the ongoing debate regarding the measurement of RAM access overhead in large-scale, sieving-based lattice attacks.
The concept above is also supported by our implementation. Actually, we provide a highly efficient, both in terms of time and memory, CPU-based implementation of the refined BGJ sieve within an optimized sieving framework. This implementation results in approximately 40% savings in RAM usage and is at least $2^{4.5}$ times more efficient in terms of gate count compared to the previous 4-GPU implementation (Ducas-Stevens-Woerden 2021). Notably, we have successfully solved the 183-dimensional SVP Darmstadt Challenge in 30 days using a 112-core server and approximately 0.87TB of RAM. The majority of previous sieving-based SVP computations relied on the HK3-sieve (Herold-Kirshanova 2017), hence this implementation could offer further insights into the behavior of these asymptotically faster sieving algorithms when applied to large-scale problems. Moreover, our refined cost estimation of SVP based on this implementation suggests that some of the NIST PQC candidates, such as Falcon-512, are unlikely to achieve NIST's security requirements.
Quantum Key-Revocable Dual-Regev Encryption, Revisited
https://iacr.org/news/item/23137
ePrint Report: Quantum Key-Revocable Dual-Regev Encryption, Revisited
Prabhanjan Ananth, Zihan Hu, Zikuan Huang
Quantum information can be used to achieve novel cryptographic primitives that are impossible to achieve classically. A recent work by Ananth, Poremba, Vaikuntanathan (TCC 2023) focuses on equipping the dual-Regev encryption scheme, introduced by Gentry, Peikert, Vaikuntanathan (STOC 2008), with key revocation capabilities using quantum information. They further showed that the key-revocable dual-Regev scheme implies the existence of fully homomorphic encryption and pseudorandom functions, with both of them also equipped with key revocation capabilities. Unfortunately, they were only able to prove the security of their schemes based on new conjectures and left open the problem of basing the security of key revocable dual-Regev encryption on well-studied assumptions.
In this work, we resolve this open problem. Assuming polynomial hardness of learning with errors (over sub-exponential modulus), we show that key-revocable dual-Regev encryption is secure. As a consequence, for the first time, we achieve the following results:
1. Key-revocable public-key encryption and key-revocable fully-homomorphic encryption satisfying classical revocation security and based on polynomial hardness of learning with errors. Prior works either did not achieve classical revocation or were based on sub-exponential hardness of learning with errors.
2. Key-revocable pseudorandom functions satisfying classical revocation from the polynomial hardness of learning with errors. Prior works relied upon unproven conjectures.
https://iacr.org/news/item/23137
ePrint Report: Quantum Key-Revocable Dual-Regev Encryption, Revisited
Prabhanjan Ananth, Zihan Hu, Zikuan Huang
Quantum information can be used to achieve novel cryptographic primitives that are impossible to achieve classically. A recent work by Ananth, Poremba, Vaikuntanathan (TCC 2023) focuses on equipping the dual-Regev encryption scheme, introduced by Gentry, Peikert, Vaikuntanathan (STOC 2008), with key revocation capabilities using quantum information. They further showed that the key-revocable dual-Regev scheme implies the existence of fully homomorphic encryption and pseudorandom functions, with both of them also equipped with key revocation capabilities. Unfortunately, they were only able to prove the security of their schemes based on new conjectures and left open the problem of basing the security of key revocable dual-Regev encryption on well-studied assumptions.
In this work, we resolve this open problem. Assuming polynomial hardness of learning with errors (over sub-exponential modulus), we show that key-revocable dual-Regev encryption is secure. As a consequence, for the first time, we achieve the following results:
1. Key-revocable public-key encryption and key-revocable fully-homomorphic encryption satisfying classical revocation security and based on polynomial hardness of learning with errors. Prior works either did not achieve classical revocation or were based on sub-exponential hardness of learning with errors.
2. Key-revocable pseudorandom functions satisfying classical revocation from the polynomial hardness of learning with errors. Prior works relied upon unproven conjectures.
Mutable Batch Arguments and Applications
https://iacr.org/news/item/23136
ePrint Report: Mutable Batch Arguments and Applications
Rishab Goyal
Non-interactive batch arguments (BARGs) let a prover compute a single proof $\pi$ proving validity of a `batch' of $k$ $\mathbf{NP}$ statements $x_1, \ldots, x_{k}$. The two central features of BARGs are succinctness and soundness. Succinctness states that proof size, $|\pi|$ does not grow with $k$; while soundness states a polytime cheating prover cannot create an accepting proof for any invalid batch of statements.
In this work, we put forth a new concept of mutability for batch arguments, called mutable batch arguments. Our goal is to re-envision how we think about and use BARGs. Traditionally, a BARG proof string $\pi$ is an immutable encoding of $k$ $\mathbf{NP}$ witness $\omega_1, \ldots, \omega_{k}$. In a mutable BARG system, each proof string $\pi$ is a mutable encoding of original witnesses. Thus, a mutable BARG captures and enables computations over a batch proof $\pi$. We also study new privacy notions for mutable BARGs, guaranteeing that a mutated proof hides all non-trivial information. Such mutable BARGs are a naturally good fit for many privacy sensitive applications.
Our main contributions can be summarized as introducing the general concept of mutable BARGs, identifying new non-trivial classes of feasible mutations over BARGs, designing new constructions for mutable BARGs satisfying mutation privacy for these classes from standard cryptographic assumptions, and developing applications of mutable BARGs to advanced signatures such as homomorphic signatures, redactable signatures, and aggregate signatures. Our results improve state-of-the-art known for many such signature systems either in terms of functionality, efficiency, security, or versatility (in terms of cryptographic assumptions).
https://iacr.org/news/item/23136
ePrint Report: Mutable Batch Arguments and Applications
Rishab Goyal
Non-interactive batch arguments (BARGs) let a prover compute a single proof $\pi$ proving validity of a `batch' of $k$ $\mathbf{NP}$ statements $x_1, \ldots, x_{k}$. The two central features of BARGs are succinctness and soundness. Succinctness states that proof size, $|\pi|$ does not grow with $k$; while soundness states a polytime cheating prover cannot create an accepting proof for any invalid batch of statements.
In this work, we put forth a new concept of mutability for batch arguments, called mutable batch arguments. Our goal is to re-envision how we think about and use BARGs. Traditionally, a BARG proof string $\pi$ is an immutable encoding of $k$ $\mathbf{NP}$ witness $\omega_1, \ldots, \omega_{k}$. In a mutable BARG system, each proof string $\pi$ is a mutable encoding of original witnesses. Thus, a mutable BARG captures and enables computations over a batch proof $\pi$. We also study new privacy notions for mutable BARGs, guaranteeing that a mutated proof hides all non-trivial information. Such mutable BARGs are a naturally good fit for many privacy sensitive applications.
Our main contributions can be summarized as introducing the general concept of mutable BARGs, identifying new non-trivial classes of feasible mutations over BARGs, designing new constructions for mutable BARGs satisfying mutation privacy for these classes from standard cryptographic assumptions, and developing applications of mutable BARGs to advanced signatures such as homomorphic signatures, redactable signatures, and aggregate signatures. Our results improve state-of-the-art known for many such signature systems either in terms of functionality, efficiency, security, or versatility (in terms of cryptographic assumptions).
Secret Sharing with Certified Deletion
https://iacr.org/news/item/23135
ePrint Report: Secret Sharing with Certified Deletion
James Bartusek, Justin Raizes
Secret sharing allows a user to split a secret into many shares so that the secret can be recovered if, and only if, an authorized set of shares is collected. Although secret sharing typically does not require any computational hardness assumptions, its security does require that an adversary cannot collect an authorized set of shares. Over long periods of time where an adversary can benefit from multiple data breaches, this may become an unrealistic assumption.
We initiate the systematic study of secret sharing with certified deletion in order to achieve security even against an adversary that eventually collects an authorized set of shares. In secret sharing with certified deletion, a (classical) secret $s$ is split into quantum shares that can be destroyed in a manner verifiable by the dealer.
We put forth two natural definitions of security. No-signaling security roughly requires that if multiple non-communicating adversaries delete sufficiently many shares, then their combined view contains negligible information about $s$, even if the total set of corrupted parties forms an authorized set. Adaptive security requires privacy of $s$ against an adversary that can continuously and adaptively corrupt new shares and delete previously-corrupted shares, as long as the total set of corrupted shares minus deleted shares remains unauthorized.
Next, we show that these security definitions are achievable: we show how to construct (i) a secret sharing scheme with no-signaling certified deletion for any monotone access structure, and (ii) a threshold secret sharing scheme with adaptive certified deletion. Our first construction uses Bartusek and Khurana's (CRYPTO 2023) 2-out-of-2 secret sharing scheme with certified deletion as a building block, while our second construction is built from scratch and requires several new technical ideas. For example, we significantly generalize the ``XOR extractor'' of Agarwal, Bartusek, Khurana, and Kumar (EUROCRYPT 2023) in order to obtain better seedless extraction from certain quantum sources of entropy, and show how polynomial interpolation can double as a high-rate randomness extractor in our context of threshold sharing with certified deletion.
https://iacr.org/news/item/23135
ePrint Report: Secret Sharing with Certified Deletion
James Bartusek, Justin Raizes
Secret sharing allows a user to split a secret into many shares so that the secret can be recovered if, and only if, an authorized set of shares is collected. Although secret sharing typically does not require any computational hardness assumptions, its security does require that an adversary cannot collect an authorized set of shares. Over long periods of time where an adversary can benefit from multiple data breaches, this may become an unrealistic assumption.
We initiate the systematic study of secret sharing with certified deletion in order to achieve security even against an adversary that eventually collects an authorized set of shares. In secret sharing with certified deletion, a (classical) secret $s$ is split into quantum shares that can be destroyed in a manner verifiable by the dealer.
We put forth two natural definitions of security. No-signaling security roughly requires that if multiple non-communicating adversaries delete sufficiently many shares, then their combined view contains negligible information about $s$, even if the total set of corrupted parties forms an authorized set. Adaptive security requires privacy of $s$ against an adversary that can continuously and adaptively corrupt new shares and delete previously-corrupted shares, as long as the total set of corrupted shares minus deleted shares remains unauthorized.
Next, we show that these security definitions are achievable: we show how to construct (i) a secret sharing scheme with no-signaling certified deletion for any monotone access structure, and (ii) a threshold secret sharing scheme with adaptive certified deletion. Our first construction uses Bartusek and Khurana's (CRYPTO 2023) 2-out-of-2 secret sharing scheme with certified deletion as a building block, while our second construction is built from scratch and requires several new technical ideas. For example, we significantly generalize the ``XOR extractor'' of Agarwal, Bartusek, Khurana, and Kumar (EUROCRYPT 2023) in order to obtain better seedless extraction from certain quantum sources of entropy, and show how polynomial interpolation can double as a high-rate randomness extractor in our context of threshold sharing with certified deletion.
Secure Multiparty Computation in the Presence of Covert Adaptive Adversaries
https://iacr.org/news/item/23134
ePrint Report: Secure Multiparty Computation in the Presence of Covert Adaptive Adversaries
Isheeta Nargis, Anwar Hasan
We design a new MPC protocol for arithmetic circuits secure against erasure-free covert adaptive adversaries with deterrence 1/2. The new MPC protocol has the same asymptotic communication cost, the number of PKE operations and the number of exponentiation operations as the most efficient MPC protocol for arithmetic circuits secure against covert static adversaries. That means, the new MPC protocol improves security from covert static security to covert adaptive adversary almost for free. For MPC problems where the number of parties n is much larger than the number of multiplication gates M, the new MPC protocol asymptotically improves communication complexity over the most efficient MPC protocol for arithmetic circuits secure against erasure-free active adaptive adversaries.
https://iacr.org/news/item/23134
ePrint Report: Secure Multiparty Computation in the Presence of Covert Adaptive Adversaries
Isheeta Nargis, Anwar Hasan
We design a new MPC protocol for arithmetic circuits secure against erasure-free covert adaptive adversaries with deterrence 1/2. The new MPC protocol has the same asymptotic communication cost, the number of PKE operations and the number of exponentiation operations as the most efficient MPC protocol for arithmetic circuits secure against covert static adversaries. That means, the new MPC protocol improves security from covert static security to covert adaptive adversary almost for free. For MPC problems where the number of parties n is much larger than the number of multiplication gates M, the new MPC protocol asymptotically improves communication complexity over the most efficient MPC protocol for arithmetic circuits secure against erasure-free active adaptive adversaries.
Proof of Stake and Activity: Rewarding On-Chain Activity Through Consensus
https://iacr.org/news/item/23133
ePrint Report: Proof of Stake and Activity: Rewarding On-Chain Activity Through Consensus
Aram Jivanyan, Karen Terjanian
We are introducing a novel consensus protocol for
blockchain, called Proof of Stake and Activity (PoSA) which can
augment the traditional Proof of Stake methods by integrating
a unique Proof of Activity system. PoSA offers a compelling
economic model that promotes decentralization by rewarding
validators based on their staked capital and also the business
value they contribute to the chain. This protocol has been
implemented already into a fully-fledged blockchain platform
called Bahamut (www.bahamut.io) which boasts hundreds of thousands of active users already.
https://iacr.org/news/item/23133
ePrint Report: Proof of Stake and Activity: Rewarding On-Chain Activity Through Consensus
Aram Jivanyan, Karen Terjanian
We are introducing a novel consensus protocol for
blockchain, called Proof of Stake and Activity (PoSA) which can
augment the traditional Proof of Stake methods by integrating
a unique Proof of Activity system. PoSA offers a compelling
economic model that promotes decentralization by rewarding
validators based on their staked capital and also the business
value they contribute to the chain. This protocol has been
implemented already into a fully-fledged blockchain platform
called Bahamut (www.bahamut.io) which boasts hundreds of thousands of active users already.
Proxying is Enough: Security of Proxying in TLS Oracles and AEAD Context Unforgeability
https://iacr.org/news/item/23132
ePrint Report: Proxying is Enough: Security of Proxying in TLS Oracles and AEAD Context Unforgeability
Zhongtang Luo, Yanxue Jia, Yaobin Shen, Aniket Kate
TLS oracles allow a TLS client to offer selective data provenance to an external (oracle) node such that the oracle node is ensured that the data is indeed coming from a pre-defined TLS server. Typically, the client/user supplies their credentials and reveals data in a zero-knowledge manner to demonstrate certain information to oracles while ensuring the privacy of the rest of the data. Conceptually, this is a standard three-party secure computation between the TLS server, TLS client (prover), and the oracle (verifier) node; however, the key practical requirement for TLS oracles to ensure that data provenance process remains transparent to the TLS server. Recent TLS oracle protocols such as DECO enforce the communication pattern of server-client-verifier and utilize a novel three-party handshake process during TLS to ensure data integrity against potential tempering by the client. However, this approach comes with a significant performance penalty on the client/prover and the verifier and raises the question if it is possible to improve the performance by putting the verifier (as a proxy) between the server and the client such that the correct TLS transcript is always available to the verifier.
This work offers both positive and negative answers to this oracle proxy question: We first formalize the oracle proxy notion that allows the verifier to directly proxy client-server TLS communication, without entering a three-party handshake or interfering with the connection in any way. We then show that for common TLS-based higher-level protocols such as HTTPS, data integrity to the verifier proxy is ensured by the variable padding built into the HTTP protocol semantics. On the other hand, if a TLS-based protocol comes without variable padding, we demonstrate that data integrity cannot be guaranteed. In this context, we then study the case where the TLS response is pre-determined and cannot be tampered with during the connection. We propose the concept of context unforgeability and show allows overcoming the impossibility. We further show that ChaCha20-Poly1305 satisfies the concept while AES-GCM does not under the standard model.
https://iacr.org/news/item/23132
ePrint Report: Proxying is Enough: Security of Proxying in TLS Oracles and AEAD Context Unforgeability
Zhongtang Luo, Yanxue Jia, Yaobin Shen, Aniket Kate
TLS oracles allow a TLS client to offer selective data provenance to an external (oracle) node such that the oracle node is ensured that the data is indeed coming from a pre-defined TLS server. Typically, the client/user supplies their credentials and reveals data in a zero-knowledge manner to demonstrate certain information to oracles while ensuring the privacy of the rest of the data. Conceptually, this is a standard three-party secure computation between the TLS server, TLS client (prover), and the oracle (verifier) node; however, the key practical requirement for TLS oracles to ensure that data provenance process remains transparent to the TLS server. Recent TLS oracle protocols such as DECO enforce the communication pattern of server-client-verifier and utilize a novel three-party handshake process during TLS to ensure data integrity against potential tempering by the client. However, this approach comes with a significant performance penalty on the client/prover and the verifier and raises the question if it is possible to improve the performance by putting the verifier (as a proxy) between the server and the client such that the correct TLS transcript is always available to the verifier.
This work offers both positive and negative answers to this oracle proxy question: We first formalize the oracle proxy notion that allows the verifier to directly proxy client-server TLS communication, without entering a three-party handshake or interfering with the connection in any way. We then show that for common TLS-based higher-level protocols such as HTTPS, data integrity to the verifier proxy is ensured by the variable padding built into the HTTP protocol semantics. On the other hand, if a TLS-based protocol comes without variable padding, we demonstrate that data integrity cannot be guaranteed. In this context, we then study the case where the TLS response is pre-determined and cannot be tampered with during the connection. We propose the concept of context unforgeability and show allows overcoming the impossibility. We further show that ChaCha20-Poly1305 satisfies the concept while AES-GCM does not under the standard model.
New Solutions to Delsarte's Dual Linear Programs
https://eprint.iacr.org/2024/730
Understanding the maximum size of a code with a given minimum distance is a major question in computer science and discrete mathematics. The most fruitful approach for finding asymptotic bounds on such codes is by using Delsarte's theory of association schemes. With this approach, Delsarte constructs a linear program such that its maximum value is an upper bound on the maximum size of a code with a given minimum distance. Bounding this value can be done by finding solutions to the corresponding dual linear program. Delsarte's theory is very general and goes way beyond binary codes.
In this work, we provide universal bounds in the framework of association schemes that generalize the Hamming bound and the Elias-Bassalygo bound, which can be applied to any association scheme constructed from a distance function. These bounds are obtained by constructing new solutions to Delsarte's dual linear program. We instantiate these results and we recover known bounds for $q$-ary codes and for constant-weight binary codes but which didn't come from the linear program method. Our other contribution is to recover, for essentially any $Q$-polynomial scheme, MRRW-type solutions to Delsarte's dual linear program which are inspired by the Laplacian approach of Friedman and Tillich instead of using the Christoffel-Darboux formulas. We show in particular how the second linear programming bound can be interpreted in this framework.
https://eprint.iacr.org/2024/730
Understanding the maximum size of a code with a given minimum distance is a major question in computer science and discrete mathematics. The most fruitful approach for finding asymptotic bounds on such codes is by using Delsarte's theory of association schemes. With this approach, Delsarte constructs a linear program such that its maximum value is an upper bound on the maximum size of a code with a given minimum distance. Bounding this value can be done by finding solutions to the corresponding dual linear program. Delsarte's theory is very general and goes way beyond binary codes.
In this work, we provide universal bounds in the framework of association schemes that generalize the Hamming bound and the Elias-Bassalygo bound, which can be applied to any association scheme constructed from a distance function. These bounds are obtained by constructing new solutions to Delsarte's dual linear program. We instantiate these results and we recover known bounds for $q$-ary codes and for constant-weight binary codes but which didn't come from the linear program method. Our other contribution is to recover, for essentially any $Q$-polynomial scheme, MRRW-type solutions to Delsarte's dual linear program which are inspired by the Laplacian approach of Friedman and Tillich instead of using the Christoffel-Darboux formulas. We show in particular how the second linear programming bound can be interpreted in this framework.
Tight Security of Double-Block Nonce-Based MACs
https://eprint.iacr.org/2024/731
In this paper, we study the security of MAC constructions among those classified by Chen et al. in ASIACRYPT '21. Precisely, $F^{\text{EDM}}_{B_2}$ (or $\mathsf{EWCDM}$ as named by Cogliati and Seurin in CRYPTO '16), $F^{\text{EDM}}_{B_3}$, $F^{\text{SoP}}_{B_2}$, $F^{\text{SoP}}_{B_3}$ (all as named by Chen et al.) are proved to be fully secure up to $2^n$ MAC queries in the nonce-respecting setting, improving the previous bound of $\frac{3n}{4}$-bit security. In particular, $F^{\text{SoP}}_{B_2}$ and $F^{\text{SoP}}_{B_3}$ enjoy graceful degradation as the number of queries with repeated nonces grows (when the underlying universal hash function satisfies a certain property called multi-xor-collision resistance). To do this, we develop a new tool, namely extended Mirror theory based on two independent permutations to a wide range of $\xi_{\max}$ including inequalities. Furthermore, we give a generic semi-black-box reduction from single-user security bound in the standard model to multi-user security bound in the ideal cipher model, yielding significantly better bounds than the naive hybrid argument. This reduction is applicable to all MAC construction we considered in this paper and even can be more generalized.
We also present matching attacks on $F^{\text{EDM}}_{B_4}$ and $F^{\text{EDM}}_{B_5}$ using $O(2^{3n/4})$ MAC queries and $O(1)$ verification query without using repeated nonces.
https://eprint.iacr.org/2024/731
In this paper, we study the security of MAC constructions among those classified by Chen et al. in ASIACRYPT '21. Precisely, $F^{\text{EDM}}_{B_2}$ (or $\mathsf{EWCDM}$ as named by Cogliati and Seurin in CRYPTO '16), $F^{\text{EDM}}_{B_3}$, $F^{\text{SoP}}_{B_2}$, $F^{\text{SoP}}_{B_3}$ (all as named by Chen et al.) are proved to be fully secure up to $2^n$ MAC queries in the nonce-respecting setting, improving the previous bound of $\frac{3n}{4}$-bit security. In particular, $F^{\text{SoP}}_{B_2}$ and $F^{\text{SoP}}_{B_3}$ enjoy graceful degradation as the number of queries with repeated nonces grows (when the underlying universal hash function satisfies a certain property called multi-xor-collision resistance). To do this, we develop a new tool, namely extended Mirror theory based on two independent permutations to a wide range of $\xi_{\max}$ including inequalities. Furthermore, we give a generic semi-black-box reduction from single-user security bound in the standard model to multi-user security bound in the ideal cipher model, yielding significantly better bounds than the naive hybrid argument. This reduction is applicable to all MAC construction we considered in this paper and even can be more generalized.
We also present matching attacks on $F^{\text{EDM}}_{B_4}$ and $F^{\text{EDM}}_{B_5}$ using $O(2^{3n/4})$ MAC queries and $O(1)$ verification query without using repeated nonces.
Compact Encryption based on Module-NTRU problems
https://eprint.iacr.org/2024/732
The Module-NTRU problem, introduced by Cheon, Kim,
Kim, Son (IACR ePrint 2019/1468), and Chuengsatiansup, Prest, Stehlé,
Wallet, Xagawa (ASIACCS ’20), generalizes the versatile NTRU assump-
tion. One of its main advantages lies in its ability to offer greater flexibil-
ity on parameters, such as the underlying ring dimension. In this work,
we present several lattice-based encryption schemes, which are IND-CPA
(or OW-CPA) secure in the standard model based on the Module-NTRU
and Module-LWE problems. Leveraging the Fujisaki-Okamoto transfor-
mations, one can obtain IND-CCA secure key encapsulation schemes.
Our first encryption scheme is based on the Module-NTRU assumption,
which uses the determinant of the secret matrix over the underlying ring
for the decryption. Our second scheme is analogue to the Module-LWE
encryption scheme, but uses only a matrix as the public key, based on a
vectorial variant of the Module-NTRU problem. In the end, we conduct
comprehensive analysis of known attacks and propose concrete parame-
ters for the instantiations. In particular, our ciphertext size is about 614
(resp. 1228) bytes for NIST Level 1 (resp. Level 5) security and small
decryption failure, placing it on par with the most recent schemes such as
the one proposed by Zhang, Feng and Yan (ASIACRYPT ’23). We also
present several competitive parameters for NIST Level 3, which has a ci-
phertext size of 921 bytes. Moreover, our schemes do not require specific
codes for plaintext encoding and decoding.
https://eprint.iacr.org/2024/732
The Module-NTRU problem, introduced by Cheon, Kim,
Kim, Son (IACR ePrint 2019/1468), and Chuengsatiansup, Prest, Stehlé,
Wallet, Xagawa (ASIACCS ’20), generalizes the versatile NTRU assump-
tion. One of its main advantages lies in its ability to offer greater flexibil-
ity on parameters, such as the underlying ring dimension. In this work,
we present several lattice-based encryption schemes, which are IND-CPA
(or OW-CPA) secure in the standard model based on the Module-NTRU
and Module-LWE problems. Leveraging the Fujisaki-Okamoto transfor-
mations, one can obtain IND-CCA secure key encapsulation schemes.
Our first encryption scheme is based on the Module-NTRU assumption,
which uses the determinant of the secret matrix over the underlying ring
for the decryption. Our second scheme is analogue to the Module-LWE
encryption scheme, but uses only a matrix as the public key, based on a
vectorial variant of the Module-NTRU problem. In the end, we conduct
comprehensive analysis of known attacks and propose concrete parame-
ters for the instantiations. In particular, our ciphertext size is about 614
(resp. 1228) bytes for NIST Level 1 (resp. Level 5) security and small
decryption failure, placing it on par with the most recent schemes such as
the one proposed by Zhang, Feng and Yan (ASIACRYPT ’23). We also
present several competitive parameters for NIST Level 3, which has a ci-
phertext size of 921 bytes. Moreover, our schemes do not require specific
codes for plaintext encoding and decoding.
Proxying is Enough: Security of Proxying in TLS Oracles and AEAD Context Unforgeability
https://eprint.iacr.org/2024/733
TLS oracles allow a TLS client to offer selective data provenance to an external (oracle) node such that the oracle node is ensured that the data is indeed coming from a pre-defined TLS server. Typically, the client/user supplies their credentials and reveals data in a zero-knowledge manner to demonstrate certain information to oracles while ensuring the privacy of the rest of the data. Conceptually, this is a standard three-party secure computation between the TLS server, TLS client (prover), and the oracle (verifier) node; however, the key practical requirement for TLS oracles to ensure that data provenance process remains transparent to the TLS server. Recent TLS oracle protocols such as DECO enforce the communication pattern of server-client-verifier and utilize a novel three-party handshake process during TLS to ensure data integrity against potential tempering by the client. However, this approach comes with a significant performance penalty on the client/prover and the verifier and raises the question if it is possible to improve the performance by putting the verifier (as a proxy) between the server and the client such that the correct TLS transcript is always available to the verifier.
This work offers both positive and negative answers to this oracle proxy question: We first formalize the oracle proxy notion that allows the verifier to directly proxy client-server TLS communication, without entering a three-party handshake or interfering with the connection in any way. We then show that for common TLS-based higher-level protocols such as HTTPS, data integrity to the verifier proxy is ensured by the variable padding built into the HTTP protocol semantics. On the other hand, if a TLS-based protocol comes without variable padding, we demonstrate that data integrity cannot be guaranteed. In this context, we then study the case where the TLS response is pre-determined and cannot be tampered with during the connection. We propose the concept of context unforgeability and show allows overcoming the impossibility. We further show that ChaCha20-Poly1305 satisfies the concept while AES-GCM does not under the standard model.
https://eprint.iacr.org/2024/733
TLS oracles allow a TLS client to offer selective data provenance to an external (oracle) node such that the oracle node is ensured that the data is indeed coming from a pre-defined TLS server. Typically, the client/user supplies their credentials and reveals data in a zero-knowledge manner to demonstrate certain information to oracles while ensuring the privacy of the rest of the data. Conceptually, this is a standard three-party secure computation between the TLS server, TLS client (prover), and the oracle (verifier) node; however, the key practical requirement for TLS oracles to ensure that data provenance process remains transparent to the TLS server. Recent TLS oracle protocols such as DECO enforce the communication pattern of server-client-verifier and utilize a novel three-party handshake process during TLS to ensure data integrity against potential tempering by the client. However, this approach comes with a significant performance penalty on the client/prover and the verifier and raises the question if it is possible to improve the performance by putting the verifier (as a proxy) between the server and the client such that the correct TLS transcript is always available to the verifier.
This work offers both positive and negative answers to this oracle proxy question: We first formalize the oracle proxy notion that allows the verifier to directly proxy client-server TLS communication, without entering a three-party handshake or interfering with the connection in any way. We then show that for common TLS-based higher-level protocols such as HTTPS, data integrity to the verifier proxy is ensured by the variable padding built into the HTTP protocol semantics. On the other hand, if a TLS-based protocol comes without variable padding, we demonstrate that data integrity cannot be guaranteed. In this context, we then study the case where the TLS response is pre-determined and cannot be tampered with during the connection. We propose the concept of context unforgeability and show allows overcoming the impossibility. We further show that ChaCha20-Poly1305 satisfies the concept while AES-GCM does not under the standard model.
Proof of Stake and Activity: Rewarding On-Chain Activity Through Consensus
https://eprint.iacr.org/2024/734
We are introducing a novel consensus protocol for
blockchain, called Proof of Stake and Activity (PoSA) which can
augment the traditional Proof of Stake methods by integrating
a unique Proof of Activity system. PoSA offers a compelling
economic model that promotes decentralization by rewarding
validators based on their staked capital and also the business
value they contribute to the chain. This protocol has been
implemented already into a fully-fledged blockchain platform
called Bahamut (www.bahamut.io) which boasts hundreds of thousands of active users already.
https://eprint.iacr.org/2024/734
We are introducing a novel consensus protocol for
blockchain, called Proof of Stake and Activity (PoSA) which can
augment the traditional Proof of Stake methods by integrating
a unique Proof of Activity system. PoSA offers a compelling
economic model that promotes decentralization by rewarding
validators based on their staked capital and also the business
value they contribute to the chain. This protocol has been
implemented already into a fully-fledged blockchain platform
called Bahamut (www.bahamut.io) which boasts hundreds of thousands of active users already.
Secure Multiparty Computation in the Presence of Covert Adaptive Adversaries
https://eprint.iacr.org/2024/735
We design a new MPC protocol for arithmetic circuits secure against erasure-free covert adaptive adversaries with deterrence 1/2. The new MPC protocol has the same asymptotic communication cost, the number of PKE operations and the number of exponentiation operations as the most efficient MPC protocol for arithmetic circuits secure against covert static adversaries. That means, the new MPC protocol improves security from covert static security to covert adaptive adversary almost for free. For MPC problems where the number of parties n is much larger than the number of multiplication gates M, the new MPC protocol asymptotically improves communication complexity over the most efficient MPC protocol for arithmetic circuits secure against erasure-free active adaptive adversaries.
https://eprint.iacr.org/2024/735
We design a new MPC protocol for arithmetic circuits secure against erasure-free covert adaptive adversaries with deterrence 1/2. The new MPC protocol has the same asymptotic communication cost, the number of PKE operations and the number of exponentiation operations as the most efficient MPC protocol for arithmetic circuits secure against covert static adversaries. That means, the new MPC protocol improves security from covert static security to covert adaptive adversary almost for free. For MPC problems where the number of parties n is much larger than the number of multiplication gates M, the new MPC protocol asymptotically improves communication complexity over the most efficient MPC protocol for arithmetic circuits secure against erasure-free active adaptive adversaries.
Secret Sharing with Certified Deletion
https://eprint.iacr.org/2024/736
Secret sharing allows a user to split a secret into many shares so that the secret can be recovered if, and only if, an authorized set of shares is collected. Although secret sharing typically does not require any computational hardness assumptions, its security does require that an adversary cannot collect an authorized set of shares. Over long periods of time where an adversary can benefit from multiple data breaches, this may become an unrealistic assumption.
We initiate the systematic study of secret sharing with certified deletion in order to achieve security even against an adversary that eventually collects an authorized set of shares. In secret sharing with certified deletion, a (classical) secret $s$ is split into quantum shares that can be destroyed in a manner verifiable by the dealer.
We put forth two natural definitions of security. No-signaling security roughly requires that if multiple non-communicating adversaries delete sufficiently many shares, then their combined view contains negligible information about $s$, even if the total set of corrupted parties forms an authorized set. Adaptive security requires privacy of $s$ against an adversary that can continuously and adaptively corrupt new shares and delete previously-corrupted shares, as long as the total set of corrupted shares minus deleted shares remains unauthorized.
Next, we show that these security definitions are achievable: we show how to construct (i) a secret sharing scheme with no-signaling certified deletion for any monotone access structure, and (ii) a threshold secret sharing scheme with adaptive certified deletion. Our first construction uses Bartusek and Khurana's (CRYPTO 2023) 2-out-of-2 secret sharing scheme with certified deletion as a building block, while our second construction is built from scratch and requires several new technical ideas. For example, we significantly generalize the ``XOR extractor'' of Agarwal, Bartusek, Khurana, and Kumar (EUROCRYPT 2023) in order to obtain better seedless extraction from certain quantum sources of entropy, and show how polynomial interpolation can double as a high-rate randomness extractor in our context of threshold sharing with certified deletion.
https://eprint.iacr.org/2024/736
Secret sharing allows a user to split a secret into many shares so that the secret can be recovered if, and only if, an authorized set of shares is collected. Although secret sharing typically does not require any computational hardness assumptions, its security does require that an adversary cannot collect an authorized set of shares. Over long periods of time where an adversary can benefit from multiple data breaches, this may become an unrealistic assumption.
We initiate the systematic study of secret sharing with certified deletion in order to achieve security even against an adversary that eventually collects an authorized set of shares. In secret sharing with certified deletion, a (classical) secret $s$ is split into quantum shares that can be destroyed in a manner verifiable by the dealer.
We put forth two natural definitions of security. No-signaling security roughly requires that if multiple non-communicating adversaries delete sufficiently many shares, then their combined view contains negligible information about $s$, even if the total set of corrupted parties forms an authorized set. Adaptive security requires privacy of $s$ against an adversary that can continuously and adaptively corrupt new shares and delete previously-corrupted shares, as long as the total set of corrupted shares minus deleted shares remains unauthorized.
Next, we show that these security definitions are achievable: we show how to construct (i) a secret sharing scheme with no-signaling certified deletion for any monotone access structure, and (ii) a threshold secret sharing scheme with adaptive certified deletion. Our first construction uses Bartusek and Khurana's (CRYPTO 2023) 2-out-of-2 secret sharing scheme with certified deletion as a building block, while our second construction is built from scratch and requires several new technical ideas. For example, we significantly generalize the ``XOR extractor'' of Agarwal, Bartusek, Khurana, and Kumar (EUROCRYPT 2023) in order to obtain better seedless extraction from certain quantum sources of entropy, and show how polynomial interpolation can double as a high-rate randomness extractor in our context of threshold sharing with certified deletion.
Mutable Batch Arguments and Applications
https://eprint.iacr.org/2024/737
Non-interactive batch arguments (BARGs) let a prover compute a single proof $\pi$ proving validity of a `batch' of $k$ $\mathbf{NP}$ statements $x_1, \ldots, x_{k}$. The two central features of BARGs are succinctness and soundness. Succinctness states that proof size, $|\pi|$ does not grow with $k$; while soundness states a polytime cheating prover cannot create an accepting proof for any invalid batch of statements.
In this work, we put forth a new concept of mutability for batch arguments, called mutable batch arguments. Our goal is to re-envision how we think about and use BARGs. Traditionally, a BARG proof string $\pi$ is an immutable encoding of $k$ $\mathbf{NP}$ witness $\omega_1, \ldots, \omega_{k}$. In a mutable BARG system, each proof string $\pi$ is a mutable encoding of original witnesses. Thus, a mutable BARG captures and enables computations over a batch proof $\pi$. We also study new privacy notions for mutable BARGs, guaranteeing that a mutated proof hides all non-trivial information. Such mutable BARGs are a naturally good fit for many privacy sensitive applications.
Our main contributions can be summarized as introducing the general concept of mutable BARGs, identifying new non-trivial classes of feasible mutations over BARGs, designing new constructions for mutable BARGs satisfying mutation privacy for these classes from standard cryptographic assumptions, and developing applications of mutable BARGs to advanced signatures such as homomorphic signatures, redactable signatures, and aggregate signatures. Our results improve state-of-the-art known for many such signature systems either in terms of functionality, efficiency, security, or versatility (in terms of cryptographic assumptions).
https://eprint.iacr.org/2024/737
Non-interactive batch arguments (BARGs) let a prover compute a single proof $\pi$ proving validity of a `batch' of $k$ $\mathbf{NP}$ statements $x_1, \ldots, x_{k}$. The two central features of BARGs are succinctness and soundness. Succinctness states that proof size, $|\pi|$ does not grow with $k$; while soundness states a polytime cheating prover cannot create an accepting proof for any invalid batch of statements.
In this work, we put forth a new concept of mutability for batch arguments, called mutable batch arguments. Our goal is to re-envision how we think about and use BARGs. Traditionally, a BARG proof string $\pi$ is an immutable encoding of $k$ $\mathbf{NP}$ witness $\omega_1, \ldots, \omega_{k}$. In a mutable BARG system, each proof string $\pi$ is a mutable encoding of original witnesses. Thus, a mutable BARG captures and enables computations over a batch proof $\pi$. We also study new privacy notions for mutable BARGs, guaranteeing that a mutated proof hides all non-trivial information. Such mutable BARGs are a naturally good fit for many privacy sensitive applications.
Our main contributions can be summarized as introducing the general concept of mutable BARGs, identifying new non-trivial classes of feasible mutations over BARGs, designing new constructions for mutable BARGs satisfying mutation privacy for these classes from standard cryptographic assumptions, and developing applications of mutable BARGs to advanced signatures such as homomorphic signatures, redactable signatures, and aggregate signatures. Our results improve state-of-the-art known for many such signature systems either in terms of functionality, efficiency, security, or versatility (in terms of cryptographic assumptions).