### All papers in 2019 (1498 results)

Show abstract

We introduce new authenticated key exchange protocols which on one hand do not resort to standard public key setups with corresponding assumptions of computationally hard problems, but on the other hand are more efficient than distributing symmetric keys among the participants. To this end, we rely on a trusted central authority distributing key material which size is independent of the total number of users, and which allows the users to obtain shared secret keys. We analyze the security of our construction taking into account various attack models. Importantly, only symmetric primitives are needed in the protocol making it an alternative to quantum-safe key exchange protocols which rely on hardness assumptions.

Last updated: 2020-01-07

Show abstract

Recently, Srinath and Chandrasekaran have proposed an undeniable blind signature scheme (UBSS) from supersingular isogeny to provide signer’s control in a quantum-resistant blind signature. However, certain weaknesses of undeniable signature have already been observed and have been overcome by formalizing the designated verifier signature (DVS). In this paper, we explore the possibility of generic construction of a DVS from hard homogeneous spaces. Further, following this motivation, we realize a quantum-resistant designated verifier blind signature (DVBS) scheme based on supersingular isogenies from the proposed generic construction. In contrast to the UBSS, our construction do not require interactive communication between the signer and the verifier, yet engages the signer in the verification. The compact signature adds more security properties in a quantum-resistant blind signature to be useful in specific applications including electronic tendering, online auctions etc.

Last updated: 2019-12-30

Show abstract

The Shell sort algorithm is one of the most practically effective sorting algorithms. However, it is difficult to execute this algorithm with its intended running time complexity on data encrypted using fully homomorphic encryption (FHE), because the insertion sort in Shell sort has to be performed by considering the worst-case input data. In this paper, in order for the sorting algorithm to be used on FHE data, we modify the Shell sort with an additional parameter $\alpha$ and a gap sequence of powers of two. The modified Shell sort is found to have the trade-off between the running time complexity of $O(n^{3/2}\sqrt{\alpha+\log\log n})$ and the sorting failure probability of $2^{-\alpha}$. Its running time complexity is close to the intended running time complexity of $O(n^{3/2})$ and the sorting failure probability can be made very low with slightly increased running time. Further, the optimal window length of the modified Shell sort is also derived via convex optimization. The proposed analysis of the modified Shell sort is numerically confirmed by using randomly generated arrays. Further, the performance of the modified Shell sort is numerically compared with the case of Ciura's optimal gap sequence and the case of the optimal window length obtained through the convex optimization.

Last updated: 2019-12-30

Show abstract

In 2020 Xin et al.proposed a new identity-based quantum signature based on Bell states scheme. By using a one-time padding (OTP) for both-side transfer operations like, "XOR", Hadamard H, and Y, they confirmed the security of the proposed scheme. However, after analyses, we found that the scheme cannot resist both the existing forgery attack and meaningful message attack. Therefore, we modified their scheme to include the required security, unforgeability, which is very important in quantum signature scheme.

Last updated: 2019-12-30

Show abstract

At CRYPTO '12, Landecker et al. introduced the cascaded LRW2 (or CLRW2) construction, and proved that it is a secure tweakable block cipher up to roughly $ 2^{2n/3} $ queries. Recently, Mennink presented a distinguishing attack on CLRW2 in $ 2n^{1/2}2^{3n/4} $ queries. In the same paper, he discussed some non-trivial bottlenecks in proving tight security bound, i.e. security up to $ 2^{3n/4} $ queries. Subsequently, he proved security up to $ 2^{3n/4} $ queries for a variant of CLRW2 using $ 4 $-wise independent AXU assumption and the restriction that each tweak value occurs at most $ 2^{n/4} $ times. Moreover, his proof relies on a version of mirror theory which is yet to be publicly verified. In this paper, we resolve the bottlenecks in Mennink's approach and prove that the original CLRW2 is indeed a secure tweakable block cipher up to roughly $ 2^{3n/4} $ queries. To do so, we develop two new tools: First, we give a probabilistic result that provides improved bound on the joint probability of some special collision events; Second, we present a variant of Patarin's mirror theory in tweakable permutation settings with a self-contained and concrete proof. Both these results are of generic nature, and can be of independent interests. To demonstrate the applicability of these tools, we also prove tight security up to roughly $ 2^{3n/4} $ queries for a variant of DbHtS, called DbHtS-p, that uses two independent universal hash functions.

