International Association
for Cryptologic Research

A reliable source of randomness is not only an essential building block in various cryptographic, security, and distributed systems protocols, but also plays an integral part in the design of many new blockchain proposals. Consequently, the topic of publicly-verifiable, bias-resistant and unpredictable randomness has recently enjoyed increased attention in a variety of scientific contributions, as well as projects from the industry. In particular random beacon protocols, which are aimed at continuous operation, can be a vital component for many current Proof-of-Stake based distributed ledger proposals. We improve upon existing random beacon approaches by introducing HydRand, a novel distributed protocol based on publicly-verifiable secret sharing (PVSS) to ensure unpredictability, bias-resistance, and public-verifiability of a continuous sequence of random beacon values. Furthermore, HydRand is able to provide guaranteed output delivery of randomness at regular and predictable intervals in the presence of adversarial behavior. In comparison to existing PVSS based approaches, our solution improves scalability by lowering the communication complexity from $ \mathcal{O}(n^3) $ to $ \mathcal{O}(n^2) $. Furthermore, we are the first to present a comparison of recently described schemes in the area of random beacon protocols.

Recently, NIST started the process of standardizing quantum- resistant public-key cryptographic algorithms. WalnutDSA, the subject of this paper, is one of the 20 proposed signature schemes that are being considered for standardization. Walnut relies on a one-way function called E-Multiplication, which has a rich algebraic structure. This paper shows that this structure can be exploited to launch several practical attacks against the Walnut cryptosystem. The attacks work very well in practice; it is possible to forge signatures and compute equivalent secret keys for the 128-bit and 256-bit security parameters submitted to NIST in less than a second and in less than a minute respectively.

Power analysis side channel attacks rely on aligned traces. As a counter-measure, devices can use a jittered clock to misalign the power traces. In this paper we suggest a way to overcome this counter-measure, using an old method of integrating samples over time followed by a correlation attack (Sliding Window CPA). We theoretically re-analyze this general method with characteristics of jittered clocks and show that it is stronger than previously believed. We show that integration of samples over a suitably chosen window size actually amplifies the correlation both with and without jitter - as long as multiple leakage points are present within the window. We then validate our analysis on a new data-set of traces measured on a board implementing a jittered clock. Our experiments show that the SW-CPA attack with a well-chosen window size is very successful against a jittered clock counter-measure and significantly outperforms previous suggestions, requiring a much smaller set of traces to correctly identify the correct key.

[Postdoc Fellow Position@NSYSU]

Postdoctoral research fellow position to work on Applied Cryptography, 5G, Wireless, and IoT Security is available in the Department of Computer Science and Engineering at National Sun Yat-sen University. Welcome the fresh Ph.D., who is going to build strong publication for pursuing the faculty position.

The publication of research works will focus on the prestigious international journals and security conferences as the following shortlists.

Journals:

IEEE or ACM Transactions journals with top ranking or high impact factor.

Conferences:

IEEE S&P, Usenix Sec, ACM CCS, Crypto, Eurocrypt, Asiacrypt, NDSS, FC, PETS, FSE, ESORICS, PKC, ACNS, AsiaCCS, TCC, CT-RSA, ACM WiSec, IEEE CSF, etc.

Qualification:

- Candidates should have a Ph.D. Degree (CS or EE), and strong background in applied cryptography, wireless and 5G security, IoT security, and authentication protocol.

- Strong publication record (major journals or top security conference papers).

- Good written and oral communication skills.

- Work experience in relevant research projects is preferable.

KPI: The number of submissions to the shortlisted journals and conferencesper year.

The initial appointment will be until the end of this year(2018) but renewable depending on the availability of funding and the candidate\'s performance(at most 2 to 3years). The travel support will also be provided to attend international conferences or to visit overseas universities. The candidate will have the chance to work together with the most active and strong security research team at National Sun Yat-sen University (NSYSU, one of seven top research universities in Taiwan).

How to apply:

Interested candidates kindly send their CV to Prof. Chun-I Fan(email: cifan (at) mail.cse.nsysu.edu.tw). Initial screening of applications will begin immediately and the position will remain open until filled. Only shortlist will be notified.

Closing date for applications: 30 June 2018

