Non-interactive zero-knowledge proofs (NIZKs) are a fundamental cryptographic primitive. Despite a long history of research, we only know how to construct NIZKs under a few select assumptions, such as the hardness of factoring or using bilinear maps. Notably, there are no known constructions based on either the computational or decisional Diffie-Hellman (CDH/DDH) assumption without relying on a bilinear map.
In ASIACRYPT 2016, Bellare, Fuchsbauer and Scafuro studied security of non-interactive zero-knowledge (NIZK) arguments in the face of parameter subversion. They showed that achieving subversion soundness (soundness without trusting to the third party) and standard zero-knowledge is impossible at the same time. On the positive side, in the best case, they showed that one can achieve subversion zero-knowledge (zero-knowledge without trusting to the third party) and soundness at the same time. In this paper, we show that one can amplify their best positive result and construct NIZK arguments that can achieve subversion zero-knowledge and simulation (knowledge) soundness at the same time. Simulation (knowledge) soundness is a stronger notion in comparison with (knowledge) soundness, as it also guarantees non-malleability of proofs. Such stronger security guarantee is a must in practical systems. To prove the result, we show that given a NIZK argument that achieves Sub-ZK and (knowledge) soundness, one can use an OR-based construction to define a new language and build a NIZK argument that will guarantee Sub-ZK and simulation (knowledge) soundness at the same time. We instantiate the construction with the state-of-the-art zk-SNARK proposed by Groth [Eurocrypt 2016] and obtain an efficient SNARK that guarantees Sub-ZK and simulation knowledge soundness.
The security of the Bitcoin cryptocurrency system depends on the Koblitz curve secp256k1 combined with the digital signature ECDSA and the hash function SHA-256. In this paper, we show that the security of Bitcoin with ECDSA and secp256k1 is not optimal and present a detailed study of the efficiency of Bitcoin with the digital signature algorithm Ed25519 combined with the twisted Edwards curve CurveEd25519 and the hash function SHA-512. We show that Bitcoin is more secure and more efficient with the digital signature algorithm Ed25519 and the twisted Edwards curve CurveEd25519.
The Fiat-Shamir (FS) transform is a well known and widely used technique to convert any constant-round public-coin honest-verifier zero-knowledge (HVZK) proof or argument system \(\mathsf {HVZK}=(\mathcal {P},\mathcal {V})\) in a non-interactive zero-knowledge (NIZK) argument system
Jonathan Bootle, Vadim Lyubashevsky, Gregor Seiler
A key component of many lattice-based protocols is a zero-knowledge proof of knowledge of a vector \(\vec {s}\) with small coefficients satisfying \(A\vec {s}=\vec {u}\bmod \,q\). While there exist fairly efficient proofs for a relaxed version of this equation which prove the knowledge of \(\vec {s}'\) and c satisfying \(A\vec {s}'=\vec {u}c\) where \(\Vert \vec {s}'\Vert \gg \Vert \vec {s}\Vert \) and c is some small element in the ring over which the proof is performed, the proofs for the exact version of the equation are considerably less practical. The best such proof technique is an adaptation of Stern’s protocol (Crypto ’93), for proving knowledge of nearby codewords, to larger moduli. The scheme is a \(\varSigma \)-protocol, each of whose iterations has soundness error \(2{/}3\), and thus requires over 200 repetitions to obtain soundness error of \(2^{-128}\), which is the main culprit behind the large size of the proofs produced.
Giulio Malavolta, Pedro Moreno-Sánchez, Clara Schneidewind, Aniket Kate · 5 authors
Tremendous growth in cryptocurrency usage is exposing the inherent scalability issues with permissionless blockchain technology. Payment-channel networks (PCNs) have emerged as the most widely deployed solution to mitigate the scalability issues, allowing the bulk of payments between two users to be carried out off-chain. Unfortunately, as reported in the literature and further demonstrated in this paper, current PCNs do not provide meaningful security and privacy guarantees
Oblivious linear-function evaluation (OLE) is a secure two-party protocol allowing a receiver to learn any linear combination of a pair of field elements held by a sender. OLE serves as a common building block for secure computation of arithmetic circuits, analogously to the role of oblivious transfer (OT) for boolean circuits. A useful extension of OLE is vector OLE (VOLE), allowing the receiver to learn any linear combination of two vectors held by the sender. In several applications of OLE, one can replace a large number of instances of OLE by a smaller number of instances of VOLE. This motivates the goal of amortizing the cost of generating long instances of VOLE. We suggest a new approach for fast generation of pseudo-random instances of VOLE via a deterministic local expansion of a pair of short correlated seeds and no interaction. This provides the first example of compressing a non-trivial and cryptographically useful correlation with good concrete efficiency. Our VOLE generators can be used to enhance the efficiency of a host of cryptographic applications. These include secure arithmetic computation and non-interactive zero-knowledge proofs with reusable preprocessing. Our VOLE generators are based on a novel combination of function secret sharing (FSS) for multi-point functions and linear codes in which decoding is intractable. Their security can be based on variants of the learning parity with noise (LPN) assumption over large fields that resist known attacks. We provide several constructions that offer tradeoffs between different efficiency measures and the underlying intractability assumptions.
Oct 1, 2018·2018 IEEE SmartWorld, Ubiquitous Intelligence & Computing, Advanced & Trusted Computing, Scalable Computing & Communications, Cloud & Big Data Computing, Internet of People and Smart City Innovation (SmartWorld/SCALCOM/UIC/ATC/CBDCom/IOP/SCI)
Protection of IPs through watermarking techniques is prevalent to prevent IP infringement. In previous researches, authentication of watermark in IPs easily disclosures sensitive information of real embedded watermarks, where the evidence of identifying IP ownership may be attacked by illegal verifiers. Despite several watermark detection techniques can address the disclosure of sensitive information in detection procedure, the efficiency for such a detection remains relatively low. Besides, it may yield to large communication overhead on multiple authentication rounds. Motivated by the needs of robustness and efficiency, it is proposed in this work a leakage-resilient protocol to authenticate ownership of Field Programmable Gate Array (FPGA) bitfile design using zero-knowledge proof. The prover can convince the verifier that he knows a secret in the suspected bitfile design via only one interaction. Real locations of watermarks are concealed through location anonymity. With the received authentication package from the prover, the verifier cannot obtain other useful information about watermarks. From experiments, we show that the proposed authentication technique achieves high efficiency and robustness on watermark detection.
Physical Unclonable Functions (PUFs) and Hardware Security
Advanced Steganography and Watermarking Techniques
In 1996, Stern proposed a three-pass zero-knowledge identification (ID) scheme where the cheating probability, i.e., the success probability of cheating prover, is 2/3. Since then, variants and generalization of Stern's ID have been proposed. However, within two-bit challenge space, all of them are having the cheating probability of more than half or reaching half only in an asymptotic manner with more than three passes in one round. In this paper, we propose the first code-based zero-knowledge three-pass ID scheme with the cheating probability of exactly half even with only two-bit challenge space. Our proposed ID scheme can reduce the necessary number of rounds in order to achieve the targeted security against impersonation. Since rewinding technique cannot be used against a quantum adversary in the security proof, we prove the security using the lossy paradigm and rely on the decisional version of syndrome decoding problem so that we do not have to rewind the adversary.
Aug 1, 2018·2018 17th IEEE International Conference On Trust, Security And Privacy In Computing And Communications/ 12th IEEE International Conference On Big Data Science And Engineering (TrustCom/BigDataSE)
Dimaz Ankaa Wijaya, Joseph K. Liu, Ron Steinfeld, Dongxi Liu
Monero is one of the privacy-preserving cryptocurrencies employing CryptoNote protocol. The privacy features in Monero are provided by cryptographic techniques such as linkable ring signature and one-time public key. Recent studies show that the majority of Monero inputs are traceable prior to mandatory RingCT transaction. After the RingCT was implemented, the problems were mitigated. We propose a novel attack to reduce the anonymity of Monero transactions or even to fully deanonymise the inputs. The proposed protocol can be launched in RingCT protocol and enables multiple attackers to collaborate without trusting each other. The attack scheme can be planted in the existing Monero services without extra fees and without putting the users' money at risk.
Domhnall Carlin, Philip OrKane, Sakir Sezer, Jonah Burgess
With the rise in worth and popularity of cryptocurrencies, a new opportunity for criminal gain is being exploited and with little currently offered in the way of defence. The cost of mining (i.e., earning cryptocurrency through CPU-intensive calculations that underpin the blockchain technology) can be prohibitively expensive, with hardware costs and electrical overheads previously offering a loss compared to the cryptocurrency gained. Off-loading these costs along a distributed network of machines via malware offers an instantly profitable scenario, though standard Anti-virus (AV) products offer some defences against file-based threats. However, newer fileless malicious attacks, occurring through the browser on seemingly legitimate websites, can easily evade detection and surreptitiously engage the victim machine in computationally-expensive cryptomining (cryptojacking). With no current academic literature on the dynamic opcode analysis of cryptomining, to the best of our knowledge, we present the first such experimental study. Indeed, this is the first such work presenting opcode analysis on non-executable files. Our results show that browser-based cryptomining within our dataset can be detected by dynamic opcode analysis, with accuracies of up to 100%. Further to this, our model can distinguish between cryptomining sites, weaponized benign sites, de-weaponized cryptomining sites and real world benign sites. As it is process-based, our technique offers an opportunity to rapidly detect, prevent and mitigate such attacks, a novel contribution which should encourage further future work.