Decoy accounts are often used as an indicator of the compromise of sensitive data, such as password files. An attacker targeting only specific known-to-be-real accounts might, however, remain undetected. A more effective method proposed by Juels and Rivest at CCS'13 is to maintain additional fake passwords associated with each account. An attacker who gains access to the password file is unable to tell apart real passwords from fake passwords, and the attempted usage of a false password immediately sets off an alarm indicating a password file compromise. Password-Authenticated Key Exchange (PAKE) has long been recognised for its strong security guarantees when it comes to low-entropy password authentication and secure channel establishment, without having to rely on the setup of a PKI. In this paper, we introduce SweetPAKE, a new cryptographic primitive that offers the same security guarantees as PAKE for key exchange, while allowing clients with a single password to authenticate against servers with n candidate passwords for that account and establish a secure channel. Additional security properties are identified and formalized to ensure that (a) high-entropy session keys are indistinguishable from random, even if later on the long-term secret password becomes corrupted (forward secrecy); (b) upon password file leakage, an adversary cannot tell apart real from fake passwords; and (c) a malicious client cannot trigger a false alarm. We capture these properties by extending well-established game-based definitions of PAKE. Furthermore, we propose a new UC formulation that comprehensively unifies both SweetPAKE (session key indistinguishability and sugarword indistinguishability) and a related notion known as Oblivious-PAKE. Finally, we propose efficient SweetPAKE and Oblivious-PAKE protocols constructed from Password-Authenticated Public-Key Encryption (PAPKE) that satisfy all the proposed notions.

Multi-Precision Integer (MPI) arithmetic is a performance-critical component of many public-key cryptosystems, including besides classical ones (e.g., RSA, ECC) also isogeny-based post-quantum schemes. In this paper, we analyze and compare two widely-used MPI representations, namely full-radix and reduced-radix, for the efficient implementation of modular arithmetic operations on the 64-bit RISC-V (RV64GC) architecture. We also evaluate how the execution times of both can be further improved with Instruction Set Extensions (ISEs). The ISEs we propose are able to accelerate a CSIDH-512 class group action by a factor of 1.71 compared to a standard software implementation on a 64-bit Rocket core. This speed-up comes at the cost of a hardware overhead of about 10%.

peer reviewed

Privacy is a notoriously difficult property to achieve in complicated systems and especially in electronic voting schemes. Moreover, electronic voting schemes is a class of systems that require very high assurance. The literature contains a number of ballot privacy definitions along with security proofs for common systems. Some machine-checked security proofs have also appeared. We define a new ballot privacy notion that captures a larger class of voting schemes. This notion improves on the state of the art by taking into account that verification in many schemes will happen or must happen after the tally has been published, not before as in previous definitions. As a case study we give a machine-checked proof of privacy for Selene, which is a remote electronic voting scheme which offers an attractive mix of security properties and usability. Prior to our work, the computational privacy of Selene has never been formally verified. Finally, we also prove that MiniVoting and Belenios satisfies our definition.

Privacy is a notoriously difficult property to achieve in complicated systems and especially in electronic voting schemes. Moreover, electronic voting schemes is a class of systems that require very high assurance. The literature contains a number of ballot privacy definitions along with security proofs for common systems. Some machine-checked security proofs have also appeared. We define a new ballot privacy notion that captures a larger class of voting schemes. This notion improves on the state of the art by taking into account that verification in many schemes will happen or must happen after the tally has been published, not before as in previous definitions. As a case study we give a machine-checked proof of privacy for Selene, which is a remote electronic voting scheme which offers an attractive mix of security properties and usability. Prior to our work, the computational privacy of Selene has never been formally verified. Finally, we also prove that MiniVoting and Belenios satisfies our definition.

