Quantum protocols for untrusted computations

In this paper, we propose new quantum arithmetic protocols among multiple parties. Let some parties have values. A problem is to find a protocol such that under the condition that any eavesdropper intercepting any quantum system being exchanged among the parties must not be able to acquire information, the parties compute an arithmetic operation such as addition and multiplication, and transfer its computing result to another party. One of main ideas to solve this problem is based on operating state phases. A quantum addition algorithm based on operating phases has been proposed by Draper, but his algorithm was not considered being eavesdropped. We propose secure quantum arithmetic protocols.     

An efficient and secure Diffie–Hellman key agreement protocol based on Chebyshev chaotic map

This paper proposes a new efficient and secure Diffie–Hellman key agreement protocol based on Chebyshev chaotic map. The proposed key agreement protocol uses the semi-group property of Chebyshev polynomials to agree Diffie–Hellman based session key. The proposed protocol provides strong security compared with the previous related protocols. In addition, the proposed protocol does not require any timestamp information and greatly reduces computational costs between communication parties. As a result, the proposed protocol is more practical and provides computational/communicational efficiency compare with several previously proposed key agreement protocols based on Chebyshev chaotic map.     

Chaotic map based key agreement with/out clock synchronization

In order to address Bergamo et al.’s attack, Xiao et al. proposed a key agreement protocol using chaotic maps. Han then presented three attacks on Xiao et al.’s protocol. To enhance the security of key agreement based on chaotic maps, Chang et al. proposed a new key agreement using passphrase, which works in clock synchronization environment. However, their protocol still has some issues: one is its passphrase is not easy to remember and much longer than password; the second one is it cannot resist guessing attack if the constructed passphrase is easy to remember and also has already existed in some rational dictionaries; the third one is it cannot work without clock synchronization. In this paper, we will present two different key agreement protocols, which can resist guessing attack. The first one works in clock synchronization environment. The second one can work without clock synchronization. They both use authenticated password for secure communications. The protocols are secure against replaying attacks and a shared session key can be established.     

An improved key agreement protocol based on chaos

Cryptography based on chaos theory has developed fast in the past few years, but most of the researches focus on secret key cryptography. There are few public key encryption algorithms and cryptographic protocols based on chaos, which are also of great importance for network security. We introduce an enhanced key agreement protocol based on Chebyshev chaotic map. Utilizing the semi-group property of Chebyshev polynomials, the proposed key exchange algorithm works like Diffie–Hellman algorithm. The improved protocol overcomes the drawbacks of several previously proposed chaotic key agreement protocols. Both analytical and experimental results show that it is effective and secure.     

Strengthening the security of authenticated key exchange against bad randomness

Recent history has revealed that many random number generators (RNGs) used in cryptographic algorithms and protocols were not providing appropriate randomness, either by accident or on purpose. Subsequently, researchers have proposed new algorithms and protocols that are less dependent on the RNG. One exception is that all prominent authenticated key exchange (AKE) protocols are insecure given bad randomness, even when using good long-term keying material. We analyse the security of AKE protocols in the presence of adversaries that can perform attacks based on chosen randomness, i.e., attacks in which the adversary controls the randomness used in protocol sessions. We propose novel stateful protocols, which modify memory shared among a user’s sessions, and show in what sense they are secure against this worst case randomness failure. We develop a stronger security notion for AKE protocols that captures the security that we can achieve under such failures, and prove that our main protocol is correct in this model. Our protocols make substantially weaker assumptions on the RNG than existing protocols.     

Multi-party computation with conversion of secret sharing

Classical results in unconditionally secure multi-party computation (MPC) protocols with a passive adversary indicate that every n-variate function can be computed by n participants, such that no set of size t < n/2 participants learns any additional information other than what they could derive from their private inputs and the output of the protocol. We study unconditionally secure MPC protocols in the presence of a passive adversary in the trusted setup (‘semi-ideal’) model, in which the participants are supplied with some auxiliary information (which is random and independent from the participant inputs) ahead of the protocol execution (such information can be purchased as a “commodity” well before a run of the protocol). We present a new MPC protocol in the trusted setup model, which allows the adversary to corrupt an arbitrary number t < n of participants. Our protocol makes use of a novel subprotocol for converting an additive secret sharing over a field to a multiplicative secret sharing, and can be used to securely evaluate any n-variate polynomial G over a field F, with inputs restricted to non-zero elements of F. The communication complexity of our protocol is O(ℓ · n ²) field elements, where ℓ is the number of non-linear monomials in G. Previous protocols in the trusted setup model require communication proportional to the number of multiplications in an arithmetic circuit for G; thus, our protocol may offer savings over previous protocols for functions with a small number of monomials but a large number of multiplications.     

Secure multi-party computation made simple

Known secure multi-party computation protocols are quite complex, involving non-trivial mathematical structures and sub-protocols. The purpose of this paper is to present a very simple approach to secure multi-party computation with straight-forward security proofs. This approach naturally yields protocols secure for mixed (active and passive) corruption and general (as opposed to threshold) adversary structures, confirming the previously proved tight bounds in a simpler framework. Due to their simplicity, the described protocols are well-suited for didactic purposes, which is a main goal of this paper.     

