The article deals with the problems of cryptographic protection of data processing algorithms and techniques. They are novel techniques allowing to process private information without disclosing it to persons engaged in processing. One of the main applications of such security tools is the creation of personalized information services, which opens up new opportunities for business and reduces the risks of unauthorized access to personal data. We review important building blocks for cryptographic protection of data processing, such as zero-knowledge proofs, secure multi-party computations, and homomorphic encryption. Often, personalized information services are based on data mining and machine learning, so privacy-preserved machine learning is a very important building block for them. We analyze the concept of differential privacy which serves as the basis for privacy-preserving machine learning and some other cryptographic schemes. At the end of the paper, we forecast the perspectives of encrypted data processing.
Many important cryptographic primitives offer probabilistic guarantees of security that can be specified as quantitative hyperproperties; these are specifications that stipulate the existence of a certain number of traces in the system satisfying certain constraints. Verification of such hyperproperties is extremely challenging because they involve simultaneous reasoning about an unbounded number of different traces. In this paper, we introduce a technique for verification of quantitative hyperproperties based on the notion of trace enumeration relations. These relations allow us to reduce the problem of trace-counting into one of model-counting of formulas in first-order logic. We also introduce a set of inference rules for machine-checked reasoning about the number of satisfying solutions to first-order formulas (aka model counting). Putting these two components together enables semi-automated verification of quantitative hyperproperties on infinite state systems. We use our methodology to prove confidentiality of access patterns in Path ORAMs of unbounded size, soundness of a simple interactive zero-knowledge proof protocol as well as other applications of quantitative hyperproperties studied in past work.
Nabil Alkeilani Alkadri, Rachid El Bansarkhani, Johannes Buchmann
A canonical identification (CID) scheme is a 3-move protocol consisting of a commitment, challenge, and response. It constitutes the core design of many cryptographic constructions such as zero-knowledge proof systems and various types of signature schemes. Unlike number-theoretic constructions, CID in the lattice setting usually forces provers to abort and repeat the whole authentication process once the distribution of the computed response does not follow a target distribution independent from the secret key. This concept has been realized by means of rejection sampling, which makes sure that the secrets involved in a protocol are concealed after a certain number of repetitions. This however has a negative impact on the efficiency of interactive protocols because it leads to a number of communication rounds that is multiplicative in the number of aborting participants (or rejection sampling procedures). In this work we show how the CID scheme underlying many lattice-based protocols can be designed with smaller number of aborts or even without aborts. Our new technique exploits (unbalanced) binary hash trees and thus significantly reduces the communication complexity. We show how to apply this new method within interactive zero-knowledge proofs. We also present BLAZE \(^{+}\): a further application of our technique to the recently proposed lattice-based blind signature scheme BLAZE (FC’20). We show that BLAZE \(^{+}\) has an improved performance and communication complexity compared to BLAZE while preserving the size of keys and signatures.
In this paper we continue to speak about the concept of Self-Sovereign Identity (SSI), but not in the cases of IoT devices as it was in previous works [1]. The main purpose of this research is the usage of digital identity in two cases: a) SSI of a single person in Knowledge based system “Experts Ledger” and b) SSI of a company and candidate in HR matching systems. Though these two systems are developed for different issues, the idea of SSI in both is similar. The overview of these systems is done, and the pros and cons of using SSI with the relation of Zero-Knowledge Proof (ZKP) in each of them is made.
Cloud storage systems provide a flexible, convenient and friendly way for users to outsource data. However, users lose control of their data once outsourcing them to the cloud. Public auditing was introduced to ensure data integrity, in which a third-party auditor (TPA) is delegated to execute auditing tasks. In general, TPA generates and sends challenge information to the cloud server (CS), which proves data possession accordingly. However, the TPA may not perform public auditing protocol honestly or may even collude with CS to deceive users. Some existing public auditing schemes utilize blockchain to resist against the malicious TPA. However, the CS may guess the challenge messages and there is a risk that users' information may be leaked to the TPA during the process of auditing. In this paper, we propose a decentralized and privacy-preserving public auditing scheme based on blockchain (DBPA), in which a blockchain is utilized as an unpredictable source for the generation of (random) challenge information, and the auditor is required to record the audit process onto the blockchain. Due to the characteristics of blockchain, users can check the audit results publicly. Moreover, zero-knowledge proof is used in DBPA to protect user's privacy during the audit process so that the response information returned by the CS does not leak information about user's data. Security analysis and performance evaluation show that DBPA is secure and efficient.
Zongyang Zhang, Weihan Li, Haitao Liu, Jianwei Liu
With the continuous development and popularity of blockchain technology, anonymity of cryptocurrency has attracted wide attention. Zcash is an altcoin of Bitcoin aiming to protect blockchain anonymity. Its anonymity is highly guaranteed by zero-knowledge proofs. However, it is still practicable to decrease Zcash's anonymity. In this paper, we provide a refined empirical analysis of Zcash anonymity. We improve current address clustering methods and increase the clustering rate by 9%. We also analyze the whole process of distributing mining reward and identify 87.5% addresses and 25.7% transactions. Besides, we simplify Zcash transaction network and then pick out nodes (edges) which play important roles in network connectivity. We show that these nodes are mostly mining pools. In particular, users participating in shieldedpool are mostly founders, miners and mining pools, although shieldedpool itself is designed for protecting anonymity of users with high privacy requirements. Our results, to an extent, are opposite to the original intention of Zcash.
Smart contracts are protocols that can automatically execute a transaction including an electronic contract when a condition is satisfied without a trusted third party. In a representative use-case, a smart contract is executed when multiple parties fairly trade on a blockchain asset. On blockchain systems, a smart contract can be regarded as a system participant, responding to the information received, receiving and storing values, and sending information and values outwards. Also, a smart contract can temporarily keep assets, and always perform operations in accordance with prior rules. Many cryptocurrencies have implemented smart contracts. At POST2018, Atzei et al. give formulations of seven fair exchange protocols using smart contract on Bitcoin: oracle, escrow, intermediated payment, timed commitment, micropayment channels, fair lotteries, and contingent payment. However, they only give an informal discussion on security. In this paper, we verify the fairness of their seven protocols by using the formal verification tool ProVerif. As a result, we show that five protocols (the oracle, intermediated payment, timed commitment, micropayment channels and fair lotteries protocols) satisfy fairness, which were not proved formally. Also, we re-find known attacks to break fairness of two protocols (the escrow and contingent payment protocols). For the escrow protocol, we formalize the two-party scheme and the three-party scheme with an arbitrator, and show that the two-party scheme does not satisfy fairness as Atzei et al. showed. For the contingent payment protocol, we formalize the protocol with the non-interactive zero-knowledge proof (NIZK), and re-find the attack shown by Campanelli et al. at CCS 2017. Also, we show that a countermeasure with subversion NIZK against the attack works properly while it is not formally proved.
Ben Kreuter, Tancrède Lepoint, Michele Orrù, Mariana Raykova
We present a cryptographic construction for anonymous tokens with private metadata bit, called PMBTokens. This primitive enables an issuer to provide a user with a lightweight, single-use anonymous trust token that can embed a single private bit, which is accessible only to the party who holds the secret authority key and is private with respect to anyone else. Our construction generalizes and extends the functionality of Privacy Pass (PETS’18) with this private metadata bit capability. It provides unforgeability, unlinkability, and privacy for the metadata bit properties based on the DDH and CTDH assumptions in the random oracle model. Both Privacy Pass and PMBTokens rely on non-interactive zero-knowledge proofs (NIZKs). We present new techniques to remove the need for NIZKs, while still achieving unlinkability. We implement our constructions and we report their efficiency costs.
We present a modification to RingCT protocol with stealth addresses that makes it compatible with Delegated Proof of Stake based consensus mechanisms called Delegated RingCT.
Our scheme has two building blocks: a customised version of an Integrated Signature and Encryption scheme composed of a public key encryption scheme and two signature schemes (a digital signature and a linkable ring signature); and non-interactive zero knowledge proofs. We give a description of the scheme, security proofs and a prototype implementation whose benchmarking is discussed.
Although Delegated RingCT doesn't have the same degree of anonymity as other RingCT constructions, we argue that the benefits that the compatibility with DPoS consensus mechanisms brings constitutes a reasonable trade-off for being able to develop an anonymous decentralised cryptocurrency that is faster and more scalable than existing ones.
Takuzu and Juosan are logical Nikoli games in the spirit of Sudoku. In Takuzu, a grid must be filled with 0’s and 1’s under specific constraints. In Juosan, the grid must be filled with vertical and horizontal dashes with specific constraints. We give physical algorithms using cards to realize zero-knowledge proofs for those games. The goal is to allow a player to show that he/she has the solution without revealing it. Previous work on Takuzu showed a protocol with multiple instances needed. We propose two improvements: only one instance needed and a soundness proof. We also propose a similar proof for Juosan game.
Privacy-focused crypto-currencies, such as Zcash or Monero, aim to provide strong cryptographic guarantees for transaction confidentiality and unlinkability.In this paper, we describe side-channel attacks that let remote adversaries bypass these protections.We present a general class of timing side-channel and traffic-analysis attacks on receiver privacy.These attacks enable an active remote adversary to identify the (secret) payee of any transaction in Zcash or Monero.The attacks violate the privacy goals of these crypto-currencies by exploiting side-channel information leaked by the implementation of different system components.Specifically, we show that a remote party can link all transactions that send funds to a user, by measuring the response time of that user's P2P node to certain requests.The timing differences are large enough that the attacks can be mounted remotely over a WAN.We responsibly disclosed the issues to the affected projects, and they have patched the vulnerabilities.We further study the impact of timing side-channels on the zero-knowledge proof systems used in these cryptocurrencies.We observe that in Zcash's implementation, the time to generate a zero-knowledge proof depends on secret transaction data, and in particular on the amount of transacted funds.Hence, an adversary capable of measuring proof generation time could break transaction confidentiality, despite the proof system's zero-knowledge property.Our attacks highlight the dangers of side-channel leakage in anonymous crypto-currencies, and the need to systematically protect them against such attacks.