Last updated: 2020-05-15

Show abstract

Verifiable outsourcing systems offload a large computation to a remote server, but require that the remote server provide a succinct proof, called a SNARK, that proves that the server carried out the computation correctly. Real-world applications of this approach can be found in several blockchain systems that employ verifiable outsourcing to process a large number of transactions off-chain. This reduces the on-chain work to simply verifying a succinct proof that transaction processing was done correctly. In practice, verifiable outsourcing of state updates is done by updating the leaves of a Merkle tree, recomputing the resulting Merkle root, and proving using a SNARK that the state update was done correctly.
In this work, we use a combination of existing and novel techniques to implement an RSA accumulator inside of a SNARK, and use it as a replacement for a Merkle tree. We specifically optimize the accumulator for compatibility with SNARKs. Our experiments show that the resulting system reduces costs compared to existing approaches that use Merkle trees for committing to the current state. These results apply broadly to any system that needs to offload batches of state updates to an untrusted server.

Last updated: 2020-06-23

Show abstract

Solving the equation $P_a(X):=X^{q+1}+X+a=0$ over finite field
$\GF{Q}$, where $Q=p^n, q=p^k$ and $p$ is a prime, arises in many
different contexts including finite geometry, the inverse Galois
problem \cite{ACZ2000}, the construction of difference sets with
Singer parameters \cite{DD2004}, determining cross-correlation
between $m$-sequences \cite{DOBBERTIN2006,HELLESETH2008} and to
construct error-correcting codes \cite{Bracken2009}, as well as to
speed up the index calculus method for computing discrete logarithms
on finite fields \cite{GGGZ2013,GGGZ2013+} and on algebraic curves
\cite{M2014}.
Subsequently, in
\cite{Bluher2004,HK2008,HK2010,BTT2014,Bluher2016,KM2019,CMPZ2019,MS2019},
the $\GF{Q}$-zeros of $P_a(X)$ have been studied: in
\cite{Bluher2004} it was shown that the possible values of the
number of
the zeros that $P_a(X)$ has in $\GF{Q}$ is $0$, $1$, $2$ or $p^{\gcd(n, k)}+1$.
Some criteria for the number of the $\GF{Q}$-zeros of $P_a(x)$ were
found in \cite{HK2008,HK2010,BTT2014,KM2019,MS2019}.
However, while the ultimate goal is to identify all the
$\GF{Q}$-zeros,
even in the case $p=2$, it was solved only under the condition $\gcd(n, k)=1$ \cite{KM2019}.
We discuss this equation without any restriction on $p$ and
$\gcd(n,k)$. New criteria for the number of the $\GF{Q}$-zeros of
$P_a(x)$ are proved. For the cases of one or two $\GF{Q}$-zeros, we
provide explicit expressions for these rational zeros in terms of
$a$. For the case of $p^{\gcd(n, k)}+1$ rational zeros, we provide a
parametrization of such $a$'s and express the $p^{\gcd(n, k)}+1$
rational zeros by using that parametrization.

Last updated: 2019-12-30

Show abstract

We show that many symmetric cryptography primitives would not be less safe with significantly fewer rounds. To support this claim, we review the cryptanalysis progress in the last 20 years, examine the reasons behind the current number of rounds, and analyze the risk of doing fewer rounds. Advocating a rational and scientific approach to round numbers selection, we propose revised number of rounds for AES, BLAKE2, ChaCha, and SHA-3, which offer more consistent security margins across primitives and make them much faster, without increasing the security risk.

Last updated: 2021-05-24

Show abstract

Almost perfect nonlinear (APN) and almost bent (AB) functions are integral components of modern block ciphers and play a fundamental role in symmetric cryptography. In this paper, we describe a procedure for searching for quadratic APN functions with coefficients in GF(2) over the finite fields GF(2^n) and apply this procedure to classify all such functions over GF(2^n) with n up to 9. We discover two new APN functions (which are also AB) over GF(2^9) that are CCZ-inequivalent to any known APN function over this field. We also verify that there are no quadratic APN functions with coefficients in GF(2) over GF(2^n) with n between 6 and 8 other than the currently known ones.

