International Association
for Cryptologic Research

Multi-valued validated asynchronous Byzantine agreement (MVBA), proposed in the elegant work of Cachin et al. (CRYPTO ’01), is fundamental for critical fault-tolerant services such as atomic broadcast in the asynchronous network. It was left as an open problem to asymptotically reduce the $O(ln^2+lambda n^2+n^3)$ communication (where $n$ is the number of parties, $l$ is the input length, and $lambda$ is the security parameter). Recently, Abraham et al. (PODC ’19) removed the $n^3$ term to partially answer the question when input is small. However, in other typical cases, e.g., building atomic broadcast through MVBA, the input length $l >= lambda n$, and thus the communication is dominated by the $ln^2$ term and the problem raised by Cachin et al. remains open.

We fill the gap and answer the remaining part of the above open problem. In particular, we present two MVBA protocols with $O(l n+lambda n^2$ communicated bits, which is optimal when $l >= lambda n$. We also maintain other benefits including optimal resilience to tolerate up to $n/3$ adaptive Byzantine corruptions, optimal expected constant running time, and optimal $O(n^2) messages.

At the core of our design, we propose asynchronous provable dispersal broadcast (APDB) in which each input can be split and dispersed to every party and later recovered in an efficient way. Leveraging APDB and asynchronous binary agreement, we design an optimal MVBA protocol, Dumbo-MVBA; we also present a general self-bootstrap framework Dumbo-MVBA★ to reduce the communication of any existing MVBA protocols.

HoneyBadgerBFT, proposed by Miller et al. [32] as the first practical asynchronous atomic broadcast protocol, demonstrated impressive performance. The core of HoneyBadgerBFT (HB-BFT) is to achieve batching consensus using asynchronous common subset protocol (ACS) of Ben-Or et al., constituted with $n$ reliable broadcast protocol (RBC) to have each node propose its input, followed by $n$ asynchronous binary agreement protocol (ABA) to make a decision for each proposed value ($n$ is the total number of nodes).

In this paper, we propose two new atomic broadcast protocols (called Dumbo1, Dumbo2) both of which have asymptotically and practically better efficiency. In particular, the ACS of Dumbo1 only runs a small $k$ (independent of $n$) instances of ABA, while that of Dumbo2 further reduces it to constant! At the core of our techniques are two major observations: (1) reducing the number of ABA instances significantly improves efficiency; and (2) using multi-valued validated Byzantine agreement (MVBA) which was considered sub-optimal for ACS in [32] in a more careful way could actually lead to a much more efficient ACS.

We implement both Dumbo1, Dumbo2 and deploy them as well as HB-BFT on 100 Amazon EC2 t2.medium instances uniformly distributed throughout 10 different regions across the globe, and run extensive experiments in the same environments. The experimental results show that our protocols achieve multi-fold improvements over HoneyBadgerBFT on both latency and throughput, especially when the system scale becomes moderately large.

A high-quality outsourced storage service is crucial for many existing applications. For example, hospitals and data centers need to guarantee the availability of their systems to perform routine daily activities. Such a system should protect users against downtime and ensure data availability over time. Continuous data availability is a critical property to measure the quality of an outsourced storage service, which implies that outsourced data is continuously available to the server during the entire storage period. We formally study the Proof of Storage-Time (PoSt), the notion initially proposed in the Filecoin whitepaper, which enables a verifier to audit the continuous data availability of an outsourced storage service. We provide a formal security model of PoSt and generic constructions that are proven secure under our definition. Moreover, our concrete instantiation can yield a PoSt protocol with an extremely efficient verification: a single hash computation to verify a proof of size around 200 bits. This makes our scheme applicable even in the decentralized storage marketplace enabled by blockchain.

In this paper we make an extensive analysis of SAKE$^+$ and SAKE$^+$-AM, two key exchange protocols. We show that several attacks are practicable against these protocols. This invalidates several claims made by the authors regarding the (security) properties of their protocols. Our results question also the correctness of the corresponding security proofs, made in the computational model (using the game-based methodology), and with the ProVerif verification tool.

PudgyTurtle is a way to use keystream to encode plaintext before XOR-based (stream cipher-like) encryption. It makes stream ciphers less efficient -- a typical implementation requiring about five times as much keystream and producing about twice as much ciphertext -- but also more robust against time-memory-data tradeoff attacks. PudgyTurtle can operate alongside any keystream generator, and thus functions somewhat like an encryption mode for stream ciphers. Here, we introduce the mechanics or PudgyTurtle and discuss its design motivations.

We present a generic forgery attack on signature schemes constructed from 5-round identification schemes made non-interactive with the Fiat-Shamir transform. The attack applies to ID schemes that use parallel repetition to decrease the soundness error. The attack can be mitigated by increasing the number of parallel repetitions, and our analysis of the attack facilitates parameter selection.

We apply the attack to MQDSS, a post-quantum signature scheme relying on the hardness of the MQ-problem. Concretely, forging a signature for the L1 instance of MQDSS, which should provide 128 bits of security, can be done in $\approx 2^{95}$ operations. We verify the validity of the attack by implementing it for round-reduced versions of MQDSS, and the designers have revised their parameter choices accordingly.

We also survey other post-quantum signature algorithms and find the attack succeeds against PKP-DSS (a signature scheme based on the hardness of the permuted kernel problem) and list other schemes that may be affected. Finally, we use our analysis to choose parameters and investigate the performance of a 5-round variant of the Picnic scheme.

A major challenge when applying cryptography on constrained environments is the trade-off between performance and security. In this work, we analyzed different strategies for the optimization of several candidates of NIST's lightweight cryptography standardization project on a RISC-V architecture. In particular, we studied the general impact of optimizing symmetric-key algorithms in assembly and in plain C. Furthermore, we present optimized implementations, achieving a speed-up of up to 81% over available implementations, and discuss general implementation strategies.

The nonlinearity of Boolean function is an important cryptographic criteria in the Best Affine Attack approach. In this paper, based on the definition of nonlinearity, we propose a new design index of nonlinear feedback shift registers. Using the index and the correlative necessary conditions of de Bruijn sequence feedback function, we prove that when $n \ge 9$, the maximum nonlinearity $Nl{(f)_{\max }}$ of arbitrary $n - $order de Bruijn sequence feedback function $f$ satisfies $3 \cdot {2^{n - 3}} - ({Z_n} + 1) < Nl{(f)_{\max }} \le {2^{n - 1}} - {2^{\frac{{n - 1}}{2}}}$ and the nonlinearity of de Bruijn sequence feedback function, based on the spanning tree of adjacency graph of affine shift registers, has a fixed value. At the same time, this paper gives the correlation analysis and practical application of the index.

The SISCOM Research Group (https://siscom.upc.edu/en) within the Department of Network Engineering (https://entel.upc.edu/en) at the Universitat Politècnica de Catalunya (UPC) (https://www.upc.edu/en/) welcomes and encourages applications for a PhD position in the area of database privacy to start in fall 2020.

DESCRIPTION OF POSITION

The PhD position has a duration of 3 years and is made available through the research project “Big Data Anonymization” funded by “la Caixa”, a top Spanish financial institution. The main objectives of this project are to pioneer advance beyond state of the art on the design of anonymization algorithms and to develop a comprehensive understanding of privacy in a context of big data. The ultimate aim is to contribute to making big data compatible with the right to privacy. For the scholarship, we are looking for a candidate who is qualified to undertake supervised independent research in the area of database anonymization, in particular in the protection of dynamic data under popular syntactic models (e.g., l-diversity, t-closeness) and differential privacy.

QUALIFICATIONS

We seek a highly motivated PhD student

• who has completed or is about to complete by summer 2020 a Master's degree in mathematics, computer science, or telecom engineering;
• with excellent academic record;
• good analytical skills;
• strong oral and written communication skills.

APPLICATION

Candidates should send to Prof. Jordi Forné (jordi.forne@upc.edu) the following information:

• their CV (including list of publications, if any);
• their academic record (with marks);
• a certificate of English (TOEFL, Cambridge or similar).

DEADLINE

September 15, 2020.

Closing date for applications:

Contact: Prof. Jordi Forné

Event date: 9 November 2020
Submission deadline: 23 July 2020
Notification: 26 August 2020

1. Overall introduction. There are Ph.D. position openings (full scholarship, tuition & very competitive stipend) at Dr. Jiafeng Harvest Xie's Security & Cryptography (SAC) Lab for the Fall of 2020, located at the Department of Electrical and Computer Engineering of Villanova University (PA, USA).

2. Research area. Post quantum cryptography hardware implementation, fault detection/attack, and hardware security.

3. Qualification. Preferred to have research experience in the areas of cryptographic engineering, fault detection, hardware security, and VLSI design. Students from electrical/computer engineering, computer science, and cryptography (applied mathematics) or other related majors are WARMLY welcome! Programming skills such as HDL, C++ will be more favorable.

NOTE: because of the time urgency, it's better that you are currently in U.S.

4. Application process. Interested students can directly send the CV/resume to Dr. Jiafeng Harvest Xie's email: jiafeng.xie@villanova.edu.

5. Application information. The detailed application requirement is available at the department website.

6. Additional information. Villanova University is a private research university located in Radnor Township, a suburb northwest of Philadelphia, Pennsylvania. U.S. News & World Report ranks Villanova as tied for the 46th best National University in the U.S. for 2020.

7. PI introduction. Dr. Jiafeng Harvest Xie is currently an Assistant Professor at the Department of Electrical and Computer Engineering of Villanova University. His research interests include cryptographic engineering, hardware security, and VLSI digital design. He is the Best Paper Awardee of IEEE HOST 2019. He is also the Associate Editor for Microelectronics Journal, IEEE Access, and IEEE Trans. Circuits and Systems II.

Contact: Dr. Jiafeng Harvest Xie, email: jiafeng.xie@villanova.edu

Closing date for applications:

Contact: Dr. Jiafeng Harvest Xie, email: jiafeng.xie@villanova.edu

More information: https://www1.villanova.edu/villanova/engineering/departments/ece/facultyStaff/biodetail.html?mail=jiafeng.xie@villanova.

The comparison function of the two numbers is one of the most commonly used operations in many applications including deep learning and data processing systems. Several studies have been conducted to efficiently evaluate the comparison function in homomorphic encryption schemes which only allow addition and multiplication for the ciphertext. Recently, new comparison methods that approximate sign function using composite polynomial in the homomorphic encryption, called homomorphic comparison operation, were proposed and it was proved that the methods have optimal asymptotic complexity. In this paper, we propose new optimal algorithms that approximate the sign function in the homomorphic encryption by using composite polynomials of the minimax approximate polynomials, which are constructed by the modified Remez algorithm. It is proved that the number of required non-scalar multiplications and depth consumption for the proposed algorithms are less than those for any methods that use a composite polynomial of component polynomials with odd degree terms approximating the sign function, respectively. In addition, an optimal polynomial-time algorithm for the proposed homomorphic comparison operation is proposed by using dynamic programming. As a result of numerical analysis, for the case that we want to minimize the number of non-scalar multiplications, the proposed algorithm reduces the required number of non-scalar multiplications and depth consumption by about 33\% and 35\%, respectively, compared to those for the previous work. In addition, for the case that we want to minimize the depth consumption, the proposed algorithm reduces the required number of non-scalar multiplications and depth consumption by about 10\% and 47\%, respectively, compared to those for the previous work.

Secure Elements (SEs) are hardware trust anchors which provide cryptographic services including secure storage of secret keys and certificates. In long-living devices certain cryptographic functions might get insecure over time, e.g. new implementation attacks or bugs are discovered, and might require to be updated. On FPGAs, partial reconfiguration (PR) offers the opportunity to overcome this issue by replacing buggy or outdated hardware on the fly. This work provides an architecture for an FPGA-based secure element that can be securely updated. The proposed mechanism uses a side-channel protected authenticated encryption with associated data (AEAD) engine for decryption and authentication of partial bitstreams, while the device unique key is generated from a Physical Unclonable Function (PUF). A proof-of-concept of the design is implemented on a Xilinx Zynq-7020 FPGA.

We give a four-round black-box construction of a commit-and-prove protocol with succinct communication. Our construction is WI and has constant soundness error, and it can be upgraded into a one that is ZK and has negligible soundness error by relying on a round-preserving transformation of Khurana et al. (TCC 2018). Our construction is obtained by combining the MPC-in-the-head technique of Ishai et al. (SICOMP 2009) with the two-round succinct argument of Kalai et al. (STOC 2014), and the main technical novelty lies in the analysis of the soundness---we show that, although the succinct argument of Kalai et al. does not necessarily provide soundness for NP statements, it can be used in the MPC-in-the-head technique for proving the consistency of committed MPC views. Our construction is based on sub-exponentially hard collision-resistant hash functions, two-round PIRs, and two-round OTs.

We study adaptive security of delayed-input Sigma protocols and non-interactive zero-knowledge (NIZK) proof systems in the common reference string (CRS) model. Our contributions are threefold:

- We exhibit a generic compiler taking any delayed-input Sigma protocol and returning a delayed-input Sigma protocol satisfying adaptive-input special honest-verifier zero-knowledge (SHVZK). In case the initial Sigma protocol also satisfies adaptive-input special soundness, our compiler preserves this property. - We revisit the recent paradigm by Canetti et al. (STOC 2019) for obtaining NIZK proof systems in the CRS model via the Fiat-Shamir transform applied to so-called trapdoor Sigma protocols, in the context of adaptive security. In particular, assuming correlation-intractable hash functions for all sparse relations, we prove that Fiat- Shamir NIZKs satisfy either: (i) Adaptive soundness (and non-adaptive zero-knowledge), so long as the challenge is obtained by hashing both the prover’s first round and the instance being proven; (ii) Adaptive zero-knowledge (and non-adaptive soundness), so long as the challenge is obtained by hashing only the prover’s first round, and further assuming that the initial trapdoor Sigma protocol satisfies adaptive-input SHVZK. - We exhibit a generic compiler taking any Sigma protocol and returning a trapdoor Sigma protocol. Unfortunately, this transform does not preserve the delayed-input property of the initial Sigma protocol (if any). To complement this result, we also give yet another compiler taking any delayed-input trapdoor Sigma protocol and returning a delayed-input trapdoor Sigma protocol with adaptive-input SHVZK.

An attractive feature of our first two compilers is that they allow obtaining efficient delayed-input Sigma protocols with adaptive security, and efficient Fiat-Shamir NIZKs with adaptive soundness (and non-adaptive zero-knowledge) in the CRS model. Prior to our work, the latter was only possible using generic NP reductions.

Terakey is an encryption system whose confidentiality can be demonstrated from first principles, without making assumptions about the computational difficulty of certain mathematical problems. It employs a key that is much larger than the anticipated volume of message traffic. It is based on the one-time pad, but addresses the risk of key reuse stochastically. Conventional cryptographic techniques can be used to ameliorate infrequent byte collisions. The large size of the key reduces the risk of key exfiltration and facilitates physical security measures to maintain a secure chain of control for the key. Terakey also serves as a potential alternative for comparison with quantum key distribution technology, arguably providing equivalent security with fewer complications.

The classical heuristic complexity of the Number Field Sieve (NFS) is the solution of an optimization problem that involves an unknown function, usually noted $o(1)$ and called $\xi(N)$ throughout this paper, which tends to zero as the entry $N$ grows. The aim of this paper is to find optimal asymptotic choices of the parameters of NFS as $N$ grows, in order to minimize its heuristic asymptotic computational cost. This amounts to minimizing a function of the parameters of NFS bound together by a non-linear constraint. We provide precise asymptotic estimates of the minimizers of this optimization problem, which yield refined formulas for the asymptotic complexity of NFS. One of the main outcomes of this analysis is that $\xi(N)$ has a very slow rate of convergence: We prove that it is equivalent to $4{\log}{\log}{\log}\,N/(3{\log}{\log}\,N)$. Moreover, $\xi(N)$ has an unpredictable behavior for practical estimates of the complexity. Indeed, we provide an asymptotic series expansion of $\xi$ and numerical experiments indicate that this series starts converging only for $N>\exp(\exp(25))$, far beyond the practical range of NFS. This raises doubts on the relevance of NFS running time estimates that are based on setting $\xi=0$ in the asymptotic formula.

In recent year’s security has become an important role in the field of Defense, Business, Medical and Industries.Different types of cryptography algorithms has been implemented in order to provide security with high performance. A hash function is a cryptography algorithm without a key such as MD5, SHA-family. Secure hash algorithm which is standardized by NIST as secured hashing in FIPS. In this paper we mainly focus on code optimization and increase the performance of SHA-512. To optimize and increase the performance of SHA-512 we have modified the algorithm and proposed Modified Secure hash algorithm(MSHA-512 ). It is a one-way hash function that can process a message to produce a condensed representation called a message digest.In this proposed algorithm within the limited rounds (40 rounds instead of 80 rounds) we can obtain exact result which is same as traditional SHA-512 algorithm. By using MSHA-512 algorithm we can reduce the time upto 50% for the same process, which increases the performance of the algorithm and helps to increase the flexibility of server in running streams. The MSHA-512 generates the same hash code as we generate in the SHA-512 for all different size of inputs. MSHA-512 is developed and designed to overcome the time complexity of SHA-512 and increase the performance of it by reducing the rounds.

Blockchain databases are storage systems that combine properties of blockchains and databases like decentralization, tamper-proofness, low query latency and support for complex queries. Blockchain databases are an emerging and important class of blockchain technology that is critical to the development of non-trivial smart contracts, distributed applications and decentralized marketplaces. In this work, we consider the problem of designing end-to-end encrypted blockchain databases to support the development of decentralized applications that need to store and query sensitive data. In particular, we show how to design what we call blockchain encrypted multi-maps (EMM) which can be used to instantiate various kinds of NoSQL blockchain databases like key-value stores or document databases. We propose three blockchain EMM constructions, each of which achieves different tradeoffs between query, add and delete efficiency. All of our constructions are legacy-friendly in the sense that they can be implemented on top of any existing blockchain. This is particularly challenging since blockchains do not support data deletion. We implemented our schemes on the Algorand blockchain and evaluated their concrete efficiency empirically. Our experiments show that they are practical.

Broadcast Encryption is a fundamental primitive supporting sending a secure message to any chosen target set of $N$ users. While many efficient constructions are known, understanding the efficiency possible for an ``Anonymous Broadcast Encryption'' (ANOBE), i.e., one which can hide the target set itself, is quite open. The best solutions by Barth, Boneh, and Waters ('06) and Libert, Paterson, and Quaglia ('12) are built on public key encryption (PKE) and their ciphertext sizes are, in fact, $N$ times that of the underlying PKE (rate=$N$). Kiayias and Samary ('12), in turn, showed a lower bound showing that such rate is the best possible if $N$ is an independent unbounded parameter. However, when considering certain user set size bounded by a system parameter (e.g., the security parameter), the problem remains interesting. We consider the problem of comparing ANOBE with PKE under the same assumption. We call such schemes Anonymous Broadcast Encryption for Bounded Universe -- AnoBEB.

We first present an AnoBEB construction for up to $k$ users from LWE assumption, where $k$ is bounded by the scheme security parameter. The scheme does not grow with the parameter and beat the PKE method. Actually, our scheme is as efficient as the underlying LWE public-key encryption; namely, the rate is, in fact, $1$ and thus optimal. The scheme is achieved easily by an observation about an earlier scheme with a different purpose.

More interestingly, we move on to employ the new AnoBEB in other multimedia broadcasting methods and, as a second contribution, we introduce a new approach to construct an efficient ``Trace and Revoke scheme'' which combines the functionalites of revocation and of tracing people (called traitors) who in a broadcasting schemes share their keys with the adversary which, in turn, generates a pirate receiver. Note that, as was put forth by Kiayias and Yung (EUROCRYPT '02), combinatorial traitor tracing schemes can be constructed by combining a system for small universe, integrated via an outer traceability codes (collusion-secure code or identifying parent property (IPP) code). There were many efficient traitor tracing schemes from traceability codes, but no known scheme supports revocation as well. Our new approach integrates our AnoBEB system with a Robust IPP code, introduced by Barg and Kabatiansky (IEEE IT '13). This shows an interesting use for robust IPP in cryptography. The robust IPP codes were only implicitly shown by an existence proof. In order to make our technique concrete, we propose two explicit instantiations of robust IPP codes. Our final construction gives the most efficient trace and revoke scheme in the bounded collusion model.