Follow blockchain research across journals, conferences, and preprint repositories.
972 results · page 18 of 41
Yanhua Zhang, Yifeng Yin, Ximeng Liu, Qikun Zhang · 5 authors
No abstract is available for this record.
Dan Boneh, Rosario Gennaro, Steven Goldfeder
No abstract is available for this record.
Joachim Breitner, Nadia Heninger
No abstract is available for this record.
Michael Backes, Lucjan Hanzlik, Amir Herzberg, Aniket Kate · 5 authors
No abstract is available for this record.
Elette Boyle, Niv Gilboa, Yuval Ishai, Ariel Nof
Secure multiparty computation enables a set of parties to securely carry out a joint computation on their private inputs without revealing anything but the output. A particularly motivated setting is that of three parties with a single corruption (hereafter denoted 3PC). This 3PC setting is particularly appealing for two main reasons: (1) it admits more efficient MPC protocols than in other standard settings; (2) it allows in principle to achieve full security (and fairness). Highly efficient protocols exist within this setting with security against a semi-honest</> adversary; however, a significant gap remains between these and protocols with stronger security against a malicious</> adversary. In this paper, we narrow this gap within concretely efficient protocols. More explicitly, we have the following contributions: Concretely Efficient Malicious 3PC. We present an optimized 3PC protocol for arithmetic circuits over rings with (amortized) communication of 1 ring element per multiplication gate per party, matching the best semi-honest protocols. The protocol applies also to Boolean circuits, significantly improving over previous protocols even for small circuits. Our protocol builds on recent techniques of Boneh et al. (Crypto 2019) for sublinear zero-knowledge proofs on distributed data, together with an efficient semi-honest protocol based on replicated secret sharing (Araki et al., CCS 2016). We present a concrete analysis of communication and computation costs, including several optimizations. For example, for 40-bit statistical security, and Boolean circuit with a million (nonlinear) gates, the overhead on top of the semi-honest protocol can involve less than 0.5KB of communication for the entire circuit,</> while the computational overhead is dominated by roughly 30 multiplications per gate in the field F247. In addition, we implemented and benchmarked the protocol for varied circuit sizes. Full Security. We augment the 3PC protocol to further provide full security</> (with guaranteed output delivery) while maintaining amortized 1 ring element communication per party per multiplication gate, and with hardly any impact on concrete efficiency. This is contrasted with the best previous 3PC protocols from the literature, which allow a corrupt party to mount a denial-of-service attack without being detected.
Lorenzo Grassi, Dmitry Khovratovich, Christian Rechberger, Arnab Roy · 5 authors
No abstract is available for this record.
Muhammed F. Esgin, Ron Steinfeld, Joseph K. Liu, Dongxi Liu
We devise new techniques for design and analysis of efficient lattice-based zero-knowledge proofs (ZKP). First, we introduce one-shot proof techniques for non-linear polynomial relations of degree \(k\ge 2\), where the protocol achieves a negligible soundness error in a single execution, and thus performs significantly better in both computation and communication compared to prior protocols requiring multiple repetitions. Such proofs with degree \(k\ge 2\) have been crucial ingredients for important privacy-preserving protocols in the discrete logarithm setting, such as Bulletproofs (IEEE S&P ’18) and arithmetic circuit arguments (EUROCRYPT ’16). In contrast, one-shot proofs in lattice-based cryptography have previously only been shown for the linear case (\(k=1\)) and a very specific quadratic case (\(k=2\)), which are obtained as a special case of our technique.
Dan Boneh, Elette Boyle, Henry Corrigan-Gibbs, Niv Gilboa · 5 authors
We introduce and study the notion of fully linear probabilistically checkable proof systems. In such a proof system, the verifier can make a small number of linear queries that apply jointly to the input and a proof vector.
Xixun Yu, Zheng Yan, Rui Zhang
No abstract is available for this record.
Xin Pei, Liang Sun, Xuefeng Li, Kaiyan Zheng · 5 authors
While the multiple party computation (MPC) has been suggested for over two decades, we still have not witnessed implementations that make MPC or its derivates deployed in a palpable reality. Difficulties stem from serial security and trust issues, typically expressed in data leakage, lazy calculation, and deny of payment etc. Many solutions rely on a third party to organize parties co-working, however, this requires each participant to totally trust the third party and delegate the source data and payment to it. In this paper, we suggest a protocol under blockchain structure to achieve efficient MPC without a trusted third party. The cooperation and schedule tasks are executed by a zero-knowledge coordinator, while the smart contracts is used to handle user request and safe payment. Cryptography techniques are adopted to ensure confidentiality, privacy-preserving and verifiability. All the data are transferred and calculated in the cipher state, and only the payed user can decrypt for the calculation result.
André Souto
Security of data is crucial in nowadays societies. One of the most basic security protocols are the zero-knowledge protocols where a prover convinces a verifier of the knowledge of a secret information without revealing that piece of information. The tradicional approach to prove the security of these protocols is based on the (im)possibility of simulation of the interactions. A more fundamental way to prove the security is based solely on the information conveyed about proof. In order to establish that connection and quantifying the number of possible transformations that one can use in these protocols, we use Kolmogorov complexity and in particular we focus on the incompressibility theorem. In this paper we study the counterpart of this theorem by, instead of providing the number of x such that for a fixed y, Kt(x|y) ≈ Kt(x), we study for a fixed y the number of x such that Kt(x|y) ≈ Kt(x). As a second contribution of this paper we present an extension of the results regarding Kolmogorov one-way functions started in [3]. This cryptographic primitives have the property to be easy to compute but hard to invert and are a basilar ingredient for digital security.
José Ignacio Orlicki
This project was focused on designing a tool for optimizing complex transactions in a traditional bank accounts, Bitcoin wallet accounts and Bitcoin exchanges. The challenges include transference fees eroding the amounts transferred, Bitcoin volatility and arbitrage. The tool should support hundreds of accounts with each account identifi ed by a bank or exchange, and a currency. The basic user-case, we call it Debit Scenario, appears when an account consumes it capital and has very little funding (sink or demand account), then the user set a minimum funding for the account, and we need to balance all the accounts of the network, using many currency circulations though many paths to satisfy the specifi ed funding limits. Another user case, we called it Custodian Scenario, is when certain accounts (i.e. supply or non-custodians) has upper limit on the amount of capital so we need to distribute the excess value in other accounts (i.e. demand or custodians) of the network. The problem was modelled as a multi-commodity min-cost max- flow problem with specifi c constraints including arbitrage information, and solved with linear programming. Simple and complex numerical scenarios are presented too.
Maharage Nisansala Sevwandi Perera, Takeshi Koshiba
No abstract is available for this record.
Alessandro Chiesa, Michael A. Forbes, Tom Gur, Nicholas Spooner
Zero knowledge plays a central role in cryptography and complexity. The seminal work of Ben-Or et al. (STOC 1988) shows that zero knowledge can be achieved unconditionally for any language in NEXP , as long as one is willing to make a suitable physical assumption : if the provers are spatially isolated, then they can be assumed to be playing independent strategies. Quantum mechanics, however, tells us that this assumption is unrealistic, because spatially-isolated provers could share a quantum entangled state and realize a non-local correlated strategy. The MIP * model captures this setting. In this work, we study the following question: Does spatial isolation still suffice to unconditionally achieve zero knowledge even in the presence of quantum entanglement? We answer this question in the affirmative: we prove that every language in NEXP has a 2-prover zero knowledge interactive proof that is sound against entangled provers; that is, NEXP ⊆ ZK-MIP * . Our proof consists of constructing a zero knowledge interactive probabilistically checkable proof with a strong algebraic structure, and then lifting it to the MIP * model. This lifting relies on a new framework that builds on recent advances in low-degree testing against entangled strategies, and clearly separates classical and quantum tools. Our main technical contribution is the development of new algebraic techniques for obtaining unconditional zero knowledge; this includes a zero knowledge variant of the celebrated sumcheck protocol, a key building block in many probabilistic proof systems. A core component of our sumcheck protocol is a new algebraic commitment scheme, whose analysis relies on algebraic complexity theory.
David Derler, Daniel Slamanig
No abstract is available for this record.
Sanketh Menda, John Watrous
This paper investigates the power of quantum statistical zero knowledge interactive proof systems in the relativized setting. We prove the existence of an oracle relative to which quantum statistical zero-knowledge does not contain UP intersect coUP, and we prove that quantum statistical zero knowledge does not contain UP relative to a random oracle with probability 1. Our proofs of these statements rely on a bound on output state discrimination for relativized quantum circuits based on the quantum adversary method of Ambainis, following a technique similar to one used by Ben-David and Kothari to prove limitations on a query complexity variant of quantum statistical zero-knowledge.
Souradyuti Paul, Ananya Shrivastava
No abstract is available for this record.
Takashi Yamakawa
Bilinear maps (also called pairings) have been used for constructing various kinds of cryptographic primitives including (but not limited to) short signatures, identity-based encryption, attribute-based encryption, and non-interactive zero-knowledge proof systems. In known instantiations of cryptographic bilinear maps based on eliptic curves, source and target groups are different groups, which may restrict applications of bilinear maps. Cheon and Lee studied self-bilinear maps, which are bilinear maps whose source and target groups are identical. They showed huge potential of self-bilinear maps by showing that self-bilinear maps can be transformed into multilinear maps, which give further more cryptographic applications including (but not limited to) multiparty non-interactive key exchange, broadcast encryption, attribute-based encryption, homomorphic signatures, and obfuscation. However, they also showed a strong negative result on the existence of cryptographic self-bilinear maps. Namely, they showed that if there exists an efficiently computable self-bilinear map on a known order group, then the computational Diffie-Hellman (CDH) assumption does not hold on the group. This means that cryptographically useful self-bilinear maps do not exist on groups of known order. On the other hand, there is no negative result for self-bilinear maps on groups of unknown order. Indeed, Yamakawa et al. gave a partial positive result for self-bilinear maps on unknown order groups. Namely, they constructed self-bilinear maps with auxiliary information, which is a weaker variant of self-bilinear maps based on indistinguishability obfuscation. Though they showed that they are sufficient for some applications of self-bilinear maps, they are not as useful as "ideal" self-bilinear maps, which do not need auxiliary information. In this talk, we first review the construction of self-bilinear maps with auxiliary information given by Yamakawa et al. Then we consider the possibility of constructing ideal self-bilinear maps.
Yi Deng, Xuyang Song, Jingyue Yu, Yu Chen
No abstract is available for this record.
Matteo Campanelli, Rosario Gennaro
No abstract is available for this record.
Zvika Brakerski, Vadim Lyubashevsky, Vinod Vaikuntanathan, Daniel Wichs
No abstract is available for this record.
Charanjit S. Jutla, Miyako Ohkubo, Arnab Roy
No abstract is available for this record.
Fuyuki Kitagawa, Keisuke Tanaka
We propose a framework for achieving a public-key encryption (PKE) scheme that satisfies key dependent message security against chosen ciphertext attacks (KDM-CCA security) based on projective hash function. Our framework can be instantiated under the decisional diffie-hellman (DDH), quadratic residuosity (QR), and decisional composite residuosity (DCR) assumptions. The constructed schemes are KDM-CCA secure with respect to affine functions and compatible with the amplification method shown by Applebaum (EUROCRYPT 2011). Thus, they lead to PKE schemes satisfying KDM-CCA security for all functions computable by a-priori bounded size circuits. They are the first PKE schemes satisfying such a security notion in the standard model using neither non-interactive zero knowledge proof nor bilinear pairing. The above framework based on projective hash function captures only KDM-CCA security in the single user setting. However, we can prove the KDM-CCA security in the multi user setting of our concrete instantiations by using their algebraic structures explicitly. Especially, we prove that our DDH based scheme satisfies KDM-CCA security in the multi user setting with the same parameter setting as in the single user setting.
Yusuke Sakai, Shuichi Katsumata, Nuttapong Attrapadung, Goichiro Hanaoka
No abstract is available for this record.