1,720,964 research outputs found
On the Complete Non-malleability of the Fujisaki-Okamoto Transform
No full textThe Fujisaki-Okamoto (FO) transform (CRYPTO 1999 and JoC 2013) turns any weakly (i.e., IND-CPA) secure public-key encryption (PKE) scheme into a strongly (i.e., IND-CCA) secure key encapsulation method (KEM) in the random oracle model (ROM). Recently, the FO transform re-gained momentum as part of CRISTAL-Kyber, selected by the NIST as the PKE winner of the post-quantum cryptography standardization project. Following Fischlin (ICALP 2005), we study the complete non-malleability of KEMs obtained via the FO transform. Intuitively, a KEM is completely non-malleable if no adversary can maul a given public key and ciphertext into a new public key and ciphertext encapsulating a related key for the underlying blockcipher. On the negative side, we find that KEMs derived via FO are not completely non-malleable in general. On the positive side, we show that complete non-malleability holds in the ROM by assuming the underlying PKE scheme meets an additional property, or by a slight tweak of the transformation
Terrorist Attacks for Fake Exposure Notifications in Contact Tracing Systems
Full text linkIn this work we show that an adversary can attack the integrity of contact tracing systems based on Google-Apple Exposure Notifications (GAEN) by leveraging blockchain technology. We show that through smart contracts there can be an on-line market where infected individuals interested in monetizing their status can upload to the servers of the GAEN-based systems some keys (i.e., TEKs) chosen by a non-infected adversary. In particular, the infected individual can anonymously and digitally trade the upload of TEKs without a mediator and without running risks of being cheated. This vulnerability can therefore be exploited to generate large-scale fake exposure notifications of at-risk contacts with serious consequences (e.g., jeopardizing parts of the health system, affecting results of elections, imposing the closure of schools, hotels or factories). As main contribution, we design a smart contract with two collateral deposits that works, in general, on GAEN-based systems. We then also suggest the design of a more sophisticated smart contract, using DECO, that could be used to attack in a different way GAEN-based systems (i.e., this second smart contract can succeed even in case GAEN systems are repaired making ineffective the first smart contract). Our work shows how to realize with GAEN-based systems (in particular with Immuni and SwissCovid), the terrorist attack to decentralized contact tracing systems envisioned by Vaudenay
Data Redaction in Smart-Contract-Enabled Permissioned Blockchains
Full text linkBalancing immutability and compliance with regulations stands as a significant challenge in the realm of blockchain technology applications. Due to the increase of data-protection requirements (e.g., the General Data Protection Regulation (GDPR) in the European Union), it is essential to address the problem of deleting data from a blockchain without compromising the security and transparency of the blockchain itself. Several works proposed techniques to address the data redaction problem, and the most effective ones are mainly applicable to permissioned blockchains. In their seminal work, Ateniese et al. [EuroS&P 2017] were the first to propose a redactable blockchain. Their approach focuses on permissioned blockchains and they showed how to change the content of a transaction without breaking the chaining among blocks by using special cryptographic hash function (i.e., chameleon hash functions) and protocols for secure multi-party computation to make the required distributed computations. We observe that the redaction technique of Ateniese et al. does not take into account the possibility that the blockchain includes smart contracts and that a redaction of a transaction might leave inconsistencies in the logic of the contracts, making some remaining non-redacted transactions invalid. We find this decision rather limiting since decentralized and publicly verifiable computation guaranteed by smart-contract-enabled blockchains is indeed necessary for modern applications. In order to overcome the above limitations of the applicability of the redaction techniques of Ateniese et al., we propose a redaction technique with wider applicability that leverages succinct non-interactive arguments of knowledge (SNARKs) to realize what we call a proof-of-consistency. A SNARK will be computed to show that the current state of a smart contract is consistent with respect to a previous state since there existed transactions, now redacted, that produced the current state from a former publicly verifiable state. Therefore, a successful verification of such a SNARK allows to maintain the consistency of the non-redacted transactions with the state of the smart contract, and the resulting blockchain maintains public verifiability and consistency in the presence of redacted transactions
Compact Proofs of Partial Knowledge for Overlapping CNF Formulae
No full textAt CRYPTO ’94, Cramer, Damgård, and Schoenmakers introduced a general technique for constructing honest-verifier zero-knowledge proofs of partial knowledge (PPK), where a prover Alice wants to prove to a verifier Bob she knows τ witnesses for τ claims out of k claims without revealing the indices of those τ claims. Their solution starts from a base honest-verifier zero-knowledge proof of knowledge Σ and requires to run in parallel k execution of the base protocol, giving a complexity of O(kγ(Σ)), where γ(Σ) is the communication complexity of the base protocol. However, modern practical scenarios require communication-efficient zero-knowledge proofs tailored to handle partial knowledge in specific application-dependent formats. In this paper, we propose a technique to compose a large class of Σ-protocols for atomic statements into Σ-protocols for PPK over formulae in conjunctive normal form (CNF) that overlap, in the sense that there is a common subset of literals among all clauses of the formula. In such formulae, the statement is expressed as a conjunction of m clauses, each of which consists of a disjunction of k literals (i.e., each literal is an atomic statement) and l literals are shared among clauses. The prover, for a threshold parameter τ≤k, proves knowledge of at least τ witnesses for τ distinct literals in each clause. At the core of our protocol, there is a new technique to compose Σ-protocols for regular CNF relations (i.e., when τ=1) that exploits the overlap among clauses and that we then generalize to formulae where τ>1 providing improvements over state-of-the-art constructions
Multi-key and Multi-input Predicate Encryption from Learning with Errors
No full textWe put forward two natural generalizations of predicate encryption (PE), dubbed multi-key and multi-input PE. More in details, our contributions are threefold.
- Definitions. We formalize security of multi-key PE and multi-input PE following the standard indistinguishability paradigm, and modeling security both against malicious senders (i.e., corruption of encryption keys) and malicious receivers (i.e., collusions).
- Constructions. We construct adaptively secure multi-key and multi-input PE supporting the conjunction of poly-many arbitrary single-input predicates, assuming the sub-exponential hardness of the learning with errors (LWE) problem.
- Applications. We show that multi-key and multi-input PE for expressive enough predicates suffices for interesting cryptographic applications, including non-interactive multi-party computation (NI-MPC) and matchmaking encryption (ME).
In particular, plugging in our constructions of multi-key and multi-input PE, under the sub-exponential LWE assumption, we obtain the first ME supporting arbitrary policies with unbounded collusions, as well as robust (resp. non-robust) NI-MPC for so-called all-or-nothing functions satisfying a non-trivial notion of reusability and supporting a constant (resp. polynomial) number of parties. Prior to our work, both of these applications required much heavier tools such as indistinguishability obfuscation or compact functional encryption
Cryptographic and Financial Fairness
No full textA recent trend in multi-party computation is to achieve cryptographic fairness via monetary penalties, i.e. each honest player either obtains the output or receives a compensation in the form of a cryptocurrency. We pioneer another type of fairness, financial fairness, that is closer to the real-world valuation of financial transactions. Intuitively, a penalty protocol is financially fair if the net present cost of participation (the total value of cash inflows less cash outflows, weighted by the relative discount rate) is the same for all honest participants, even when some parties cheat. We formally define the notion, show several impossibility results based on game theory, and analyze the practical effects of (lack of) financial fairness if one was to run the protocols for real on Bitcoin using Bloomberg's dark pool trading. For example, we show that the ladder protocol (CRYPTO'14), and its variants (CCS'15 and CCS'16), fail to achieve financial fairness both in theory and in practice, while the penalty protocols of Kumaresan and Bentov (CCS'14) and Baum, David and Dowsley (FC'20) are financially fair
Shielded Computations in Smart Contracts Overcoming Forks
No full textIn this work, we consider executions of smart contracts for implementing secure multi-party computation (MPC) protocols on forking blockchains (e.g., Ethereum), and we study security and delay issues due to forks. In this setting, the classical double-spending problem tells us that messages of the MPC protocol should be confirmed on-chain before playing the next ones, thus slowing down the entire execution. Our contributions are twofold: For the concrete case of fairly tossing multiple coins with penalties, we notice that the lottery protocol of Andrychowicz et al. (S&P ’14) becomes insecure if players do not wait for the confirmations of several transactions. In addition, we present a smart contract that instead retains security even when all honest players immediately answer to transactions appearing on-chain. We analyze the performance using Ethereum as testbed.We design a compiler that takes any “digital and universally composable” MPC protocol (with or without honest majority), and transforms it into another one (for the same task and same setup) which maintains security even if all messages are played on-chain without delays. The special requirements on the starting protocol mean that messages consist only of bits (e.g., no hardware token is sent) and security holds also in the presence of other protocols. We further show that our compiler satisfies fairness with penalties as long as honest players only wait for confirmations once. By reducing the number of confirmations, our protocols can be significantly faster than natural constructions
Efficient Proofs of Knowledge for Threshold Relations
No full textRecently, there has been great interest towards constructing efficient zero-knowledge proofs for practical languages. In this work, we focus on proofs for threshold relations, in which the prover is required to prove knowledge of witnesses for k out of l statements. The main contribution of our work is an efficient and modular transformation that starting from a large class of Σ -protocols and a corresponding threshold relation Rk,l, provides an efficient Σ -protocol for Rk,l with improved communication complexity w.r.t. prior results. Our transformation preserves statistical/perfect honest-verifier zero knowledge
A Black-Box Construction of Fully-Simulatable, Round-Optimal Oblivious Transfer from Strongly Uniform Key Agreement
Full text linkWe show how to construct maliciously secure oblivious transfer (M-OT) from a strengthening of key agreement (KA) which we call strongly uniform KA (SU-KA), where the latter roughly means that the messages sent by one party are computationally close to uniform, even if the other party is malicious. Our transformation is black-box, almost round preserving (adding only a constant overhead of up to two rounds), and achieves standard simulation-based security in the plain model. As we show, 2-round SU-KA can be realized from cryptographic assumptions such as low-noise LPN, high-noise LWE, Subset Sum, DDH, CDH and RSA—all with polynomial hardness—thus yielding a black-box construction of fully-simulatable, round-optimal, M-OT from the same set of assumptions (some of which were not known before)
- …