Introduced in 1996, NTRUEncrypt is not only one of the earliest but also one of the most scrutinized lattice-based cryptosystems and expected to remain secure in the upcoming era of quantum computing. Furthermore, NTRUEncrypt offers some efficiency benefits over “pre-quantum” cryptosystems like RSA or ECC since the low-level arithmetic operations are less computation-intensive and, thus, more suitable for constrained devices. In this paper we present Avrntru, a highly-optimized implementation of NTRUEncrypt for 8-bit AVR microcontrollers that we developed from scratch to reach high performance and resistance to timing attacks. Avrntru complies with the EESS #1 v3.1 specification and supports product-form parameter sets such as ees443ep1, ees587ep1, and ees743ep1. An entire encryption (including mask generation and blinding-polynomial generation) using the ees443ep1 parameters requires 847973 clock cycles on an ATmega1281 microcontroller; the decryption is more costly and has an execution time of 1051871 cycles. We achieved these results with the help of a novel hybrid technique for multiplication in a truncated polynomial ring, whereby one of the operands is a sparse ternary polynomial in product form and the other an arbitrary element of the ring. A constant-time multiplication in the ring given by the ees443ep1 parameters takes only 192577 cycles, which sets a new speed record for the arithmetic part of a lattice-based cryptosystem on AVR.

Abstract Mobile device manufacturers and operating system developers increasingly deploy MAC address randomization to protect user privacy and prevent adversaries from tracking persistent hardware identifiers. Early MAC address randomization implementations suffered from logic bugs and information leakages that defeated the privacy benefits realized by using temporary, random addresses, allowing devices and users to be tracked in the wild. Recent work either assumes these implementation flaws continue to exist in modern MAC address randomization implementations, or considers only dated software or small numbers of devices. In this work, we revisit MAC address randomization by performing a cross-sectional study of 160 models of mobile phones, including modern devices released subsequent to previous studies. We tested each of these phones in a lab setting to determine whether it uses randomization, under what conditions it randomizes its MAC address, and whether it mitigates known tracking vulnerabilities. Our results show that, although very new phones with updated operating systems generally provide a high degree of privacy to their users, there are still many phones in wide use today that do not effectively prevent tracking.

Internet voting can afford more inclusive and inexpensive elections. The flip side is that the integrity of the election can be compromised by adversarial attacks and malfunctioning voting infrastructure. Individual verifiability aims to protect against such risks by letting voters verify that their votes are correctly registered in the electronic ballot box. Therefore, voters need to carry out additional tasks making human factors crucial for security. In this article, we establish a categorization of individually verifiable Internet voting schemes based on voter interactions. For each category in our proposed categorization, we evaluate a voting scheme in a user study with a total of 100 participants. In our study, we assessed usability, user experience, trust, and further qualitative data to gain deeper insights into voting schemes. Based on our results, we conclude with recommendations for developers and policymakers to inform the choices and design of individually verifiable Internet voting schemes.

In e-voting protocols, cryptographers must balance usability with strong security guarantees, such as privacy and verifiability. In traditional e-voting protocols, privacy is often provided by a trusted authority that learns the votes and computes the tally. Some protocols replace the trusted authority by a set of authorities, and privacy is guaranteed if less than a threshold number of authorities are corrupt. For verifiability, stronger security is demanded. Typically, corrupt authorities that try to fake the tally result must always be detected.To provide verifiability, many e-voting protocols use Non-Interactive Zero-Knowledge proofs (NIZK). Thanks to their non-interactive nature, NIZK allow anybody, including third parties that do not participate in the protocol, to verify the correctness of the tally. Therefore, NIZK can be used to obtain universal verifiability. Additionally, NIZK also improve usability because they allow voters to cast a vote non-interactively.The disadvantage of NIZK is that their security is based on setup assumptions such as the common reference string (CRS) or the random oracle model. The former requires a trusted party to generate a CRS. The latter, though a popular model for secure protocol design, has been shown to be unsound.We address the design of e-voting protocols that provide verifiability without any trust assumptions. We show that Non-Interactive Witness-Indistinguishable proofs can be used for this purpose. Our e-voting protocols are private under the Decision Linear assumption, while perfect individual verifiability, i.e. a fake tally is detected with probability 1, holds unconditionally. Perfect universal verifiability requires a trusted public bulletin board. We remark that our definition of verifiability does not consider eligibility or end-to-end verifiability. First, we present a general construction that supports any tally function. Then, we show how to efficiently instantiate it for specific types of elections through Groth-Sahai proofs.

