Completeness for Symmetric Two-Party Functionalities: Revisited

Understanding the minimal assumptions required for carrying out cryptographic tasks is one of the fundamental goals of theoretic cryptography. A rich body of work has been dedicated to understanding the complexity of cryptographic tasks in the context of (semi-honest) secure two-party computation. Much of this work has focused on the characterization of trivial and complete functionalities (resp., functionalities that can be securely implemented unconditionally, and functionalities that can be used to securely compute all functionalities). Most previous works define reductions via an ideal implementation of the functionality; i.e., f reduces to g if one can implement f using a black-box (or oracle) that computes the function g and returns the output to both parties. Such a reduction models the computation of f as an atomic operation. However, in the real world, protocols proceed in rounds, and the output is not learned by the parties simultaneously. In this paper, we show that this distinction is significant. Specifically, we show that there exist symmetric functionalities (where both parties receive the same outcome) that are neither trivial nor complete under “black-box reductions,” and yet the existence of a constant-round protocol for securely computing such a functionality implies infinitely often oblivious transfer (meaning that it is secure for infinitely many values of the security parameter). In light of the above, we propose an alternative definitional infrastructure for studying the triviality and completeness of functionalities.     

A survey of information authentication

The general principles that underlie all authentication schemes are reviewed and illustrated using the examples of an early telegraphy cable code, a US military authentication protocol, and authentication of electronic funds transfers in the US Federal Reserve System. Authentication threats from inside the system (i.e. untrustworthy sender or receiver) are described. The classification of authentication schemes as computationally secure, provably secure, or unconditionally secure is explained, and theoretical results are presented showing that a large number of encoding rules must be available in any unconditionally secure authentication code. Current authentication practices are examined     

Information Theoretic Bounds on Authentication Systems in Query Model

Authentication codes provide message integrity guarantees in an information theoretic sense within a symmetric key setting. Information theoretic bounds on the success probability of an adversary who has access to previously authenticated messages have been derived by Simmons and Rosenbaum, among others. In this paper, we consider a strong attack scenario where the adversary is adaptive and has access to authentication and verification oracles. We derive information theoretic bounds on the success probability of the adversary and on the key size of the code. This brings the study of unconditionally secure authentication systems on a par with the study of computationally secure ones. We characterize the codes that meet these bounds and compare our result with the earlier ones.     

Unconditionally Secure Steganography Against Active Attacks

In this paper, we study unconditionally secure stegosystems against active attacks over an insecure channel in which an adversary can read and write a message. More specifically, we propose an information-theoretic model for steganography in the presence of active adversaries by extending both Simmons' and Cachin's works; and we show a generic construction of stegosystems secure against active attacks by using authenticated encryption in unconditional setting. Although the idea behind this construction is already used in different models (i.e., computational models and/or information-theoretic models with passive adversaries) of steganography, our contribution lies in showing the construction methodology provides provable and unconditional security against active adversaries.     

Almost security of cryptographic Boolean functions

The propagation criterion, PC(/spl lscr/) of order k, is one of the most general cryptographic criteria of secure Boolean functions f. In this paper, we formalize its /spl epsiv/-almost version. The new definition requires that f(X)+f(X+/spl Delta/) is almost uniformly distributed while in the original definition, it must be strictly uniformly distributed. Better parameters are then obtained than the strict PC(/spl lscr/) of order k functions. To construct /spl epsiv/-almost PC(/spl lscr/) of order k functions, we introduce a notion of domain distance.     

姚氏百万富翁问题的高效解决方案

姚氏百万富翁问题解决方案已经成为许多多方保密计算问题解决方案的一个基本模块,但现有的解决方案效率低下,因而影响到其他多方保密计算方案的效率.本文利用长度函数与不经意传输设计了一个高效的解决方案,新方案同原有方案相比,计算复杂性明显降低.     

Byzantine Agreement Given Partial Broadcast

This paper considers unconditionally secure protocols for reliable broadcast among a set of n players, where up to t of the players can be corrupted by a (Byzantine) adversary but the remaining h = n - t players remain honest. In the standard model with a complete, synchronous network of bilateral authenticated communication channels among the players, broadcast is achievable if and only if 2n/h < 3. We show that, by extending this model by the existence of partial broadcast channels among subsets of b players, global broadcast can be achieved if and only if the number h of honest players satisfies 2n/h < b + 1. Achievability is demonstrated by protocols with communication and computation complexities polynomial in the size of the network, i.e., in the number of partial broadcast channels. A respective characterization for the related consensus problem is also given.     

PUF‐based solutions for secure communications in Advanced Metering Infrastructure (AMI)

