Skip to main content
main-content

Über dieses Buch

This book constitutes the proceedings of the 7th International Conference on Information Theoretic Security, ICITS 2013, held in Singapore in November 2013. The 14 papers presented in this volume were carefully reviewed and selected from 49 submissions. Topics of interest are: unconditional security, quantum cryptography, authentication codes, wiretap channels, randomness extraction, codes and cryptography, lattices and cryptography, secret sharing, multiparty Computation, bounded storage model, oblivious transfer, nonlocality and nonsignaling, quantum information theory, network coding security, physical models and assumptions, physical layer security.

Inhaltsverzeichnis

Frontmatter

How to Construct Strongly Secure Network Coding Scheme

We say that a network coding scheme is

strongly

$$1$$

1

-secure if a source node

$$s$$

s

can multicast

$$n$$

n

field elements

$$\{m_1, \cdots , m_n\}$$

{

m

1

,

,

m

n

}

to a set of sink nodes

$$\{t_1, \cdots , t_q\}$$

{

t

1

,

,

t

q

}

in such a way that any single edge leaks no information on any

$$S \subset \{m_1, \cdots , m_n\}$$

S

{

m

1

,

,

m

n

}

with

$$|S|=n-1$$

|

S

|

=

n

-

1

, where

$$n=\min _{t_i}$$

n

=

min

t

i

max-flow

$$(s,t_i)$$

(

s

,

t

i

)

is the maximum transmission capacity. We also say that a

strongly

$$h$$

h

-secure network coding scheme is

strongly

$$(h+1)$$

(

h

+

1

)

-secure if any

$$h+1$$

h

+

1

edges leak no information on any

$$S \subset \{m_1, \cdots , m_n\}$$

S

{

m

1

,

,

m

n

}

with

$$|S|=n-(h+1)$$

|

S

|

=

n

-

(

h

+

1

)

.

In this paper, we show the first explicit algorithm which can construct

strongly

$$k$$

k

-secure network coding schemes. In particular, it runs in polynomial time for fixed

$$k$$

k

.

Kaoru Kurosawa, Hiroyuki Ohta, Kenji Kakuta

Secure Two-Party Computation: A Visual Way

In this paper we propose a novel method for performing secure two-party computation. By merging together in a suitable way two beautiful ideas of the 80’s and the 90’s, Yao’s garbled circuit construction and Naor and Shamir’s visual cryptography, respectively, we enable Alice and Bob to securely evaluate a function

$$f(\cdot ,\cdot )$$

f

(

·

,

·

)

of their inputs,

$$x$$

x

and

$$y$$

y

, through a

pure physical

process. Indeed, once Alice has prepared a set of properly constructed transparencies, Bob computes the function value

$$f(x,y)$$

f

(

x

,

y

)

by applying a sequence of simple steps which require the use of a pair of scissors, superposing transparencies, and the human visual system. A crypto-device for the function evaluation process is not needed any more.

Paolo D’Arco, Roberto De Prisco

Measure-Independent Characterization of Contrast Optimal Visual Cryptography Schemes

The

contrast

in visual cryptography has received a lot of attention. It has been studied using three different measures. In this paper we follow a

measure-independent

approach, which, by using the structural properties of the schemes, enables us to provide a characterization of optimal schemes that is independent of the specific measure used to assess the contrast. In particular we characterize and provide constructions of optimal schemes for the cases of

$$(2,n)$$

(

2

,

n

)

-threshold and

$$(n,n)$$

(

n

,

n

)

-threshold schemes. Then, we apply the measure-independent results to the three measures that have been used in the literature obtaining both new characterizations and constructions of optimal schemes and alternative proofs of known results.

Paolo D’Arco, Roberto De Prisco, Alfredo De Santis

On $$(k, n)$$ ( k , n ) Visual Cryptography Scheme with $$t$$ t Essential Parties

In visual cryptography schemes (VCS), we often denote the set of all parties by

$$P=\{1,2,\cdots ,n\}$$

P

=

{

1

,

2

,

,

n

}

. Arumugam et al. proposed a

$$(k,n)$$

(

k

,

n

)

-VCS with one essential party recently, in which only subset

$$S$$

S

of parties satisfying

$$S\subseteq P$$

S

P

and

$$|S|\ge k$$

|

S

|

k

and

$$1\in S$$

1

S

can recover the secret. In this paper, we extend Arumugam et al.’s idea and propose a

$$(k,n)$$

(

k

,

n

)

-VCS with

$$t$$

t

essential parties, say

$$(k,n,t)$$

(

k

,

n

,

t

)

-VCS for brevity, in which only subset

$$S$$

S

of parties satisfying

$$S\subseteq P$$

S

P

and

$$|S|\ge k$$

|

S

|

k

and

$$\{1,2,\ldots ,t\}\in S$$