Speeding up Exponentiation using an Untrusted Computational Resource

We present protocols for speeding up fixed-base variable-exponent exponentiation and variable-base fixed-exponent exponentiation using an untrusted computational resource. In the fixed-base protocols, the exponent may be blinded. In the variable-base protocols, the base may be blinded. The protocols are described for exponentiation in a cyclic group. We describe how to extend them to exponentiation modulo an integer where the modulus is the product of primes with single multiplicity. The protocols provide a speedup of over the square-and-multiply algorithm, where k is the bitlength of the exponent. One application of the protocols is to speed up exponentiation-based verification in discrete log-based signature and credential schemes. The protocols also allow signature verifiers to dynamically choose, for each message, the amount of work it would like to perform to verify the signature. This results in a work-security tradeoff. We introduce a fifth protocol to perform variable-base variable- exponent exponentiation, which also has this feature. Our model allows the trusted resource to perform computations in its idle time. The protocols facilitate the offloading of work to the offline stage, such that the work the trusted resource performs when it has to do an exponentiation is smaller. Our protocols are unconditionally secure.     

On the security of p-party protocols

Characterizations of secure multi-party symmetric and nonsymmetric cascade protocols are given. A simple correspondence problem over an alphabet is shown linearly reducible to the security problem of symmetric name-stamp protocols. Also, the security problem of nonsymmetric protocols is shown linearly reducible to that of symmetric protocols.     

On the convergence of population protocols when population goes to infinity

Population protocols have been introduced as a model of sensor networks consisting of very limited mobile agents with no control over their own movement. A population protocol corresponds to a collection of anonymous agents, modeled by finite automata, that interact with one another to carry out computations, by updating their states, using some rules.Their computational power has been investigated under several hypotheses but always when restricted to finite size populations. In particular, predicates stably computable in the original model have been characterized as those definable in Presburger arithmetic.We study mathematically the convergence of population protocols when the size of the population goes to infinity. We do so by giving general results, that we illustrate through the example of a particular population protocol for which we even obtain an asymptotic development.This example shows in particular that these protocols seem to have a rather different computational power when a huge population hypothesis is considered.     

Practical unconditionally secure two-channel message authentication

We investigate unconditional security for message authentication protocols that are designed using two-channel cryptography. (Two-channel cryptography employs a broadband, insecure wireless channel and an authenticated, narrow-band manual channel at the same time.) We study both noninteractive message authentication protocols (NIMAPs) and interactive message authentication protocols (IMAPs) in this setting. First, we provide a new proof of nonexistence of nontrivial unconditionally secure NIMAPs. This proof consists of a combinatorial counting argument and is much shorter than the previous proof by Wang and Safavi-Naini, which was based on probability distribution arguments. We also prove a new result which holds in a weakened attack model. Further, we propose a generalization of an unconditionally secure 3-round IMAP due to Naor, Segev and Smith. The IMAP is based on two ?-Δ universal hash families. With a careful choice of parameters, our scheme improves that of Naor et al. Our scheme is very close to optimal for most parameter situations of practical interest. Finally, a variation of the 3-round IMAP is presented, in which only one hash family is required.     

Chaotic maps-based password-authenticated key agreement using smart cards

Password-based authenticated key agreement using smart cards has been widely and intensively researched. Inspired by the semi-group property of Chebyshev maps and key agreement protocols based on chaotic maps, we proposed a novel chaotic maps-based password-authenticated key agreement protocol with smart cards. In our protocol, we avoid modular exponential computing or scalar multiplication on elliptic curve used in traditional authenticated key agreement protocols using smart cards. Our analysis shows that our protocol has comprehensive characteristics and can withstand attacks, including the insider attack, replay attack, and others, satisfying essential security requirements. Performance analysis shows that our protocol can refrain from consuming modular exponential computing and scalar multiplication on an elliptic curve. The computational cost of our protocol compared with related protocols is acceptable.     

Secure collaborative supply chain planning and inverse optimization – The JELS model

It is a well-acknowledged fact that collaboration between different members of a supply chain yields a significant potential to increase overall supply chain performance. Sharing private information has been identified as prerequisite for collaboration and, at the same time, as one of its major obstacles. One potential avenue for overcoming this obstacle is Secure Multi-Party Computation (SMC). SMC is a cryptographic technique that enables the computation of any (well-defined) mathematical function by a number of parties without any party having to disclose its input to another party. In this paper, we show how SMC can be successfully employed to enable joint decision-making and benefit sharing in a simple supply chain setting. We develop secure protocols for implementing the well-known “Joint Economic Lot Size (JELS) Model” with benefit sharing in such a way that none of the parties involved has to disclose any private (cost and capacity) data. Thereupon, we show that although computation of the model’s outputs can be performed securely, the approach still faces practical limitations. These limitations are caused by the potential of “inverse optimization”, i.e., a party can infer another party’s private data from the output of a collaborative planning scheme even if the computation is performed in a secure fashion. We provide a detailed analysis of “inverse optimization” potentials and introduce the notion of “stochastic security”, a novel approach to assess the additional information a party may learn from joint computation and benefit sharing. Based on our definition of “stochastic security” we propose a stochastic benefit sharing rule, develop a secure protocol for this benefit sharing rule, and assess under which conditions stochastic benefit sharing can guarantee secure collaboration.     

