All papers in 2022 (Page 17 of 1781 results)

Last updated:  2022-02-24
Vector Commitments over Rings and Compressed $\Sigma$-Protocols
Uncategorized
Thomas Attema, Ignacio Cascudo, Ronald Cramer, Ivan Bjerre Damgård, Daniel Escudero
Show abstract
Uncategorized
Compressed $\Sigma$-Protocol Theory (CRYPTO 2020) presents an ``alternative'' to Bulletproofs that achieves the same communication complexity while adhering more elegantly to existing $\Sigma$-protocol theory, which enables their techniques to be directly applicable to other widely used settings in the context of ``plug \& play'' algorithmics. Unfortunately, their techniques are restricted to arithmetic circuits over \emph{prime} fields, which rules out the possibility of using more machine-friendly moduli such as powers of $2$, which have proven to improve efficiency in applications. In this work we show that such techniques can be generalized to the case of arithmetic circuits modulo \emph{any} number. This enables the use of powers of $2$, which can prove to be beneficial for efficiency, but it also facilitates the use of other moduli that might prove useful in different applications. In order to achieve this, we first present an instantiation of the main building block of the theory of compressed $\Sigma$-protocols, namely compact vector commitments. Our construction, which may be of independent interest, is homomorphic modulo any positive integer $m$, a result that was not known in the literature before. Second, we generalize the Compressed $\Sigma$-Protocol Theory from finite fields to $\mathbb{Z}_m$. The main challenge here is ensuring that there are large enough challenge sets as to fulfill the necessary soundness requirements, which is achieved by considering certain ring extensions. Our techniques have application as publicly verifiable zero knowledge proofs of correct computation on homomorphically encrypted data, where for a more flexible parameter instantiation it is useful that the ciphertext space is allowed to be a modular or Galois ring rather than a field: concretely, our protocols can be plugged as a commit-and-proof argument into a recent result on efficient verifiable computation schemes on encrypted data with context-hiding (PKC 21) which exploited this advantage.
Last updated:  2022-09-21
Towards Globally Optimized Hybrid Homomorphic Encryption - Featuring the Elisabeth Stream Cipher
Orel Cosseron, Clément Hoffmann, Pierrick Méaux, François-Xavier Standaert
Hybrid Homomorphic Encryption (HHE) reduces the amount of computation client-side and band- width usage in a Fully Homomorphic Encryption (FHE) framework. HHE requires the usage of specific sym- metric schemes that can be evaluated homomorphically efficiently. In this paper, we introduce the paradigm of Group Filter Permutator (GFP) as a generalization of the Improved Filter Permutator paradigm introduced by M ́eaux et al. From this paradigm, we specify Elisabeth , a family of stream cipher and give an instance: Elisabeth-4 . After proving the security of this scheme, we provide a Rust implementation of it and ensure its performance is comparable to state-of-the-art HHE. The true strength of Elisabeth lies in the available opera- tions server-side: while the best HHE applications were limited to a few multiplications server-side, we used data sent through Elisabeth-4 to homomorphically evaluate a neural network inference. Finally, we discuss the improvement and loss between the HHE and the FHE framework and give ideas to build more efficient schemes from the Elisabeth family
Last updated:  2022-02-20
Locally Verifiable Signature and Key Aggregation
Rishab Goyal, Vinod Vaikuntanathan
Aggregate signatures (Boneh, Gentry, Lynn, Shacham, Eurocrypt 2003) enable compressing a set of $N$ signatures on $N$ different messages into a short aggregate signature. This reduces the space complexity of storing the signatures from linear in $N$ to a fixed constant (that depends only on the security parameter). However, verifying the aggregate signature requires access to all $N$ messages, resulting in the complexity of verification being at least $\Omega(N)$. In this work, we introduce the notion of locally verifiable aggregate signatures that enable efficient verification: given a short aggregate signature $\sigma$ (corresponding to a set $\mathcal{M}$ of $N$ messages), the verifier can check whether a particular message $m$ is in the set, in time independent of $N$. Verification does not require knowledge of the entire set $\mathcal{M}$. We demonstrate many natural applications of locally verifiable aggregate signature schemes: in the context of certificate transparency logs; in blockchains; and for redacting signatures, even when all the original signatures are produced by a single user. We provide two constructions of single-signer locally verifiable aggregate signatures, the first based on the RSA assumption and the second on the bilinear Diffie-Hellman inversion assumption, both in the random oracle model. As an additional contribution, we introduce the notion of compressing cryptographic keys in identity-based encryption (IBE) schemes, show applications of this notion, and construct an IBE scheme where the secret keys for $N$ identities can be compressed into a single aggregate key, which can then be used to decrypt ciphertexts sent to any of the $N$ identities.
Last updated:  2022-11-09
Lower Bound on SNARGs in the Random Oracle Model
Iftach Haitner, Daniel Nukrai, Eylon Yogev
Succinct non-interactive arguments (SNARGs) have become a fundamental primitive in the cryptographic community. The focus of this work is constructions of SNARGs in the Random Oracle Model (ROM). Such SNARGs enjoy post-quantum security and can be deployed using lightweight cryptography to heuristically instantiate the random oracle. A ROM-SNARG is \emph{$(t,\varepsilon)$-sound} if no $t$-query malicious prover can convince the verifier to accept a false statement with probability larger than $\varepsilon$. Recently, Chiesa-Yogev (CRYPTO '21) presented a ROM-SNARG of length ${\Theta}(\log (t/\varepsilon) \cdot \log t)$ (ignoring $\log n$ factors, for $n$ being the instance size). This improvement, however, is still far from the (folklore) lower bound of $\Omega(\log (t/\varepsilon))$. Assuming the \textit{randomized exponential-time hypothesis}, we prove a tight lower bound of ${\Omega}(\log (t/\varepsilon) \cdot \log t)$ for the length of {$(t,\varepsilon)$-sound} ROM-SNARGs. Our lower bound holds for constructions with non-adaptive verifiers and strong soundness notion called \textit{salted soundness}, restrictions that hold for \emph{all} known constructions (ignoring contrived counterexamples). We prove our lower bound by transforming any short ROM-SNARG (of the considered family) into a same length ROM-SNARG in which the verifier asks only a \emph{few} oracles queries, and then apply the recent lower bound of Chiesa-Yogev (TCC '20) for such SNARGs.
Last updated:  2022-11-02
The Power of the Differentially Oblivious Shuffle in Distributed Privacy Mechanisms
Mingxun Zhou, Elaine Shi
The shuffle model has been extensively investigated in the distributed differential privacy (DP) literature. For a class of useful computational tasks, the shuffle model allows us to achieve privacy-utility tradeoff similar to those in the central model, while shifting the trust from a central data curator to a ``trusted shuffle'' which can be implemented through either trusted hardware or cryptography. Very recently, several works explored cryptographic instantiations of a new type of shuffle with relaxed security, called {\it differentially oblivious (DO) shuffles}. These works demonstrate that by relaxing the shuffler's security from simulation-style secrecy to differential privacy, we can achieve asymptotical efficiency improvements. A natural question arises, can we replace the shuffler in distributed DP mechanisms with a DO-shuffle while retaining a similar privacy-utility tradeoff? In this paper, we prove an optimal privacy amplification theorem by composing any locally differentially private (LDP) mechanism with a DO-shuffler, achieving parameters that tightly match the shuffle model. Moreover, we explore multi-message protocols in the DO-shuffle model, and construct mechanisms for the real summation and histograph problems. Our error bounds approximate the best known results in the multi-message shuffle-model up to sub-logarithmic factors. Our results also suggest that just like in the shuffle model, allowing each client to send multiple messages is fundamentally more powerful than restricting to a single message. As an application, we derive the result of using repeated DO-shuffling for privacy-preserving time-series data aggregation.
Last updated:  2022-02-20
Towards Fair Multiparty Computation in Scriptless Distributed Ledger Systems
Minze Xu, Yuan Zhang, Sheng Zhong
Fairness is one of the fundamental properties for multiparty computation (MPC) protocols. Although fair MPC protocols for general functions is shown to be impossible with a dishonest majority, a variant of fairness called ``fairness with penalty'' has been explored recently. A MPC protocol provides fairness with penalty if either all participants can get the output, or the dishonest parties who break the protocol after getting the output will be financially penalized. Fairness with penalty is enabled by previous works leveraging the emerging distributed ledger systems (DLS), e.g. Bitcoin and Ethereum. They utilize the scripting functionality provided by the DLSs to make automatic penalty practical without relying on any trusted third party. However, there is also a significant number of DLSs that do not provide the scripting functionality. In this paper, we propose the ROSE protocol which enables fairness with penalty while only requiring the underlying DLS can verify and broadcast digital signatures on transactions. This requirement can be fulfilled by almost all DLSs, including the scriptless DLSs. To the best of our knowledge, it is still unknown how to realize fairness with penalty on scriptless DLSs before our work. We also provide a implementation of ROSE. The experimental results show that applying ROSE only brings little computation and communication overhead.
Last updated:  2022-07-27
WeRLman: To Tackle Whale (Transactions), Go Deep (RL)
Roi Bar-Zur, Ameer Abu-Hanna, Ittay Eyal, Aviv Tamar
The security of proof-of-work blockchain protocols critically relies on incentives. Their operators, called miners, receive rewards for creating blocks containing user-generated transactions. Each block rewards its creator with newly minted tokens and with transaction fees paid by the users. The protocol stability is violated if any of the miners surpasses a threshold ratio of the computational power; she is then motivated to deviate with selfish mining and increase her rewards. Previous analyses of selfish mining strategies assumed constant rewards. But with statistics from operational systems, we show that there are occasional whales- blocks with exceptional rewards. Modeling this behavior implies a state-space that grows exponentially with the parameters, becoming prohibitively large for existing analysis tools. We present the WeRLman framework to analyze such models. WeRLman uses deep Reinforcement Learning (RL), inspired by the state-of-the-art AlphaGo Zero algorithm. Directly extending AlphaGo Zero to a stochastic model leads to high sampling noise, which is detrimental to the learning process. Therefore, WeRLman employs novel variance reduction techniques by exploiting the recurrent nature of the system and prior knowledge of transition probabilities. Evaluating WeRLman against models we can accurately solve demonstrates it achieves unprecedented accuracy in deep RL for blockchain. We use WeRLman to analyze the incentives of a rational miner in various settings and upper-bound the security threshold of Bitcoin-like blockchains. We show, for the first time, a negative relationship between fee variability and the security threshold. The previously known bound, with constant rewards, stands at 0.25. We show that considering whale transactions reduces this threshold considerably. In particular, with Bitcoin historical fees and its future minting policy, its threshold for deviation will drop to 0.2 in 10 years, 0.17 in 20 years, and to 0.12 in 30 years. With recent fees from the Ethereum smart-contract platform, the threshold drops to 0.17. These are below the common sizes of large miners.
Last updated:  2022-02-20
How to Launch a Powerful Side-Channel Collision Attack?
Jiangshan Long, Changhai Ou, Yajun Ma, Yifan Fan, Hua Chen, Shihui Zheng
Benefiting from its independence of leakage model, side-channel collision attack is one of the most common distinguishers and attracts wide attention. Although several improvements have been given, its performance on attacking a single collision value has not been significantly improved. Its optimization and efficiency is still an open problem. To solve this, we theoretically analyze the quantitative relationship between encryptions and collisions in this paper, and propose an efficient side-channel attack named Collision-Paired Correlation Attack (CPCA) for low noise scenarios to guarantee that the side with fewer samples in a collision to be detected is completely paired. This optimizes the inefficient utilization of collision information in the existing collision attacks. Moreover, to further exploit the collision information, we maximize the collision pairing, and this optimization significantly improves CPCA and extends our CPCA to large noise scenarios. Finally, to reduce computation complexity, we further optimize our CPCA to a CPA-like distinguisher. Our further theoretical study fully illustrates that our CPCA provides the upper security bound of CECA, and experimental results fully show its superiority.
Last updated:  2022-06-22
Collision-Resistance from Multi-Collision-Resistance
Ron D. Rothblum, Prashant Nalini Vasudevan
Collision-resistant hash functions (CRH) are a fundamental and ubiquitous cryptographic primitive. Several recent works have studied a relaxation of CRH called t-way multi-collision-resistant hash functions (t-MCRH). These are families of functions for which it is computationally hard to find a t-way collision, even though such collisions are abundant (and even (t-1)-way collisions may be easy to find). The case of t=2 corresponds to standard CRH, but it is natural to study t-MCRH for larger values of t. Multi-collision-resistance seems to be a qualitatively weaker property than standard collision-resistance. Nevertheless, in this work we show a non-blackbox transformation of any moderately shrinking t-MCRH, for t in {2,4}, into an (infinitely often secure) CRH. This transformation is non-constructive - we can prove the existence of a CRH but cannot explicitly point out a construction. Our result partially extends to larger values of t. In particular, we show that for suitable values of t>t', we can transform a t-MCRH into a t'-MCRH, at the cost of reducing the shrinkage of the resulting hash function family and settling for infinitely often security. This result utilizes the list-decodability properties of Reed-Solomon codes.
Last updated:  2022-02-20
A remark on NIST SP 800-22 serial test
Corina-Elena Bogos, Razvan Mocanu, Emil Simion
This paper represents a cumulative review of the serial statistical test over the canonical values used in testing and freely generated values. Also in this paper, we study by simulation, the variation of second type error, depending on certain factors: the range of p1,the length of the bit string represented by n and the value of m-bit pattern.
Last updated:  2022-02-20
Practical and Improved Byzantine Reliable Broadcast and Asynchronous Verifiable Information Dispersal from Hash Functions
Nicolas Alhaddad, Sisi Duan, Mayank Varia, Haibin Zhang
This paper improves upon two fundamental and closely related primitives in fault-tolerant distributed computing---Byzantine reliable broadcast (BRB) and asynchronous verifiable information dispersal (AVID). We make improvements asymptotically (for our AVID construction), concretely (much lower hidden constants), and practically (having 3 steps, using hash functions only, and avoiding using online error correction on the bulk data). The state of the art BRB protocol of Das, Xiang, and Ren (DXR BRB, CCS 2021) uses hash functions only and achieves a communication overhead of $O(nL + kn^2)$, where $n$, $L$, and $k$ are the number of replicas, the message length, and the security parameter, respectively. More precisely, DXR BRB incurs a concrete communication of $7nL + 2kn^2$, with a large constant 7 for the bulk data term (i.e., the $nL$ term). Das, Xiang, and Ren asked an open question if it is possible "from a practical point of view to make the hidden constants small." Two other limitations of DXR BRB that authors emphasized are that "higher computation costs due to encoding and decoding of the message" due to applying error correcting codes on bulk data and the fact that "in the presence of malicious nodes, each honest node may have to try decoding $f$ times" due to the use of an online error correcting algorithm. Meanwhile, the state of the art AVID protocols achieve $O(L+kn^2)$ communication assuming trusted setup. Apparently, there is a mismatch between BRB and AVID protocols: another natural open problem is whether it is possible to build a setup-free AVID protocol with $O(L+kn^2)$ communication. In this work, we answer all these open questions in the affirmative. We first provide a hash-based BRB protocol that improves concretely on DXR BRB, having low constants and avoiding using online error correction on bulk data. Our key insight is to encode the consistency proof, not just the message. Our technique allows disseminating the message and proof together. Then we provide the first setup-free AVID protocol achieving $O(L+kn^2)$ communication. Both our BRB and AVID protocols are practical because they have 3 steps, a multiplicative factor of 3 for the bulk data term, use hash functions only, and they avoid applying online error correction on bulk data.
Last updated:  2022-06-16
gOTzilla: Efficient Disjunctive Zero-Knowledge Proofs from MPC in the Head, with Application to Proofs of Assets in Cryptocurrencies
Foteini Baldimtsi, Panagiotis Chatzigiannis, S. Dov Gordon, Phi Hung Le, Daniel McVicker
We present gOTzilla, a protocol for interactive zero-knowledge proofs for very large disjunctive statements of the following format: given publicly known circuit $C$, and set of values $Y = \{y_1, \ldots, y_n\}$, prove knowledge of a witness $x$ such that $C(x) = y_1 \lor C(x) = y_2 \lor \cdots \lor C(x) = y_n$. These type of statements are extremely important for the proof of assets (PoA) problem in cryptocurrencies where a prover wants to prove the knowledge of a secret key $sk$ that associates with the hash of a public key $H(pk)$ posted on the ledger. We note that the size of $n$ in popular cryptocurrencies, such as Bitcoin, is estimated to 80 million. For the construction of gOTzilla, we start by observing that if we restructure the proof statement to an equivalent of proving knowledge of $(x,y)$ such that $(C(x) = y) \land (y = y_1 \lor \cdots \lor y = y_n))$, then we can reduce the disjunction of equalities to 1-out-of-N oblivious transfer (OT). Our overall protocol is based on the MPC in the head (MPCitH) paradigm. We additionally provide a concrete, efficient extension of our protocol for the case where $C$ combines algebraic and non-algebraic statements (which is the case in the PoA application). We achieve an asymptotic communication cost of $O(\log n)$ plus the proof size of the underlying MPCitH protocol. While related work has similar asymptotic complexity, our approach results in concrete performance improvements. We implement our protocol and provide benchmarks. Concretely, for a set of size 1 million entries, the total run-time of our protocol is 14.89 seconds using 48 threads, with 6.18 MB total communication, which is about 4x faster compared to the state of the art when considering a disjunctive statement with algebraic and non-algebraic elements.
Last updated:  2022-04-12
SP 800-22 and GM/T 0005-2012 Tests: Clearly Obsolete, Possibly Harmful
Markku-Juhani O. Saarinen
When it comes to cryptographic random number generation, poor understanding of the security requirements and ``mythical aura'' of black-box statistical testing frequently leads it to be used as a substitute for cryptanalysis. To make things worse, a seemingly standard document, NIST SP 800-22, describes 15 statistical tests and suggests that they can be used to evaluate random and pseudorandom number generators in cryptographic applications. The Chinese standard GM/T 0005-2012 describes similar tests. These documents have not aged well. The weakest pseudorandom number generators will easily pass these tests, promoting false confidence in insecure systems. We strongly suggest that SP 800-22 be withdrawn by NIST; we consider it to be not just irrelevant but actively harmful. We illustrate this by discussing the ``reference generators'' contained in the SP 800-22 document itself. None of these generators are suitable for modern cryptography, yet they pass the tests. For future development, we suggest focusing on stochastic modeling of entropy sources instead of model-free statistical tests. Random bit generators should also be reviewed for potential asymmetric backdoors via trapdoor one-way functions, and for security against quantum computing attacks.
Last updated:  2023-07-13
Hardness of Approximation for Stochastic Problems via Interactive Oracle Proofs
Gal Arnon, Alessandro Chiesa, Eylon Yogev
Hardness of approximation aims to establish lower bounds on the approximability of optimization problems in NP and beyond. We continue the study of hardness of approximation for problems beyond NP, specifically for \emph{stochastic} constraint satisfaction problems (SCSPs). An SCSP with $k$ alternations is a list of constraints over variables grouped into $2k$ blocks, where each constraint has constant arity. An assignment to the SCSP is defined by two players who alternate in setting values to a designated block of variables, with one player choosing their assignments uniformly at random and the other player trying to maximize the number of satisfied constraints. In this paper, we establish hardness of approximation for SCSPs based on interactive proofs. For $k \leq O(\log n)$, we prove that it is $AM[k]$-hard to approximate, to within a constant, the value of SCSPs with $k$ alternations and constant arity. Before, this was known only for $k = O(1)$. Furthermore, we introduce a natural class of $k$-round interactive proofs, denoted $IR[k]$ (for \emph{interactive reducibility}), and show that several protocols (e.g., the sumcheck protocol) are in $IR[k]$. Using this notion, we extend our inapproximability to all values of $k$: we show that for every $k$, approximating an SCSP instance with $O(k)$ alternations and constant arity is $IR[k]$-hard. While hardness of approximation for CSPs is achieved by constructing suitable PCPs, our results for SCSPs are achieved by constructing suitable IOPs (interactive oracle proofs). We show that every language in $AM[k \leq O(\log n)]$ or in $IR[k]$ has an $O(k)$-round IOP whose verifier has \emph{constant} query complexity (\emph{regardless} of the number of rounds $k$). In particular, we derive a ``sumcheck protocol'' whose verifier reads $O(1)$ bits from the entire interaction transcript.
Last updated:  2022-06-23
Verifiable Relation Sharing and Multi-Verifier Zero-Knowledge in Two Rounds: Trading NIZKs with Honest Majority
Benny Applebaum, Eliran Kachlon, Arpita Patra
We introduce the problem of Verifiable Relation Sharing (VRS) where a client (prover) wishes to share a vector of secret data items among $k$ servers (the verifiers) while proving in zero-knowledge that the shared data satisfies some properties. This combined task of sharing and proving generalizes notions like verifiable secret sharing and zero-knowledge proofs over secret-shared data. We study VRS from a theoretical perspective and focus on its round complexity. As our main contribution, we show that every efficiently-computable relation can be realized by a VRS with an optimal round complexity of two rounds where the first round is input-independent (offline round). The protocol achieves full UC-security against an active adversary that is allowed to corrupt any $t$-subset of the parties that may include the client together with some of the verifiers. For a small (logarithmic) number of parties, we achieve an optimal resiliency threshold of $t<0.5(k+1)$, and for a large (polynomial) number of parties, we achieve an almost-optimal resiliency threshold of $t<0.5(k+1)(1-\epsilon)$ for an arbitrarily small constant $\epsilon>0$. Both protocols can be based on sub-exponentially hard injective one-way functions. If the parties have an access to a collision resistance hash function, we can derive statistical everlasting security, i.e., the protocols are secure against adversaries that are computationally bounded during the protocol execution and become computationally unbounded after the protocol execution. Previous 2-round solutions achieve smaller resiliency thresholds and weaker security notions regardless of the underlying assumptions. As a special case, our protocols give rise to 2-round offline/online constructions of multi-verifier zero-knowledge proofs (MVZK). Such constructions were previously obtained under the same type of assumptions that are needed for NIZK, i.e., public-key assumptions or random-oracle type assumptions (Abe et al., Asiacrypt 2002; Groth and Ostrovsky, Crypto 2007; Boneh et al., Crypto 2019; Yang, and Wang, Eprint 2022). Our work shows, for the first time, that in the presence of an honest majority these assumptions can be replaced with more conservative ``Minicrypt''-type assumptions like injective one-way functions and collision-resistance hash functions. Indeed, our MVZK protocols provide a round-efficient substitute for NIZK in settings where an honest majority is present. Additional applications are also presented.
Last updated:  2022-02-20
Digital Contact Tracing Solutions: Promises, Pitfalls and Challenges
Thien Duc Nguyen, Markus Miettinen, Alexandra Dmitrienko, Ahmad-Reza Sadeghi, Ivan Visconti
The COVID-19 pandemic has caused many countries to deploy novel digital contact tracing (DCT) systems to boost the efficiency of manual tracing of infection chains. In this paper, we systematically analyze DCT solutions and categorize them based on their design approaches and architectures. We analyze them with regard to effectiveness, security, privacy, and ethical aspects and compare prominent solutions with regard to these requirements. In particular, we discuss the shortcomings of the Google and Apple Exposure Notification API (GAEN) that is currently widely adopted all over the world. We find that the security and privacy of GAEN has considerable deficiencies as it can be compromised by severe large-scale attacks. We also discuss other proposed approaches for contact tracing, including our proposal TRACECORONA, that are based on Diffie-Hellman (DH) key exchange and aims at tackling shortcomings of existing solutions. Our extensive analysis shows thatTRACECORONA fulfills the above security requirements better than deployed state-of-the-art approaches. We have implementedTRACECORONA and its beta test version has been used by more than 2000 users without any major functional problems1, demonstrating that there are no technical reasons requiring to make compromises with regard to the requirements of DCTapproaches.
Last updated:  2022-02-20
PAC Learnability of iPUF Variants
Durba Chatterjee, Debdeep Mukhopadhyay, Aritra Hazra
Interpose PUF~(iPUF) is a strong PUF construction that was shown to be vulnerable against empirical machine learning as well as PAC learning attacks. In this work, we extend the PAC Learning results of Interpose PUF to prove that the variants of iPUF are also learnable in the PAC model under the Linear Threshold Function representation class.
Last updated:  2022-02-20
Shanrang: Fully Asynchronous Proactive Secret Sharing with Dynamic Committees
Yunzhou Yan, Yu Xia, Srinivas Devadas
We present Shanrang, the first fully asynchronous proactive secret sharing scheme with dynamic committee support. Even in the worst possible network environment, where messages could have arbitrary latencies, Shanrang allows a dynamic committee to store a secret and periodically refresh the secret shares in a distributed fashion. When the committee changes, both the old committee and the new committee jointly refresh and transfer the shares to the new committee, without revealing the secret to the adversary. With n parties, Shanrang tolerates n/4 Byzantine faults and maintains liveness as long as the messages are delivered. In contrast to prior work, Shanrang makes no assumptions on the network latency. Designing an asynchronous protocol is challenging because it is impossible to distinguish an adversary sending no messages from an honest party whose messages have not arrived yet. We evaluated Shanrang on geographically distributed machines and we found Shanrang achieved 200 seconds for handing off between 2 committees of 41 parties. Shanrang requires O(λn3 log n) messages and runs in expected O(log n) rounds for every handoff. To show Shanrang is robust even in a harsh network environ- ment, we test Shanrang on the Tor network and it shows robust performance.
Last updated:  2022-02-20
A High Performance Payment Processing System Designed for Central Bank Digital Currencies
James Lovejoy, Cory Fields, Madars Virza, Tyler Frederick, David Urness, Kevin Karwaski, Anders Brownworth, Neha Narula
In light of continued innovation in money and payments, many central banks are exploring the creation of a central bank digital currency (CBDC), a new form of central bank money which supplements existing central bank reserve account balances and physical currency. This paper presents Hamilton, a flexible transaction processor design that supports a range of models for a CBDC and minimizes data storage in the core transaction processor by storing unspent funds as opaque hashes. Hamilton supports users custodying their own funds or custody provided by financial intermediaries. We describe and evaluate two implementations: the atomizer architecture which provides a globally ordered history of transactions but is limited in throughput (170,000 transactions per second), and the 2PC architecture that scales peak throughput almost linearly with resources (up to a measured throughput of 1.7M transactions per second) but does not provide a globally ordered list of transactions. We released our two architectures under the MIT open source license at https://github.com/mit-dci/opencbdc-tx.
Last updated:  2023-11-20
On the precision loss in approximate homomorphic encryption
Anamaria Costache, Benjamin R. Curtis, Erin Hales, Sean Murphy, Tabitha Ogilvie, and Rachel Player
Since its introduction at Asiacrypt 2017, the CKKS approximate homomorphic encryption scheme has become one of the most widely used and implemented homomorphic encryption schemes. Due to the approximate nature of the scheme, application developers using CKKS must ensure that the evaluation output is within a tolerable error of the corresponding plaintext computation. Choosing appropriate parameters requires a good understanding of how the noise will grow through the computation. A strong understanding of the noise growth is also necessary to limit the performance impact of mitigations to the attacks on CKKS presented by Li and Micciancio (Eurocrypt 2021). In this work we present a comprehensive noise analysis of CKKS, that considers noise coming both from the encoding and homomorphic operations. Our main contribution is the first average-case analysis for CKKS noise, and we also introduce refinements to prior worst-case noise analyses. We develop noise heuristics both for the original CKKS scheme and the RNS variant presented at SAC 2018. We then evaluate these heuristics by comparing the predicted noise growth with experiments in the HEAAN and FullRNS-HEAAN libraries, and by comparing with a worst-case noise analysis as done in prior work. Our findings show mixed results: while our new analyses lead to heuristic estimates that more closely model the observed noise growth than prior approaches, the new heuristics sometimes slightly underestimate the observed noise growth. This evidences the need for implementation-specific noise analyses for CKKS, which recent work has shown to be effective for implementations of similar schemes.
Last updated:  2022-02-20
D-KODE: Mechanism to Generate and Maintain a Billion Keys
Easwar Vivek Mangipudi, Aniket Kate
This work considers two prominent key management problems in the blockchain space: (i) allowing a (distributed) blockchain system to securely airdrop/send some tokens to a potential client Bob, who is yet to set up the required cryptographic key for the system, and (ii) creating a (distributed) cross-chain bridge that allows interoperability at scale by allowing a (changing) set of nodes in a blockchain to perform transactions on the other blockchain. The existing solutions for the first problem need Bob to either generate and maintain private keys locally for the first time in his life — a usability bottleneck — or place trust in third-party custodial services — a privacy and censorship nightmare. Towards solving both problems in a distributed setting against a threshold-bounded adversary, distributed key generation (DKG) based solutions are actively employed; here, a set of servers generate the transactions in a distributed manner and link them to clients’ ids. Nevertheless, these solutions introduce computation and communication overhead that is linear in the number of keys and do not scale well even for a million keys, especially for proactive security against a mobile adversary. This work presents a Keys-On-Demand (D-KODE) distributed protocol suite that lets the blockchain system securely generate the public key of any Bob against a mobile threshold adversary. Multiple servers, here, compute discrete-log private/public keys on the fly through distributed pseudo-random function evaluations on the queried public string. D-KODE also introduces a proactive security mechanism for the employed black-box secret-sharing based DKG to maintain the system’s longitudinal security. The proposed protocol scales well for a very high number of keys as its communication and computation complexity is independent of the number of keys. Our experimental analysis demonstrates that, for a 20-node network with a 2/3 honest majority, D-KODE starts to outperform the state of the art as the number of keys reaches 94K. D-KODE is practical as it takes less than 100msec to generate a secret key for a single-threaded server in a 20-node setup
Last updated:  2022-02-12
Random primes in arithmetic progressions
Pascal Giorgi, Bruno Grenet, Armelle Perret du Cray, Daniel S. Roche
We describe a straightforward method to generate a random prime q such that the multiplicative group GF(q)* also has a random large prime-order subgroup. The described algorithm also yields this order p as well as a p'th primitive root of unity. The methods here are efficient asymptotically, but due to large constants may not be very useful in practical settings.
Last updated:  2022-04-06
A Note on Blockchain Authentication Methods For Mobile Devices In Healthcare
George-Mircea Grosu, Silvia-Elena Nistor, Emil Simion
The past couple of decades witnessed a tremendous expansion in the IoT world that gathers now billions of devices, sensors, users and transactions. The aspirations of ubiquitous computing have changed the computing world drastically, from a parallel point of view, to distributed, then grid and cloud computing – all these just to keep up with the proliferation of devices and the users’ expectations. Alongside with this fast development, many issues appeared, especially in terms of scalability and security. Regardless of protocol, device, applications or technologies used, there will be critical data involved and, therefore, vulnerabilities that can affect the performance of the system or be exploited maliciously. The higher the number of devices, the more constraints appear and along with these constraints the existing models and technologies become overwhelmed and simply not enough. The size of the IoT and its autonomous character make it impossible to sustain and implement a centralized authentication system. Therefore, to allow reliable peer authentication and to approach a trust level management, we propose discussing a model based on blockchain technology. Blockchain is a revolutionary technology, modeled by a linear sequence of blocks, considered to be the future of wireless networks security. We rely on this new data structure to address two major components of security in mobile networks: authentication and trust.
Last updated:  2022-07-14
Bitslicing Arithmetic/Boolean Masking Conversions for Fun and Profit with Application to Lattice-Based KEMs
Olivier Bronchain, Gaëtan Cassiers
The performance of higher-order masked implementations of lattice-based based key encapsulation mechanisms (KEM) is currently limited by the costly conversions between arithmetic and boolean masking. While bitslicing has been shown to strongly speed up masked implementations of symmetric primitives, its use in arithmetic-to-Boolean and Boolean-to-arithmetic masking conversion gadgets has never been thoroughly investigated. In this paper, we first show that bitslicing can indeed accelerate existing conversion gadgets. We then optimize these gadgets, exploiting the degrees of freedom offered by bitsliced implementations. As a result, we introduce new arbitrary-order boolean masked addition, arithmetic-to-boolean and boolean-to-arithmetic masking conversion gadgets, each in two variants: modulo $2^k$ and modulo $p$ (for any integers $k$ and $p$). Practically, our new gadgets achieve a speedup of up to 25x over the state of the art. Turning to the KEM application, we develop the first open-source embedded (Cortex-M4) implementations of Kyber768 and Saber masked at arbitrary order. The implementations based on the new bitsliced gadgets achieve a speedup of 1.8x for Kyber and 3x for Saber, compared to the implementation based on state of the art gadgets. The bottleneck of the bitslice implementations is the masked Keccak-f[1600] permutation.
Last updated:  2022-02-24
Shuffle-based Private Set Union: Faster and More Secure
Yanxue Jia, Shi-Feng Sun, Hong-Sheng Zhou, Jiajun Du, Dawu Gu
Private Set Union ($\mathsf{PSU}$) allows two players, the sender and the receiver, to compute the union of their input datasets without revealing any more information than the result. While it has found numerous applications in practice, not much research has been carried out so far, especially for large datasets. In this work, we take shuffling technique as a key to design $\mathsf{PSU}$ protocols for the first time. By shuffling receiver's set, we put forward the first protocol, denoted as $\Pi_{\mathsf{PSU}}^{\mathsf{receiver}}$, that eliminates the expensive operations in previous works, such as additive homomorphic encryption and repeated operations on the receiver's set. It outperforms the state-of-the-art design by Kolesnikov et al. (ASIACRYPT 2019) in both efficiency and security; the unnecessary leakage in Kolesnikov et al.'s design, can be avoided in our design. We further extend our investigation to the application scenarios in which both players may hold unbalanced input datasets. We propose our second protocol $\Pi_{\mathsf{PSU}}^{\mathsf{sender}}$, by shuffling the sender's dataset. This design can be viewed as a dual version of our first protocol, and it is suitable in the cases where the sender's input size is much smaller than the receiver's. Finally, we implement our protocols $\Pi_{\mathsf{PSU}}^{\mathsf{receiver}}$ and $\Pi_{\mathsf{PSU}}^{\mathsf{sender}}$ in C++ on big datasets, and perform a comprehensive evaluation in terms of both scalability and parallelizability. The results demonstrate that our design can obtain a $4$-$5 \times$ improvement over the state-of-the-art by Kolesnikov et al. with a single thread in WAN/LAN settings.
Last updated:  2022-09-19
Universal Reductions: Reductions Relative to Stateful Oracles
Benjamin Chan, Cody Freitag, Rafael Pass
We define a framework for analyzing the security of cryptographic protocols that makes minimal assumptions about what a "realistic model of computation is". In particular, whereas classical models assume that the attacker is a (perhaps non-uniform) probabilistic polynomial-time algorithm, and more recent definitional approaches also consider quantum polynomial-time algorithms, we consider an approach that is more agnostic to what computational model is physically realizable. Our notion of universal reductions models attackers as PPT algorithms having access to some arbitrary unbounded stateful Nature that cannot be rewound or restarted when queried multiple times. We also consider a more relaxed notion of universal reductions w.r.t. time-evolving, $k$-window, Natures that makes restrictions on Nature - roughly speaking, Nature's behavior may depend on number of messages it has received and the content of the last $k(\lambda)$-messages (but not on "older" messages). We present both impossibility results and general feasibility results for our notions, indicating to what extent the extended Church-Turing hypotheses are needed for a well-founded theory of Cryptography.
Last updated:  2022-08-04
FairTraDEX: A Decentralised Exchange Preventing Value Extraction
Conor McMenamin, Vanesa Daza, Matthias Fitzi, Padraic O'Donoghue
We present FairTraDEX, a decentralized exchange (DEX) protocol based on frequent batch auctions (FBAs), which provides formal game-theoretic guarantees against extractable value. FBAs when run by a trusted third-party provide unique game-theoretic optimal strategies which ensure players are shown prices equal to the liquidity provider's fair price, excluding explicit, pre-determined fees. FairTraDEX replicates the key features of an FBA that provide these game-theoretic guarantees using a combination of set-membership in zero-knowledge protocols and an escrow-enforced commit-reveal protocol. We extend the results of FBAs to handle monopolistic and/or malicious liquidity providers. We provide real-world examples that demonstrate that the costs of executing orders in existing academic and industry-standard protocols become prohibitive as order size increases due to basic value extraction techniques, popularized as maximal extractable value. We further demonstrate that FairTraDEX protects against these execution costs, guaranteeing a fixed fee model independent of order size, the first guarantee of it's kind for a DEX protocol. We also provide detailed Solidity and pseudo-code implementations of FairTraDEX, making FairTraDEX a novel and practical contribution.
Last updated:  2022-02-12
Coeus: A System for Oblivious Document Ranking and Retrieval
Ishtiyaque Ahmad, Laboni Sarker, Divyakant Agrawal, Amr El Abbadi, Trinabh Gupta
Given a private string q and a remote server that holds a set of public documents D, how can one of the K most relevant documents to q in D be selected and viewed without anyone (not even the server) learning anything about q or the document? This is the oblivious document ranking and retrieval problem. In this paper, we describe Coeus, a system that solves this problem. At a high level, Coeus composes two cryptographic primitives: secure matrix-vector product for scoring document relevance using the widely-used term frequency-inverse document frequency (tf-idf) method, and private information retrieval (PIR) for obliviously retrieving documents. However, Coeus reduces the time to run these protocols, thereby improving the user-perceived latency, which is a key performance metric. Coeus first reduces the PIR overhead by separating out private metadata retrieval from document retrieval, and it then scales secure matrix-vector product to tf-idf matrices with several hundred billion elements through a series of novel cryptographic refinements. For a corpus of English Wikipedia containing 5 million documents, a keyword dictionary with 64K keywords, and on a cluster of 143 machines on AWS, Coeus enables a user to obliviously rank and retrieve a document in 3.9 seconds---a 24x improvement over a baseline system.
Last updated:  2022-02-28
Faulty isogenies: a new kind of leakage
Gora Adj, Jesús-Javier Chi-Domínguez, Víctor Mateu, Francisco Rodríguez-Henríquez
In SIDH and SIKE protocols, public keys are defined over quadratic extensions of prime fields. We present in this work a projective invariant property characterizing affine Montgomery curves defined over prime fields. We then force a secret 3-isogeny chain to repeatedly pass through a curve defined over a prime field in order to exploit the new property and inject zeros in the A-coefficient of an intermediate curve to successfully recover the isogeny chain one step at a time. Our results introduce a new kind of fault attacks applicable to SIDH and SIKE.
Last updated:  2022-02-12
K-XMSS and K-SPHINCS$^+$:Hash based Signatures with\\Korean Cryptography Algorithms
Minjoo Sim, Siwoo Eum, Gyeongju Song, HyeokDong Kwon, Kyungbae Jang, HyunJun Kim, HyunJi Kim, Yujin Yang, Wonwoong Kim, Wai-Kong Lee, Hwajeong Seo
Hash-Based Signature (HBS) uses a hash function to construct a digital signature scheme, where its security is guaranteed by the collision resistance of the hash function used. To provide sufficient security in the post-quantum environment, the length of hash should be satisfied. Modern HBS can be classified into stateful and stateless schemes. Two representative stateful and stateless HBS are XMSS and SPHINCS$^+$, respectively. In this paper, we propose two HBS schemes: K-XMSS and K-SPHINCS$^+$, which replace internal hash functions of XMSS and SPHINCS$^+$ with Korean cryptography algorithms. K-XMSS is a stateful signature, while K-SPHINCS$^+$ is its stateless counterpart. We also showcase the reference implementation of K-XMSS and K-SPHINCS$^+$ employing LSH and two hash functions based on block ciphers (i.e. CHAM and LEA) as the internal hash function. The reference code is developed as a proof-of-concept, which can be optimized for better performance using advanced implementation techniques (e.g. AVX2 and NEON).
Last updated:  2022-02-12
Addendum to Linear Cryptanalyses of Three AEADs with GIFT-128 as Underlying Primitives
Ling Sun, Wei Wang, Meiqin Wang
In ToSC 2021(2), Sun et al. implemented an automatic search with the Boolean satisfiability problem (SAT) method on GIFT-128 and identified a 19-round linear approximation with the expected linear potential being $2^{-117.43}$, which is utilised to launch a 24-round attack on the cipher. In this addendum, we discover a new 19-round linear approximation with a lower expected linear potential. However, in the attack, one more round can be appended after the distinguisher. As a result, we improve the previous optimal linear attack by one round and put forward a 25-round linear attack. Given that the optimal differential attack on GIFT-128, for now, covers 27-round, the resistances of the cipher against differential and linear attacks still have a 2-round gap.
Last updated:  2023-08-08
The Generalized Montgomery Coordinate: A New Computational Tool for Isogeny-based Cryptography
Tomoki Moriya, Hiroshi Onuki, Yusuke Aikawa, Tsuyoshi Takagi
Recently, some studies have constructed one-coordinate arithmetics on elliptic curves. For example, formulas of the $x$-coordinate of Montgomery curves, $x$-coordinate of Montgomery$^-$ curves, $w$-coordinate of Edwards curves, $w$-coordinate of Huff's curves, $\omega$-coordinates of twisted Jacobi intersections have been proposed. These formulas are useful for isogeny-based cryptography because of their compactness and efficiency. In this paper, we define a novel function on elliptic curves called the generalized Montgomery coordinate that has the five coordinates described above as special cases. For a generalized Montgomery coordinate, we construct an explicit formula of scalar multiplication that includes the division polynomial, and both a formula of an image point under an isogeny and that of a coefficient of the codomain curve. Finally, we present two applications of the theory of a generalized Montgomery coordinate. The first one is the construction of a new efficient formula to compute isogenies on Montgomery curves. This formula is more efficient than the previous one for high degree isogenies as the $\sqrt{\vphantom{2}}$\'{e}lu's formula in our implementation. The second one is the construction of a new generalized Montgomery coordinate for Montgomery$^-$ curves used for CSURF.
Last updated:  2022-09-15
Putting up the swiss army knife of homomorphic calculations by means of TFHE functional bootstrapping
Pierre-Emmanuel Clet, Martin Zuber, Aymen Boudguiga, Renaud Sirdey, Cédric Gouy-Pailler
In this work, we first propose a new functional bootstrapping with TFHE for evaluating any function of domain and codomain the real torus T by using a small number of bootstrappings. This result improves some aspects of previous approaches: like them, we allow for evaluating any functions, but with better precision. In addition, we develop more efficient multiplication and addition over ciphertexts building on the digit-decomposition approach. As a practical application, our results lead to an efficient implementation of ReLU, one of the most used activation functions in deep learning. The paper is concluded by extensive experimental results comparing each building block as well as their practical relevance and trade-offs.
Last updated:  2022-05-31
Attacks on the Firekite cipher
Thomas Johansson, Willi Meier, Vu Nguyen
Firekite is a synchronous stream cipher using a pseudo-random number generator (PRNG) whose security relies on the hardness of the \textit{Learning Parity with Noise} (LPN) problem. It is one of a few LPN-based symmetric encryption schemes and it can be very efficiently implemented on a low-end SoC FPGA. The designers, Bogos, Korolija, Locher, and Vaudenay, demonstrated appealing properties of Firekite such as requiring only one source of cryptographically strong bits, small key size, high attainable throughput, and a concrete measurement for the bit level security depending on the selected practical parameters. We propose distinguishing and key-recovery attacks on Firekite by exploiting the structural properties of its PRNG. We adopt several \textit{birthday-paradox} techniques to show that a particular sum of Firekite's output has a low Hamming weight with higher probability than the random case. We achieve the best distinguishing attacks with complexities $2^{66.75}$ and $2^{106.75}$ for Firekite's parameters corresponding to $80$-bit and $128$-bit security, respectively. By applying the distinguishing attacks and an additionally suggested algorithm, one can also recover the secret matrix used in the Firekite PRNG, which is built from the secret key bits. This key recovery attack works on most large parameter sets and has slightly larger complexity, for example $2^{69.87}$ on the $80$-bit security parameters $n=16384, m = 216, k = 216$.
Last updated:  2022-02-12
Constructing new superclasses of bent functions from known ones
Uncategorized
Amar Bapić, Enes Pasalic, Fengrong Zhang, Samir Hodžić
Show abstract
Uncategorized
Some recent research articles [23, 24] addressed an explicit specification of indicators that specify bent functions in the so-called $\mathcal{C}$ and $\mathcal{D}$ classes, derived from the Maiorana- McFarland ($\mathcal{M}$) class by C. Carlet in 1994 [5]. Many of these bent functions that belong to $\mathcal{C}$ or $\mathcal{D}$ are provably outside the completed $\mathcal{M}$ class. Nevertheless, these modifications are performed on affine subspaces, whereas modifying bent functions on suitable subsets may provide us with further classes of bent functions. In this article, we exactly specify new families of bent functions obtained by adding together indicators typical for the $\mathcal{C}$ and $\mathcal{D}$ class, thus essentially modifying bent functions in $\mathcal{M}$ on suitable subsets instead of subspaces. It is shown that the modification of certain bent functions in $\mathcal{M}$ gives rise to new bent functions which are provably outside the completed $\mathcal{M}$ class. Moreover, we consider the so-called 4-bent concatenation (using four different bent functions on the same variable space) of the (non)modified bent functions in $\mathcal{M}$ and show that we can generate new bent functions in this way which do not belong to the completed $\mathcal{M}$ class either. This result is obtained by specifying explicitly the duals of four constituent bent functions used in the concatenation. The question whether these bent functions are also excluded from the completed versions of $\mathcal{PS}$, $\mathcal{C}$ or $\mathcal{D}$ remains open and is considered difficult due to the lack of membership indicators for these classes.
Last updated:  2022-02-12
Training Differentially Private Models with Secure Multiparty Computation
Sikha Pentyala, Davis Railsback, Ricardo Maia, Rafael Dowsley, David Melanson, Anderson Nascimento, Martine De Cock
We address the problem of learning a machine learning model from training data that originates at multiple data owners, while providing formal privacy guarantees regarding the protection of each owner's data. Existing solutions based on Differential Privacy (DP) achieve this at the cost of a drop in accuracy. Solutions based on Secure Multiparty Computation (MPC) do not incur such accuracy loss but leak information when the trained model is made publicly available. We propose an MPC solution for training DP models. Our solution relies on an MPC protocol for model training, and an MPC protocol for perturbing the trained model coefficients with Laplace noise in a privacy-preserving manner. The resulting MPC+DP approach achieves higher accuracy than a pure DP approach, while providing the same formal privacy guarantees. Our work obtained first place in the iDASH2021 Track III competition on confidential computing for secure genome analysis.
Last updated:  2022-02-09
An elementary construction of QR-UOV
Yasufumi Hashimoto
QR-UOV is a variant of UOV with smaller keys proposed at Asiacrypt 2021. In this paper, we show that QR-UOV can be constructed by a smaller UOV over an extension field.
Last updated:  2022-02-09
Rainbow Differential Privacy
Ziqi Zhou, Onur Gunlu, Rafael G. L. D'Oliveira, Muriel Medard, Parastoo Sadeghi, Rafael F. Schaefer
We extend a previous framework for designing differentially private (DP) mechanisms via randomized graph colorings that was restricted to binary functions, corresponding to colorings in a graph, to multi-valued functions. As before, datasets are nodes in the graph and any two neighboring datasets are connected by an edge. In our setting, we assume each dataset has a preferential ordering for the possible outputs of the mechanism, which we refer to as a rainbow. Different rainbows partition the graph of datasets into different regions. We show that when the DP mechanism is pre-specified at the boundary of such regions, at most one optimal mechanism can exist. Moreover, if the mechanism is to behave identically for all same-rainbow boundary datasets, the problem can be greatly simplified and solved by means of a morphism to a line graph. We then show closed form expressions for the line graph in the case of ternary functions. Treatment of ternary queries in this paper displays enough richness to be extended to higher-dimensional query spaces with preferential query ordering, but the optimality proof does not seem to follow directly from the ternary proof.
Last updated:  2022-02-09
Composition construction of new bent functions from known dually isomorphic bent functions
Guangpu Gao, Weiguo Zhang, Yongjuan Wang
Bent functions are optimal combinatorial objects and have been studied over the last four decades. Secondary construction plays a central role in constructing bent functions since it may generate bent functions outside the primary classes of bent functions. In this study, we improve a theoretical framework of the secondary construction of bent functions in terms of the composition of Boolean functions. Based on this framework, we propose several constructions of bent functions through the composition of a balanced Boolean function and dually isomorphic (DI) bent functions defined herein. In addition, we present a construction of self-dual bent functions.
Last updated:  2022-02-09
Efficient Verifiable Partially-Decryptable Commitments from Lattices and Applications
Muhammed F. Esgin, Ron Steinfeld, Raymond K. Zhao
We introduce verifiable partially-decryptable commitments (VPDC), as a building block for constructing efficient privacy-preserving protocols supporting auditability by a trusted party. A VPDC is an extension of a commitment along with an accompanying proof, convincing a verifier that (i) the given commitment is well-formed and (ii) a certain part of the committed message can be decrypted using a (secret) trapdoor known to a trusted party. We first formalize VPDCs and then introduce a general decryption feasibility result that overcomes the challenges in relaxed proofs arising in the lattice setting. Our general result can be applied to a wide class of Fiat-Shamir based protocols and may be of independent interest. Next, we show how to extend the commonly used lattice-based `Hashed-Message Commitment' (HMC) scheme into a succinct and efficient VPDC. In particular, we devise a novel `gadget'-based Regev-style (partial) decryption method, compatible with efficient relaxed lattice-based zero-knowledge proofs. We prove the soundness of our VPDC in the setting of adversarial proofs, where a prover tries to create a valid VPDC output that fails in decryption. To demonstrate the effectiveness of our results, we extend a private blockchain payment protocol, MatRiCT, by Esgin et al. (ACM CCS '19) into a formally auditable construction, which we call MatRiCT-Au, with very low communication and computation overheads over MatRiCT.
Last updated:  2023-09-01
Efficient Hybrid Exact/Relaxed Lattice Proofs and Applications to Rounding and VRFs
Muhammed F. Esgin, Ron Steinfeld, Dongxi Liu, and Sushmita Ruj
In this work, we study hybrid exact/relaxed zero-knowledge proofs from lattices, where the proved relation is exact in one part and relaxed in the other. Such proofs arise in important real-life applications such as those requiring verifiable PRF evaluation and have so far not received significant attention as a standalone problem. We first introduce a general framework, LANES+, for realizing such hybrid proofs efficiently by combining standard relaxed proofs of knowledge RPoK and the LANES framework (due to a series of works in Crypto'20, Asiacrypt'20, ACM CCS'20). The latter framework is a powerful lattice-based proof system that can prove exact linear and multiplicative relations. The advantage of LANES+ is its ability to realize hybrid proofs more efficiently by exploiting RPoK for the high-dimensional part of the secret witness while leaving a low-dimensional secret witness part for the exact proof that is proven at a significantly lower cost via LANES. Thanks to the flexibility of LANES+, other exact proof systems can also be supported. We apply our LANES+ framework to construct substantially shorter proofs of rounding, which is a central tool for verifiable deterministic lattice-based cryptography. Based on our rounding proof, we then design an efficient long-term verifiable random function (VRF), named LaV. LaV leads to the shortest VRF outputs among the proposals of standard (i.e., long-term and stateless) VRFs based on quantum-safe assumptions. Of independent interest, we also present generalized results for challenge difference invertibility, a fundamental soundness security requirement for many proof systems.
Last updated:  2022-02-09
On the Related-Key Attack Security of Authenticated Encryption Schemes
Sebastian Faust, Juliane Krämer, Maximilian Orlt, Patrick Struck
Related-key attacks (RKA) are powerful cryptanalytic attacks, where the adversary can tamper with the secret key of a cryptographic scheme. Since their invention, RKA security has been an important design goal in cryptography, and various works aim at designing cryptographic primitives that offer protection against related-key attacks. At EUROCRYPT'03, Bellare and Kohno introduced the first formal treatment of related-key attacks focusing on pseudorandom functions and permutations. This was later extended to cover other primitives such as signatures and public key encryption schemes, but until now, a comprehensive formal security analysis of authenticated encryption schemes with associated data (AEAD) in the RKA setting has been missing. The main contribution of our work is to close this gap for the relevant class of nonce-based AEAD schemes. To this end, we revisit the common approach to construct AEAD from encryption and message authentication. We extend the traditional security notion of AEAD to the RKA setting and consider an adversary that can tamper with the key $K_e$ and $K_m$ of the underlying encryption and MAC, respectively. We study two security models. In our weak setting, we require that tampering will change both $K_e$ and $K_m$, while in our strong setting, tampering can be arbitrary, i.e., only one key might be affected. We then study the security of the standard composition methods by analysing the nonce-based AEAD schemes N1 (Encrypt-and-MAC), N2 (Encrypt-then-MAC), and N3 (MAC-then-Encrypt) due to Namprempre, Rogaway, and Shrimpton (EUROCRYPT'03). We show that these schemes are weakly RKA secure, while they can be broken under a strong related-key attack. Finally, based on the N3 construction, we give a novel AEAD scheme that achieves our stronger notion.
Last updated:  2022-09-28
Sponge-based Authenticated Encryption: Security against Quantum Attackers
Christian Janson, Patrick Struck
In this work, we study the security of sponge-based authenticated encryption schemes against quantum attackers. In particular, we analyse the sponge-based authenticated encryption scheme SLAE as put forward by Degabriele et al. (ASIACRYPT'19). We show that the scheme achieves security in the post-quantum (QS1) setting in the quantum random oracle model by using the one-way to hiding lemma. Furthermore, we analyse the scheme in a fully-quantum (QS2) setting. There we provide a set of attacks showing that SLAE does not achieve ciphertext indistinguishability and hence overall does not provide the desired level of security.
Last updated:  2022-04-08
Resisting Key-Extraction and Code-Compression: a Secure Implementation of the HFE Signature Scheme in the White-Box Model
Pierre Galissant, Louis Goubin
Cryptography is increasingly deployed in applications running on open devices in which the software is extremely vulnerable to attacks, since the attacker has complete control over the execution platform and the software implementation itself. This creates a challenge for cryptography: design implementations of cryptographic algorithms that are secure, not only in the black-box model, but also in this attack context that is referred to as the white-box adversary model. Moreover, emerging applications such as mobile payment, mobile contract signing or blockchain-based technologies have created a need for white-box implementations of public-key cryptography, and especially of signature algorithms. However, while many attempts were made to construct white-box implementations of block-ciphers, almost no white-box implementations have been published for what concerns asymmetric schemes. We present here a concrete white-box implementation of the well-known HFE signature algorithm for a specific set of internal polynomials. For a security level $2^{80}$, the public key size is approximately 62.5 MB and the white-box implementation of the signature algorithm has a size approximately 256 GB.
Last updated:  2022-02-09
Ten years of cube attacks
Marco Cianfriglia, Elia Onofri, Silvia Onofri, Marco Pedicini
In 2009, Dinur and Shamir proposed the cube attack, an algebraic cryptanalysis technique that only requires black box access to a target cipher. Since then, this attack has received both many criticisms and endorsements from crypto community; this work aims at revising and collecting the many attacks that have been proposed starting from it. We categorise all of these attacks in five classes; for each class, we provide a brief summary description along with the state-of-the-art references and the most recent cryptanalysis results. Furthermore, we extend and refine the new notation we proposed in 2021 and we use it to provide a consistent definition for each attack family. Finally, in the appendix, we provide an in-depth description of the kite attack framework, a cipher independent tool we firstly proposed in 2018 that implements the kite attack on GPUs. To prove its effectiveness, we use Mickey2.0 as a use case, showing how to embed it in the framework.
Last updated:  2022-05-26
Twilight: A Differentially Private Payment Channel Network
Maya Dotan, Saar Tochner, Aviv Zohar, Yossi Gilad
Payment channel networks (PCNs) provide a faster and cheaper alternative to transactions recorded on the blockchain. Clients can trustlessly establish payment channels with relays by locking coins and then send signed payments that shift coin balances over the network's channels. Although payments are never published, anyone can track a client's payment by monitoring changes in coin balances over the network's channels. We present Twilight, the first PCN that provides a rigorous differential privacy guarantee to its users. Relays in Twilight run a noisy payment processing mechanism that hides the payments they carry. This mechanism increases the relay's cost, so Twilight combats selfish relays that wish to avoid it using a trusted execution environment (TEE) that ensures they follow its protocol. The TEE does not store the channel's state, which minimizes the trusted computing base. Crucially, Twilight ensures that even if a relay breaks the TEE's security, it cannot break the integrity of the PCN. We analyze Twilight in terms of privacy and cost and study the trade-off between them. We implement Twilight using Intel's SGX framework and evaluate its performance using relays deployed on two continents. We show that a route consisting of 4 relays handles 820 payments/sec.
Last updated:  2022-02-09
Do NOT Misuse the Markov Cipher Assumption - Automatic Search for Differential and Impossible Differential Characteristics in ARX Ciphers
Zheng Xu, Yongqiang Li, Lin Jiao, Mingsheng Wang, Willi Meier
Firstly, we improve the evaluation theory of differential propagation for modular additions and XORs, respectively. By introducing the concept of $additive$ $sums$ and using signed differences, we can add more information of value propagation to XOR differential propagation to calculate the probabilities of differential characteristics more precisely. Based on our theory, we propose the first modeling method to describe the general ARX differential propagation, which is not based on the Markov cipher assumption. Secondly, we propose an automatic search tool for differential characteristics with more precise probabilities in ARX ciphers. We find that some differential characteristics that used to be valid become impossible, and some probabilities that used to be underestimated increase. In applications, for CHAM-64/128 (one of the underlying block ciphers in COMET, one of 32 second-round candidates in NIST’s lightweight cryptography standardization process), we find that there is no valid $39$-round differential characteristic with a probability of $2^{-63}$ computed using previous methods, and we correct the probabilities to $2^{-64}$ and $2^{-64}$ instead of $2^{-65}$ and $2^{-65}$ computed using previous methods for two 39-round differential characteristics starting from the $1$-st round, respectively; however, if we search for differential characteristics starting from the $5$-th round, the two differential characteristics are invalid, which means that the round constants can affect the security of ARX ciphers against differential cryptanalysis; for Alzette with $c = \tt{0xb7e15162}$ (one of the S-boxes in SPARKLE, one of 10 finalists in NIST’s lightweight cryptography standardization process), we correct the probabilities to $0$ and $2^{-22}$ instead of $2^{-23}$ and $2^{-23}$ computed using previous methods for two 4-round differential characteristics, respectively; for XTEA, we correct the probabilities to $0$ and $2^{-49}$ instead of $2^{-58}$ and $2^{-56}$ computed using previous methods for two 10-round differential characteristics, respectively. Moreover, for Alzette with $c = \tt{0xb7e15162}$, XTEA, the $\tt{quarterround}$ function of Salsa20, and the round function of Chaskey, we find some invalid DCs that Leurent’s ARX Toolkit cannot detect. Thirdly, we propose a SAT-based automatic search tool for impossible differential characteristics in ARX ciphers. We find some distinguishers ignored by previous methods. In applications, for CHAM-64/128, we find five $20$-round and nineteen $19$-round impossible differential characteristics starting from the $3$-rd round for the first time. However, if we search for impossible differential characteristics starting from the $1$-st round, we cannot find any $20$-round impossible differential characteristic, which means that the round constants can affect the security of ARX ciphers against impossible differential cryptanalysis. Moreover, we find more impossible differential characteristics for 18-round, 16-round, 14-round, and 12-round CHAM-64/128, respectively. According to our results, the differential (resp. impossible differential) attack constructed by the previous methods of placing a DC (resp. an ID) anywhere in a block cipher may be invalid.
Last updated:  2022-02-09
Functional Cryptanalysis: Application to reduced-round Xoodoo
Emanuele Bellini, Rusydi H. Makarim
This paper proposes functional cryptanalysis, a flexible and versatile approach to analyse symmetric-key primitives with two primary features. Firstly, it is a generalization of multiple attacks including (but not limited to) differential, rotational and rotational-xor cryptanalysis. Secondly, it is a theoretical framework that unifies all of the aforementioned cryptanalysis techniques and at the same time opens up possibilities for the development of new cryptanalytic approaches. The main idea of functional cryptanalysis is the usage of binary relations in the form of functions, hence the name functional, instead of binary operations like in a classical settings of "differential"-like cryptanalysis. We establish the theoretical foundations of functional cryptanalysis from standard terminologies. This work also presents an interpretation of functional cryptanalysis from the point of view of commutative algebra. In particular, we exhibit an algorithm to compute the functional probability (hence differential, rotational, and rotational-xor probability) using Grobner bases. We demonstrate the applicability of functional cryptanalysis against reduced-round Xoodoo and compare it against the best differential. To avoid dealing with invalid differential trails, we propose a method to construct a valid differential trail using Satisfiability Modulo Theory (SMT). To the best of our knowledge, this is the first time the SMT model is used to construct a valid differential while previous approaches rely on Mixed-Integer Linear Programming (MILP) model. Lastly, we remark that the use of non-translation functionals shares analogous advantages and limitations with the use of nonlinear approximations in linear cryptanalysis.
Last updated:  2022-02-09
Faster verification of V2X BSM messages via Message Chaining
Eduardo Lopes Cominetti, Marcos Vinicius M. Silva, Marcos A. Simplicio Jr., Harsh Kupwade Patil, Jefferson E. Ricardini
Vehicular-to-Everything (V2X) communications enable vehicles to exchange messages with other entities, including nearby vehicles and pedestrians. V2X is, thus, essential for establishing an Intelligent Transportation System (ITS), where vehicles use information from their surroundings to reduce traffic congestion and improve safety. To avoid abuse, V2X messages should be digitally signed using valid digital certificates. Messages sent by unauthorized entities can then be discarded, while misbehavior can lead to the revocation of the corresponding certificates. One challenge in this scenario is that messages must be verified shortly after arrival (e.g., within centiseconds), whereas vehicles may receive thousands of them per second. To handle this issue, some solutions propose prioritization or delayed-verification mechanisms, while others involve signature schemes that support batch verification. In this manuscript, we discuss two mechanisms that complement such proposals, enabling the authentication of a sequence of messages from the same source with one single signature verification. Our analysis shows that the technique can reduce the number of verified signatures by around 90% for reliable communication channels, and by more than 65% for a maximum packet loss rate of 20%.
Last updated:  2022-04-11
On Defeating Graph Analysis of Anonymous Transactions
Uncategorized
Christoph Egger, Russell W. F. Lai, Viktoria Ronge, Ivy K. Y. Woo, Hoover H. F. Yin
Show abstract
Uncategorized
In a ring-signature-based anonymous cryptocurrency, signers of a transaction are hidden among a set of potential signers, called a ring, whose size is much smaller than the number of all users. The ring-membership relations specified by the sets of transactions thus induce bipartite transaction graphs, whose distribution is in turn induced by the ring sampler underlying the cryptocurrency. Since efficient graph analysis could be performed on transaction graphs to potentially deanonymise signers, it is crucial to understand the resistance of (the transaction graphs induced by) a ring sampler against graph analysis. Of particular interest is the class of partitioning ring samplers. Although previous works showed that they provide almost optimal local anonymity, their resistance against global, e.g. graph-based, attacks were unclear. In this work, we analyse transaction graphs induced by partitioning ring samplers. Specifically, we show (partly analytically and partly empirically) that, somewhat surprisingly, by setting the ring size to be at least logarithmic in the number of users, a graph-analysing adversary is no better than the one that performs random guessing in deanonymisation up to constant factor of 2.
Last updated:  2022-09-19
Light the Signal: Optimization of Signal Leakage Attacks against LWE-Based Key Exchange
Yue Qin, Ruoyu Ding, Chi Cheng, Nina Bindel, Yanbin Pan, Jintai Ding
Key exchange protocols from the learning with errors (LWE) problem share many similarities with the Diffie–Hellman–Merkle (DHM) protocol, which plays a central role in securing our Internet. Therefore, there has been a long time effort in designing authenticated key exchange directly from LWE to mirror the advantages of DHM-based protocols. In this paper, we revisit signal leakage attacks and show that the severity of these attacks against LWE-based (authenticated) key exchange is still underestimated. In particular, by converting the problem of launching a signal leakage attack into a coding problem, we can significantly reduce the needed number of queries to reveal the secret key. Specifically, for DXL-KE we reduce the queries from 1,266 to only 29, while for DBS-KE, we need only 748 queries, a great improvement over the previous 1,074,434 queries. Moreover, our new view of signals as binary codes enables recognizing vulnerable schemes more easily. As such we completely recover the secret key of a password-based authenticated key exchange scheme by Dabra et al. with only 757 queries and partially reveal the secret used in a two-factor authentication by Wang et al. with only one query. The experimental evaluation supports our theoretical analysis and demonstrates the efficiency and effectiveness of our attacks. Our results caution against underestimating the power of signal leakage attacks as they are applicable even in settings with a very restricted number of interactions between adversary and victim.
Last updated:  2022-02-09
A LeVeL Paying Field: Cryptographic Solutions towards Social Accountability and Financial Inclusion
Gideon Samid
Thousands of digital money protocols compete for attention; the vast majority of them are a minor variation of the Satoshi Nakamoto 2008 proposal. It is time to extract the underlying principles of the Bitcoin revolution and re-assemble them in a way that preserves its benefits and gets rid of its faults. BitMint*LeVeL is a move in this direction. It upholds the fundamental migration of money from hidden bank accounts to cryptographically protected publicly exposed digital coins; it enables a cyber version of peer-to-peer cash transactions. Bitcoin and its variants rely on a fixed public/private key algorithm. Being 'fixed' turns it into a resting target for advanced cryptanalysis. The LeVeL protocol assigns each coin holder to pick their own public/private key algorithm. An attacker would have to compromise all the algorithms used by all previous coin owners -- a substantial security upgrade relative to Bitcoin. LeVeL applies to self-referential money like Bitcoin or fiat currency, and to other-referential money, serving as a claim check for assets, like gold or fiat currency. Bitcoin decentralization is groundbreaking but it gives too much aid and comfort to wrongdoers. BitMint*LeVeL re-imagines decentralization via the notion of the InterMint: Money is minted by many smoothly interchangeable mints competing for traders. Lastly, BitMint*LeVeL is built on top of the original BitMint protocol which was implemented in the legacy banking system, and thus it offers a smooth migration into cyberspace. 1.2 Billion people around us have no bank account, but do have cell phones. The LeVeL offers social accountability and financial inclusion.
Last updated:  2022-02-13
TOFU - Toggle Count Analysis made simple
Michael Gruber, Georg Sigl
Protection against physical attacks is a major requirement for cryptographic implementations running on devices which are accessible to an attacker. Side-channel attacks are the most common types of physical attacks, the most frequent side-channel is the device's power consumption. In this work we propose a novel open-source tool called TOFU which synthesizes VCD simulation traces into power traces, with adjustable leakage models. Additionally, we propose a workflow which is only based on open-source tools. The functionality of TOFU and the proposed workflow was verified by a CPA of a AES hardware implementation. We also provide numbers for the required running time of TOFU for a trace synthesis with respect to the according VCD file size. Furthermore, we provide TOFU's source code.
Last updated:  2022-02-09
Time-Memory tradeoffs for large-weight syndrome decoding in ternary codes
Pierre Karpman, Charlotte Lefevre
We propose new algorithms for solving a class of large-weight syndrome decoding problems in random ternary codes. This is the main generic problem underlying the security of the recent Wave signature scheme (Debris-Alazard et al., 2019), and it has so far received limited attention. At SAC 2019 Bricout et al. proposed a reduction to a binary subset sum problem requiring many solutions, and used it to obtain the fastest known algorithm. However ---as is often the case in the coding theory literature--- its memory cost is proportional to its time cost, which makes it unattractive in most applications. In this work we propose a range of memory-efficient algorithms for this problem, which describe a near-continuous time-memory tradeoff curve. Those are obtained by using the same reduction as Bricout et al. and carefully instantiating the derived subset sum problem with exhaustive-search algorithms from the literature, in particular dissection (Dinur et al., 2012) and dissection in tree (Dinur, 2019). We also spend significant effort adapting those algorithms to decrease their granularity, thereby allowing them to be smoothly used in a syndrome decoding context when not all the solutions to the subset sum problem are required. For a proposed parameter set for Wave, one of our best instantiations is estimated to cost $2^{177}$ bit operations and requiring $2^{88.5}$ bits of storage, while we estimate this to be $2^{152}$ and $2^{144}$ for the best algorithm from Bricout et al..
Last updated:  2022-02-09
CCA secure ElGamal encryption over an integer group where ICDH assumption holds
Gyu-Chol. Kim, Jae-Yong. Sin, Yong-Bok. Jong
In order to prove the ElGamal CCA (Chosen Ciphertext Attack) security in the random oracle model, it is necessary to use the group (i.e., ICDH group) where ICDH assumption holds. Until now, only bilinear group where ICDH assumption is equivalent to CDH assumption has been known as the ICDH group. In this paper, we introduce another ICDH group in which ICDH assumption holds under the RSA assumption. Based on this group, we propose the CCA secure ElGamal encryption. And we describe the possibility to speed up decryption by reducing CRT (Chinese Remainder Theorem) exponents in CCA secure ElGamal.
Last updated:  2022-02-09
Storage Security in Cloud Computing: Data Auditing Protocols
Andrei-Alexandru Brebu, Mihai Iacov, Emil Simion
Cloud computing has emerged as a necessity for hosting data on cloud servers so that information can be accessed and shared remotely. It was quickly adopted because it provides quality of service for various remotely available, easy-to-configure, and easy-to- use products, such as IaaS (Infrastructure as a Service) or PaaS (Platform as a Service). However, this new paradigm of data hosting brings new challenges. Some of the challenges related to the issue of security require independent audit services to verify the integrity of cloud-hosted data. With many end users and companies moving from on-premise to cloud models for their business, cloud data security is a critical concept that needs to be managed. First, we identify security requirements. Second, we look at potential solutions to ensure data integrity in cloud storage. Last, we propose a data auditing solution that can be used to detect corrupt data or file anomalies in the storage system.
Last updated:  2022-07-12
Profiled Side-channel Attack on Cryptosystems based on the Binary Syndrome Decoding Problem
Brice Colombier, Vlad-Florin Drăgoi, Pierre-Louis Cayrel, Vincent Grosso
The NIST standardization process for post-quantum cryptography has been drawing the attention of researchers to the submitted candidates. One direction of research consists in implementing those candidates on embedded systems and that exposes them to physical attacks in return. The Classic McEliece cryptosystem, which is among the four finalists of round 3 in the Key Encapsulation Mechanism category, builds its security on the hardness of the syndrome decoding problem, which is a classic hard problem in code-based cryptography. This cryptosystem was recently targeted by a laser fault injection attack leading to message recovery. Regrettably, the attack setting is very restrictive and it does not tolerate any error in the faulty syndrome. Moreover, it depends on the very strong attacker model of laser fault injection, and does not apply to optimised implementations of the algorithm that make optimal usage of the machine words capacity. In this article, we propose a to change the angle and perform a message-recovery attack that relies on side-channel information only. We improve on the previously published work in several key aspects. First, we show that side-channel information, obtained with power consumption analysis, is sufficient to obtain an integer syndrome, as required by the attack framework. This is done by leveraging classic machine learning techniques that recover the Hamming weight information very accurately. Second, we put forward a computationally-efficient method, based on a simple dot product and information-set decoding algorithms, to recover the message from the, possibly inaccurate, recovered integer syndrome. Finally, we present a masking countermeasure against the proposed attack.
Last updated:  2022-11-24
On the Performance Gap of a Generic C Optimized Assembler and Wide Vector Extensions for Masked Software with an Ascon-{\it{p}} test case
Dor Salomon, Itamar Levi
Efficient implementations of software masked designs constitute both an important goal and a significant challenge to Side Channel Analysis attack (SCA) security. In this paper we discuss the shortfall between generic C implementations and optimized (inline-) assembly versions while providing a large spectrum of efficient and generic masked implementations for any order, and demonstrate cryptographic algorithms and masking gadgets with reference to the state of the art. Our main goal is to show the prime performance gaps we can expect between different implementations and suggest how to harness the underlying hardware efficiently, a daunting task for various masking-orders or masking algorithm (multiplications, refreshing etc.). This paper focuses on implementations targeting wide vector bitsliced designs such as the ISAP algorithm. We explore concrete instances of implementations utilizing processors enabled by wide-vector capability extensions of the AMD64 Instruction Set Architecture (ISA); namely, the SSE2/3/4.1, AVX-2 and AVX-512 Streaming Single Instruction Multiple Data (SIMD) extensions. These extensions mainly enable efficient memory level parallelism and provide a gradual reduction in computation-time as a function of the level of extension and the hardware support for instruction-level parallelism. For the first time we provide a complete open-source repository of such gadgets tailored for these extensions, various gadgets types and for all orders. We evaluate the disparities between $\mathit{generic}$ high-level language masking implementations for optimized (inline-) assembly and conventional single execution path data-path architectures such as the ARM architecture. We underscore the crucial trade-off between state storage in the data-memory as compared to keeping it in the register-file (RF). This relates specifically to masked designs, and is particularly difficult to resolve because it requires inline-assembly manipulations and is not natively supported by compilers. Moreover, as the masking order ($d$) increases and the state gets larger, there must be an increase in data memory read/write accesses for state handling since the RF is simply not large enough. This requires careful optimization which depends to a considerable extent on the underlying algorithm to implement. We discuss how full utilization of SSE extensions is not always possible; i.e. when $d$ is not a power of two, and pin-point the optimal $d$ values and very sub-optimal values of $d$ which aggressively under-utilize the hardware. More generally, this paper presents several different fully generic masked implementations for any order or multiple highly optimized (inline-) assembly instances which are quite generic (for a wide spectrum of ISAs and extensions), and provide very specific implementations targeting specific extensions. The goal is to promote open-source availability, research, improvement and implementations relating to SCA security and masked designs. The building blocks and methodologies provided here are portable and can be easily adapted to other algorithms.
Last updated:  2022-02-09
CryptoMaze: Privacy-Preserving Splitting of Off-Chain Payments
Subhra Mazumdar, Sushmita Ruj
Payment Channel Networks or PCNs solve the problem of scalability in Blockchain by executing payments off-chain. Due to a lack of sufficient capacity in the network, high-valued payments are split and routed via multiple paths. Existing multi-path payment protocols either fail to achieve atomicity or are susceptible to wormhole attack. We propose a secure and privacy-preserving atomic multi-path payment protocol CryptoMaze. Our protocol avoids the formation of multiple off-chain contracts on edges shared by the paths routing partial payments. It also guarantees unlinkability between partial payments. We provide a formal definition of the protocol in the Universal Composability framework and analyze the security. We implement CryptoMaze on several instances of Lightning Network and simulated networks. Our protocol requires 11s for routing a payment of 0.04 BTC on a network instance comprising 25600 nodes. The communication cost is less than 1MB in the worst-case. On comparing the performance of CryptoMaze with several state-of-the-art payment protocols, we observed that our protocol outperforms the rest in terms of computational cost and has a feasible communication overhead.
Last updated:  2022-02-09
Quantum cryptography with classical communication: parallel remote state preparation for copy-protection, verification, and more
Alexandru Gheorghiu, Tony Metger, Alexander Poremba
Quantum mechanical effects have enabled the construction of cryptographic primitives that are impossible classically. For example, quantum copy-protection allows for a program to be encoded in a quantum state in such a way that the program can be evaluated, but not copied. Many of these cryptographic primitives are two-party protocols, where one party, Bob, has full quantum computational capabilities, and the other party, Alice, is only required to send random BB84 states to Bob. In this work, we show how such protocols can generically be converted to ones where Alice is fully classical, assuming that Bob cannot efficiently solve the LWE problem. In particular, this means that all communication between (classical) Alice and (quantum) Bob is classical, yet they can still make use of cryptographic primitives that would be impossible if both parties were classical. We apply this conversion procedure to obtain quantum cryptographic protocols with classical communication for unclonable encryption, copy-protection, computing on encrypted data, and verifiable blind delegated computation. The key technical ingredient for our result is a protocol for classically-instructed parallel remote state preparation of BB84 states. This is a multi-round protocol between (classical) Alice and (quantum polynomial-time) Bob that allows Alice to certify that Bob must have prepared $n$ uniformly random BB84 states (up to a change of basis on his space). Furthermore, Alice knows which specific BB84 states Bob has prepared, while Bob himself does not. Hence, the situation at the end of this protocol is (almost) equivalent to one where Alice sent $n$ random BB84 states to Bob. This allows us to replace the step of preparing and sending BB84 states in existing protocols by our remote-state preparation protocol in a generic and modular way.
Last updated:  2022-04-25
Crime and Punishment in Distributed Byzantine Decision Tasks (Extended Version)
Pierre Civit, Seth Gilbert, Vincent Gramoli, Rachid Guerraoui, Jovan Komatovic, Zarko Milosevic, Adi Serendinschi
A decision task is a distributed input-output problem in which each process starts with its input value and eventually produces its output value. Examples of such decision tasks are broad and range from consensus to reliable broadcast to lattice agreement. A distributed protocol solves a decision task if it enables processes to produce admissible output values despite arbitrary (Byzantine) failures. Unfortunately, it has been known for decades that many decision tasks cannot be solved if the system is overly corrupted, i.e., safety of distributed protocols solving such tasks can be violated in unlucky scenarios. By contrast, only recently did the community discover that some of these distributed protocols can be made accountable by ensuring that correct processes irrevocably detect some faulty processes responsible for any safety violation. This realization is particularly surprising (and positive) given that accountability is a powerful tool to mitigate safety violations in distributed protocols. Indeed, exposing crimes and introducing punishments naturally incentivize exemplarity. In this paper, we propose a generic transformation of any non-synchronous distributed protocol solving a decision task into its accountable version. Our transformation is built upon the well-studied simulation of crash failures on top of Byzantine failures and increases the communication complexity by a quadratic multiplicative factor in the worst case.
Last updated:  2022-02-09
Practical Seed Recovery of Fast Cryptographic Pseudo Random Number Generators
Uncategorized
Florette Martinez
Show abstract
Uncategorized
Trifork is a family of pseudo-random number generators described in 2010 by Orue et al. It is based on Lagged Fibonacci Generators and has been claimed as cryptographically secure. In 2017 was presented a new family of lightweight pseudo-random number generators: Arrow. These generators are based on the same techniques as Trifork and designed to be light, fast and secure, so they can allow private communication between resource-constrained devices. The authors based their choices of parameters on NIST standards on lightweight cryptography and claimed these pseudo-random number generators were of cryptographic strength. We present practical implemented algorithms that reconstruct the internal states of the Arrow generators for different parameters given in the original article. These algorithms enable us to predict all the following outputs and recover the seed. These attacks are all based on a simple guess-and-determine approach which is efficient enough against these generators. We also present an implemented attack on Trifork, this time using lattice-based techniques. We show it cannot have more than 64 bits of security, hence it is not cryptographically secure.
Last updated:  2022-02-20
Hardware Implementation of SpoC-128
Ambati Sathvik, Tirunagari Rahul, Anubhab Baksi, Vikramkumar Pudi
In this work, we present a hardware implementation of the lightweight Authenticated Encryption with Associated Data (AEAD) SpoC-128. Designed by AlTawy, Gong, He, Jha, Mandal, Nandi and Rohit; SpoC-128 was submitted to the Lightweight Cryptography (LWC) competition being organised by the National Institute of Standards and Technology (NIST) of the United States Department of Commerce. Our implementation follows the Application Programming Interface (API) specified by the cryptographic engineering research group in the George Mason University (GMU). The source codes are available over the public internet as an open-source project.
Last updated:  2022-02-09
Streebog compression function as PRF in secret-key settings
Vitaly Kiryukhin
Security of the many keyed hash-based cryptographic constructions (such as HMAC) depends on the fact that the underlying compression function $g(H,M)$ is a pseudorandom function (PRF). This paper presents key-recovery algorithms for 7 rounds (of 12) of Streebog compression function. Two cases were considered, as a secret key can be used: the previous state $H$ or the message block $M$. The proposed methods implicitly show that Streebog compression function has a large security margin as PRF in the above-mentioned secret-key settings.
Last updated:  2022-03-06
AuxChannel: Enabling Efficient Bi-Directional Channel for Scriptless Blockchains
Zhimei Sui, Joseph K. Liu, Jiangshan Yu, Man Ho Au, Jia Liu
Payment channels have been a promising solution to blockchain scalability. While payment channels for script-empowered blockchains (such as Bitcoin and Ethereum) have been well studied, developing payment channels for scriptless blockchains (such as Monero) is considered challenging. In particular, enabling bidirectional payment on scriptless blockchains remains an open challenge. This work closes this gap by providing AuxChannel, the first bi-directional payment channel protocol for scriptless blockchains, meaning that building payment channels only requires the support of verifiably encrypted signature (aka adaptor signature) on the underlying blockchain. AuxChannel leverages verifiably encrypted signature to create a commitment for each off-chain payment and deploys a verifiable decentralised key escrow service to resolve dispute. To enable efficient construction of AuxChannel, we introduce a new cryptographic primitive, named Consecutive Verifiably Encrypted Signature (CVES), as a core building block and it can also be of independent interest for other applications. We provide and implement a provably secure instantiation on Schnorr-based CVES. We also provide a formal security analysis on the security of the proposed AuxChannel.
Last updated:  2023-03-16
Rocca: An Efficient AES-based Encryption Scheme for Beyond 5G (Full version)
Kosei Sakamoto, Fukang Liu, Yuto Nakano, Shinsaku Kiyomoto, Takanori Isobe
In this paper, we present an AES-based authenticated-encryption with associated-data scheme called Rocca, with the purpose to reach the requirements on the speed and security in 6G systems. To achieve ultrafast software implementations, the basic design strategy is to take full advantage of the AES-NI and SIMD instructions as that of the AEGIS family and Tiaoxin-346. Although Jean and Nikolić have generalized the way to construct efficient round functions using only one round of AES (aesenc) and 128-bit XOR operation and have found several efficient candidates, there still seems to exist potential to further improve it regarding speed and state size. In order to minimize the critical path of one round, we remove the case of applying both aesenc and XOR in a cascade way for one round. By introducing a cost-free block permutation in the round function, we are able to search for candidates in a larger space without sacrificing the performance. Consequently, we obtain more efficient constructions with a smaller state size than candidates by Jean and Nikolić. Based on the newly-discovered round function, we carefully design the corresponding AEAD scheme with 256-bit security by taking several reported attacks on the AEGIS family and Tiaxion-346 into account. Our AEAD scheme can reach 178 Gbps which is almost 5 times faster than the AEAD scheme of SNOW-V. Rocca is also much faster than other efficient schemes with 256-bit key length, e.g. AEGIS-256 and AES-256-GCM. As far as we know, Rocca is the first dedicated cryptographic algorithm targeting 6G systems, i.e., 256-bit key length and the speed of more than 100 Gbps.
Last updated:  2022-05-26
GMHL: Generalized Multi-Hop Locks for Privacy-Preserving Payment Channel Networks
Uncategorized
Zilin Liu, Anjia Yang, Jian Weng, Tao Li, Huang Zeng, Xiaojian Liang
Show abstract
Uncategorized
Payment channel network (PCN), not only improving the transaction throughput of blockchain but also realizing cross-chain payment, is a very promising solution to blockchain scalability problem. Most existing PCN constructions focus on either atomicity or privacy properties. Moreover, they are built on specific scripting features of the underlying blockchain such as HTLC or are tailored to several signature algorithms like ECDSA and Schnorr. In this work, we devise a Generalized Multi-Hop Locks (GMHL) based on adaptor signature and randomizable puzzle, which supports both atomicity and privacy preserving(unlinkability). We instantiate GMHL with a concrete design that relies on a Guillou-Quisquater-based adaptor signature and a novel designed RSA-based randomizable puzzle. Furthermore, we present a generic PCN construction based on GMHL, and formally prove its security in the universal composability framework. This construction only requires the underlying blockchain to perform signature verification, and thus can be applied to various (non-/Turing-complete) blockchains. Finally, we simulate the proposed GMHL instance and compare with other protocols. The results show that our construction is efficient comparable to other constructions while remaining the good functionalities.
Last updated:  2022-01-31
Blockchain based AI-enabled Industry 4.0 CPS Protection against Advanced Persistent Threat
Ziaur Rahman, Xun Yi, Ibrahim Khalil
Industry 4.0 is all about doing things in a concurrent, secure, and fine-grained manner. IoT edge-sensors and their associated data play a predominant role in today's industry ecosystem. Breaching data or forging source devices after injecting advanced persistent threats (APT) damages the industry owners' money and loss of operators' lives. The existing challenges include APT injection attacks targeting vulnerable edge devices, insecure data transportation, trust inconsistencies among stakeholders, incompliant data storing mechanisms, etc. Edge-servers often suffer because of their lightweight computation capacity to stamp out unauthorized data or instructions, which in essence, makes them exposed to attackers. When attackers target edge servers while transporting data using traditional PKI-rendered trusts, consortium blockchain (CBC) offers proven techniques to transfer and maintain those sensitive data securely. With the recent improvement of edge machine learning, edge devices can filter malicious data at their end which largely motivates us to institute a Blockchain and AI aligned APT detection system. The unique contributions of the paper include efficient APT detection at the edge and transparent recording of the detection history in an immutable blockchain ledger. In line with that, the certificateless data transfer mechanism boost trust among collaborators and ensure an economical and sustainable mechanism after eliminating existing certificate authority. Finally, the edge-compliant storage technique facilitates efficient predictive maintenance. The respective experimental outcomes reveal that the proposed technique outperforms the other competing systems and models.
Last updated:  2022-01-31
XCC: Theft-Resilient and Collateral-Optimized Cryptocurrency-Backed Assets
Theodore Bugnet, Alexei Zamyatin
The need for cross-blockchain interoperability is higher than ever. Today, there exists a plethora of blockchain-based cryptocurrencies, with varying levels of adoption and diverse niche use cases, and yet communication across blockchains is still in its infancy. Despite the vast potential for novel applications in an interoperable ecosystem, cross-chain tools and protocols are few and often limited. Cross-chain communication requires a trusted third party, as the Fair Exchange problem is reducible to it. However, the decentralised consensus of blockchains can be used as a source of trust, and financial incentives can achieve security. XCLAIM uses these principles to enable collateralised cryptocurrency-backed assets to be created and used. However, full collateralization is inefficient, and to protect against exchange rate fluctuations overcollateralization is necessary. This is a significant barrier to scaling, and as a result, in practice, most systems still employ a centralised architecture. In this work, we introduce XCC, an extension to the XCLAIM framework which allows for a significant reduction in collateral required. By making use of periodic, timelocked commitments on the backing blockchain, XCC decouples locked collateral from issued CBAs, allowing fractional collateralization without loss of security. We instantiate XCC between Bitcoin and Ethereum to showcase practical feasibility. XCC is compatible with the majority of existing blockchains without modification.
Last updated:  2022-11-04
Faster Kyber and Dilithium on the Cortex-M4
Amin Abdulrahman, Vincent Hwang, Matthias J. Kannwischer, Amber Sprenkels
This paper presents faster implementations of the lattice-based schemes Dilithium and Kyber on the Cortex-M4. Dilithium is one of the three signature finalists in the NIST post-quantum project (NIST PQC), while Kyber is one of the four key-encapsulation mechanism (KEM) finalists. Our optimizations affect the core polynomial arithmetic using the number-theoretic transform (NTT) of both schemes. Our main contributions are threefold: We present a faster signed Barrett reduction for Kyber, propose to switch to a smaller prime modulus for the polynomial multiplications \(c\mathbf{s}_1\) and \(c\mathbf{s}_2\) in the signing procedure of Dilithium, and apply various known optimizations to the polynomial arithmetic in both schemes. Using a smaller prime modulus is particularly interesting as it allows using the Fermat number transform resulting in especially fast code. We outperform the state-of-the-art for both Dilithium and Kyber. For Dilithium, our NTT and iNTT are faster by 5.2% and 5.7%. Switching to a smaller modulus results in speed-up of 33.1%-37.6% for the relevant operations (sum of basemul and iNTT) in the signing procedure. For Kyber, the optimizations results in 15.9%-17.8% faster matrix-vector product which presents the core arithmetic operation in Kyber.
Last updated:  2022-11-25
Breaking Panther
Christina Boura, Rachelle Heim Boissier, Yann Rotella
Panther is a sponge-based lightweight authenticated encryption scheme published at Indocrypt 2021. Its round function is based on four Nonlinear Feedback Shift Registers (NFSRs). We show here that it is possible to fully recover the secret key of the construction by using a single known plaintext-ciphertext pair and with minimal computational ressources. Furthermore, we show that in a known ciphertext setting an attacker is able with the knowledge of a single ciphertext to decrypt all plaintext blocks expect for the very first ones and can forge the tag with only one call and probability one. As we demonstrate, the problem of the design comes mainly from the low number of iterations of the round function during the absorption phase. All of our attacks have been implemented and validated.
Last updated:  2022-04-14
Revisiting Higher-Order Masked Comparison for Lattice-Based Cryptography: Algorithms and Bit-sliced Implementations
Jan-Pieter D'Anvers, Michiel Van Beirendonck, Ingrid Verbauwhede
Masked comparison is one of the most expensive operations in side-channel secure implementations of lattice-based post-quantum cryptography, especially for higher masking orders. First, we introduce two new masked comparison algorithms, which improve the arithmetic comparison of D'Anvers et al. and the hybrid comparison method of Coron et al. respectively. We then look into implementation-specific optimizations, and show that small specific adaptations can have a significant impact on the overall performance. Finally, we implement various state-of-the-art comparison algorithms and benchmark them on the same platform (ARM-Cortex M4) to allow a fair comparison between them. We improve on the arithmetic comparison of D'Anvers et al. with a factor $\approx 20\%$ by using Galois Field multiplications and the hybrid comparison of Coron et al. with a factor $\approx 25\%$ by streamlining the design. Our implementation-specific improvements allow a speedup of a straightforward comparison implementation of $\approx 33\%$. We discuss the differences between the various algorithms and provide the implementations and a testing framework to ease future research.
Last updated:  2022-08-09
Perfectly-Secure Synchronous MPC with Asynchronous Fallback Guarantees
Ananya Appan, Anirudh Chandramouli, Ashish Choudhury
Secure multi-party computation (MPC) is a fundamental problem in secure distributed computing. An MPC protocol allows a set of $n$ mutually distrusting parties to carry out any joint computation of their private inputs, without disclosing any additional information about their inputs. MPC with information-theoretic security (also called unconditional security) provides the strongest security guarantees and remains secure even against computationally unbounded adversaries. Perfectly-secure MPC protocols is a class of information-theoretically secure MPC protocols, which provides all the security guarantees in an error-free fashion. The focus of this work is perfectly-secure MPC. Known protocols are designed assuming either a synchronous or an asynchronous communication network. It is well known that perfectly-secure synchronous MPC protocol is possible as long as adversary can corrupt any $t_s < n/3$ parties. On the other hand, perfectly-secure asynchronous MPC protocol can tolerate up to $t_a < n/4$ corrupt parties. A natural question is does there exist a single MPC protocol for the setting where the parties are not aware of the exact network type and which can tolerate up to $t_s < n/3$ corruptions in a synchronous network and up to $t_a < n/4$ corruptions in an asynchronous network. We design such a best-of-both-worlds perfectly-secure MPC protocol, provided $3t_s + t_a < n$ holds. For designing our protocol, we design two important building blocks, which are of independent interest. The first building block is a best-of-both-worlds Byzantine agreement (BA) protocol tolerating $t < n/3$ corruptions and which remains secure, both in a synchronous as well as asynchronous network. The second building block is a polynomial-based best-of-both-worlds verifiable secret-sharing (VSS) protocol, which can tolerate up to $t_s$ and $t_a$ corruptions in a synchronous and in an asynchronous network respectively.
Last updated:  2022-01-31
Public Key Compression and Fast Polynomial Multiplication for NTRU using the Corrected Hybridized NTT-Karatsuba Method
Rohon Kundu, Alessandro de Piccoli, Andrea Visconti
NTRU is a lattice-based public-key cryptosystem that has been selected as one of the Round III finalists at the NIST Post-Quantum Cryptography Standardization. Compressing the key sizes to increase efficiency has been a long-standing open question for lattice-based cryptosystems. In this paper we provide a solution to three seemingly opposite demands for NTRU cryptosystem: compress the key size, increase the security level, optimize performance by implementing fast polynomial multiplications. We consider a specific variant of NTRU known as NTRU-NTT. To perform polynomial optimization, we make use of the Number-Theoretic Transformation (NTT) and hybridize it with the Karatsuba Algorithm. Previous work done in providing 2-part Hybridized NTT-Karatsuba Algorithm contained some operational errors in the product expression, which have been detected in this paper. Further, we conjectured the corrected expression and gave a detailed mathematical proof of correctness. In this paper, for the first time, we optimize NTRU-NTT using the corrected Hybridized NTT-Karatsuba Algorithm. The significance of compressing the value of the prime modulus $q$ lies with decreasing the key sizes. We achieve a 128-bit post-quantum security level for a modulus value of 83,969 which is smaller than the previously known modulus value of 1,061,093,377, while keeping $n$ constant at 2048.
Last updated:  2022-01-31
Payment with Dispute Resolution: A Protocol For Reimbursing Frauds' Victims
Aydin Abadi, Steven J. Murdoch
An "Authorised Push Payment" (APP) fraud refers to the case where fraudsters deceive a victim to make payments to bank accounts controlled by them. The total amount of money stolen via APP frauds is swiftly growing. Although regulators have provided guidelines to improve victims' protection, the guidelines are vague and the victims are not receiving sufficient protection. To facilitate victims' reimbursement, in this work, we propose a protocol called "Payment with Dispute Resolution" (PwDR) and formally define it. The protocol lets an honest victim prove its innocence to a third-party dispute resolver while preserving the protocol participants' privacy. It makes black-box use of a standard online banking system. We evaluate its asymptotic cost and runtime via a prototype implementation. Our evaluation indicates that the protocol is efficient. It imposes only O(1) overheads to the customer and bank. Also, it takes a dispute resolver 0.09 milliseconds to settle a dispute between the two parties.
Last updated:  2022-02-09
Profiling Side-Channel Attacks on Dilithium: A Small Bit-Fiddling Leak Breaks It All
Soundes Marzougui, Vincent Ulitzsch, Mehdi Tibouchi, Jean-Pierre Seifert
We present an end-to-end (equivalent) key recovery attack on the Dilithium lattice-based signature scheme, one of the top contenders in the NIST postquantum cryptography competition. The attack is based on a small side-channel leakage we identified in a bit unpacking procedure inside Dilithium signature generation. We then combine machine-learning based profiling with various algorithmic techniques, including least squares regression and integer linear programming, in order to leverage this small leakage into essentially full key recovery: we manage to recover, from a moderate number of side-channel traces, enough information to sign arbitrary messages. We confirm the practicality of our technique using concrete experiments against the ARM Cortext-M4 implementation of Dilithium, and verify that our attack is robust to real-world conditions such as noisy power measurements. This attack appears difficult to protect against reliably without strong side-channel countermeasures such as masking of the entire signing algorithm, and underscores the necessity of implementing such countermeasures despite their known high cost.
Last updated:  2022-01-31
Preserving Buyer-Privacy in Decentralized Supply Chain Marketplaces
Varun Madathil, Alessandra Scafuro, Kemafor Anyanwu, Sen Qiao, Akash Pateria, Binil Starly
Technology is being used increasingly for lowering the trust barrier in domains where collaboration and cooperation are necessary, but reliability and efficiency are critical due to high stakes. An example is an industrial marketplace where many suppliers must participate in production while ensuring reliable outcomes; hence, partnerships must be pursued with care. Online marketplaces like Xometry facilitate partnership formation by vetting suppliers and mediating the marketplace. However, such an approach requires that all trust be vested in the middleman. This centralizes control, making the system vulnerable to being biased towards specific providers. The use of blockchains is now being explored to bridge the trust gap needed to support decentralizing marketplaces, allowing suppliers and customers to interact more directly by using the information on the blockchain. A typical scenario is the need to preserve privacy in certain interactions initiated by the buyer (e.g., protecting a buyer’s intellectual property during outsourcing negotiations). In this work, we initiate the formal study of matching between suppliers and buyers when buyer-privacy is required for some marketplace interactions and make the following contributions. First, we devise a formal security definition for private interactive matching in the Universally Composable (UC) Model that captures the privacy and correctness properties expected in specific supply chain marketplace interactions. Second, we provide a lean protocol based on any programmable blockchain, anonymous group signatures, and public-key encryption. Finally, we implement the protocol by instantiating some of the blockchain logic by extending the BigChainDB blockchain platform.
Last updated:  2022-09-07
Minotaur: Multi-Resource Blockchain Consensus
Matthias Fitzi, Xuechao Wang, Sreeram Kannan, Aggelos Kiayias, Nikos Leonardos, Pramod Viswanath, Gerui Wang
Resource-based consensus is the backbone of permissionless distributed ledger systems. The security of such protocols relies fundamentally on the level of resources actively engaged in the system. The variety of different resources (and related proof protocols, some times referred to as PoX in the literature) raises the fundamental question whether it is possible to utilize many of them in tandem and build multi-resource consensus protocols. The challenge in combining different resources is to achieve fungibility between them, in the sense that security would hold as long as the cumulative adversarial power across all resources is bounded. In this work, we put forth Minotaur, a multi-resource blockchain consensus protocol that combines proof of work (PoW) and proof-of-stake (PoS), and we prove it optimally fungible. At the core of our design, Minotaur operates in epochs while continuously sampling the active computational power to provide a fair exchange between the two resources, work and stake. Further, we demonstrate the ability of Minotaur to handle a higher degree of work fluctuation as compared to the Bitcoin blockchain; we also generalize Minotaur to any number of resources. We demonstrate the simplicity of Minotaur via implementing a full stack client in Rust (available open source). We use the client to test the robustness of Minotaur to variable mining power and combined work/stake attacks and demonstrate concrete empirical evidence towards the suitability of Minotaur to serve as the consensus layer of a real-world blockchain.
Last updated:  2022-03-31
E-Tenon: An Efficient Privacy-Preserving Secure Open Data Sharing Scheme for EHR System
Zhihui Lin, Prosanta Gope, Jianting Ning, Biplab Sikdar
The transition from paper-based information to Electronic Health Records (EHRs) has driven various advancements in the modern healthcare industry. In many cases, patients need to share their EHR with healthcare professionals. Given the sensitive and security-critical nature of EHRs, it is essential to consider the security and privacy issues of storing and sharing EHR. However, existing security solutions excessively encrypt the whole database, where the entire database is required to be decrypted for each access request, which is a time-consuming process. On the other hand, the use of EHR for medical research (e.g. development of precision medicine, diagnostics techniques etc.) as well optimisation of practises in healthcare organisations, requires the EHR to be analysed and for that they should be easily accessible without compromising the privacy of the patient. In this paper, we propose an efficient technique called E-Tenon that not only securely keeps all EHR publicly accessible but also provides the desirable security features. To the best of our knowledge, this is the first work in which an Open Database is used for protecting EHR. The proposed concept of E-Tenon empowers patients to securely share their EHR under multi-level, fine-grained access policies defined by themselves. Analyses show that our system outperforms existing solutions in terms of computational complexity.
Last updated:  2022-01-31
MPC-Friendly Commitments for Publicly Verifiable Covert Security
Nitin Agrawal, James Bell, Adrià Gascón, Matt J. Kusner
We address the problem of efficiently verifying a commitment in a two-party computation. This addresses the scenario where a party P1 commits to a value x to be used in a subsequent secure computation with another party P2 that wants to receive assurance that P1 did not cheat, i.e. that x was indeed the value inputted into the secure computation. Our constructions operate in the publicly verifiable covert (PVC) security model, which is a relaxation of the malicious model of MPC appropriate in settings where P1 faces a reputational harm if caught cheating. We introduce the notion of PVC commitment scheme and indexed hash functions to build commitments schemes tailored to the PVC framework, and propose constructions for both arithmetic and Boolean circuits that result in very efficient circuits. From a practical standpoint, our constructions for Boolean circuits are 60× faster to evaluate securely, and use 36× less communication than baseline methods based on hashing. Moreover, we show that our constructions are tight in terms of required non-linear operations, by proving lower bounds on the nonlinear gate count of commitment verification circuits. Finally, we present a technique to amplify the security properties our constructions that allows to efficiently recover malicious guarantees with statistical security.
Last updated:  2023-01-24
Lattice-Based Linkable Ring Signature in the Standard Model
Mingxing Hu, Zhen Liu
Ring signatures enable a user to sign messages on behalf of an arbitrary set of users, called the ring. The anonymity property guarantees that the signature does not reveal which member of the ring signed the message. The notion of linkable ring signatures (LRS) is an extension of the concept of ring signatures such that there is a public way of determining whether two signatures have been produced by the same signer. Lattice-based LRS is an important and active research line since lattice-based cryptography has attracted more attention due to its distinctive features, especially the quantum-resistant. However, all the existing lattice-based LRS relied on random oracle heuristics, i.e., no lattice-based LRS in the standard model has been introduced so far. In this paper, we present a lattice-based LRS scheme in the standard model. Toward our goal, we present a lattice basis extending algorithm which is the key ingredient in our construction, that may be of indepen- dent interest
Last updated:  2022-01-31
Development of Cryptography since Shannon
Funda Özdemir, Çetin Kaya Koç
This paper presents the development of cryptography since Shannon's seminal paper ``Communication Theory of Secrecy Systems'' in 1949.
Last updated:  2022-01-31
Performance of Hierarchical Transforms in Homomorphic Encryption: A case study on Logistic Regression inference
Pedro Geraldo M. R. Alves, Jheyne N. Ortiz, Diego F. Aranha
Recent works challenged the Number-Theoretic Transform (NTT) as the most efficient method for polynomial multiplication in GPU implementations of Fully Homomorphic Encryption schemes such as CKKS and BFV. In particular, these works argue that the Discrete Galois Transform (DGT) is a better candidate for this particular case. However, these claims were never rigorously validated, and only intuition was used to argue in favor of each transform. This work brings some light on the dis- cussion by developing similar CUDA implementations of the CKKS cryptosystem, differing only in the underlying transform and related data structure. We ran several experiments and collected perfor- mance metrics in different contexts, ranging from the basic direct comparison between the transforms to measuring the impact of each one on the inference phase of the logistic regression algorithm. Our observations suggest that, despite some specific polynomial ring configurations, the DGT in a stan- dalone implementation does not offer the same performance as the NTT. However, when we consider the entire cryptosystem, we noticed that the effects of the higher arithmetic density of the DGT on other parts of the implementation is substantial, implying a considerable performance improvement of up to 15% on the homomorphic multiplication. Furthermore, this speedup is consistent when we consider a more complex application, indicating that the DGT suits better the target architecture.
Last updated:  2022-10-19
Orienteering with one endomorphism
Sarah Arpin, Mingjie Chen, Kristin E. Lauter, Renate Scheidler, Katherine E. Stange, Ha T. N. Tran
In supersingular isogeny-based cryptography, the path-finding problem reduces to the endomorphism ring problem. Can path-finding be reduced to knowing just one endomorphism? It is known that a small endomorphism enables polynomial-time path-finding and endomorphism ring computation (Love-Boneh [36]). An endomorphism gives an explicit orientation of a supersingular elliptic curve. In this paper, we use the volcano structure of the oriented supersingular isogeny graph to take ascending/descending/horizontal steps on the graph and deduce path-finding algorithms to an initial curve. Each altitude of the volcano corresponds to a unique quadratic order, called the primitive order. We introduce a new hard problem of computing the primitive order given an arbitrary endomorphism on the curve, and we also provide a sub-exponential quantum algorithm for solving it. In concurrent work (Wesolowski [54]), it was shown that the endomorphism ring problem in the presence of one endomorphism with known primitive order reduces to a vectorization problem, implying path-finding algorithms. Our path-finding algorithms are more general in the sense that we don't assume the knowledge of the primitive order associated with the endomorphism.
Last updated:  2023-02-17
Lattice Signature can be as Simple as Lattice Encryption
Dingfeng Ye, Jun Xu, Guifang Huang, Lei Hu
Existing lattice signature schemes are much less efficient than encryption schemes due to the rejection sampling paradigm. We give a new construction which avoids rejection sampling by using temporary public keys and structured secrets in a Bliss type scheme. Structured secrets also improve existing lattice encryption schemes to nearly the same extreme efficiency. Our signing algorithm is comparative with this optimized encryption efficiency. Our signature scheme allows the same key pair work as an encryption scheme. For lightweight implementation, our techniques allow integrating of public-key encryption and signature in a simple circuit which only needs to do small integer additions as the main part of computation.
Last updated:  2022-01-31
On Regenerating Codes and Proactive Secret Sharing: Relationships and Implications
Karim Eldefrawy, Nicholas Genise, Rutuja Kshirsagar, Moti Yung
We look at two basic coding theoretic and cryptographic mechanisms developed separately and investigate relationships between them and their implications. The first mechanism is Proactive Secret Sharing (PSS), which allows randomization and repair of shares using information from other shares. PSS enables constructing secure multi-party computation protocols that can withstand mobile dynamic attacks. This self-recovery and the redundancy of uncorrupted shares allows a system to overcome recurring faults throughout its lifetime, eventually finishing the computation (or continuing forever to maintain stored data). The second mechanismis Regenerating Codes (RC) which were extensively studied and adopted in distributed storage systems. RC are error correcting (or erasure handling) codes capable of recovering a block of a distributively held codeword from other servers' blocks. This self-healing nature enables more robustness of a code distributed over different machines. Given that the two mechanisms have a built-in self-healing (leading to stabilizing) and that both can be based on Reed Solomon Codes, it is natural to formally investigate deeper relationships between them. We prove that a PSS scheme can be converted into an RC scheme, and that under some conditions RC can be utilized to instantiate a PSS scheme. This allows us, in turn, to leverage recent results enabling more efficient polynomial interpolation (due to Guruswami and Wooters) to improve the efficiency of a PSS scheme. We also show that if parameters are not carefully calibrated, such interpolation techniques (allowing partial word leakage) may be used to attack a PSS scheme over time. Secondly, the above relationships give rise to extended (de)coding notions. Our first example is mapping the generalized capabilities of adversaries (called generalized adversary structures) from the PSS realm into the RC one. Based on this we define a new variant of RC we call Generalized-decoding Regenerating Code (GRC) where not all network servers have a uniform sub-codeword (motivated by non-uniform probability of attacking different servers case). We finally highlight several interesting research directions due to our results, e.g., designing new improved GRC, and more adaptive RC re-coding techniques.
Last updated:  2022-08-05
Spatial Encryption Revisited: From Delegatable Multiple Inner Product Encryption and More
Huy Quoc Le, Dung Hoang Duong, Willy Susilo, Josef Pieprzyk
Spatial Encryption (SE), which involves encryption and decryption with affne/vector objects, was introduced by Boneh and Hamburg at Asiacrypt 2008. Since its introduction, SE has been shown as a versatile and elegant tool for implementing many other important primitives such as (Hierarchical) Identity-based Encryption ((H)IBE), Broadcast (H)IBE, Attribute-based Encryption, and Forward-secure cryptosystems. This paper revisits SE toward a more compact construction in the lattice setting. In doing that, we introduce a novel primitive called Delegatable Multiple Inner Product Encryption (DMIPE). It is a delegatable generalization of Inner Product Encryption (IPE) but different from the Hierarchical IPE (HIPE) (Okamoto and Takashima at Asiacrypt 2009). We point out that DMIPE and SE are equivalent in the sense that there are security-preserving conversions between them. As a proof of concept, we then successfully instantiate a concrete DMIPE construction relying on the hardness of the decisional learning with errors problem. In turn, the DMIPE design implies a more compact lattice-based SE in terms of sizes compared with SEs converted from HIPE (e.g., Xagawa’s HIPE at PKC 2013) using the framework by Chen et al. (Designs, Codes, and Cryptography, 2014). Furthermore, we demonstrate that one can also use SE to implement the Allow-/Deny-list encryption, which subsumes, e.g., puncturable encryption (Green and Miers at IEEE S&P 2015).
Last updated:  2022-01-31
Timing leakage analysis of non-constant-time NTT implementations with Harvey butterflies
Nir Drucker, Tomer Pelleg
Harvey butterflies and their variants are core primitives in many optimized number-theoretic transform (NTT) implementations, such as those used by the HElib and SEAL homomorphic encryption libraries. However, these butterflies are not constant-time algorithms and may leak secret data when incorrectly implemented. Luckily for SEAL and HElib, the compilers optimize the code to run in constant-time. We claim that relying on the compiler is risky and demonstrate how a simple code modification can cause leakage, which can reduce the hardness of the ring learning with errors (R-LWE) instances used by these libraries, for example, from 2^128 to 2^104.
Last updated:  2022-11-07
Public-Key Encryption from Homogeneous CLWE
Andrej Bogdanov, Miguel Cueto Noval, Charlotte Hoffmann, Alon Rosen
The homogeneous continuous LWE (hCLWE) problem is to distinguish samples of a specific high-dimensional Gaussian mixture from standard normal samples. It was shown to be at least as hard as Learning with Errors, but no reduction in the other direction is currently known. We present four new public-key encryption schemes based on the hardness of hCLWE, with varying tradeoffs between decryption and security errors, and different discretization techniques. Our schemes yield a polynomial-time algorithm for solving hCLWE using a Statistical Zero-Knowledge oracle.
Last updated:  2022-01-31
Rethinking Watermark: Providing Proof of IP Ownership in Modern SoCs
N. Nalla Anandakumar, M. Sazadur Rahman, Mridha Md Mashahedur Rahman, Rasheed Kibria, Upoma Das, Farimah Farahmandi, Fahim Rahman, Mark M. Tehranipoor
Intellectual property (IP) cores are essential to creating modern system-on-chips (SoCs). Protecting the IPs deployed in modern SoCs has become more difficult as the IP houses have been established across the globe over the past three decades. The threat posed by IP piracy and overuse has been a topic of research for the past decade or so and has led to creation of a field called watermarking. IP watermarking aims of detecting unauthorized IP usage by embedding excess, nonfunctional circuitry into the SoC. Unfortunately, prior work has been built upon assumptions that cannot be met within the modern SoC design and verification processes. In this paper, we first provide an extensive overview of the current state-of-the-art IP watermarking. Then, we challenge these dated assumptions and propose a new path for future effective IP watermarking approaches suitable for today's complex SoCs in which IPs are deeply embedded.
Last updated:  2022-01-31
The multiplicative complexity of interval checking
Thomas Häner, Mathias Soeken
We determine the exact AND-gate cost of checking if $a\leq x < b$, where $a$ and $b$ are constant integers. Perhaps surprisingly, we find that the cost of interval checking never exceeds that of a single comparison and, in some cases, it is even lower.
Last updated:  2022-01-25
Attacks on Encrypted Range Search Schemes in Multiple Dimensions
Francesca Falzon, Evangelia Anna Markatou, Zachary Espiritu, Roberto Tamassia
We present the first systematic security evaluation of multi-attribute range search schemes on symmetrically encrypted data. We present four database reconstruction attacks that apply to a broad class of schemes and rely on volume and search pattern leakage. For schemes achieving efficiency by decomposing a query into a small number of subqueries, we further show how to exploit their structure pattern, i.e., co-occurrences of subqueries. We introduce a flexible framework for building secure range search schemes by adapting a broad class of geometric search data structures (including range trees and quadtrees) to operate on encrypted data. We give four concrete range search schemes within our framework that support queries on an arbitrary number of dimensions (attributes) and offer a sliding scale of efficiency and security trade-offs. We provide a security proof for any scheme derived from our framework and a thorough analysis of the leakage of our concrete schemes, characterizing the set of equivalent databases and demonstrating information theoretic limitations on reconstruction attacks. Our attacks are the first that do not require the observation of the access pattern to reconstruct data from range queries in two and higher dimensions. Our work shows that for range queries, structure pattern leakage can be as vulnerable to attacks as access pattern leakage. We give a comprehensive evaluation of our schemes and attacks with a complexity analysis, a prototype implementation, and an experimental assessment on real-world datasets.
Last updated:  2022-09-20
NTRU-$\nu$-um: Secure Fully Homomorphic Encryption from NTRU with Small Modulus
Kamil Kluczniak
NTRUEncrypt is one of the first lattice-based encryption schemes. Furthermore, the earliest fully homomorphic encryption (FHE) schemes rely on the NTRU problem. Currently, NTRU is one of the leading candidates in the NIST post-quantum standardization competition. What makes NTRU appealing is the age of the cryptosystem and relatively good performance. Unfortunately, FHE based on NTRU became impractical due to efficient attacks on NTRU instantiations with ``overstretched'' modulus. In particular, currently, NTRU-based FHE schemes to support a reasonable circuit depth require instantiating NTRU with a very large modulus. Breaking the NTRU problem for such large moduli turns out to be easy. Due to these attacks, any serious work on practical NTRU-based FHE essentially stopped. In this paper, we reactivate research on practical FHE that can be based on NTRU. We design an efficient bootstrapping scheme in which the noise growth is small enough to keep the modulus to dimension ratio relatively small, thus avoiding the negative consequences of ``overstretching'' the modulus. Our bootstrapping algorithm is an accumulator-type bootstrapping scheme analogous to AP/FHEW/TFHE. Finally, we show that we can use the bootstrapping procedure to compute any function over $\mathbb{Z}_t$. Consequently, we obtain one of the fastest FHE bootstrapping schemes able to compute any function over elements of a finite field alongside reducing the error.
Last updated:  2022-01-25
A survey on the security protocols employed by mobile messaging applications
Ștefania Andrieș, Andrei-Daniel Miron, Andrei Cristian, Emil Simion
Recently, there has been an increase in the popularity of messaging applications that use end-to-end encryption. Among them were Telegram (in October 2021 it has 550 million active users), Signal (in January 2022 it has over 50 million downloads in the Google Play Store), WhatsApp (according to Statista, in 2021 it has over 2 billion active users), Wire (until January 2022 it has been downloaded for over 1 million times on Android devices). Two distinct protocols underlying these applications are noted: MTProto (developed in Russia by Nikolai Durov) and Signal (developed in the US by Moxie Marlinspike). This paper presents the two protocols and examines from the point of view of the primitive cryptographic security used and how the authenticated encryption, key derivation and asynchronous messaging are performed.
Last updated:  2023-12-18
The Internet Computer for Geeks
The DFINITY Team
Smart contracts are a new form of software that will revolutionize how software is written, IT systems are maintained, and applications and whole businesses are built. Smart contracts are composable and autonomous pieces of software that run on decentralized blockchains, which makes them tamperproof and unstoppable. In this paper, we describe the Internet Computer (IC), which is a radical new design of blockchain that unleashes the full potential of smart contracts, overcoming the limitations of smart contracts on traditional blockchains with respect to speed, storage costs, and computational capacity. This allows smart contracts for the first time to implement fully decentralized applications that are hosted end to end on blockchain. The IC consists of a set of cryptographic protocols that connects independently operated nodes into a collection of blockchains. These blockchains host and execute ``canisters'', the IC’s form of smart contracts. Canisters can store data, perform very general computations on that data, and provide a complete technology stack, serving web pages directly to end users. Computational and storage costs are covered by a ``reverse-gas model'', where canister developers pre-pay costs in cycles that are obtained from ICP, the native token of the IC. ICP tokens are also used for governance: the IC is governed by a decentralized autonomous organization, or DAO, which, among other things, determines changes to the topology of the network and upgrades to the protocol.
Last updated:  2022-03-12
PlonKup: Reconciling PlonK with plookup
Luke Pearson, Joshua Fitzgerald, Héctor Masip, Marta Bellés-Muñoz, Jose Luis Muñoz-Tapia
In 2019, Gabizon, Williamson, and Ciobotaru introduced PlonK – a fast and flexible ZK-SNARK with an updatable and universal structured reference string. PlonK uses a grand product argument to check permutations of wire values, and exploits convenient interactions between multiplicative subgroups and Lagrange bases. The following year, Gabizon and Williamson used similar techniques to develop plookup – a ZK-SNARK that can verify that each element from a list of queries can be found in a public lookup table. In this paper, we present PlonKup, a fully succinct ZK-SNARK that integrates the ideas from plookup into PlonK in an efficient way.
Last updated:  2022-01-25
Cross-Domain Identity-based Matchmaking Encryption
Axin Wu, Jian Weng, Weiqi Luo, Anjia Yang, Jia-Nan Liu, Zike Jiang
Recently, Ateniese et al. (CRYPTO 2019) proposed a new cryptographic primitive called matchmaking encryption (ME), which provides fine-grained access control over encrypted data by allowing both the sender and receiver to specify access control policies. The encrypted message can be decrypted correctly if and only if the attributes of the sender and receiver simultaneously meet each other's specified policies. In current ME, when users from different organizations need secret communication, they need to be managed by a single-authority center. However, it is more reasonable if users from different domains obtain secret keys from their own authority centers, respectively. Inspired by this, we extend ME to cross-domain scenarios. Specifically, we introduce the concept of the cross-domain ME and instantiate it in the identity-based setting (i.e., cross-domain identity-based ME). Then, we first formulate and design a cross-domain identity-based ME (IB-ME) scheme and prove its privacy and authenticity in the random oracle model. Further, we extend the cross-domain IB-ME to the multi-receiver setting and give the formal definition, concrete scheme and security proof. Finally, we analyze and implement the schemes, which confirms the efficiency feasibility.
Last updated:  2022-11-11
Token meets Wallet: Formalizing Privacy and Revocation for FIDO2
Lucjan Hanzlik, Julian Loss, Benedikt Wagner
The FIDO2 standard is a widely-used class of challenge-response type protocols that allows to authenticate to an online service using a hardware token. Barbosa et al. (CRYPTO `21) provided the first formal security model and analysis for the FIDO2 standard. However, their model has two shortcomings: (1) It does not include privacy, one of the key features claimed by FIDO2. (2) It only covers tokens that store {all secret keys locally}. In contrast, due to limited memory, most existing FIDO2 tokens either derive all secret keys from a common seed or store keys on the server (the latter approach is also known as {key wrapping}). In this paper, we revisit the security of the WebAuthn component of FIDO2 as implemented in practice. Our contributions are as follows. (1) We adapt the model of Barbosa et al. so as to capture authentication tokens using key derivation or key wrapping. (2) We provide the {first formal definition of privacy for the WebAuthn component of FIDO2}. We then prove the privacy of this component in common FIDO2 token implementations if the underlying building blocks are chosen appropriately. (3) We address the unsolved problem of {global key revocation} in FIDO2. To this end, we introduce and analyze a simple revocation procedure that builds on the popular BIP32 standard used in cryptocurrency wallets and can efficiently be implemented with existing FIDO2 servers.
Last updated:  2022-03-10
Zef: Low-latency, Scalable, Private Payments
Mathieu Baudet, Alberto Sonnino, Mahimna Kelkar, George Danezis
We introduce Zef, the first Byzantine-Fault Tolerant (BFT) protocol to support payments in anonymous digital coins at arbitrary scale. Zef follows the communication and security model of FastPay: both protocols are asynchronous, low-latency, linearly-scalable, and powered by partially-trusted sharded authorities. In contrast with FastPay, user accounts in Zef are uniquely-identified and safely removable. Zef coins are bound to an account by a digital certificate and otherwise stored off-chain by their owners. To create and redeem coins, users interact with the protocol via privacy-preserving operations: Zef uses randomized commitments and NIZK proofs to hide coin values; and, created coins are made unlinkable using the blind and randomizable threshold anonymous credentials of Coconut. Besides the detailed specifications and our analysis of the protocol, we are making available an open-source implementation of Zef in Rust. Our extensive benchmarks on AWS confirm textbook linear scalability and demonstrate a confirmation time under one second at nominal capacity. Compared to existing anonymous payment systems based on a blockchain, this represents a latency speedup of three orders of magnitude, with no theoretical limit on throughput.
Last updated:  2023-08-01
Feta: Efficient Threshold Designated-Verifier Zero-Knowledge Proofs
Carsten Baum, Robin Jadoul, Emmanuela Orsini, Peter Scholl, Nigel P. Smart
Zero-Knowledge protocols have increasingly become both popular and practical in recent years due to their applicability in many areas such as blockchain systems. Unfortunately, public verifiability and small proof sizes of zero-knowledge protocols currently come at the price of strong assumptions, large prover time, or both, when considering statements with millions of gates. In this regime, the most prover-efficient protocols are in the designated verifier setting, where proofs are only valid to a single party that must keep a secret state. In this work, we bridge this gap between designated-verifier proofs and public verifiability by distributing the verifier. Here, a set of verifiers can then verify a proof and, if a given threshold $t$ of the $n$ verifiers is honest and trusted, can act as guarantors for the validity of a statement. We achieve this while keeping the concrete efficiency of current designated-verifier proofs, and present constructions that have small concrete computation and communication cost. We present practical protocols in the setting of threshold verifiers with $t<n/4$ and $t<n/3$, for which we give performance figures, showcasing the efficiency of our approach.
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.