Last updated: 2019-12-30

Show abstract

In 2017, Ward Beullens \textit{et al.} submitted Lifted Unbalanced Oil and Vinegar (LUOV)\cite{beullens2017field}, a signature scheme based on the famous multivariate public key cryptosystem (MPKC) called Unbalanced Oil and Vinegar (UOV), to NIST for the competition for post-quantum public key scheme standardization. The defining feature of LUOV is that, though the public key $\mathcal{P}$ works in the extension field of degree $r$ of $\mathbb{F}_2$, the coefficients of $\mathcal{P}$ come from $\mathbb{F}_2$. This is done to significantly reduce the size of $\mathcal{P}$.
The LUOV scheme is now in the second round of the NIST PQC standardization process.
In this paper we introduce a new attack on LUOV. It exploits the "lifted" structure of LUOV to reduce direct attacks on it to those over a subfield. We show that this reduces the complexity below the targeted security for the NIST post-quantum standardization competition.

Last updated: 2020-07-20

Show abstract

While messaging systems with strong security guarantees are widely used in practice, designing a protocol that scales efficiently to large groups and enjoys similar security guarantees remains largely open. The two existing proposals to date are ART (Cohn-Gordon et al., CCS18) and TreeKEM (IETF, The Messaging Layer Security Protocol, draft). TreeKEM is the currently considered candidate by the IETF MLS working group, but dynamic group operations (i.e. adding and removing users) can cause efficiency issues. In this paper we formalize and analyze a variant of TreeKEM which we term Tainted TreeKEM (TTKEM for short). The basic idea underlying TTKEM was suggested by Millican (MLS mailing list, February 2018). This version is more efficient than TreeKEM for some natural distributions of group operations, we quantify this through simulations.
Our second contribution is two security proofs for TTKEM which establish post compromise and forward secrecy even against adaptive attackers. If $n$ is the group size and $Q$ the number of operations, the security loss (to the underlying PKE) in the Random Oracle Model is a polynomial factor $(Qn)^2$, and in the Standard Model a quasipolynomial $Q^{\log(n)}$. Our proofs can be adapted to TreeKEM as well. Before our work no security proof for any TreeKEM-like protocol establishing tight security against an adversary who can adaptively choose the sequence of operations was known. We also are the first to prove (or even formalize) active security where the server can arbitrarily deviate from the protocol specification. Proving fully active security - where also the users can arbitrarily deviate - remains open.

Last updated: 2020-10-20

Show abstract

Fine-grained cryptographic primitives are secure against adversaries with bounded resources and can be computed by honest users with less resources than the adversaries.
In this paper, we revisit the results by Degwekar, Vaikuntanathan, and Vasudevan in Crypto 2016 on fine-grained cryptography and show constructions of three key fundamental fine-grained cryptographic primitives: one-way permutations, hash proof systems (which in turn implies a public-key encryption scheme against chosen chiphertext attacks), and trapdoor one-way functions.
All of our constructions are computable in $\mathsf{NC}^1$ and secure against (non-uniform) $\mathsf{NC}^1$ circuits under the widely believed worst-case assumption $\mathsf{NC}^1 \subsetneq \oplus \mathsf{L/poly}$.

Last updated: 2019-12-30

Show abstract

The existing power trace extractors consider the case that the number of power traces owned by the attacker is sufficient to guarantee his successful attacks, and the goal of power trace extraction is to lower the complexity rather than increase the success rates. Although having strict theoretical proofs, they are too simple and leakage characteristics of POIs have not been thoroughly analyzed. They only maximize the variance of data-dependent power consumption component and ignore the noise component, which results in very limited SNR to improve and seriously affects the performance of extractors. In this paper, we provide a rigorous theoretical analysis of SNR of power traces, and propose a novel SNR-centric extractor, named Shortest Distance First (SDF), to extract power traces with smallest the estimated noise by taking advantage of known plaintexts. In addition, to maximize the variance of the exploitable component while minimizing the noise, we refer to the SNR estimation model and propose another novel extractor named Maximizing Estimated SNR First (MESF). Finally, we further propose an advanced extractor called Mean optimized MESF (MMESF) that exploits the mean power consumption of each plaintext byte value to more accurately and reasonably estimate the data-dependent power consumption of the corresponding samples. Experiments on both simulated power traces and measurements from an ATmega328p micro-controller demonstrate the superiority of our new extractors.