An unsolved debate in the field of usable security concerns whether security mechanisms should be visible, or black-boxed away from the user for the sake of usability. However, tying this question to pragmatic usability factors only might be simplistic. This study aims at researching the impact of displaying security mechanisms on User Experience (UX) in the context of e-voting. Two versions of an e-voting application were designed and tested using a between-group experimental protocol (N=38). Version D displayed security mechanisms, while version ND did not reveal any security-related information. We collected data on UX using stan-dardised evaluation scales and semi-structured interviews. Version D performed better overall in terms of UX and need fulfilment. Qualitative analysis of the interviews gives further insights into factors impacting perceived security. Our study adds to existing research suggesting a conceptual shift from usability to UX and discusses implications for designing and evaluating secure systems.

Nowadays, recommender system is an indispensable tool in many information services, and a large number of algorithms have been designed and implemented. However, fed with very large datasets, state-of-the-art recommendation algorithms often face an efficiency bottleneck, i.e., it takes huge amount of computing resources to train a recommendation model. In order to satisfy the needs of privacy-savvy users who do not want to disclose their information to the service provider, the complexity of most existing solutions becomes prohibitive. As such, it is an interesting research question to design simple and efficient recommendation algorithms that achieve reasonable accuracy and facilitate privacy protection at the same time. In this paper, we propose an efficient recommendation algorithm, named CryptoRec, which has two nice properties: (1) can estimate a new user's preferences by directly using a model pre-learned from an expert dataset, and the new user's data is not required to train the model; (2) can compute recommendations with only addition and multiplication operations. As to the evaluation, we first test the recommendation accuracy on three real-world datasets and show that CryptoRec is competitive with state-of-the-art recommenders. Then, we evaluate the performance of the privacy-preserving variants of CryptoRec and show that predictions can be computed in seconds on a PC. In contrast, existing solutions will need tens or hundreds of hours on more powerful computers.

Machine-Learning-as-a-Service has become increasingly popular, with Recommendation-as-a-Service as one of the representative examples. In such services, providing privacy protection for the users is an important topic. Reviewing privacy-preserving solutions which were proposed in the past decade, privacy and machine learning are often seen as two competing goals at stake. Though improving cryptographic primitives (e.g., secure multi-party computation (SMC) or homomorphic encryption (HE)) or devising sophisticated secure protocols has made a remarkable achievement, but in conjunction with state-of-the-art recommender systems often yields far-from-practical solutions. We tackle this problem from the direction of machine learning. We aim to design crypto-friendly recommendation algorithms, thus to obtain efficient solutions by directly using existing cryptographic tools. In particular, we propose an HE-friendly recommender system, refer to as CryptoRec, which (1) decouples user features from latent feature space, avoiding training the recommendation model on encrypted data; (2) only relies on addition and multiplication operations, making the model straightforwardly compatible with HE schemes. The properties turn recommendation-computations into a simple matrix-multiplication operation. To further improve efficiency, we introduce a sparse-quantization-reuse method which reduces the recommendation-computation time by $9\times$ (compared to using CryptoRec directly), without compromising the accuracy. We demonstrate the efficiency and accuracy of CryptoRec on three real-world datasets. CryptoRec allows a server to estimate a user's preferences on thousands of items within a few seconds on a single PC, with the user's data homomorphically encrypted, while its prediction accuracy is still competitive with state-of-the-art recommender systems computing over clear data. Our solution enables Recommendation-as-a-Service on large datasets in a nearly real-time (seconds) level.

peer reviewed

Password Authenticated Key Exchange (PAKE) allows a user to establish a secure cryptographic key with a server, using only knowledge of a pre-shared password. One of the basic security requirements of PAKE is to prevent offline dictionary attacks.