A Formal Language for Cryptographic Protocol Requirements

In this paper we present a formal language for specifying and reasoning about cryptographic protocol requirements. We give sets of requirements for key distribution protocols and for key agreement protocols in that language. We look at a key agreement protocol due to Aziz and Diffie that might meet those requirements and show how to specify it in the language of the NRL Protocol Analyzer. We also show how to map our formal requirements to the language of the NRL Protocol Analyzer and use the Analyzer to show that the protocol meets those requirements. In other words, we use the Analyzer to assess the validity of the formulae that make up the requirements in models of the protocol. Our analysis reveals an implicit assumption about implementations of the protocol and reveals subtleties in the kinds of requirements one might specify for similar protocols.     

A note on the strong authenticated key exchange with auxiliary inputs

Recently, Chen et al. proposed a framework for authenticated key exchange (AKE) protocols (referred to as CMYSG scheme) in Designs, Codes and Cryptography (available at http://link.springer.com/article/10.1007/s10623-016-0295-3). It is claimed that the proposed AKE protocol is secure in a new leakage-resilient eCK model w.r.t. auxiliary inputs (AI-LR-eCK). The main tool used for the generic construction is the smooth projective hash function (SPHF). In this note, we revisit the CMYSG scheme and point out a subtle flaw in the original security proof. Precisely, we show that the AI-LR-eCK security of the proposed construction cannot be successfully reduced to a pseudo-random SPHF and thus the CMYSG scheme is not secure as claimed. To restore the security proof, we replace the underlying typical SPHF with a 2-smooth SPHF, and show that such a replacement combined with a \(\pi \hbox {PRF}\) suffices to overcome the subtle flaw.     

数据伪装技术支撑的安全多方计算研究

对于多方安全计算目前国内外已有许多研究成果,从安全方面去看很多解法是尽善尽美,但在实际的运行中却不尽人意.为了开发实用的安全多方计算解法,研究了支撑可调节安全等级的安全多方计算的多种数据伪装技术.包括线性变换伪装、(Z+V)伪装和多项式函数伪装.设计了各种数据伪装的详细协议,并对其安全性与复杂性进行了分析.最终得出各种数据伪装技术是可以在有效性和安全性之间进行调节的,即用户可在性能和安全性之间权衡两者的轻重程度,然后作出抉择,选择适合于实际情况的安全级别.     

Secure communications with strange planet protocol

This paper investigates the strange planet problem for the purpose of secure communication. To this end, the problem is modeled with automata, and the essential principle under the transitions is discovered. Based on it, the sound conditions for secure communications with the strange planet problem are given. Finally, a small application of strange planet protocol is presented.     

保护私有信息的一般线性方程组计算协议

作为科学计算的一个重要问题,保护私有信息的线性方程组的求解在金融、机械及通信等领域有着广泛的应用.在不经意传输的意义下,利用有限域上计算Moore-Penrose伪逆矩阵的概率算法,设计新的安全协议,解决了隐私保护的一般线性方程组在有限域上的安全两方计算问题,并利用模拟范例证明该协议在半诚实模型下是安全的.     

Satisfiability and completeness of protocols for electronic negotiations

Many of the existing e-negotiation support systems are built around one negotiation protocol. This effectively restricts their use to those problems and interactions that had been assumed a priori by the systems’ designers. Field and experimental studies show that the way the negotiation process is structured depends on the negotiators’ characteristics, the problem and the context in which an agreement is sought. It has also been recognized in literature that both the way a problem is represented and the solution process implemented strongly influence the results at which individual decision-makers and negotiators arrive. Building on the e-negotiation Montreal taxonomy this article proposes a more complete typology of protocols and their characteristics. It also presents the elements of a theory for the design of negotiation protocols. The proposed protocol formalism allows for the construction of models from which users can select a protocol instance that suits them and/or is appropriate for the problem at-hand. Furthermore, this formalism allows for the construction of protocols that can be modified during the user–system interactions. The paper also presents two key requirements for negotiation protocols embedded in support systems, namely their satisfiability and completeness.     

An anonymous key agreement protocol based on chaotic maps

Recently, Tseng et al. proposed a novel key agreement protocol based on chaotic maps. They claimed that the protocol achieved session key agreement between a server and a user, and allowed the user to anonymously interact with the server. This paper, however, will demonstrate that Tseng et al.’s protocol can not guarantee user anonymity and protocol security against an insider adversary who is a legal user, and it can not provide perfect forward secrecy. Furthermore, the current paper presents a new key agreement protocol based on Chebyshev chaotic map in order to conquer these problems. In contrast with Tseng et al.’s protocol, the proposed protocol is more secure and preserves user anonymity.