33 results sorted by ID
Possible spell-corrected query: ranging
Quasi-Optimal Permutation Ranking and Applications to PERK
Slim Bettaieb, Alessandro Budroni, Marco Palumbi, Décio Luiz Gazzoni Filho
Applications
A ranking function for permutations maps every permutation of length $n$ to a unique integer between $0$ and $n!-1$. For permutations of size that are of interest in cryptographic applications, evaluating such a function requires multiple-precision arithmetic. This work introduces a quasi-optimal ranking technique that allows us to rank a permutation efficiently without needing a multiple-precision arithmetic library. We present experiments that show the computational advantage of our method...
Blockchain Large Language Models
Yu Gai, Liyi Zhou, Kaihua Qin, Dawn Song, Arthur Gervais
Applications
This paper presents a dynamic, real-time approach to detecting anomalous blockchain transactions. The proposed tool, BlockGPT, generates tracing representations of blockchain activity and trains from scratch a large language model to act as a real-time Intrusion Detection System. Unlike traditional methods, BlockGPT is designed to offer an unrestricted search space and does not rely on predefined rules or patterns, enabling it to detect a broader range of anomalies. We demonstrate the...
2022/1780
Last updated: 2023-06-11
More Efficient Key Ranking for Optimal Collision Side-Channel Attacks
Cezary Glowacz
Implementation
In [Optimal Collision Side-Channel Attacks] we studied collision side-channel attacks, and derived an optimal distinguisher for key ranking. In this note we propose a heuristic estimation procedure for key ranking based on this distinguisher, and provide estimates of lower bounds for secret key ranks in collision side-channel attacks. The procedure employs nonuniform sampling introduced in [MCRank: Monte Carlo Key Rank Estimation for Side-Channel Security Evaluations], and it is more...
Comparing Key Rank Estimation Methods
Rebecca Young, Luke Mather, Elisabeth Oswald
Implementation
Recent works on key rank estimation methods claim that algorithmic key rank estimation is too slow, and suggest two new ideas: replacing repeat attacks with simulated attacks (PS-TH-GE rank estimation), and a shortcut rank estimation method that works directly on distinguishing vector distributions (GEEA). We take these ideas and provide a comprehensive comparison between them and a performant implementation of a classical, algorithmic ranking approach, as well as some earlier work on...
2022/674
Last updated: 2023-06-11
A Note on Key Ranking for Optimal Collision Side-Channel Attacks
Cezary Glowacz
Implementation
In "Optimal collision side-channel attacks" (https://eprint.iacr.org/2019/828) we studied, and derived an optimal distinguisher for key ranking. In this note we propose a heuristic estimation procedure for key ranking based on this distinguisher, and provide estimates of lower bounds for secret key ranks in collision side channel attacks.
Finding One Common Item, Privately
Tyler Beauregard, Janabel Xia, Mike Rosulek
Cryptographic protocols
Private set intersection (PSI) allows two parties, who each hold a set of items, to learn which items they have in common, without revealing anything about their other items. Some applications of PSI would be better served by revealing only one common item, rather than the entire set of all common items. In this work we develop simple special-purpose protocols for privately finding one common item (FOCI) from the intersection of two sets. The protocols differ in how that item is chosen ---...
Rethinking Modular Multi-Exponentiation in Real-World Applications
Vidal Attias, Luigi Vigneri, Vassil Dimitrov
Implementation
The importance of efficient multi-exponen- tiation algorithms in a large spectrum of cryptographic applications continues to grow. Previous literature on the subject pays attention exclusively on the mini- mization of the number of modular multiplications. However, a small reduction of the multiplicative com- plexity can be easily overshadowed by other figures of merit. In this article, we demonstrate that the most efficient algorithm for computing multi-exponentiation changes if considering...
Coeus: A System for Oblivious Document Ranking and Retrieval
Ishtiyaque Ahmad, Laboni Sarker, Divyakant Agrawal, Amr El Abbadi, Trinabh Gupta
Cryptographic protocols
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...
Preparation for Post-Quantum era: a survey about blockchain schemes from a post-quantum perspective
Andrada-Teodora Ciulei, Marian-Codrin Crețu, Emil Simion
Cryptographic protocols
Blockchain is a type of Distributed Ledger Technology (DLT) that has been included in various types of fields due to its numerous benefits: transparency, efficiency, reduced costs, decentralization, and distributivity realized through public-key cryptography and hash functions. At the same time, the increased progress of quantum computers and quantum-based algorithms threatens the security of the classical cryptographic algorithms, in consequence, it represents a risk for the Blockchain...
Toward Optimal Deep-Learning Based Side-Channel Attacks: Probability Concentration Inequality Loss and Its Usage
Akira Ito, Rei Ueno, Naofumi Homma
Implementation
In this paper, we present solutions to some open problems for constructing efficient deep learning-based side-channel attacks (DL-SCAs) through a theoretical analysis. There are two major open problems in DL-SCAs: (i) the effect of the difference in secret key values used for profiling and attack phases is unclear, and (ii) the optimality of the negative log-likelihood (NLL) loss function used in the conventional learning method is unknown. These two problems have hindered the accurate...
Reputation at Stake! A Trust Layer over Decentralized Ledger for Multiparty Computation and Reputation-Fair Lottery
Mario Larangeira
Cryptographic protocols
This work leverages on the framework of Karakostas et al. (SCN'20) by extending it to the realm of reputation and trust. At the best of our knowledge, it is the first to introduce reputation and trust to proof of stake systems. Namely, we show that their delegation framework can be repurposed to construct a trust layer over a proof of stake consensus protocol in addition to its original stake delegation application. Furthermore, we show that such extension yields a concrete reputation system...
Improving Recent Side-Channel Attacks Against the DES Key Schedule
Andreas Wiemers, Johannes Mittmann
Implementation
Recent publications consider side-channel attacks against the key schedule
of the Data Encryption Standard (DES). These publications identify a leakage model
depending on the XOR of register values in the DES key schedule.
Building on this leakage model, we first revisit a discrete model which assumes that
the Hamming distances between subsequent round keys leak without error. We
analyze this model formally and provide theoretical explanations for observations
made in previous works.
Next we...
Data Oblivious Algorithms for Multicores
Vijaya Ramachandran, Elaine Shi
Foundations
As secure processors such as Intel SGX (with hyperthreading) become widely adopted, there is a growing appetite for private analytics on big data. Most prior works on data-oblivious algorithms adopt the classical PRAM model to capture parallelism. However, it is widely understood that PRAM does not best capture realistic multicore processors, nor does it reflect
parallel programming models adopted in practice.
In this paper, we initiate the study of parallel data oblivious algorithms on...
Ranking Loss: Maximizing the Success Rate in Deep Learning Side-Channel Analysis
Gabriel Zaid, Lilian Bossuet, François Dassance, Amaury Habrard, Alexandre Venelli
Secret-key cryptography
The side-channel community recently investigated a new approach, based on deep learning, to significantly improve profiled attacks against embedded systems. Compared to template attacks, deep learning techniques can deal with protected implementations, such as masking or desynchronization, without substantial pre-processing. However, important issues are still open. One challenging problem is to adapt the methods classically used in the machine learning field (e.g. loss function, performance...
Distributed Auditing Proofs of Liabilities
Konstantinos Chalkias, Kevin Lewi, Payman Mohassel, Valeria Nikolaenko
Cryptographic protocols
Distributed Auditing Proofs of Liabilities (DAPOL) provides a novel zero knowledge proof solution to a particular class of auditing cases, in which we assume that the audited entity does not have any incentive to increase its liabilities or obligations. There are numerous domains requiring such an auditing feature, including proving financial solvency, transparent fundraising campaigns and accurate lottery jackpot amounts. Additionally, the algorithm provides a solution to official reports,...
Ordinos: A Verifiable Tally-Hiding E-Voting System
Ralf Kuesters, Julian Liedtke, Johannes Mueller, Daniel Rausch, Andreas Vogt
Cryptographic protocols
Modern electronic voting systems (e-voting systems) are designed to provide not only vote privacy but also (end-to-end) verifiability. Several verifiable e-voting systems have been proposed in the literature, with Helios being one of the most prominent ones.
Almost all such systems, however, reveal not just the voting result but also the full tally, consisting of the exact number of votes per candidate or even all single votes. There are several situations where this is undesirable. For...
A Comprehensive Framework for Fair and Efficient Benchmarking of Hardware Implementations of Lightweight Cryptography
Jens-Peter Kaps, William Diehl, Michael Tempelmeier, Farnoud Farahmand, Ekawat Homsirikamol, Kris Gaj
Implementation
In this paper, we propose a comprehensive framework for fair and efficient benchmarking of hardware implementations of lightweight cryptography (LWC). Our framework is centered around the hardware API (Application Programming Interface) for the implementations of lightweight authenticated ciphers, hash functions, and cores combining both functionalities. The major parts of our API include the minimum compliance criteria, interface, and communication protocol supported by the LWC core. The...
2019/935
Last updated: 2019-08-22
Interpretable Encrypted Searchable Neural Networks
Kai Chen, Zhongrui Lin, Jian Wan, Chungen Xu
Applications
In cloud security, traditional searchable encryption (SE) requires high computation and communication overhead for dynamic search and update. The clever combination of machine learning (ML) and SE may be a new way to solve this problem. This paper proposes interpretable encrypted searchable neural networks (IESNN) to explore probabilistic query, balanced index tree construction and automatic weight update in an encrypted cloud environment. In IESNN, probabilistic learning is used to obtain...
On the alpha value of polynomials in the tower number field sieve algorithm
Aurore Guillevic, Shashank Singh
Public-key cryptography
In this paper, we provide a notable step towards filling the gap between theory (estimates of running-time) and practice (a discrete logarithm record computation) for the Tower Number Field Sieve (TNFS) algorithm. We propose a generalisation of ranking formula for selecting the polynomials used in the very first step of TNFS algorithm. For this we provide a definition and an exact implementation (Magma and SageMath) of the alpha function. This function measures the bias in the smoothness...
Achieving Fine-grained Multi-keyword Ranked Search over Encrypted Cloud Data
Guowen Xu, Hongwei Li
Secret-key cryptography
With the advancement of Cloud computing, people now store their
data on remote Cloud servers for larger computation and storage resources. However,
users’ data may contain sensitive information of users and should not be
disclosed to the Cloud servers. If users encrypt their data and store the encrypted
data in the servers, the search capability supported by the servers will be significantly
reduced because the server has no access to the data content. In this paper,
we propose a...
Two Sides of the Same Coin: Counting and Enumerating Keys Post Side-Channel Attacks Revisited.
Daniel P. Martin, Luke Mather, Elisabeth Oswald
Implementation
Motivated by the need to assess the concrete security of a device after a side channel attack, there has been a flurry of recent work designing both key rank and key enumeration algorithms. Two main competitors for key ranking can be found in the literature: a convolution based algorithm
put forward by Glowacz et al. (FSE 2015), and a path counting based algorithm proposed by Martin et al. (Asiacrypt 2015). Both key ranking algorithms can be extended to key enumeration algorithms (Poussier...
Guru: Universal Reputation Module for Distributed Consensus Protocols
Alex Biryukov, Daniel Feher, Dmitry Khovratovich
Cryptographic protocols
In this paper we describe how to couple reputation systems with distributed consensus protocols to provide high-throughput highly-scalable consensus for large peer-to-peer networks of untrusted validators.
We introduce reputation module Guru, which can be laid on top of various consensus protocols such as PBFT or HoneyBadger. It ranks nodes based on the outcomes of consensus rounds run by a small committee, and adaptively selects the committee based on the current reputation. The protocol...
A Bounded-Space Near-Optimal Key Enumeration Algorithm for Multi-Dimensional Side-Channel Attacks
Liron David, Avishai Wool
Enumeration of cryptographic keys in order of likelihood based on side-channel leakages has a significant importance in cryptanalysis. Previous algorithms enumerate the keys in optimal order, however their space complexity is $\Omega(n^{d/2})$ when there are d subkeys and n candidate values per subkey. We propose a new key enumeration algorithm that has a space complexity bounded by $O(d^2 w+dn)$, when w is a design parameter, which allows the enumeration of many more keys without exceeding...
Low Depth Circuits for Efficient Homomorphic Sorting
Gizem S. Çetin, Yarkın Doröz, Berk Sunar, Erkay Savaş
Applications
We introduce a sorting scheme which is capable of efficiently sorting encrypted data without the secret key. The technique is obtained by focusing on the multiplicative depth of the sorting circuit alongside the more traditional metrics such as number of comparisons and number of iterations. The reduced depth allows much reduced noise growth and thereby makes it possible to select smaller parameter sizes in somewhat homomorphic encryption instantiations resulting in greater efficiency...
Tradeoff Cryptanalysis of Memory-Hard Functions
Alex Biryukov, Dmitry Khovratovich
We explore time-memory and other tradeoffs for memory-hard functions, which are supposed to impose significant computational and time penalties if less memory is used than intended. We analyze three finalists of the Password Hashing Competition: Catena, which was presented at Asiacrypt 2014, \textsf{yescrypt} and Lyra2.
We demonstrate that Catena's proof of tradeoff resilience is flawed, and attack it with a novel \emph{precomputation tradeoff}. We show that using $M^{4/5}$ memory instead...
Tighter, faster, simpler side-channel security evaluations beyond computing power
Daniel J. Bernstein, Tanja Lange, Christine van Vredendaal
Implementation
A Eurocrypt 2013 paper "Security evaluations beyond computing power: How to analyze side-channel attacks you cannot mount?" by Veyrat-Charvillon, Gérard, and Standaert proposed a "Rank Estimation Algorithm" (REA) to estimate the difficulty of finding a secret key given side-channel information from independent subkeys, such as the 16 key bytes in AES-128 or the 32 key bytes in AES-256. The lower and upper bounds produced by the algorithm are far apart for most key ranks. The algorithm can...
Sorting and Searching Behind the Curtain: Private Outsourced Sort and Frequency-Based Ranking of Search Results Over Encrypted Data
Foteini Baldimtsi, Olga Ohrimenko
Cryptographic protocols
We study the problem of private outsourced sorting of encrypted
data. We start by proposing a novel sorting protocol that allows a user to outsource his data to a cloud server in an encrypted form and then request the server to perform computations on this data and sort the result. To perform the sorting the server is assisted by a secure coprocessor with minimal computational and memory resources. The server and the coprocessor are assumed to be honest but curious, i.e., they honestly...
Secret and Verifiable Delegated Voting for Wide Representation
Yefim Leifman
Cryptographic protocols
This paper combines cryptographic voting and web page ranking and proves that it is possible to hold elections so as not to limit a voter by a list of candidates, to benefit from voter's personal experience in dealing with people, to make wide and proportional representation, and to achieve secrecy, including incoercibility, and verifiability of cryptographic voting systems.
Security ranking among assumptions within the Uber assumption framework
Antoine Joux, Antoine Rojat
Over the past decade bilinear maps have been used to build a large variety of cryptosystems. In parallel to new functionalities, we have also seen the emergence of many security assumptions. This leads to the general question of comparing two such assumptions. Boneh, Boyen and Goh introduced the Uber assumption as an attempt to offer a general framework for security assessment. Their idea is to propose a generic security assumption that can be specialized to suit the needs of any proof of...
Comparison of seven SHA-3 candidates software implementations on smart cards.
Mourad Gouicem
Implementation
In this work, we present and compare seven SHA-3 second-round candidates implementations on two different architectures used on smart cards: the Intel 8051 and the ARM7TDMI. After presenting the performances of our implementations, we explain for each candidate the main differences between our 8-bit and 32-bit implementations. Then, we compare our results to those of two benchmarks published at the second SHA-3 candidates conference this summer, and deduce a ranking according to performance...
Comparing Hardware Performance of Fourteen Round Two SHA-3 Candidates Using FPGAs
Ekawat Homsirikamol, Marcin Rogawski, Kris Gaj
Implementation
Performance in hardware has been demonstrated to be an important factor in the evaluation of candidates for cryptographic standards. Up to now, no consensus exists on how such an evaluation should be performed in order to make it fair, transparent, practical, and acceptable for the majority of the cryptographic community. In this report, we formulate a proposal for a fair and comprehensive evaluation methodology, and apply it to the comparison of hardware performance of 14 Round~2 SHA-3...
Unfolding Method for Shabal on Virtex-5 FPGAs: Concrete Results.pdf
Julien Francq, Céline Thuillet
Implementation
Recent cryptanalysis on SHA-1 family has led the NIST to call for a public competition named SHA-3 Contest.
Efficient implementations on various platforms are a criterion for ranking performance of all the candidates in this competition.
It appears that most of the hardware architectures proposed for SHA-3 candidates are basic.
In this paper, we focus on an optimized implementation of the Shabal candidate.
We improve the state-of-the-art using the unfolding method.
This transformation leads...
A Small-Scale Voting Protocol Hiding Vote-Counts of All Candidates
Pei-yih Ting, Po-Yueh Hung
Cryptographic protocols
In this paper, we focus on the design of the winner-determination procedure of an electronic voting protocol used at critical elections, e.g. at the meeting of the board of a company for critical business decisions or a parliamentary committee for legislation. The number of participating voters is limited to several hundreds but the voting should satisfy a new privacy requirement that the accumulated vote-counts of all candidates should be kept as secret as possible. This additional...
A ranking function for permutations maps every permutation of length $n$ to a unique integer between $0$ and $n!-1$. For permutations of size that are of interest in cryptographic applications, evaluating such a function requires multiple-precision arithmetic. This work introduces a quasi-optimal ranking technique that allows us to rank a permutation efficiently without needing a multiple-precision arithmetic library. We present experiments that show the computational advantage of our method...
This paper presents a dynamic, real-time approach to detecting anomalous blockchain transactions. The proposed tool, BlockGPT, generates tracing representations of blockchain activity and trains from scratch a large language model to act as a real-time Intrusion Detection System. Unlike traditional methods, BlockGPT is designed to offer an unrestricted search space and does not rely on predefined rules or patterns, enabling it to detect a broader range of anomalies. We demonstrate the...
In [Optimal Collision Side-Channel Attacks] we studied collision side-channel attacks, and derived an optimal distinguisher for key ranking. In this note we propose a heuristic estimation procedure for key ranking based on this distinguisher, and provide estimates of lower bounds for secret key ranks in collision side-channel attacks. The procedure employs nonuniform sampling introduced in [MCRank: Monte Carlo Key Rank Estimation for Side-Channel Security Evaluations], and it is more...
Recent works on key rank estimation methods claim that algorithmic key rank estimation is too slow, and suggest two new ideas: replacing repeat attacks with simulated attacks (PS-TH-GE rank estimation), and a shortcut rank estimation method that works directly on distinguishing vector distributions (GEEA). We take these ideas and provide a comprehensive comparison between them and a performant implementation of a classical, algorithmic ranking approach, as well as some earlier work on...
In "Optimal collision side-channel attacks" (https://eprint.iacr.org/2019/828) we studied, and derived an optimal distinguisher for key ranking. In this note we propose a heuristic estimation procedure for key ranking based on this distinguisher, and provide estimates of lower bounds for secret key ranks in collision side channel attacks.
Private set intersection (PSI) allows two parties, who each hold a set of items, to learn which items they have in common, without revealing anything about their other items. Some applications of PSI would be better served by revealing only one common item, rather than the entire set of all common items. In this work we develop simple special-purpose protocols for privately finding one common item (FOCI) from the intersection of two sets. The protocols differ in how that item is chosen ---...
The importance of efficient multi-exponen- tiation algorithms in a large spectrum of cryptographic applications continues to grow. Previous literature on the subject pays attention exclusively on the mini- mization of the number of modular multiplications. However, a small reduction of the multiplicative com- plexity can be easily overshadowed by other figures of merit. In this article, we demonstrate that the most efficient algorithm for computing multi-exponentiation changes if considering...
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...
Blockchain is a type of Distributed Ledger Technology (DLT) that has been included in various types of fields due to its numerous benefits: transparency, efficiency, reduced costs, decentralization, and distributivity realized through public-key cryptography and hash functions. At the same time, the increased progress of quantum computers and quantum-based algorithms threatens the security of the classical cryptographic algorithms, in consequence, it represents a risk for the Blockchain...
In this paper, we present solutions to some open problems for constructing efficient deep learning-based side-channel attacks (DL-SCAs) through a theoretical analysis. There are two major open problems in DL-SCAs: (i) the effect of the difference in secret key values used for profiling and attack phases is unclear, and (ii) the optimality of the negative log-likelihood (NLL) loss function used in the conventional learning method is unknown. These two problems have hindered the accurate...
This work leverages on the framework of Karakostas et al. (SCN'20) by extending it to the realm of reputation and trust. At the best of our knowledge, it is the first to introduce reputation and trust to proof of stake systems. Namely, we show that their delegation framework can be repurposed to construct a trust layer over a proof of stake consensus protocol in addition to its original stake delegation application. Furthermore, we show that such extension yields a concrete reputation system...
Recent publications consider side-channel attacks against the key schedule of the Data Encryption Standard (DES). These publications identify a leakage model depending on the XOR of register values in the DES key schedule. Building on this leakage model, we first revisit a discrete model which assumes that the Hamming distances between subsequent round keys leak without error. We analyze this model formally and provide theoretical explanations for observations made in previous works. Next we...
As secure processors such as Intel SGX (with hyperthreading) become widely adopted, there is a growing appetite for private analytics on big data. Most prior works on data-oblivious algorithms adopt the classical PRAM model to capture parallelism. However, it is widely understood that PRAM does not best capture realistic multicore processors, nor does it reflect parallel programming models adopted in practice. In this paper, we initiate the study of parallel data oblivious algorithms on...
The side-channel community recently investigated a new approach, based on deep learning, to significantly improve profiled attacks against embedded systems. Compared to template attacks, deep learning techniques can deal with protected implementations, such as masking or desynchronization, without substantial pre-processing. However, important issues are still open. One challenging problem is to adapt the methods classically used in the machine learning field (e.g. loss function, performance...
Distributed Auditing Proofs of Liabilities (DAPOL) provides a novel zero knowledge proof solution to a particular class of auditing cases, in which we assume that the audited entity does not have any incentive to increase its liabilities or obligations. There are numerous domains requiring such an auditing feature, including proving financial solvency, transparent fundraising campaigns and accurate lottery jackpot amounts. Additionally, the algorithm provides a solution to official reports,...
Modern electronic voting systems (e-voting systems) are designed to provide not only vote privacy but also (end-to-end) verifiability. Several verifiable e-voting systems have been proposed in the literature, with Helios being one of the most prominent ones. Almost all such systems, however, reveal not just the voting result but also the full tally, consisting of the exact number of votes per candidate or even all single votes. There are several situations where this is undesirable. For...
In this paper, we propose a comprehensive framework for fair and efficient benchmarking of hardware implementations of lightweight cryptography (LWC). Our framework is centered around the hardware API (Application Programming Interface) for the implementations of lightweight authenticated ciphers, hash functions, and cores combining both functionalities. The major parts of our API include the minimum compliance criteria, interface, and communication protocol supported by the LWC core. The...
In cloud security, traditional searchable encryption (SE) requires high computation and communication overhead for dynamic search and update. The clever combination of machine learning (ML) and SE may be a new way to solve this problem. This paper proposes interpretable encrypted searchable neural networks (IESNN) to explore probabilistic query, balanced index tree construction and automatic weight update in an encrypted cloud environment. In IESNN, probabilistic learning is used to obtain...
In this paper, we provide a notable step towards filling the gap between theory (estimates of running-time) and practice (a discrete logarithm record computation) for the Tower Number Field Sieve (TNFS) algorithm. We propose a generalisation of ranking formula for selecting the polynomials used in the very first step of TNFS algorithm. For this we provide a definition and an exact implementation (Magma and SageMath) of the alpha function. This function measures the bias in the smoothness...
With the advancement of Cloud computing, people now store their data on remote Cloud servers for larger computation and storage resources. However, users’ data may contain sensitive information of users and should not be disclosed to the Cloud servers. If users encrypt their data and store the encrypted data in the servers, the search capability supported by the servers will be significantly reduced because the server has no access to the data content. In this paper, we propose a...
Motivated by the need to assess the concrete security of a device after a side channel attack, there has been a flurry of recent work designing both key rank and key enumeration algorithms. Two main competitors for key ranking can be found in the literature: a convolution based algorithm put forward by Glowacz et al. (FSE 2015), and a path counting based algorithm proposed by Martin et al. (Asiacrypt 2015). Both key ranking algorithms can be extended to key enumeration algorithms (Poussier...
In this paper we describe how to couple reputation systems with distributed consensus protocols to provide high-throughput highly-scalable consensus for large peer-to-peer networks of untrusted validators. We introduce reputation module Guru, which can be laid on top of various consensus protocols such as PBFT or HoneyBadger. It ranks nodes based on the outcomes of consensus rounds run by a small committee, and adaptively selects the committee based on the current reputation. The protocol...
Enumeration of cryptographic keys in order of likelihood based on side-channel leakages has a significant importance in cryptanalysis. Previous algorithms enumerate the keys in optimal order, however their space complexity is $\Omega(n^{d/2})$ when there are d subkeys and n candidate values per subkey. We propose a new key enumeration algorithm that has a space complexity bounded by $O(d^2 w+dn)$, when w is a design parameter, which allows the enumeration of many more keys without exceeding...
We introduce a sorting scheme which is capable of efficiently sorting encrypted data without the secret key. The technique is obtained by focusing on the multiplicative depth of the sorting circuit alongside the more traditional metrics such as number of comparisons and number of iterations. The reduced depth allows much reduced noise growth and thereby makes it possible to select smaller parameter sizes in somewhat homomorphic encryption instantiations resulting in greater efficiency...
We explore time-memory and other tradeoffs for memory-hard functions, which are supposed to impose significant computational and time penalties if less memory is used than intended. We analyze three finalists of the Password Hashing Competition: Catena, which was presented at Asiacrypt 2014, \textsf{yescrypt} and Lyra2. We demonstrate that Catena's proof of tradeoff resilience is flawed, and attack it with a novel \emph{precomputation tradeoff}. We show that using $M^{4/5}$ memory instead...
A Eurocrypt 2013 paper "Security evaluations beyond computing power: How to analyze side-channel attacks you cannot mount?" by Veyrat-Charvillon, Gérard, and Standaert proposed a "Rank Estimation Algorithm" (REA) to estimate the difficulty of finding a secret key given side-channel information from independent subkeys, such as the 16 key bytes in AES-128 or the 32 key bytes in AES-256. The lower and upper bounds produced by the algorithm are far apart for most key ranks. The algorithm can...
We study the problem of private outsourced sorting of encrypted data. We start by proposing a novel sorting protocol that allows a user to outsource his data to a cloud server in an encrypted form and then request the server to perform computations on this data and sort the result. To perform the sorting the server is assisted by a secure coprocessor with minimal computational and memory resources. The server and the coprocessor are assumed to be honest but curious, i.e., they honestly...
This paper combines cryptographic voting and web page ranking and proves that it is possible to hold elections so as not to limit a voter by a list of candidates, to benefit from voter's personal experience in dealing with people, to make wide and proportional representation, and to achieve secrecy, including incoercibility, and verifiability of cryptographic voting systems.
Over the past decade bilinear maps have been used to build a large variety of cryptosystems. In parallel to new functionalities, we have also seen the emergence of many security assumptions. This leads to the general question of comparing two such assumptions. Boneh, Boyen and Goh introduced the Uber assumption as an attempt to offer a general framework for security assessment. Their idea is to propose a generic security assumption that can be specialized to suit the needs of any proof of...
In this work, we present and compare seven SHA-3 second-round candidates implementations on two different architectures used on smart cards: the Intel 8051 and the ARM7TDMI. After presenting the performances of our implementations, we explain for each candidate the main differences between our 8-bit and 32-bit implementations. Then, we compare our results to those of two benchmarks published at the second SHA-3 candidates conference this summer, and deduce a ranking according to performance...
Performance in hardware has been demonstrated to be an important factor in the evaluation of candidates for cryptographic standards. Up to now, no consensus exists on how such an evaluation should be performed in order to make it fair, transparent, practical, and acceptable for the majority of the cryptographic community. In this report, we formulate a proposal for a fair and comprehensive evaluation methodology, and apply it to the comparison of hardware performance of 14 Round~2 SHA-3...
Recent cryptanalysis on SHA-1 family has led the NIST to call for a public competition named SHA-3 Contest. Efficient implementations on various platforms are a criterion for ranking performance of all the candidates in this competition. It appears that most of the hardware architectures proposed for SHA-3 candidates are basic. In this paper, we focus on an optimized implementation of the Shabal candidate. We improve the state-of-the-art using the unfolding method. This transformation leads...
In this paper, we focus on the design of the winner-determination procedure of an electronic voting protocol used at critical elections, e.g. at the meeting of the board of a company for critical business decisions or a parliamentary committee for legislation. The number of participating voters is limited to several hundreds but the voting should satisfy a new privacy requirement that the accumulated vote-counts of all candidates should be kept as secret as possible. This additional...