{

1

,

2

,

,

t

}

S

can recover the secret. Furthermore, some bounds for the

optimal pixel expansion

and

optimal relative contrast

of

$$(k,n,t)$$

(

k

,

n

,

t

)

-VCS are derived.

Teng Guo, Feng Liu, ChuanKun Wu, YaWei Ren, Wen Wang

New Lower Bounds for Privacy in Communication Protocols

Communication complexity is a central model of computation introduced by Yao [

22

], where two players, Alice and Bob, receive inputs

$$x$$

and

$$y$$

respectively and want to compute

$$f(x,y)$$

for some fixed function

$$f$$

with the least amount of communication. Recently people have revisited the question of the privacy of such protocols: is it possible for Alice and Bob to compute

$$f(x,y)$$

without revealing too much information about their inputs? There are two types of privacy for communication protocols that have been proposed: first, an information theoretic definition ([

9

,

15

]), which for Boolean functions is equivalent to the notion of information cost introduced by [

12

] and that has since found many important applications; second, a combinatorial definition introduced by [

13

] and further developed by [

1

].

We provide new results for both notions of privacy, as well as the relation between them. Our new lower bound techniques both for the combinatorial and the information-theoretic definitions enable us to give tight bounds for the privacy of several functions, including Equality, Disjointness, Inner Product, Greater Than. In the process we also prove tight bounds (up to 1 or 2 additive bits) for the external information complexity of these functions.

We also extend the definitions of privacy to bounded-error randomized protocols and provide a relation between the two notions and the communication complexity. Again, we are able to prove tight bounds for the above-mentioned functions as well as the Vector in Subspace and Gap Hamming Distance problems.

Iordanis Kerenidis, Mathieu Laurière, David Xiao

On the Transmit Beamforming for MIMO Wiretap Channels: Large-System Analysis

With the growth of wireless networks, security has become a fundamental issue in wireless communications due to the broadcast nature of these networks. In this work, we consider MIMO wiretap channels in a fast fading environment, for which the overall performance is characterized by the ergodic MIMO secrecy rate. Unfortunately, the direct solution to finding ergodic secrecy rates is prohibitive due to the expectations in the rates expressions in this setting. To overcome this difficulty, we invoke the large-system assumption, which allows a deterministic approximation to the ergodic mutual information. Leveraging results from random matrix theory, we are able to characterize the achievable ergodic secrecy rates. Based on this characterization, we address the problem of covariance optimization at the transmitter. Our numerical results demonstrate a good match between the large-system approximation and the actual simulated secrecy rates, as well as some interesting features of the precoder optimization.

Maksym A. Girnyk, Frédéric Gabry, Mikko Vehkaperä, Lars K. Rasmussen, Mikael Skoglund

Information Theoretic Security for Encryption Based on Conditional Rényi Entropies

In this paper, information theoretic cryptography is discussed based on conditional Rényi entropies. Our discussion focuses not only on cryptography but also on the definitions of conditional Rényi entropies and the related information theoretic inequalities. First, we revisit conditional Rényi entropies, and clarify what kind of properties are required and actually satisfied. Then, we propose security criteria based on Rényi entropies, which suggests us deep relations between (conditional) Rényi entropies and error probabilities by using several guessing strategies. Based on these results, unified proof of impossibility, namely, the lower bounds on key sizes are derived based on conditional Rényi entropies. Our model and lower bounds include the Shannon’s perfect secrecy, and the min-entropy based encryption presented by Dodis, and Alimomeni and Safavi-Naini at ICITS2012. Finally, a new optimal symmetric key encryption protocol achieving the lower bounds is proposed.

Mitsugu Iwamoto, Junji Shikata

Insider-Proof Encryption with Applications for Quantum Key Distribution

We introduce insider-proof private channels which are private channels that additionally allow for security even when the key is correlated with the message. This prevents an insider, who has access to secret keys and the capability of choosing messages to be sent on the channel, from signalling to someone who can read the ciphertexts. We give a construction for approximately insider-proof private channels using 2-universal hash functions.

Quantum key distribution (QKD) offers the promise of information-theoretically secure communication, provided a number of assumptions are met. Ideally, the number of these assumptions required in a protocol should be reduced to a minimum. This is the motivation behind device independent QKD (DIQKD) protocols which use an adversarial model for the quantum devices. However, a previous report [

3

] pointed out that current protocols for DIQKD can leak key to an outside adversary when devices are used repeatedly. We show how to use the insider-proof private channel to allow DIQKD protocols to reuse devices any desired number of times without leaking information.

Matthew McKague, Lana Sheridan

Superposition Attacks on Cryptographic Protocols