Last updated: 2019-12-30

Show abstract

We present efficient Zero-Knowledge Proofs of Knowledge (ZKPoK) for linear and multiplicative relations among secret messages hidden as Ring Learning With Errors (RLWE) samples. Messages are polynomials in $\mathbb{Z}_q[x]/\left<x^{n}+1\right>$ and our proposed protocols for a ZKPoK are based on the celebrated paper by Stern on identification schemes using coding problems (Crypto'93). Our $5$-move protocol achieves a soundness error slightly above $1/2$ and perfect Zero-Knowledge.
As an application we present Zero-Knowledge Proofs of Knowledge of relations between committed messages. The resulting commitment scheme is perfectly binding with overwhelming probability over the choice of the public key, and computationally hiding under the RLWE assumption. Compared with previous Stern-based commitment scheme proofs we decrease computational complexity, improve the size of the parameters and reduce the soundness error of each round.

Last updated: 2020-09-02

Show abstract

Identity-based encryption (IBE) is a powerful mechanism for maintaining security. However, systems based on IBE are unpopular when compared with those of the public-key encryption (PKE). In our opinion, one of the reasons is a gap between theory and practice. For example, a generic transformation of weakly/strongly robust IBE from any IBE has been proposed by Abdalla et al., no robust IBE scheme is explicitly given. This means that, theoretically, anyone can construct a weakly/strongly robust IBE scheme by employing this transformation. However, this seems not easily applicable to non-cryptographers. In this paper, we first introduce the Gentry IBE scheme constructed over Type-3 pairings by employing the transformation proposed by Abe et al., and second we explicitly give strongly/weakly robust Gentry IBE schemes by employing the Abdalla et al. transformation. Finally, we show its implementation result and show that we can add strong robustness to the Gentry IBE scheme with a very few additional costs. We employ the mcl library to support a Barreto-Naehrig curve defined over the 462-bit prime. The encryption requires about 5 ms, whereas the decryption requires about 9 ms.

Last updated: 2020-04-28

Show abstract

Blockchain, which realizes state machine replication (SMR), is a fundamental building block of decentralized systems, such as cryptocurrencies and smart contracts. These systems require a consensus protocol in their global-scale, public, and trustless networks. In such an environment, consensus protocols require high resiliency, which is the ability to tolerate a fraction of faulty replicas, and thus synchronous protocols have been gaining significant research attention recently. Abraham et al. proposed a simple and practical synchronous SMR protocol called Sync Hotstuff (to be presented in IEEE S\&P 2020). Sync Hotstuff achieves $2\Delta$ latency, which is near optimal in a synchronous protocol, and its throughput without lock-step execution is comparable to that of partially synchronous protocols. Sync Hotstuff was presented under a standard synchronous model as well as under a weaker, but more realistic, model called mobile sluggish model. Sync Hotstuff also adopts an optimistic responsive mode, in which the latency is independent of $\Delta$. However, Sync Hotstuff has a critical security vulnerability with which an adversary can conduct double spending or denial-of-service attack. In this paper, we present an attack we call force-locking attack on Sync Hotstuff. This attack violates the safety, i.e., consistency of agreements, of the protocol under the standard synchronous model and the liveness, i.e., progress of agreements, of all versions of the protocol, including the mobile sluggish model and responsive mode. The force-locking attack is not only a specific attack on Sync Hotstuff but also on some general blockchain protocols. After describing the attack, we will present some refinements to prevent this attack. Our refinements remove the security vulnerability on Sync Hotstuff without any performance compromises. We will also provide formal proofs of the security for each model.

Last updated: 2020-01-24

Show abstract

We study the computation and communication costs and their possible trade-offs in various constructions for private information retrieval (PIR), including schemes based on homomorphic encryption and the Gentry--Ramzan PIR (ICALP'05).
We improve over the construction of SealPIR (S&P'18) using compression techniques and a new oblivious expansion, which reduce the communication bandwidth by 60% while preserving essentially the same computation cost. We then present MulPIR, a PIR protocol leveraging multiplicative homomorphism to implement the recursion steps in PIR. This eliminates the exponential dependence of PIR communication on the recursion depth due to the ciphertext expansion, at the cost of an increased computational cost for the server. Additionally, MulPIR outputs a regular homomorphic encryption ciphertext, which can be homomorphically post-processed. As a side result, we describe how to do conjunctive and disjunctive PIR queries.
On the other end of the communication--computation spectrum, we take a closer look at Gentry--Ramzan PIR, a scheme with asymptotically optimal communication rate. Here, the bottleneck is the server's computation, which we manage to reduce significantly. Our optimizations enable a tunable trade-off between communication and computation, which allows us to reduce server computation by as much as 85%, at the cost of an increased query size. We further show how to efficiently construct PIR for sparse databases. Our constructions support batched queries, as well as symmetric PIR.
We implement all of our PIR constructions, and compare their communication and computation overheads with respect to each other for several application scenarios.

Last updated: 2021-08-03

Show abstract

We present a new succinct zero knowledge argument scheme for layered arithmetic circuits without trusted setup. The prover time is $O(C + n \log n)$ and the proof size is $O(D \log C + \log^2 n)$ for a $D$-depth circuit with $n$ inputs and $C$ gates. The verification time is also succinct, $O(D \log C + \log^2 n)$, if the circuit is structured. Our scheme only uses lightweight cryptographic primitives such as collision-resistant hash functions and is plausibly post-quantum secure. We implement a zero knowledge argument system, Virgo, based on our new scheme and compare its performance to existing schemes. Experiments show that it only takes 53 seconds to generate a proof for a circuit computing a Merkle tree with 256 leaves, at least an order of magnitude faster than all other succinct zero knowledge argument schemes. The verification time is 50ms, and the proof size is 253KB, both competitive to existing systems.
Underlying Virgo is a new transparent zero knowledge verifiable polynomial delegation scheme with logarithmic proof size and verification time. The scheme is in the interactive oracle proof model and may be of independent interest.

Last updated: 2020-07-16

Show abstract

In this work we study metric properties of the well-known family of binary Reed-Muller codes. Let $A$ be an arbitrary subset of the Boolean cube, and $\widehat{A}$ be the metric complement of $A$ --- the set of all vectors of the Boolean cube at the maximal possible distance from $A$. If the metric complement of $\widehat{A}$ coincides with $A$, then the set $A$ is called a metrically regular set. The problem of investigating metrically regular sets appeared when studying bent functions, which have important applications in cryptography and coding theory and are also one of the earliest examples of a metrically regular set. In this work we describe metric complements and establish the metric regularity of the codes $\mathcal{RM}(0,m)$ and $\mathcal{RM}(k,m)$ for $k \geqslant m-3$. Additionally, the metric regularity of the codes $\mathcal{RM}(1,5)$ and $\mathcal{RM}(2,6)$ is proved. Combined with previous results by Tokareva N. (2012) concerning duality of affine and bent functions, this establishes the metric regularity of most Reed-Muller codes with known covering radius. It is conjectured that all Reed-Muller codes are metrically regular.

Last updated: 2020-10-19

Show abstract

Vélu's formulas for computing isogenies over Weierstrass model of elliptic curves has been extended to other models of elliptic curves such as the Huff model, the Edwards model and the Jacobi model of elliptic curves. This work continues this line of research by providing efficient formulas for computing isogenies over elliptic curves of Hessian form. We provide explicit formulas for computing isogenies of degree 3 and isogenies of degree l not divisible by 3. The theoretical cost of computing these maps in this case is slightly faster than the case with other curves. We also extend the formulas to obtain isogenies over twisted and generalized Hessian forms of elliptic curves. The formulas in this work have been verified with the Sage software and are faster than previous results on the same curve.

Last updated: 2019-12-23