The Prêt à Voter cryptographic voting system was designed to be flexible and to offer voters a familiar and easy voting experience. In this article, we present our development of the Prêt à Voter design to a practical implementation used in a real state election in November 2014, called vVote. As well as solving practical engineering challenges, we have also had to tailor the system to the idiosyncrasies of elections in the Australian state of Victoria and the requirements of the Victorian Electoral Commission. This article includes general background, user experience, and details of the cryptographic protocols and human processes. We explain the problems, present solutions, then analyze their security properties and explain how they tie in to other design decisions.

International audience

The balance between coercion-resistance, election verifiability and usability remains unresolved in remote electronic voting despite significant research over the last few years. We propose a change of perspective, replacing the requirement of coercion-resistance with a new requirement of coercion-evidence: there should be public evidence of the amount of coercion that has taken place during a particular execution of the voting system. We provide a formal definition of coercion-evidence that has two parts. Firstly, there should be a coercion-evidence test that can be performed against the bulletin board to accurately determine the degree of coercion that has taken place in any given run. Secondly, we require coercer independence, that is the ability of the voter to follow the protocol without being detected by the coercer. To show how coercion-evidence can be achieved, we propose a new remote voting scheme, Caveat Coercitor, and we prove that it satisfies coercion-evidence. Moreover, Caveat Coercitor makes weaker trust assumptions than other remote voting systems, such as JCJ/Civitas and Helios, and has better usability properties.

In 2006, Hao and Zieliński proposed a two-round anonymous veto protocol (called AV-net), which provided exceptional efficiency compared to related techniques. In this study, the authors add a self-tallying function to the AV-net, making it a general-purpose voting protocol. The new protocol works in the same setting as the AV-net – it requires no trusted third parties or private channels, and participants execute the protocol by sending two-round public messages. Compared with related voting protocols in past work, this is significantly more efficient in terms of the number of rounds, computational cost and bandwidth usage.

In the above titled paper (ibid., vol. 4, no. 4, pp. 611-627, Dec. 09), due to a production error, the affiliations of two of the authors were listed incorrectly. The correct affiliations are presented here. Also, the name of the last author in the affiliations footnote was printed incorrectly. The correct name is P. Y. A. Ryan.

Scantegrity II is an enhancement for existing paper ballot systems. It allows voters to verify election integrity - from their selections on the ballot all the way to the final tally - by noting codes and checking for them online. Voters mark Scantegrity II ballots just as with conventional optical scan, but using a special ballot marking pen. Marking a selection with this pen makes legible an otherwise invisible preprinted confirmation code. Confirmation codes are independent and random for each potential selection on each ballot. To verify that their individual votes are recorded correctly, voters can look up their ballot serial numbers online and verify that their confirmation codes are posted correctly. The confirmation codes do not allow voters to prove how they voted. However, the confirmation codes constitute convincing evidence of error or malfeasance in the event that incorrect codes are posted online. Correctness of the final tally with respect to the published codes is proven by election officials in a manner that can be verified by any interested party. Thus, compromise of either ballot chain of custody or the software systems cannot undetectably affect election integrity. Scantegrity II has been implemented and tested in small elections in which ballots were scanned either at the polling place or centrally. Preparations for its use in a public sector election have commenced.

¿¿¿¿¿¿Pre¿t a¿ Voter provides a practical approach to end-to-end verifiable elections with a simple, familiar voter-experience. It assures a high degree of transparency while preserving secrecy of the ballot. Assurance arises from the auditability of the election itself, rather than the need to place trust in the system components. The original idea has undergone several revisions and enhancements since its inception in 2004, driven by the identification of threats, the availability of improved cryptographic primitives, and the desire to make the scheme as flexible as possible. This paper presents the key elements of the approach and describes the evolution of the design and their suitability in various contexts. We also describe the voter experience, and the security properties that the schemes provide.