Attacks on cryptographic protocols are usually modeled by allowing an adversary to ask queries to an oracle. Security is then defined by requiring that as long as the queries satisfy some constraint, there is some problem the adversary cannot solve, such as compute a certain piece of information. Even if the protocol is quantum, the queries are typically classical. In this paper, we introduce a new model of quantum attacks on protocols, where the adversary is allowed quantum access to the primitive, i.e., he may ask several classical queries in quantum superposition. This is a strictly stronger attack than the standard one, and we consider the security of several primitives in this model. We show that a secret-sharing scheme that is secure with threshold

$$t$$

t

in the standard model is secure against superposition attacks if and only if the threshold is lowered to

$$t/2$$

t

/

2

. This holds for all classical as well as all known quantum secret sharing schemes. We then consider zero- knowledge and first show that known protocols are not, in general, secure in our model by designing a superposition attack on the well-known zero-knowledge protocol for graph isomorphism. We then use our secret-sharing result to design zero-knowledge proofs for all of NP in the common reference string model. While our protocol is classical, it is sound against a cheating unbounded quantum prover and computational zero-knowledge even if the verifier is allowed a superposition attack. Finally, we consider multiparty computation and give a characterization of a class of protocols that can be shown secure, though not necessarily with efficient simulation. We show that this class contains non-trivial protocols that cannot be shown secure by running a classical simulator in superposition.

Ivan Damgård, Jakob Funder, Jesper Buus Nielsen, Louis Salvail

Overcoming Weak Expectations via the R $$\acute{e}$$ e ´ nyi Entropy and the Expanded Computational Entropy

In the ideal world, cryptographic models take for granted that the secret sources (e.g. secret keys and other secret randomness) are derived from uniform distribution. However, in reality, we may only obtain some ‘weak’ random sources guaranteed with high unpredictability (e.g. biometric data, physical sources, and secrets with partial leakage). Formally, the security of cryptographic models is measured by the expectation of some function, called ‘perfect’ expectation in the ideal model and ‘weak’ expectation in the real model respectively. We propose some elementary inequalities which show that the ‘weak’ expectation is not much worse than the ‘perfect’ expectation. Instead of discussing the results based on the min-entropy and collision entropy by Dodis and Yu [TCC 2013], we present how to overcome weak expectations dependent on the R

$$\acute{e}$$

e

´

nyi entropy and the expanded computational entropy. We achieve these results via employing the discrete form of the H

$$\ddot{o}$$

o

¨

lder inequality. We also use some techniques to guarantee that the expanded computational entropy is useful in the security model. Thus our results are more general, and we also obtain some results from a computational perspective. The results apply to all ‘unpredictability’ applications and some indistinguishability applications including CPA-secure symmetric-key encryption schemes, weak Pseudorandom Functions and Weaker Computational Extractors.

Yanqing Yao, Zhoujun Li

Modulus Computational Entropy

The so-called

leakage-chain rule

is a very important tool used in many security proofs. It gives an upper bound on the entropy loss of a random variable

$$X$$

X

in case the adversary who having already learned some random variables

$$Z_{1},\ldots ,Z_{\ell }$$

Z

1

,

,

Z

correlated with

$$X$$

X

, obtains some further information

$$Z_{\ell +1}$$

Z

+

1

about

$$X$$

X

. Analogously to the information-theoretic case, one might expect that also for the

computational

variants of entropy the loss depends only on the actual leakage, i.e. on

$$Z_{\ell +1}$$

Z

+

1

. Surprisingly, Krenn et al. have shown recently that for the most commonly used definitions of computational entropy this holds only if the computational quality of the entropy deteriorates exponentially in

$$|(Z_{1},\ldots ,Z_{\ell })|$$

|

(

Z

1

,

,

Z

)

|

. This means that the current standard definitions of computational entropy do not allow to fully capture leakage that occurred “in the past”, which severely limits the applicability of this notion.

As a remedy for this problem we propose a slightly stronger definition of the computational entropy, which we call the

modulus computational entropy

, and use it as a technical tool that allows us to prove a desired chain rule that depends only on the actual leakage and not on its history. Moreover, we show that the modulus computational entropy unifies other, sometimes seemingly unrelated, notions already studied in the literature in the context of information leakage and chain rules. Our results indicate that the modulus entropy is, up to now, the weakest restriction that guarantees that the chain rule for the computational entropy works. As an example of application we demonstrate a few interesting cases where our restricted definition is fulfilled and the chain rule holds.

Maciej Skórski

Broadcast (and Round) Efficient Verifiable Secret Sharing

Verifiable secret sharing (VSS) is a fundamental cryptographic primitive, lying at the core of secure multi-party computation (MPC) and, as the distributed analogue of a commitment functionality, used in numerous applications. In this paper we focus on unconditionally secure VSS protocols with honest majority.

In this setting it is typically assumed that parties are connected pairwise by authenticated, private channels, and that in addition they have access to a “broadcast” channel. Because broadcast

