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:
26 September 2022
Bin Liu, Antonis Michalas, Bogdan Warinschi
In this paper, we follow the line of existing study on cryptographic enforcement of Role-Based Access Control (RBAC). Inspired by the study of the relation between the existing security definitions for such system, we identify two different types of attacks which cannot be captured by the existing ones. Therefore, we propose two new security definitions towards the goal of appropriately modelling cryptographic enforcement of Role-Based Access Control policies and study the relation between our new definitions and the existing ones. In addition, we show that the cost of supporting dynamic policy update is inherently expensive by presenting two lower bounds for such systems which guarantee correctness and secure access.
Long Nie, ShaoWen Yao, Jing Liu
In most homomorphic encryption schemes based on the RLWE, the native plaintexts are represented as polynomials in a ring $Z_t[x]/x^N+1$ where $t$ is a plaintext modulus and $x^N+1$ is a cyclotomic polynomial with degree power of two. An encoding scheme should be used to transform some natural data types(such as integers and rational numbers) into polynomials in the ring. After a homomorphic computation on the polynomial is finished, the decoding procedure is invoked to obtain the result. However, conditions for decoding correctly are strict in a way. For example, the overflows of computation modulo both the plaintext modulus $t$ and the cyclotomic polynomial $x^N+1$ will result in a unexpected result for decoding. The reason is that decoding the part which is discarded by modular reduction is not 0.
We combine number theory transformation with Hensel Codes to construct a scheme. Intuitively, decoding the discarded part will yield 0 so the limitations are overcome naturally in our scheme. On the other hand, rational numbers can be handled with high precision in parallel.
Ittai Abraham, Gilad Asharov, Shravani Patil, Arpita Patra
Broadcast is an essential primitive for secure computation. We focus in this paper on optimal resilience (i.e., when the number of corrupted parties $t$ is less than a third of the computing parties $n$), and with no setup or cryptographic assumptions.
While broadcast with worst case $t$ rounds is impossible, it has been shown [Feldman and Micali STOC'88, Katz and Koo CRYPTO'06] how to construct protocols with expected constant number of rounds in the private channel model. However, those constructions have large communication complexity, specifically $\mathcal{O}(n^2L+n^6\log n)$ expected number of bits transmitted for broadcasting a message of length $L$. This leads to a significant communication blowup in secure computation protocols in this setting.
In this paper, we substantially improve the communication complexity of broadcast in constant expected time. Specifically, the expected communication complexity of our protocol is $\mathcal{O}(nL+n^4\log n)$. For messages of length $L=\Omega(n^3 \log n)$, our broadcast has no asymptotic overhead (up to expectation), as each party has to send or receive $\mathcal{O}(n^3 \log n)$ bits. We also consider parallel broadcast, where $n$ parties wish to broadcast $L$ bit messages in parallel. Our protocol has no asymptotic overhead for $L=\Omega(n^2\log n)$, which is a common communication pattern in perfectly secure MPC protocols. For instance, it is common that all parties share their inputs simultaneously at the same round, and verifiable secret sharing protocols require the dealer to broadcast a total of $\mathcal{O}(n^2\log n)$ bits.
As an independent interest, our broadcast is achieved by a packed verifiable secret sharing, a new notion that we introduce. We show a protocol that verifies $\mathcal{O}(n)$ secrets simultaneously with the same cost of verifying just a single secret. This improves by a factor of $n$ the state-of-the-art.
While broadcast with worst case $t$ rounds is impossible, it has been shown [Feldman and Micali STOC'88, Katz and Koo CRYPTO'06] how to construct protocols with expected constant number of rounds in the private channel model. However, those constructions have large communication complexity, specifically $\mathcal{O}(n^2L+n^6\log n)$ expected number of bits transmitted for broadcasting a message of length $L$. This leads to a significant communication blowup in secure computation protocols in this setting.
In this paper, we substantially improve the communication complexity of broadcast in constant expected time. Specifically, the expected communication complexity of our protocol is $\mathcal{O}(nL+n^4\log n)$. For messages of length $L=\Omega(n^3 \log n)$, our broadcast has no asymptotic overhead (up to expectation), as each party has to send or receive $\mathcal{O}(n^3 \log n)$ bits. We also consider parallel broadcast, where $n$ parties wish to broadcast $L$ bit messages in parallel. Our protocol has no asymptotic overhead for $L=\Omega(n^2\log n)$, which is a common communication pattern in perfectly secure MPC protocols. For instance, it is common that all parties share their inputs simultaneously at the same round, and verifiable secret sharing protocols require the dealer to broadcast a total of $\mathcal{O}(n^2\log n)$ bits.
As an independent interest, our broadcast is achieved by a packed verifiable secret sharing, a new notion that we introduce. We show a protocol that verifies $\mathcal{O}(n)$ secrets simultaneously with the same cost of verifying just a single secret. This improves by a factor of $n$ the state-of-the-art.
Pedro Branco, Nico Döttling, Stella Wohnig
Ring signatures allow a user to sign messages on behalf of an ad hoc set of users - a ring - while hiding her identity. The original motivation for ring signatures was whistleblowing [Rivest et al. ASIACRYPT'01]: a high government employee can anonymously leak sensitive information while certifying that it comes from a reliable source, namely by signing the leak. However, essentially all known ring signature schemes require the members of the ring to publish a structured verification key that is compatible with the scheme. This creates somewhat of a paradox since, if a user does not want to be framed for whistleblowing, they will stay clear of signature schemes that support ring signatures.
In this work, we formalize the concept of universal ring signatures (URS). A URS enables a user to issue a ring signature with respect to a ring of users, independently of the signature schemes they are using. In particular, none of the verification keys in the ring need to come from the same scheme. Thus, in principle, URS presents an effective solution for whistleblowing.
The main goal of this work is to study the feasibility of URS, especially in the standard model (i.e. no random oracles or common reference strings). We present several constructions of URS, offering different trade-offs between assumptions required, the level of security achieved, and the size of signatures: * Our first construction is based on superpolynomial hardness assumptions of standard primitives. It achieves compact signatures. That means the size of a signature depends only logarithmically on the size of the ring and on the number of signature schemes involved. * We then proceed to study the feasibility of constructing URS from standard polynomially-hard assumptions only. We construct a non-compact URS from witness encryption and additional standard assumptions. * Finally, we show how to modify the non-compact construction into a compact one by relying on indistinguishability obfuscation.
The main goal of this work is to study the feasibility of URS, especially in the standard model (i.e. no random oracles or common reference strings). We present several constructions of URS, offering different trade-offs between assumptions required, the level of security achieved, and the size of signatures: * Our first construction is based on superpolynomial hardness assumptions of standard primitives. It achieves compact signatures. That means the size of a signature depends only logarithmically on the size of the ring and on the number of signature schemes involved. * We then proceed to study the feasibility of constructing URS from standard polynomially-hard assumptions only. We construct a non-compact URS from witness encryption and additional standard assumptions. * Finally, we show how to modify the non-compact construction into a compact one by relying on indistinguishability obfuscation.
Brian Chen, Yevgeniy Dodis, Esha Ghosh, Eli Goldin, Balachandar Kesavan, Antonio Marcedone, Merry Ember Mou
Key Transparency (KT) systems allow end-to-end encrypted service providers (messaging, calls, etc.) to maintain an auditable directory of their users’ public keys, producing proofs that all participants have a consistent view of those keys, and allowing each user to check updates to their own keys. KT has lately received a lot of attention, in particular its privacy preserving variants, which also ensure that users and auditors do not learn anything beyond what is necessary to use the service and keep the service provider accountable.
Abstractly, the problem of building such systems reduces to constructing so-called append-only Zero-Knowledge Sets (aZKS). Unfortunately, existing aZKS (and KT) solutions do not allow to adequately restore the privacy guarantees after a server compromise, a form of Post-Compromise Security (PCS), while maintaining the auditability properties. In this work we address this concern through the formalization of an extension of aZKS called Rotatable ZKS (RZKS). In addition to providing PCS, our notion of RZKS has several other attractive features, such as a stronger (extractable) soundness notion, and the ability for a communication party with out-of-date data to efficiently “catch up” to the current epoch while ensuring that the server did not erase any of the past data.
Of independent interest, we also introduce a new primitive called a Rotatable Verifiable Random Function (VRF), and show how to build RZKS in a modular fashion from a rotatable VRF, ordered accumulator, and append-only vector commitment schemes.
Abstractly, the problem of building such systems reduces to constructing so-called append-only Zero-Knowledge Sets (aZKS). Unfortunately, existing aZKS (and KT) solutions do not allow to adequately restore the privacy guarantees after a server compromise, a form of Post-Compromise Security (PCS), while maintaining the auditability properties. In this work we address this concern through the formalization of an extension of aZKS called Rotatable ZKS (RZKS). In addition to providing PCS, our notion of RZKS has several other attractive features, such as a stronger (extractable) soundness notion, and the ability for a communication party with out-of-date data to efficiently “catch up” to the current epoch while ensuring that the server did not erase any of the past data.
Of independent interest, we also introduce a new primitive called a Rotatable Verifiable Random Function (VRF), and show how to build RZKS in a modular fashion from a rotatable VRF, ordered accumulator, and append-only vector commitment schemes.
Behzad Abdolmaleki, Nils Fleischhacker, Vipul Goyal, Abhishek Jain, Giulio Malavolta
We revisit the well-studied problem of preventing steganographic communication in multi-party communications. While this is known to be a provably impossible task, we propose a new model that allows circumventing this impossibility. In our model, the parties first publish a single message during an honest non-interactive pre-processing phase and then later interact in an execution phase. We show that in this model, it is indeed possible to prevent any steganographic communication in zero-knowledge protocols. Our solutions rely on standard cryptographic assumptions.
Muhammad Haris Mughees, Ling Ren
This paper studies Batch Private Information Retrieval (BatchPIR), a variant of private information retrieval (PIR) where the client wants to retrieve multiple entries from the server in one batch.
BatchPIR matches the use case of many practical applications and holds the potential for substantial efficiency improvements over PIR in terms of amortized cost per query.
Existing BatchPIR schemes have achieved decent computation efficiency but have not been able to improve communication efficiency at all.
In this paper, we present the first BatchPIR protocol that is efficient in both computation and communication for a variety of database configurations. Specifically, to retrieve a batch of 256 entries from a database with one million entries of 256 bytes each, the communication cost of our scheme is 7.2$\sim$75x better than state-of-the-art solutions.
Dana Dachman-Soled, Julian Loss, Adam O'Neill, Nikki Sigurdson
We investigate the relationship between the classical RSA and factoring problems when preprocessing is considered. In such a model, adversaries can use an unbounded amount of precomputation to produce an "advice" string to then use during the online phase, when a problem instance becomes known. Previous work (e.g., [Bernstein, Lange ASIACRYPT '13]) has shown that preprocessing attacks significantly improve the runtime of the best-known factoring algorithms. Due to these improvements, we ask whether the relationship between factoring and RSA fundamentally changes when preprocessing is allowed. Specifically, we investigate whether there is a superpolynomial gap between the runtime of the best attack on RSA with preprocessing and on factoring with preprocessing.
Our main result rules this out with respect to algorithms in a natural adaptation of the generic ring model to the preprocessing setting. In particular, in this setting we show the existence of a factoring algorithm (albeit in the random oracle model) with polynomially related parameters, for any setting of RSA parameters.
Our main result rules this out with respect to algorithms in a natural adaptation of the generic ring model to the preprocessing setting. In particular, in this setting we show the existence of a factoring algorithm (albeit in the random oracle model) with polynomially related parameters, for any setting of RSA parameters.
John Chan, Phillip Rogaway
We provide a strong definition for committing authenticated-encryption (cAE), as well as a framework that encompasses earlier and weaker definitions. The framework attends not only to what is committed but also the extent to which the adversary knows or controls keys. We slot into our framework strengthened cAE-attacks on GCM and OCB. Our main result is a simple and efficient construction, CTX, that makes a nonce-based AE (nAE) scheme committing. The transformed scheme achieves the strongest security notion in our framework. Just the same, the added computational cost (on top of the nAE scheme's cost) is a single hash over a short string, a cost independent of the plaintext's length. And there is no increase in ciphertext length compared to the base nAE scheme. That such a thing is possible, let alone easy, upends the (incorrect) intuition that you can't commit to a plaintext or ciphertext without hashing one or the other. And it motivates a simple and practical tweak to AE-schemes to make them committing.
Wouter Castryck, Thomas Decru, Marc Houben, Frederik Vercauteren
We address three main open problems concerning the use of radical isogenies, as presented by Castryck, Decru and Vercauteren at Asiacrypt 2020, in the computation of long chains of isogenies of fixed, small degree between elliptic curves over finite fields. Firstly, we present an interpolation method for finding radical isogeny formulae in a given degree $N$, which by-passes the need for factoring division polynomials over large function fields. Using this method, we are able to push the range for which we have formulae at our disposal from $N \leq 13$ to $N \leq 37$ (where in the range $18 \leq N \leq 37$ we have restricted our attention to prime powers). Secondly, using a combination of known techniques and ad-hoc manipulations, we derive optimized versions of these formulae for $N \leq 19$, with some instances performing more than twice as fast as their counterparts from 2020. Thirdly, we solve the problem of understanding the correct choice of radical when walking along the surface between supersingular elliptic curves over $\mathbb{F}_p$ with $p \equiv 7 \bmod 8$; this is non-trivial for even $N$ and was settled for $N = 2$ and $N = 4$ only, in the latter case by Onuki and Moriya at PKC 2022. We give a conjectural statement for all even $N$ and prove it for $N \leq 14$. The speed-ups obtained from these techniques are substantial: using $16$-isogenies, the computation of long chains of $2$-isogenies over $512$-bit prime fields can be accelerated by a factor $3$, and the previous implementation of CSIDH using radical isogenies can be sped up by about $12\%$.
Xiangyu Liu, Shengli Liu, Dawu Gu
We define the security notion of (strong) collision resistance for chameleon hash functions in the multi-user setting ((S-)MU-CR security). We also present three constructions, CHF_dl, CHF_rsa and CHF_fac, and prove their tight S-MU-CR security based on the discrete logarithm, RSA and factoring assumptions, respectively. In applications, our tightly S-MU-CR secure chameleon hash functions help us to lift a signature scheme from (weak) unforgeability to strong unforgeability in the multi-user setting, and the security reduction is tightness preserving. Furthermore, they can also be used to construct tightly secure online/offline signatures, chameleon signatures and proxy signatures, etc., in the multi-user setting.
Harry Eldridge, Aarushi Goel, Matthew Green, Abhishek Jain, Maximilian Zinkus
One-time programs, originally formulated by Goldwasser et al. [CRYPTO'08], are a powerful cryptographic primitive with compelling applications. Known solutions for one-time programs, however, require specialized secure hardware that is not widely available (or, alternatively, access to blockchains and very strong cryptographic tools).
In this work we investigate the possibility of realizing one-time programs from a recent and now more commonly available hardware functionality: the counter lockbox. A counter lockbox is a stateful functionality that protects an encryption key under a user-specified password, and enforces a limited number of incorrect guesses. Counter lockboxes have become widely available in consumer devices and cloud platforms.
We show that counter lockboxes can be used to realize one-time programs for general functionalities. We develop a number of techniques to reduce the number of counter lockboxes required for our constructions, that may be of independent interest.
In this work we investigate the possibility of realizing one-time programs from a recent and now more commonly available hardware functionality: the counter lockbox. A counter lockbox is a stateful functionality that protects an encryption key under a user-specified password, and enforces a limited number of incorrect guesses. Counter lockboxes have become widely available in consumer devices and cloud platforms.
We show that counter lockboxes can be used to realize one-time programs for general functionalities. We develop a number of techniques to reduce the number of counter lockboxes required for our constructions, that may be of independent interest.
Seonghak Kim, Minji Park, Jaehyung Kim, Taekyung Kim, Chohong Min
Homomorphic encryption (HE) has opened an entirely new world up in the privacy-preserving use of sensitive data by conducting computations on encrypted data. Amongst many HE schemes targeting computation in various contexts, Cheon--Kim--Kim--Song (CKKS) scheme is distinguished since it allows computations for encrypted real number data, which have greater impact in real-world applications.
CKKS scheme is a levelled homomorphic encryption scheme, consuming one level for each homomorphic multiplication. When the level runs out, a special computational circuit called bootstrapping is required in order to conduct further multiplications. The algorithm proposed by Cheon et al. has been regarded as a standard way to do bootstrapping in the CKKS scheme, and it consists of the following four steps: ModRaise, CoeffToSlot, EvalMod and SlotToCoeff. However, the steps consume a number of levels themselves, and thus optimizing this extra consumption has been a major focus of the series of recent research.
Among the total levels consumed in the bootstrapping steps, about a half of them is spent in CoeffToSlot and SlotToCoeff steps to scale up the real number components of DFT matrices and round them to the nearest integers. Each scale-up factor is very large so that it takes up one level to rescale it down. Scale-up factors can be taken smaller to save levels, but the error of rounding would be transmitted to EvalMod and eventually corrupt the accuracy of bootstrapping.
EvalMod aims to get rid of the superfluous $qI$ term from a plaintext $pt + qI$ resulting from ModRaise, where $q$ is the bottom modulus and $I$ is a polynomial with small integer coefficients. EvalRound is referred to as its opposite, obtaining $qI$. We introduce a novel bootstrapping algorithm consisting of ModRaise, CoeffToSlot, EvalRound and SlotToCoeff, which yields taking smaller scale-up factors without the damage of rounding errors.
CKKS scheme is a levelled homomorphic encryption scheme, consuming one level for each homomorphic multiplication. When the level runs out, a special computational circuit called bootstrapping is required in order to conduct further multiplications. The algorithm proposed by Cheon et al. has been regarded as a standard way to do bootstrapping in the CKKS scheme, and it consists of the following four steps: ModRaise, CoeffToSlot, EvalMod and SlotToCoeff. However, the steps consume a number of levels themselves, and thus optimizing this extra consumption has been a major focus of the series of recent research.
Among the total levels consumed in the bootstrapping steps, about a half of them is spent in CoeffToSlot and SlotToCoeff steps to scale up the real number components of DFT matrices and round them to the nearest integers. Each scale-up factor is very large so that it takes up one level to rescale it down. Scale-up factors can be taken smaller to save levels, but the error of rounding would be transmitted to EvalMod and eventually corrupt the accuracy of bootstrapping.
EvalMod aims to get rid of the superfluous $qI$ term from a plaintext $pt + qI$ resulting from ModRaise, where $q$ is the bottom modulus and $I$ is a polynomial with small integer coefficients. EvalRound is referred to as its opposite, obtaining $qI$. We introduce a novel bootstrapping algorithm consisting of ModRaise, CoeffToSlot, EvalRound and SlotToCoeff, which yields taking smaller scale-up factors without the damage of rounding errors.
Aayush Gupta, Kobi Gurkan
ZK-SNARKs (Zero Knowledge Succinct Noninteractive ARguments of Knowledge) are one of the most promising new applied cryptography tools: proofs allow anyone to prove a property about some data, without revealing that data. Largely spurred by the adoption of cryptographic primitives in blockchain systems, ZK-SNARKs are rapidly becoming computationally practical in real-world settings, shown by i.e. tornado.cash and rollups. These have enabled ideation for new identity applications based on anonymous proof-of-ownership. One of the primary technologies that would enable the jump from existing apps to such systems is the development of deterministic nullifiers.
Nullifiers are used as a public commitment to a specific anonymous account, to forbid actions like double spending, or allow a consistent identity between anonymous actions. We identify a new deterministic signature algorithm that both uniquely identifies the keypair, and keeps the account identity secret. In this work, we will define the full DDH-VRF construction, and prove uniqueness, secrecy, and existential unforgeability. We will also demonstrate a proof of concept of the nullifier.
Nullifiers are used as a public commitment to a specific anonymous account, to forbid actions like double spending, or allow a consistent identity between anonymous actions. We identify a new deterministic signature algorithm that both uniquely identifies the keypair, and keeps the account identity secret. In this work, we will define the full DDH-VRF construction, and prove uniqueness, secrecy, and existential unforgeability. We will also demonstrate a proof of concept of the nullifier.
Estuardo Alpirez Bock, Lukasz Chmielewski, Konstantina Miteloudi
The Montgomery Ladder is widely used for implementing the scalar multiplication in elliptic curve cryptographic designs. This algorithm is efficient and provides a natural robustness against (simple) side-channel attacks. Previous works however showed that implementations of the Montgomery Ladder using Lopez-Dahab projective coordinates easily leak the value of the most significant bits of the secret scalar, which led to a full key recovery in an attack known as LadderLeak. In light of such leakage, we analyse further popular methods for implementing the Montgomery Ladder. We first consider open source software implementations of the X25519 protocol which implement the Montgomery Ladder based on the ladderstep algorithm from Düll et al. [15]. We confirm via power measurements that these implementations also easily leak the most significant scalar bits, even when implementing Z-coordinate ran- domisations. We thus propose simple modifications of the algorithm and its handling of the most significant bits and show the effectiveness of our modifications via experimental results. Particularly, our re-designs of the algorithm do not incurring significant efficiency penalties. As a second case study, we consider open source hardware implementations of the Montgomery Ladder based on the complete addition formulas for prime order elliptic curves, where we observe the exact same leakage. As we explain, the most significant bits in implementations of the complete addition formulas can be protected in an analogous way as we do for Curve25519 in our first case study.
Akinori Hosoyamada, Takanori Isobe, Yosuke Todo, Kan Yasuda
Incompressibility is one of the most fundamental security goals in white-box cryptography.
Given recent advances in the design of efficient and incompressible block ciphers such as SPACE, SPNbox and WhiteBlock,
we demonstrate the feasibility of reducing incompressible AEAD modes to incompressible block ciphers.
We first observe that several existing AEAD modes of operation, including CCM, GCM(-SIV), and OCB, would be all insecure against white-box adversaries even when used with an incompressble block cipher.
This motivates us to revisit and formalize incompressibility-based security definitions for AEAD schemes and for block ciphers, so that we become able to design modes and reduce their security to that of the underlying ciphers.
Our new security notion for AEAD, which we name whPRI, is an extension of the pseudo-random injection security in the black-box setting.
Similar security notions are also defined for other cryptosystems such as privacy-only encryption schemes.
We emphasize that whPRI ensures quite strong authenticity against white-box adversaries:
existential unforgeability beyond leakage.
This contrasts sharply with previous notions which have ensured either no authenticity or only universal unforgeability.
For the underlying ciphers we introduce a new notion of whPRP, which extends that of PRP in the black-box setting.
Interestingly, our incompressibility reductions follow from a variant of public indifferentiability.
In particular, we show that a practical whPRI-secure AEAD mode can be built from a whPRP-secure block cipher: We present a SIV-like composition of the sponge construction (utilizing a block cipher as its underlying primitive) with the counter mode and prove that such a construction is (in the variant sense) public indifferentiable from a random injection.
To instantiate such an AEAD scheme, we propose a 256-bit variant of SPACE, based on our conjecture that SPACE should be a whPRP-secure cipher.
Fuyuki Kitagawa, Ryo Nishimaki
Secure software leasing is a quantum cryptographic primitive that enables us to lease software to a user by encoding it into a quantum state. Secure software leasing has a mechanism that verifies whether a returned software is valid or not. The security notion guarantees that once a user returns a software in a valid form, the user no longer uses the software.
In this work, we introduce the notion of secret-key functional encryption (SKFE) with secure key leasing, where a decryption key can be securely leased in the sense of secure software leasing. We also instantiate it with standard cryptographic assumptions. More specifically, our contribution is as follows.
- We define the syntax and security definitions for SKFE with secure key leasing. - We achieve a transformation from standard SKFE into SKFE with secure key leasing without using additional assumptions. Especially, we obtain bounded collusion-resistant SKFE for $\mathsf{P/poly}$ with secure key leasing based on post-quantum one-way functions since we can instantiate bounded collusion-resistant SKFE for $\mathsf{P/poly}$ with the assumption.
Some previous secure software leasing schemes capture only pirate software that runs on an honest evaluation algorithm (on a legitimate platform). However, our secure key leasing notion captures arbitrary attack strategies and does not have such a limitation.
As an additional contribution, we introduce the notion of single-decryptor FE (SDFE), where each functional decryption key is copy-protected. Since copy-protection is a stronger primitive than secure software leasing, this notion can be seen as a stronger cryptographic primitive than FE with secure key leasing. More specifically, our additional contribution is as follows.
- We define the syntax and security definitions for SDFE. - We achieve collusion-resistant single-decryptor PKFE for $\mathsf{P/poly}$ from post-quantum indistinguishability obfuscation and quantum hardness of the learning with errors problem.
In this work, we introduce the notion of secret-key functional encryption (SKFE) with secure key leasing, where a decryption key can be securely leased in the sense of secure software leasing. We also instantiate it with standard cryptographic assumptions. More specifically, our contribution is as follows.
- We define the syntax and security definitions for SKFE with secure key leasing. - We achieve a transformation from standard SKFE into SKFE with secure key leasing without using additional assumptions. Especially, we obtain bounded collusion-resistant SKFE for $\mathsf{P/poly}$ with secure key leasing based on post-quantum one-way functions since we can instantiate bounded collusion-resistant SKFE for $\mathsf{P/poly}$ with the assumption.
Some previous secure software leasing schemes capture only pirate software that runs on an honest evaluation algorithm (on a legitimate platform). However, our secure key leasing notion captures arbitrary attack strategies and does not have such a limitation.
As an additional contribution, we introduce the notion of single-decryptor FE (SDFE), where each functional decryption key is copy-protected. Since copy-protection is a stronger primitive than secure software leasing, this notion can be seen as a stronger cryptographic primitive than FE with secure key leasing. More specifically, our additional contribution is as follows.
- We define the syntax and security definitions for SDFE. - We achieve collusion-resistant single-decryptor PKFE for $\mathsf{P/poly}$ from post-quantum indistinguishability obfuscation and quantum hardness of the learning with errors problem.
Nan Wang, Sid Chi-Kin Chau
We propose Flashproofs, a new type of efficient special honest verifier zero-knowledge arguments with a transparent setup in the discrete logarithm (DL) setting. First, we put forth gas-efficient range arguments that achieve $O(N^{\frac{2}{3}})$ communication cost, and involve $O(N^{\frac{2}{3}})$ group exponentiations for verification and a slightly sub-linear number of group exponentiations for proving with respect to the range $[0, 2^N-1]$, where $N$ is the bit length of the range. For typical confidential transactions on blockchain platforms supporting smart contracts, verifying our range arguments consumes only 237K and 318K gas for 32-bit and 64-bit ranges, which are comparable to 220K gas incurred by verifying the most efficient zkSNARK with a trusted setup (EUROCRYPT 16) at present. Besides, the aggregation of multiple arguments can yield further efficiency improvement. Second, we present polynomial evaluation arguments based on the techniques of Bayer & Groth (EUROCRYPT 13). We provide two zero-knowledge arguments, which are optimised for lower-degree ($D \in [3, 2^9]$) and higher-degree ($D > 2^9$) polynomials, where $D$ is the polynomial degree. Our arguments yield a non-trivial improvement in the overall efficiency. Notably, the number of group exponentiations for proving drops from $8\log D$ to $3(\log D+\sqrt{\log D})$. The communication cost and the number of group exponentiations for verification decrease from $7\log D$ to $(\log D + 3\sqrt{\log D})$. To the best of our knowledge, our arguments instantiate the most communication-efficient arguments of membership and non-membership in the DL setting among those not requiring trusted setups. More importantly, our techniques enable a significantly asymptotic improvement in the efficiency of communication and verification (group exponentiations) from $O(\log D)$ to $O(\sqrt{\log D})$ when multiple arguments satisfying different polynomials with the same degree and inputs are aggregated.
Yun Lu, Yu Wei, Malik Magdon-Ismail, Vassilis Zikas
Differential Privacy (DP) is one of the gold standards of privacy. Nonetheless, when one is interested in mechanisms with theoretical guarantees, one has to either choose from a relatively small pallet of generic mechanisms, like Laplacian, Gaussian, and exponential, or develop a new, problem-specific mechanism and analyze its privacy. This makes it challenging for non-experts in security to utilize DP for preserving privacy in complex tasks in areas like machine learning, data science, and medicine, which are primary application domains of DP.
Our work aims to address the above limitation. In a nutshell we devise a methodology for domain experts with limited knowledge of security to estimate the (differential) privacy of an arbitrary mechanism. Our Eureka moment is the utilization of a link---which we prove---between the problems of DP parameter-estimation and Bayes optimal classifiers in machine learning, which we believe can be of independent interest. Our estimator methodology uses this link to achieve two desirable properties: (1) it is black-box, i.e., does not require knowledge of the underlying mechanism, and (2) it has a theoretically-proven accuracy, which depends on the underlying classifier used. This allows domain experts to design mechanisms that they conjecture offer certain (differential) privacy guarantees---but maybe cannot prove it---and apply our method to confirm (or disprove) their conjecture.
More concretely, we first prove a new impossibility result, stating that for the classical DP notion there is no black-box poly-time estimator of $(\epsilon,\delta)$-DP. This motivates a natural relaxation of DP, which we term relative DP. Relative DP preserves the desirable properties of DP---composition, robustness to post processing, and robustness to the discovery disclosure of new data---and applies in most practical settings where privacy is desired. We then devise a black-box poly-time $(\epsilon,\delta)$-relative DP estimator---the first to support mechanisms with large output spaces while having tight accuracy bounds. As a result of independent interest, we apply this theory to develop the first approximate estimator for the standard, i.e., non-relative, definition of Distributional Differential Privacy (DDP) -- aka noiseless privacy.
To demonstrate both our theory and its potential for practical impact, we devised a proof-of-concept implementation of our estimator and benchmarked it against well-studied DP mechanisms. We show that in reasonable execution time our estimator can reproduce the tight, analytically computed $\epsilon, \delta$ trade-off of Laplacian and Gaussian mechanisms---to our knowledge, the first black box estimator to do so, and for the Sparse Vector Technique, our outputs are comparable to that of a more specialized state-of-the-art $(\epsilon, \delta)$-DP estimator.
Our work aims to address the above limitation. In a nutshell we devise a methodology for domain experts with limited knowledge of security to estimate the (differential) privacy of an arbitrary mechanism. Our Eureka moment is the utilization of a link---which we prove---between the problems of DP parameter-estimation and Bayes optimal classifiers in machine learning, which we believe can be of independent interest. Our estimator methodology uses this link to achieve two desirable properties: (1) it is black-box, i.e., does not require knowledge of the underlying mechanism, and (2) it has a theoretically-proven accuracy, which depends on the underlying classifier used. This allows domain experts to design mechanisms that they conjecture offer certain (differential) privacy guarantees---but maybe cannot prove it---and apply our method to confirm (or disprove) their conjecture.
More concretely, we first prove a new impossibility result, stating that for the classical DP notion there is no black-box poly-time estimator of $(\epsilon,\delta)$-DP. This motivates a natural relaxation of DP, which we term relative DP. Relative DP preserves the desirable properties of DP---composition, robustness to post processing, and robustness to the discovery disclosure of new data---and applies in most practical settings where privacy is desired. We then devise a black-box poly-time $(\epsilon,\delta)$-relative DP estimator---the first to support mechanisms with large output spaces while having tight accuracy bounds. As a result of independent interest, we apply this theory to develop the first approximate estimator for the standard, i.e., non-relative, definition of Distributional Differential Privacy (DDP) -- aka noiseless privacy.
To demonstrate both our theory and its potential for practical impact, we devised a proof-of-concept implementation of our estimator and benchmarked it against well-studied DP mechanisms. We show that in reasonable execution time our estimator can reproduce the tight, analytically computed $\epsilon, \delta$ trade-off of Laplacian and Gaussian mechanisms---to our knowledge, the first black box estimator to do so, and for the Sparse Vector Technique, our outputs are comparable to that of a more specialized state-of-the-art $(\epsilon, \delta)$-DP estimator.
Julien Devevey, Omar Fawzi, Alain Passelègue, Damien Stehlé
Lyubashevsky’s signatures are based on the Fiat-Shamir with
aborts paradigm, whose central ingredient is the use of rejection sampling
to transform secret-dependent signature samples into samples from (or
close to) a secret-independent target distribution. Several choices for the
underlying distributions and for the rejection sampling strategy can be
considered. In this work, we study Lyubashevsky’s signatures through
the lens of rejection sampling, and aim to minimize signature size given
signing runtime requirements. Several of our results concern rejection
sampling itself and could have other applications.
We prove lower bounds for compactness of signatures given signing run-
time requirements, and for expected runtime of perfect rejection sampling
strategies. We also propose a Rényi-divergence-based analysis of Lyuba-
shevsky’s signatures which allows for larger deviations from the target
distribution, and show hyperball uniforms to be a good choice of distri-
butions: they asymptotically reach our compactness lower bounds and
offer interesting features for practical deployment. Finally, we propose
a different rejection sampling strategy which circumvents the expected
runtime lower bound and provides a worst-case runtime guarantee.