Elections are increasingly dependent on computers and telecommunication systems. Such "e-voting" schemes create socio-technical systems (combinations of technology and human organisations) that are complex and critical, as the future of nations depends on their proper operation. Thus heated debate surrounds their adoption and the possible methods for making them demonstrably dependable. We discuss the dependability requirements for such systems, and the design issues in ensuring their satisfaction, with reference to a recent proposal that uses cryptography for fault tolerance, in order to avoid some of the perceived dangers of electronic voting. Our treatment highlights the need for considering the whole socio-technical system, and for integrating security and fault tolerance viewpoints.

We discuss the prospects and perils of electronic voting technologies. We argue that poorly designed and deployed technology can be the source of major threats to the security of the voting process, although carefully designed systems have the potential to increase the trustworthiness. For a voting system to be generally accepted, however, it is essential that it be not only trustworthy but also trusted.

The importance of Information Security to virtually every level and aspect of modern society is widely accepted.The field is one of the most dynamic in computer science and a growing number of research symposia are devoted to this discipline every year.Business, government, transport, critical infrastructures etc. routinely have to face security issues.News items highlighting security concerns appear in the media with increasing frequency.The 19th ACM Symposium on Applied Computing was held 14-17 March 2004 in Nicosia, Cyprus.Its Security Track, the third in the series, hosted twelve talks, based on the respective papers included in the conference proceedings, in diverse areas of information security.The Track was organized as a research conference itself, drawing on the expertise of the ten eminent representatives of both Industry and Academia forming its program committee.Their efforts resulted in each of the forty submitted papers getting at least three reviews.This special issue of the Journal of Computer Security presents the four best papers among those presented at the conference.Originally, eight had been selected.Each of the eight was then upgraded by the authors so as to guarantee at least 30% new material with respect to the conference version.Each upgraded paper was additionally reviewed by at least two leading experts in Computer Security, and the four best papers could be selected accordingly.The best papers reflect the wide diversity of the workshop and provide, we believe, valuable contributions to the field.The first, by Bistarelli et al., uses the framework of soft constraints to model the problem of vulnerabilities cascading through a network.The second, by Collberg and Sahoo, presents an analysis of the robustness of the SHKQ software watermarking algorithm.The third, by Nenadić et al., presents a pair of related protocols for certified e-mail with fair non-repudiation of origin and receipt.The final paper, by Siaterlis and Maglaris, presents a novel data fusion based approach to the detection of distributed denial of service attacks.

MAFTIA was a three-year European research project that explored the use of fault-tolerance techniques to build intrusion-tolerant systems. The MAFTIA architecture embodies a number of key design principles for building intrusion-tolerant systems, such as the notion of distributing trust throughout the system and limiting the extent to which individual components are trusted, and the aim of this paper is to illustrate these principles and demonstrate MAFTIA s intrusion-tolerance capabilities by showing how MAFTIA mechanisms and protocols might be deployed in a realistic context. We discuss the relationship between intrusion tolerance and fault tolerance, and then describe how the MAFTIA architecture could be used to build an intrusion-tolerant version of a hypothetical e-commerce application. Using fault trees, we analyse possible attack scenarios and show how MAFTIA mechanisms protect against them. We conclude the paper with a discussion of related work and identify areas for future research.