cannot

be simulated on a point-to-point network when a third or more of the parties are corrupt, it is impossible to construct VSS (and more generally, MPC) protocols in this setting without using a broadcast channel (or some equivalent addition to the model).

A great deal of research has focused on increasing the efficiency of VSS, primarily in terms of round complexity. In this work we consider a refinement of the round complexity of VSS, by adding a measure we term

broadcast complexity

. We view the broadcast channel as an expensive resource and seek to minimize the number of rounds in which it is invoked as well.

We construct a (linear) VSS protocol which uses the broadcast channel only

twice

in the sharing phase, while running in an overall constant number of rounds.

Juan Garay, Clint Givens, Rafail Ostrovsky, Pavel Raykov

Leakage Resilience of the Blom’s Key Distribution Scheme

We initiate the study of the leakage-resilience of the information-theoretic key distribution schemes. Such schemes, originally proposed in the 1980s, have recently attracted a lot of interest in the systems community. This is because, due to their extreme efficiency, they can be executed on low-cost devices such as sensors, where the use of the public-key cryptography is infeasible. We argue that the study of leakage resilience of such schemes is particularly well-motivated, since, unlike more expensive devices, the sensors (or other similar devices) are unlikely to be physically resilient to leakage.

We concentrate on the classical scheme of Blom (CRYPTO 1982), since it is known to be optimal in a large class of such schemes. We model the leakage as an input-shrinking function. In this settings we show that Blom’s scheme is leakage-resilient in a very strong model, where the adversary can (1) compromise completely some nodes in a “standard” way, and (2) leak information

jointly

from the remaining nodes. The amount leakage that we can tolerate can be up to

$$(0.5 - \epsilon )$$

(

0.5

-

ϵ

)

of the total amount of information on the leaking nodes. We also show that this bound is optimal, by providing an attack that breaks the scheme if more leakage is available to the adversary. This attack works even in a weaker model, where the nodes leak information independently.

In the proof we make use of the theory of the randomness extractors. In particular we use the fact that inner product over a finite field is a good

$$2$$

2

-source extractor. This is possible since the Blom’s scheme is based on the matrix multiplication.

Michał Jastrzȩbski, Stefan Dziembowski

Detection of Algebraic Manipulation in the Presence of Leakage

We investigate the problem of algebraic manipulation detection (AMD) over a communication channel that partially leaks information to an adversary. We assume the adversary is computationally unbounded and there is no shared key or correlated randomness between the sender and the receiver. We introduce leakage-resilient (LR)-AMD codes to detect algebraic manipulation in this model.

We consider two leakage models. The first model, called

linear leakage

, requires the adversary’s uncertainty (entropy) about the message (or encoding randomness) to be a constant fraction of its length. This model can be seen as an extension of the original AMD study by Cramer et al. [

3

] to when some leakage to the adversary is allowed. We study

randomized strong

and

deterministic weak

constructions of linear (L)LR-AMD codes. We derive lower and upper bounds on the redundancy of these codes and show that known optimal (in rate) AMD code constructions can serve as optimal LLR-AMD codes. In the second model, called

block leakage

, the message consists of a sequence of blocks and at least one block remains with uncertainty that is a constant fraction of the block length. We focus on deterministic block (B)LR-AMD codes. We observe that designing optimal such codes is more challenging: LLR-AMD constructions cannot function optimally under block leakage. We thus introduce a new optimal BLR-AMD code construction and prove its security in the model.

We show an application of LR-AMD codes to tampering detection over wiretap channels. We next show how to compose our BLR-AMD construction, with a few other keyless primitives, to provide both integrity and confidentiality in transmission of messages/keys over such channels. We discuss our results and suggest directions for future research.

Hadi Ahmadi, Reihaneh Safavi-Naini

Backmatter

Weitere Informationen

Premium Partner

Neuer Inhalt

BranchenIndex Online

Die B2B-Firmensuche für Industrie und Wirtschaft: Kostenfrei in Firmenprofilen nach Lieferanten, Herstellern, Dienstleistern und Händlern recherchieren.

Whitepaper

- ANZEIGE -

Best Practices für die Mitarbeiter-Partizipation in der Produktentwicklung

Unternehmen haben das Innovationspotenzial der eigenen Mitarbeiter auch außerhalb der F&E-Abteilung erkannt. Viele Initiativen zur Partizipation scheitern in der Praxis jedoch häufig. Lesen Sie hier  - basierend auf einer qualitativ-explorativen Expertenstudie - mehr über die wesentlichen Problemfelder der mitarbeiterzentrierten Produktentwicklung und profitieren Sie von konkreten Handlungsempfehlungen aus der Praxis.
Jetzt gratis downloaden!

Bildnachweise