Advanced metering infrastructure (AMI) provides 2‐way communications between the utility and the smart meters. Developing authenticated key exchange (AKE) and broadcast authentication (BA) protocols is essential to provide secure communications in AMI. The security of all existing cryptographic protocols is based on the assumption that secret information is stored in the nonvolatile memories. In the AMI, the attackers can obtain some or all of the stored secret information from memories by a great variety of inexpensive and fast side‐channel attacks. Thus, all existing AKE and BA protocols are no longer secure. In this paper, we investigate how to develop secure AKE and BA protocols in the presence of memory attacks. As a solution, we propose to embed a physical unclonable function (PUF) in each party, which generates the secret values as required without the need to store them. By combining PUFs and 2 well‐known and secure protocols, we propose PUF‐based AKE and BA protocols. We show that our proposed protocols are memory leakage resilient. In addition, we prove their security in the standard model. Performance analysis of both protocols shows their efficiency for AMI applications. The proposed protocols can be easily implemented.     

The combinatorics of authentication and secrecy codes

This paper is a study of the combinatorics of unconditionally secure secrecy and authentication codes, under the assumption that each encoding rule is to be used for the transmission of some numberL of successive messages. We obtain bounds on the number of encoding rules required in order to obtain maximum levels of security. Some constructions are also given for codes which have the minimum number of encoding rules. These constructions use various types of combinatorial designs.     

Fairness Versus Guaranteed Output Delivery in Secure Multiparty Computation

In the setting of secure multiparty computation, a set of parties wish to compute a joint function of their private inputs. The computation should preserve security properties such as privacy, correctness, independence of inputs, fairness and guaranteed output delivery. In the case of no honest majority, fairness and guaranteed output delivery cannot always be obtained. Thus, protocols for secure multiparty computation are typically of two disparate types: protocols that assume an honest majority (and achieve all properties including fairness and guaranteed output delivery) and protocols that do not assume an honest majority (and achieve all properties except for fairness and guaranteed output delivery). In addition, in the two-party case, fairness and guaranteed output delivery are equivalent. As a result, the properties of fairness (which means that if corrupted parties receive output then so do the honest parties) and guaranteed output delivery (which means that corrupted parties cannot prevent the honest parties from receiving output in any case) have typically been considered to be the same. In this paper, we initiate a study of the relation between fairness and guaranteed output delivery in secure multiparty computation. We show that in the multiparty setting these properties are distinct and proceed to study under what conditions fairness implies guaranteed output delivery (the opposite direction always holds). We also show the existence of non-trivial functions for which complete fairness is achievable (without an honest majority) but guaranteed output delivery is not, and the existence of non-trivial functions for which complete fairness and guaranteed output delivery are achievable. Our study sheds light on the role of broadcast in fairness and guaranteed output delivery and shows that these properties should sometimes be considered separately.     

多重集的保密计算及应用

安全多方计算是近年来国际密码学界研究的热点问题.多重集作为标准集的推广在实际中有广泛的应用,对于多重集的保密计算问题研究具有重要的意义.本文主要研究两方多重集的交集、并集以及基于阈值和集的保密计算问题.首先针对不同问题设计相应的编码方法,结合Paillier加密方案设计保密计算协议,并应用模拟范例方法严格证明协议的安全性.效率分析和实验验证表明本文所设计的协议是简单高效的.     

Key management approaches to offer data confidentiality for secure multicast

Multicasting is an efficient way to deliver data to a large group of users in applications such as Internet stock quotes, audio and music delivery, file and video distribution, etc. Many of these applications require the security feature of data confidentiality, which is not readily offered by the "open" nature of multicast. In order to offer such confidentiality, the encryption and decryption keys must be constantly changed upon a membership change. In this article, after discussing some performance criteria to offer secure multicast, we present a number of the proposed key management schemes for data confidentiality. We categorize these schemes into four groups: key tree-based approaches, contributory key agreement schemes supported by the Diffie-Hellman algorithm, computational number theoretic approaches, and secure multicast framework approaches. Through examples, we describe the operation of the schemes and compare their performances.     

量子密钥分配协议的Petri网建模及安全性分析

量子密钥分配协议已经被证明具有无条件安全特性,但是证明过程比较复杂,不利于推广到其他量子密码协议的安全性分析和证明中.为了简化量子密码协议的安全性证明以及建立一种通用的证明方法,基于Petri网提出一种量子密钥分配协议的形式化分析方法,根据Biham的等效对称化攻击模型,将协议分为主体模型和攻击模型两部分,建立了BB84协议的Petn网模型,然后对模型进行安全性分析,分析结果表明, BB84协议是无条件安全的.该方法提高了安全性分析效率,形式上简洁统一,容易推广到其他量子密码协议的安全性分析中.     

Some Equivalences between Kernel Methods and Information Theoretic Methods