Contact: Prof. Chun-I Fan, Email: cifan (at) mail.cse.nsysu.edu.tw

More information: https://www.researchgate.net/publication/324202444_Call_for_Postdoc_Position

A number of works have focused on the setting where an adversary tampers with the shares of a secret sharing scheme. This includes literature on verifiable secret sharing, algebraic manipulation detection(AMD) codes, and, error correcting or detecting codes in general. In this work, we initiate a systematic study of what we call non-malleable secret sharing. Very roughly, the guarantee we seek is the following: the adversary may potentially tamper with all of the shares, and still, either the reconstruction procedure outputs the original secret, or, the original secret is ''destroyed'' and the reconstruction outputs a string which is completely ''unrelated'' to the original secret. Recent exciting work on non-malleable codes in the split-state model led to constructions which can be seen as 2-out-of-2 non-malleable secret sharing schemes. These constructions have already found a number of applications in cryptography. We investigate the natural question of constructing t-out-of-n non-malleable secret sharing schemes. Such a secret sharing scheme ensures that only a set consisting of t or more shares can reconstruct the secret, and, additionally guarantees non-malleability under an attack where potentially every share maybe tampered with. Techniques used for obtaining split-state non-malleable codes (or 2-out-of-2 non-malleable secret sharing) are (in some form) based on two-source extractors and seem not to generalize to our setting.

Our first result is the construction of a t-out-of-n non-malleable secret sharing scheme against an adversary who arbitrarily tampers each of the shares independently. Our construction is unconditional and features statistical non-malleability.

As our main technical result, we present t-out-of-n non-malleable secret sharing scheme in a stronger adversarial model where an adversary may jointly tamper multiple shares. Our construction is unconditional and the adversary is allowed to jointly-tamper subsets of up to (t-1) shares. We believe that the techniques introduced in our construction may be of independent interest.

