搜索结果: 1-15 共查到“密码学 Complexity”相关记录174条 . 查询时间(0.076 秒)
Transparent Polynomial Commitment Scheme with Polylogarithmic Communication Complexity
polynomial commitments zero-knowledge proofs proximity testing
2019/9/16
We introduce novel efficient and transparent construction of the polynomial commitment scheme. A polynomial commitment scheme allows one side (the prover) to commit to a polynomial of predefined degre...
Beyond Honest Majority: The Round Complexity of Fair and Robust Multi-party Computation
Fairness and Guaranteed Output Delivery MPC Round Complexity
2019/9/5
Two of the most sought-after properties of Multi-party Computation (MPC) protocols are fairness and guaranteed output delivery (GOD), the latter also referred to as robustness. Achieving both, however...
Non-malleable Zero-Knowledge Arguments with Lower Round Complexity
Zero-Knowledge Non-Malleable Multi-Collision Resistance
2019/8/30
Round complexity is one of the fundamental problems in zero-knowledge proof systems. Non-malleable zero-knowledge (NMZK) protocols are zero-knowledge protocols that provide security even when man-in-t...
Although Byzantine Agreement (BA) has been studied for three decades, perhaps somewhat surprisingly, there still exist significant gaps in our understanding regarding its round complexity. First, alth...
On the Round Complexity of Randomized Byzantine Agreement
Byzantine agreement lower bound round complexity
2019/7/31
We prove lower bounds on the round complexity of randomized Byzantine agreement (BA) protocols, bounding the halting probability of such protocols after one and two rounds.
Athena: A verifiable, coercion-resistant voting system with linear complexity
cryptographic protocols election schemes
2019/7/8
Seminal work by Juels, Catalano & Jakobsson delivered a verifiable, coercion-resistant voting system with quadratic complexity. This manuscript attempts to advance the state-of-the-art by delivering a...
Complexity of Estimating Renyi Entropy of Markov Chains
information theory Renyi entropy Min-entropy
2019/7/8
Estimating entropy of random processes is one of the fundamental problems of machine learning and property testing. It has numerous applications to anything from DNA testing and predictability of huma...
Linear Complexity of A Family of Binary pq2 -periodic Sequences From Euler Quotients
Cryptography linear complexity binary sequences
2019/6/21
We first introduce a family of binary pq2pq2 -periodic sequences based on the Euler quotients modulo pqpq, where pp and qq are two distinct odd primes and pp divides q−1q−1. The minimal po...
On the Complexity of ``Superdetermined'' Minrank Instances
Minrank problem Multivariate Cryptanalysis HFE
2019/6/21
The Minrank (MR) problem is a computational problem closely related to attacks on code- and multivariate-based schemes. In this paper we revisit the so-called Kipnis-Shamir (KS) approach to this probl...
On the Quantum Complexity of the Continuous Hidden Subgroup Problem
Quantum Algorithm Hidden Subgroup Period Finding
2019/6/19
The Hidden Subgroup Problem (HSP) aims at capturing all problems that are susceptible to be solvable in quantum polynomial time following the blueprints of Shor's celebrated algorithm. Successful solu...
On the Complexity of Collision Resistant Hash Functions: New and Old Black-Box Separations
Collision Resistance Statistical Zero Knowledge Black box separations
2019/6/12
The complexity of collision-resistant hash functions has been long studied in the theory of cryptography. While we often think about them as a Minicrypt primitive, black-box separations demonstrate th...
Unconditionally Secure Computation Against Low-Complexity Leakage
Low-Complexity Leakage complexity-theoretic assumptions
2019/6/4
We consider the problem of constructing leakage-resilient circuit compilers that are secure against global leakage functions with bounded output length. By global, we mean that the leakage can depend ...
Improved Filter Permutators: Combining Symmetric Encryption Design, Boolean Functions, Low Complexity Cryptography, and Homomorphic Encryption, for Private Delegation of Computations
Filter Permutator FLIP Homomorphic Encryption
2019/5/14
Motivated by the application of delegating computation, we revisit the design of filter permutators as a general approach to build stream ciphers that can be efficiently evaluated in a fully homomorph...
A taxonomy of pairings, their security, their complexity
Discrete Logarithm Problem Number Field Sieve Elliptic Curves
2019/5/14
A recent NFS attack against pairings made it necessary to increase the key sizes of the most popular families of pairings : BN, BLS12, KSS16, KSS18 and BLS24. The attack applies to other families of p...
In this note, we leverage some of our previous results to produce a concise and rigorous proof for the complexity of the generalized MinRank Problem in the under-defined and well-defined case. Our mai...