The concept of non-interference seeks to characterize the absence of information flows through a computer system. The intuition is startlingly simple. Suppose that we want to assert that no information may flow from user A to user B via the system S. We characterize this by asserting that B’s view of S is unchanged by any alteration in A’s behaviour. It is thus asserting that A can have no causal influence on B’s interactions with and observations of the system. Non-interference is such a simple and obvious characterization of MLS confidentiality that the security community is understandably reluctant to give it up. However, it has well known problems. First, in real systems high-level input interferes with low-level output all the time. High-level files can be encrypted, sanitized, or simply downgraded and sent on their way over low-level networks. Second, after fifteen years of trying, we still don’t have any consensus as to what is the “correct” nondeterministic formulation of it. Nondeterministic versions tend to be too weak (e.g., Nondeducibility), too strong (e.g., Noninference), too cumbersome (e.g., PNI and AFM), too limiting (e.g., the Roscoe, Woodcock, Wulf determinism approach) too Baroque (e.g., Restrictiveness), or some combination of the five. In [2] it is argued that, in a process algebraic setting, the characterization of non-interference reduces to characterizing the equivalence of certain processes. This in turn is a fundamental and difficult question of theoretical computer science and one to which there is no universally agreed answer. Thus it is not even clear whether a “correct”, Platonic notion of secrecy actually exists. Non-interference would seem to be a fundamental notion in information security. It could be argued that, if we cannot get the specification and verification of the absence of information flows right, we really don’t understand the foundations of our subject. On the other hand, it is such an abstract formulation that it seems remote from real concerns of security managers, policy makers and the developers of secure systems. Most “real” security policies are concerned with specifying who has access to what resources under what circumstances. Non-interference is never mentioned. Furthermore, non-interference is in practice impossible to realise in any real system: contention for resources etc render it infeasible. Even the so-called One-WayRegulators (e.g. the NRL Pump) allow some downward flow, albeit of low channel capacity. The study of non-interference arose from the need to understand why covert channels were possible, at a time when the only theoretical security models were access-control models, which were unable to explain them. The first wave of responses consisted of information flow models, which used the syntactic structure of statements to recognize possible flows, such as “indirect flow” from the condition of an if-then statement to variables that might be modified in its body. These models were found to overestimate flows. The second wave of models were the deterministic non-interference models, which were based on the notion of functional dependency. These models explained some covert channels, and found flows only where they really existed. Subsequent varieties of models found more channels by allowing for nondeterminacy in the computer system model, either “possibilistic” or probabilistic, and still other models addressed desirable features like composability. What’s wrong with these models? This question could be addressed at several levels. At the policy level, it has been suggested that no one cares about covert channels anymore, therefore models that purport to explain them are uninteresting. This does not really seem to be a valid response. There may be a shift in application areas, however. There is less emphasis in the design of multilevel operating systems, but more interest in something like the Bleichenbacher attack on the PKCS #1 cryptographic protocol standard [1], where a channel that is due partly to the algorithm and partly to the protocol design leads to compromise of encrypted data. Attacks that might expose a stored key are of great concern. The basic principles of information compromise still apply. There is also the practical question of how noninterference theory can be translated into efficient algorithms for detecting covert channels. Non-interference anal-

Various formulations of non-interference have been proposed to try to characterise the absence of information flows in system or network. There is still no consensus in the information security community as to which of these accurately captures our intuition of the notion of secrecy. We argue that non-interference is closely related to the characterisation of process equivalence. What constitutes process equivalence is itself a fundamental question in computer science with several distinct definitions proposed in the literature. We illustrate how several of the definitions of non-interference mirror notions of process equivalence. Casting these security concepts in a process algebraic framework clarifies, for example, the role of non-determinism and allows results to be carried over regarding composition and the completeness of unwinding rules. We also discuss some natural generalisations of the approach.

The information security community has long debated the exact definition of the term "security". Even if we focus on the more modest notion of confidentiality the precise definition remains controversial. In their seminal paper, Goguen and Meseguer (1982) took an important step towards a formalisation of the notion of absence of information flow with the concept of non-interference. This too was found to have problems and limitations, particularly when applied to systems displaying non-determinism which led to a proliferation of refinements of this notion and there is still no consensus as to which of these is "correct". We show that this central concept in information security is closely related to a central concept of computer science: that of the equivalence of systems. The notion of non-interference depends ultimately on our notion of process equivalence. However what constitutes the equivalence of two processes is itself a deep and controversial question in computer science with a number of distinct definitions proposed in the literature. We illustrate how several of the leading candidates for a definition of non-interference mirror notions of system equivalence. Casting these security concepts in a process algebraic framework clarifies the relationship between them and allows many results to be carried over regarding, for example, composition and unwinding. We also outline some generalisations of non-interference to handle partial and conditional information flows.