Inspired by the well studied problem of perfectly secure message transmission introduced in the seminal work of Dolev et. al (J. of ACM'93), we also initiate the study of non-malleable message transmission. Non-malleable message transmission can be seen as a natural generalization in which the goal is to ensure that the receiver either receives the original message, or, the original message is essentially destroyed and the receiver receives an ''unrelated'' message, when the network is under the influence of an adversary who can byzantinely corrupt all the nodes in the network. As natural applications of our non-malleable secret sharing schemes, we propose constructions for non-malleable message transmission.

In this paper, we optimize the performances and compare several recent masking schemes in bitslice on 32-bit arm devices, with a focus on multiplication. Our main conclusion is that efficiency (or randomness) gains always come at a cost, either in terms of composability or in terms of resistance against horizontal attacks. Our evaluations should therefore allow a designer to select a masking scheme based on implementation constraints and security requirements. They also highlight the increasing feasibility of (very) high-order masking that are offered by increasingly powerful embedded devices, with new opportunities of high-security devices in various contexts.

One of the 3 tracks of iDASH Privacy & Security Workshop 2017 competition was to execute a whole genome variants search on private genomic data. Particularly, the search application was to find the top most significant SNPs (Single-Nucleotide Polymorphisms) in a database of genome records labeled with control or case.Privacy and confidentiality of genome data had to be ensured using Intel SGX enclaves. The typical use-case of this application is the multi-party computation (each party possessing one or several genome records) of the SNPs which statistically differentiate control and case genome datasets. In this paper we discuss the solution submitted by our team to this competition. Our solution consists of two applications: (i) compress and encrypt genome files and (ii) perform genome processing (top most important SNPs search). We have opted for a horizontal treatment of genome records and heavily used parallel processing. Rust programming language was employed to develop both applications. Execution performance of the processing applications scales well and very good performance metrics are obtained. Contest organizers selected it as the best submission amongst other received competition entries and our team was awarded the first prize on this track.

The security of the Jao-De Feo Supersingular Isogeny Diffie-Hellman (SIDH) key agreement scheme is based on the intractability of the Computational Supersingular Isogeny (CSSI) problem --- computing ${\mathbb F}_{p^2}$-rational isogenies of degrees $2^e$ and $3^e$ between certain supersingular elliptic curves defined over ${\mathbb F}_{p^2}$. The classical meet-in-the-middle attack on CSSI has an expected running time of $O(p^{1/4})$, but also has $O(p^{1/4})$ storage requirements. In this paper, we demonstrate that the van Oorschot-Wiener collision finding algorithm has a lower cost (but higher running time) for solving CSSI, and thus should be used instead of the meet-in-the-middle attack to assess the security of SIDH against classical attacks. The smaller parameter $p$ brings significantly improved performance for SIDH.

Garg, Gentry and Halevi (GGH13) described the first candidate multilinear maps using ideal lattices. However, Hu and Jia recently presented an efficient attack on the GGH13 map, which breaks the multipartite key exchange (MPKE) and witness encryption (WE) based on GGH13. In this work, we describe a new variant of GGH13 using secret ring, which preserves the origin functionality of GGH13. The security of our variant depends upon the following new hardness problem. Given the determinant of the circular matrix of some element in a secret ring, the problem is to find this secret ring and reconstruct this element.

This paper proposes DeepSigns, a novel end-to-end framework for systematic Watermarking and Intellectual Property (IP) protection in the context of deep learning. DeepSigns, for the first time, introduces a generic watermarking methodology that is applicable in both and black-box settings, where the adversary may or may not know the internal details of the model. The proposed methodology embeds the signature in the probability density function (pdf) of the data abstraction obtained in different layers of a deep neural network. Our approach is robust to removal and transformation attacks including model compression, model fine-tuning, and/or watermark overwriting. Extensive proof-of-concept evaluations on MNIST and CIFAR10 datasets, as well as a wide variety of neural networks architectures including Wide Residual Networks (Wide-ResNet), Multi-Layer Perceptron (MLP), and Convolutional Neural Networks (CNNs) corroborate DeepSigns' effectiveness and applicability.

One of the most efficient post-quantum signature schemes is Rainbow whose harness is based on the multivariate quadratic polynomial (MQ) problem. ELSA, a new multivariate signature scheme proposed at Asiacrypt 2017,has a similar construction to Rainbow. Its advantages, compared to Rainbow, are its smaller secret key and faster signature generation. In addition, its existential unforgeability against an adaptive chosen-message attack has been proven under the hardness of the MQ-problem induced by a public key of ELSA with a specific parameter set in the random oracle model. The high efficiency of ELSA is derived from a set of hidden quadratic equations used in the process of signature generation. However, the hidden quadratic equations yield a vulnerability. In fact, a piece of information of these equations can be recovered by using valid signatures and an equivalent secret key can be partially recovered from it. In this paper, we describe how to recover an equivalent secret key of ELSA by a chosen message attack. Our experiments show that we can recover an equivalent secret key for the claimed $128$-bit security parameter of ELSA on a standard PC in $177$ seconds with $1326$ valid signatures.

Discrete Gaussian Sampling is a fundamental tool in lattice cryptography which has been used in digital signatures, identify-based encryption, attribute-based encryption, zero-knowledge proof and fully homomorphic cryptosystem. How to obtain integers under discrete Gaussian distribution more accurately and more efficiently with a more easily implementable procedure is a core problem in discrete Gaussian Sampling. In 2010, Peikert first formulated a convolution theorem for sampling discrete Gaussian and demonstrated its theoretical soundness. Several improved and more practical versions of convolution based sampling have been proposed recently. In this paper, we improve the error estimation of convolution discrete Gaussian sampling by considering different types of errors (including some types that are missing from previous work) and expanding the theoretical result into a practical analysis. Our result provides much more accurate error bounds which are tightly matched by our experiments. Furthermore, we analyze two existing practical convolution sampling schemes under our framework. We observed that their sets of parameters need to be modified in order to achieve their preset goals. These goals can be met using the suggested parameters based on our estimation results and our experiments show the consistences as well. In this paper, we also prove some improved inequalities for discrete Gaussian measure.

We initiate the study of perfect (rather than merely statistical) reductions among cryptographic primitives. For simplicity, we focus on finite functionalities.

In addition to the obvious theoretical appeal of the question towards better understanding secure computation, perfect, as opposed to statistical reductions may be useful for designing MPC protocols with high concrete efficiency, achieved by eliminating the dependence on a security parameter.

1-out-of-2 bit-OT (dubbed OT) was shown to be complete for statistically secure 2PC for all functionalities [Kil88, IPS08]. Existing protocols in the OT-hybrid model only offer statistically secure with abort (efficient) protocols (requiring no further computational assumptions). In general, fairness can not be guaranteed, and only security with abort is achievable [Cleve86]. If the protocol is not required to be efficient in the security parameter $k$, then all 2PC functionalities can be securely evaluated [GK10] with statistical security in the OT-hybrid model.

As opposed to the statistical setting, it is not known whether OT is complete for perfectly secure 2PC. Furthermore, only a few examples of functionalities that have such protocols are known: we are only aware of string-OT and TO (OT with reversed roles) as perfectly reducible to OT. On the negative side, a large class is known, as implied by the fairness literature. By definition, functionalities not securely computable with fairness require super-polynomial in $k$ computational (and round) complexity to evaluate with error $neg(k)$ in the OT-hybrid model. This implies that these functionalities not computable with fairness are also not computable with perfect security (in the OT-hybrid model). For symmetric boolean functionalities, this class been fully characterized [ABMO15].

Back to the statistical world, quite surprisingly [IKOPS11] demonstrate that all client-server functionalities can be efficiently reduced to OT with statistical full security (no abort) in only one round.

Motivated by this relative ``ease'' of client-server functionalities for statistically secure 2PC in the OT-hybrid model, we study perfect reductions to OT for this class of functions. We prove that for many client-server functions of the form $f: X\times Y\rightarrow \{0,1\}$, where server domain size $|Y|$ is larger than client domain size $X$, have a perfect reduction to OT. More precisely, a $g(|X|,|Y|)=\Omega(1)$-fraction of functions are perfectly reducible to OT. This fraction grows roughly as $1-exp(|X|-|Y|)$. Furthermore, our reduction is 1-round using an oracle to secure evaluation of ${\text{OT}}^l$ (as in [IKOPS11]). As an example, this class contains $\text{2-out-of-5-OT}$. More generally, for $f: X\times Y\rightarrow Z$, $\Omega(1)$ of the functions with $|Y|>|X|(|Z|-1)$ are perfectly reducible to OT in 1 round.

Our work leaves open the question of whether all finite client-server functionalities are perfectly reducible to OT (not necessarily in one round). Another open question is whether 2PC functionalities that do have perfectly secure protocols in the OT hybrid model differ in round complexity, as is the case for statistical protocols.

We present a variation on the CM method that produces elliptic curves over prime fields with nearly prime order that do not admit many efficiently computable isogenies. Assuming the Bateman-Horn conjecture, we prove that elliptic curves produced this way almost always have a large embedding degree, and thus are resistant to the MOV attack on the ECDLP.

The security analysis of real-world protocols involves reduction steps that are conceptually simple but have to handle complicated protocol details. Taking inspiration from Universal Composability, Abstract Cryptography, Pi-calculus and F*-based analysis we propose a new technique for writing simple reductions to avoid mistakes, have more selfcontained concrete security statements, and allow the writer and reader to focus on the interesting steps of the proof. Our method replaces a monolithic protocol game with a collection of so-called packages that are composed by calling each other. Every component scheme is replaced by a package parameterized by a bit b. Packages with a bit 0 behave like a concrete scheme, while packages with a bit 1 behave like an ideal version. The indistinguishability of the two packages captures security properties, such as the concrete pseudo-random function being indistinguishable from a random function. In a security proof of a real-life protocol, one then needs to flip a package’s bit from 0 to 1. To do so, in our methodology, we consider all other packages as the reduction. We facilitate the concise description of such reductions by a number of Pi-calculus-style algebraic operations on packages that are justified by state separation and interface restrictions. Our proof method handles “simple” steps using algebraic rules and leaves “interesting” steps to existing game-based proof techniques such as, e.g., the code-based analysis suggested by Bellare and Rogaway. In addition to making simple reductions more precise, we apply our techniques to two composition proofs: a proof of self-composition using a hybrid argument, and the composition of key generating and key consuming components. Consistent with our algebraic style the proofs are generic. For concreteness, we apply them to the KEM-DEM proof of hybrid-encryption by Cramer and Shoup and the proof for composability of Bellare-Rogaway secure key exchange protocols with symmetric-key protocols.

We apply Smith's construction to generate four-dimensional GLV curves with fast arithmetic in the group law as well as in the base field. As Costello and Longa did in [5] for a 128-bit security level, we btained an interesting curve for fast GLV scalar multiplication, providing a high level of security (254 bits). Our curve is defined over a well-known finite field: $\mathbb{F}_{p^2}$ where $p = 2^{255} - 19$. We finally explicit the two endomorphisms used during GLV decomposition.

Geosocial applications collect (and record) users’ precise location data to perform proximity computations, such as notifying a user or triggering a service when a friend is within geographic proximity. With the growing popularity of mobile devices that have sophisticated localization capability, it becomes more convenient and tempting to share location data. But the precise location data in plaintext not only exposes user’s whereabouts but also mobility pa erns that are sensitive and cannot be changed easily. This paper proposes cryptographic protocols on top of spatial cloaking to reduce the resolution of location and balance between data utility and privacy. Specifically, we interest in the setting that allows users to send periodic updates of precise coordinates and define privacy preferences to control the granularity of the location, both in an encrypted format. Our system supports three kinds of user queries — “Where is this user?”, “Who is nearby?”, and “How close is this user from another user?”. Also, we develop a new algorithm to improve the multidimensional data access by reducing significant masking error. Our prototype and various performance evaluations on different platforms demonstrated that our system is practical.

While many cryptographic protocols for card games have been proposed, all of them focus on card games where players have some state that must be kept secret from each other, e.g. closed cards and bluffs in Poker. This scenario poses many interesting technical challenges, which are addressed with cryptographic tools that introduce significant computational and communication overheads (e.g. zero-knowledge proofs). In this paper, we consider the case of games that do not require any secret state to be maintained (e.g. Blackjack and Baccarat). Basically, in these games, cards are chosen at random and then publicly advertised, allowing for players to publicly announce their actions (before or after cards are known). We show that protocols for such games can be built from very lightweight primitives such as digital signatures and canonical random oracle commitments, yielding constructions that far outperform all known card game protocols in terms of communication, computational and round complexities. Moreover, in constructing highly efficient protocols, we introduce a new technique based on verifiable random functions for extending coin tossing, which is at the core of our constructions. Besides ensuring that the games are played correctly, our protocols support financial rewards and penalties enforcement, guaranteeing that winners receive their rewards and that cheaters get financially penalized. In order to do so, we build on blockchain-based techniques that leverage the power of stateful smart contracts to ensure fair protocol execution.

In this position paper, we initiate a systematic treatment of reaching consensus in a permissionless network. We prove several simple but hopefully insightful lower bounds that demonstrate exactly why reaching consensus in a permissionless setting is fundamentally more difficult than the classical, permissioned setting. We then present a simplified proof of Nakamoto's blockchain which we recommend for pedagogical purposes. Finally, we survey recent results including how to avoid well-known painpoints in permissionless consensus, and how to apply core ideas behind blockchains to solve consensus in the classical, permissioned setting and meanwhile achieve new properties that are not attained by classical approaches.

The goal of white-box cryptography is to implement cryptographic algorithms securely in software in the presence of an adversary that has complete access to the software's program code and execution environment. In particular, white-box cryptography needs to protect the embedded secret key from being extracted. As for today, all publicly available white-box implementations turned out succeptible to key extraction attacks. In the meanwhile, white-box cryptography is widely deployed in commercial implementations that claim to be secure. Bos, Hubain, Michiels and Teuwen (CHES 2016) introduced differential computational analysis (DCA), the first automated attack on white-box cryptography. The DCA attack performs a statistical analysis on execution traces. These traces contain information about the execution, such as memory addresses or register values, that is collected via binary instrumentation tooling during the encryption process. The white-box implementations that were attacked by Bos et al., as well as white-box implementations that have been described in the literature, protect the embedded key by using internal encodings techniques that have been introduced by Chow, Eisen, Johnson and van Oorschot (SAC 2002). In this paper, we prove rigorously that such internal encodings are too weak to protect against the DCA attack and thereby explain the experimental success of the DCA attack of Bos et al.