Coercion-Resistant Voting in Linear Time via Fully Homomorphic Encryption: Towards a Quantum-Safe Scheme

in Financial Cryptography and Data Security 2019. FC 2019: International Workshops, CIW, VOTING, and WTSC (2020)

We present an approach for performing the tallying work in the coercion-resistant JCJ voting protocol, introduced by Juels, Catalano, and Jakobsson, in linear time using fully homomorphic encryption (FHE ... [more ▼]

We present an approach for performing the tallying work in the coercion-resistant JCJ voting protocol, introduced by Juels, Catalano, and Jakobsson, in linear time using fully homomorphic encryption (FHE). The suggested enhancement also paves the path towards making JCJ quantum-resistant, while leaving the underlying structure of JCJ intact. The pairwise comparison-based approach of JCJ using plaintext equivalence tests leads to a quadratic blow-up in the number of votes, which makes the tallying process rather impractical in realistic settings with a large number of voters. We show how the removal of invalid votes can be done in linear time via a solution based on recent advances in various FHE primitives such as hashing, zero-knowledge proofs of correct decryption, verifiable shuffles and threshold FHE. We conclude by touching upon some of the advantages and challenges of such an approach, followed by a discussion of further security and post-quantum considerations. [less ▲]

Authenticated Key Distribution: When the Coupon Collector is Your Enemy

in Innovative Security Solutions for Information Technology and Communications (2019, November 14)

We introduce new authenticated key exchange protocols which on the one hand do not resort to standard public key setups with corresponding assumptions of computationally hard problems, but on the other ... [more ▼]

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

A Lightweight Implementation of NTRUEncrypt for 8-bit AVR Microcontrollers

E-print/Working paper (2019)

Introduced in 1996, NTRUEncrypt is not only one of the earliest but also one of the most scrutinized lattice-based cryptosystems and a serious contender in NIST’s ongoing Post-Quantum Cryptography (PQC ... [more ▼]

Introduced in 1996, NTRUEncrypt is not only one of the earliest but also one of the most scrutinized lattice-based cryptosystems and a serious contender in NIST’s ongoing Post-Quantum Cryptography (PQC) standardization project. An important criterion for the assessment of candidates is their computational cost in various hardware and software environments. This paper contributes to the evaluation of NTRUEncrypt on the ATmega class of AVR microcontrollers, which belongs to the most popular 8-bit platforms in the embedded domain. More concretely, we present AvrNtru, a carefully-optimized implementation of NTRUEncrypt that we developed from scratch with the goal of achieving high performance and resistance to timing attacks. AvrNtru complies with version 3.3 of the EESS#1 specification and supports recent product-form parameter sets like ees443ep1, ees587ep1, and ees743ep1. A full encryption operation (including mask generation and blinding- polynomial generation) using the ees443ep1 parameters takes 834,272 clock cycles on an ATmega1281 microcontroller; the decryption is slightly more costly and has an execution time of 1,061,683 cycles. When choosing the ees743ep1 parameters to achieve a 256-bit security level, 1,539,829 clock cycles are cost for encryption and 2,103,228 clock cycles for decryption. We achieved these results thanks to a novel hybrid technique for multiplication in truncated polynomial rings where one of the operands is a sparse ternary polynomial in product form. Our hybrid technique is inspired by Gura et al’s hybrid method for multiple-precision integer multiplication (CHES 2004) and takes advantage of the large register file of the AVR architecture to minimize the number of load instructions. A constant-time multiplication in the ring specified by the ees443ep1 parameters requires only 210,827 cycles, which sets a new speed record for the arithmetic component of a lattice-based cryptosystem on an 8-bit microcontroller. [less ▲]

Security – Visible, Yet Unseen? How Displaying Security Mechanisms Impacts User Experience and Perceived Security

in Proceedings of ACM CHI Conference on Human Factors in Computing Systems (CHI2019) (2019, April)

An unsolved debate in the field of usable security concerns whether security mechanisms should be visible, or blackboxed away from the user for the sake of usability. However, tying this question to ... [more ▼]

An unsolved debate in the field of usable security concerns whether security mechanisms should be visible, or blackboxed 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 standardised 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. [less ▲]

Risk-Limiting Tallies

in Electronic Voting: Proceedings of E-Vote-ID (2019)

An offline dictionary attack against zkPAKE protocol

in An offline dictionary attack against zkPAKE protocol (2019)

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 require- ments of ... [more ▼]

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 require- ments of PAKE is to prevent o ine dictionary attacks. In this paper, we revisit zkPAKE, an augmented PAKE that has been recently proposed by Mochetti, Resende, and Aranha (SBSeg 2015). Our work shows that the zkPAKE protocol is prone to o ine password guess- ing attack, even in the presence of an adversary that has only eavesdrop- ping capabilities. Results of performance evaluation show that our attack is practical and e cient.Therefore, zkPAKE is insecure and should not be used as a password-authenticated key exchange mechanism. [less ▲]

Revisiting Deniability in Quantum Key Exchange via Covert Communication and Entanglement Distillation

in Secure IT Systems, 23rd Nordic Conference, NordSec 2018. Lecture Notes in Computer Science, vol 11252. Springer, Cham (2018, November 02)

We revisit the notion of deniability in quantum key exchange (QKE), a topic that remains largely unexplored. In the only work on this subject by Donald Beaver, it is argued that QKE is not necessarily ... [more ▼]

We revisit the notion of deniability in quantum key exchange (QKE), a topic that remains largely unexplored. In the only work on this subject by Donald Beaver, it is argued that QKE is not necessarily deniable due to an eavesdropping attack that limits key equivocation. We provide more insight into the nature of this attack and how it extends to other constructions such as QKE obtained from uncloneable encryption. We then adopt the framework for quantum authenticated key exchange, developed by Mosca et al., and extend it to introduce the notion of coercer-deniable QKE, formalized in terms of the indistinguishability of real and fake coercer views. Next, we apply results from a recent work by Arrazola and Scarani on covert quantum communication to establish a connection between covert QKE and deniability. We propose DC-QKE, a simple deniable covert QKE protocol, and prove its deniability via a reduction to the security of covert QKE. Finally, we consider how entanglement distillation can be used to enable information-theoretically deniable protocols for QKE and tasks beyond key exchange. [less ▲]

Facilitating Privacy-preserving Recommendation-as-a-Service with Machine Learning

Poster (2018, October)

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 users is an ... [more ▼]

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 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. [less ▲]

An Offline Dictionary Attack Against zkPAKE Protocol

Poster (2018, June)

Password Authenticated Key Exchange (PAKE) allows a user to establish a strong cryptographic key with a server, using only knowledge of a pre-shared password. One of the basic security requirements of ... [more ▼]

Password Authenticated Key Exchange (PAKE) allows a user to establish a strong cryptographic key with a server, using only knowledge of a pre-shared password. One of the basic security requirements of PAKE is to prevent o ine dictionary attacks. In this paper, we revisit zkPAKE, an augmented PAKE that has been recently proposed by Mochetti, Resende, and Aranha (SBSeg 2015). Our work shows that the zkPAKE protocol is prone to o ine password guessing attack, even in the presence of an adversary that has only eavesdropping capabilities. Therefore, zkPAKE is insecure and should not be used as a password-authenticated key exchange mechanism [less ▲]

From Clustering Supersequences to Entropy Minimizing Subsequences for Single and Double Deletions

E-print/Working paper (2018)

A binary string transmitted via a memoryless i.i.d. deletion channel is received as a subsequence of the original input. From this, one obtains a posterior distribution on the channel input, corresponding ... [more ▼]

A binary string transmitted via a memoryless i.i.d. deletion channel is received as a subsequence of the original input. From this, one obtains a posterior distribution on the channel input, corresponding to a set of candidate supersequences weighted by the number of times the received subsequence can be embedded in them. In a previous work it is conjectured on the basis of experimental data that the entropy of the posterior is minimized and maximized by the constant and the alternating strings, respectively. In this work, in addition to revisiting the entropy minimization conjecture, we also address several related combinatorial problems. We present an algorithm for counting the number of subsequence embeddings using a run-length encoding of strings. We then describe methods for clustering the space of supersequences such that the cardinality of the resulting sets depends only on the length of the received subsequence and its Hamming weight, but not its exact form. Then, we consider supersequences that contain a single embedding of a fixed subsequence, referred to as singletons, and provide a closed form expression for enumerating them using the same run-length encoding. We prove an analogous result for the minimization and maximization of the number of singletons, by the alternating and the uniform strings, respectively. Next, we prove the original minimal entropy conjecture for the special cases of single and double deletions using similar clustering techniques and the same run-length encoding, which allow us to characterize the distribution of the number of subsequence embeddings in the space of compatible supersequences to demonstrate the effect of an entropy decreasing operation. [less ▲]