In this paper, we discuss some equivalences between two recently introduced statistical learning schemes, namely Mercer kernel methods and information theoretic methods. We show that Parzen window-based estimators for some information theoretic cost functions are also cost functions in a corresponding Mercer kernel space. The Mercer kernel is directly related to the Parzen window. Furthermore, we analyze a classification rule based on an information theoretic criterion, and show that this corresponds to a linear classifier in the kernel space. By introducing a weighted Parzen window density estimator, we also formulate the support vector machine in this information theoretic perspective.

---

     

无条件安全的可验证密钥共享系统

讨论了门限方案的抗欺骗功能，研究了基于最大距离可分码的门限方案的抗欺骗功能；基于无条件安全认证码构造了无条件安全的可防止欺骗的密钥共享方案，并讨论了该方案的特性。     

一种轻量级隐私保护的RFID群组证明协议

设计高效安全的群组证明协议有利于RFID(Radio Frequency Identification)系统的广泛应用.本文提出了一种轻量级隐私保护的RFID群组证明协议LPGP(Lightweight Privacy-Preserving Grouping Proof),LPGP协议只使用计算复杂度比较小的伪随机发生器和散列运算来提高协议的运行效率,并且LPGP协议具有认证性、隐私性和可证明安全性,满足了RFID系统群组证明协议的安全性要求.与现有的群组证明协议相比,LPGP协议的标签只需较小的计算复杂度和存储空间,具有较高的效率.     

基于平滑熵的防主动攻击的无条件安全秘密钥的提取

本文研究通信双方基于平滑熵在不安全且非认证的公共信道上实现防主动攻击的无条件安全秘密钥的提取.首先讨论了在不安全且非认证的公共信道上根据部分保密的密钥实现认证的方法,然后根据以上方法以抗击敌手在通信双方进行无条件安全秘密钥提取时的主动攻击,得出了通信双方以一定概率所协商的秘密钥长度.     

More Efficient Oblivious Transfer Extensions

Oblivious transfer (OT) is one of the most fundamental primitives in cryptography and is widely used in protocols for secure two-party and multi-party computation. As secure computation becomes more practical, the need for practical large-scale OT protocols is becoming more evident. OT extensions are protocols that enable a relatively small number of “base-OTs” to be utilized to compute a very large number of OTs at low cost. In the semi-honest setting, Ishai et al. (Advances in cryptology—CRYPTO’03, vol 2729 of LNCS, Springer, 2003) presented an OT extension protocol for which the cost of each OT (beyond the base-OTs) is just a few hash function operations. In the malicious setting, Nielsen et al. (Advances in cryptology—CRYPTO’12, vol 7417 of LNCS, Springer, 2012) presented an efficient OT extension protocol for the setting of malicious adversaries that is secure in a random oracle model. In this work, we improve OT extensions with respect to communication complexity, computation complexity, and scalability in the semi-honest, covert, and malicious model. Furthermore, we show how to modify our maliciously secure OT extension protocol to achieve security with respect to a version of correlation robustness instead of the random oracle. We also provide specific optimizations of OT extensions that are tailored to the use of OT in various secure computation protocols such as Yao’s garbled circuits and the protocol of Goldreich–Micali–Wigderson, which reduce the communication complexity even further. We experimentally verify the efficiency gains of our protocols and optimizations.     

A blind source separation based method for speech encryption

The underdetermined problem poses a significant challenge in blind source separation (BSS) where the number of the source signals is greater than that of the mixed signals. Motivated by the fact that the security of many cryptosystems relies on the apparent intractability of the computational problems such as the integer factorization problem, we exploit the intractability of the underdetermined BSS problem to present a novel BSS-based speech encryption by properly constructing the underdetermined mixing matrix for encryption, and by generating the key signals that satisfy the necessary condition for the proposed method to be unconditionally secure. Both extensive computer simulations and performance analyses results show that the proposed method has high level of security while retaining excellent audio quality.     

Efficient Protocols for the General Millionaires' Problem

Secure multiparty computation (SMC) is a research focusing in the international cryptographic com-munity. The protocols used to address the millionaires' problem are the basic building blocks of most SMC proto-cols and their efficiency dominates that of many other SMC protocols. To the best of our knowledge, almost all proto-cols used to address the millionaires' problem are based on integers, which means that their applications are lim-ited. In this study, we propose precise and efficient proto-cols for rational numbers based on additively homomorphic encryptions. One of our protocols is inspired by computa-tional geometry and it reduces the millionaires' problem to computing the area of a triangle formed by three private points. This approach can determine whether the relation-ship between two private inputs is greater than, equal to or less than, and it has a much lower computational complex-ity compared with existing methods. We proved that these protocols are secure using simulation paradigm. Our ap-proaches can be used in many SMC protocols that involve rational numbers and integers, and they can also be used directly to solve some secure multiparty computational ge-ometry problem in rational number field.