Pavel A Panchenko

A N Arkhipova

Marina A Zakharko

Gediminas Jonusauskas

Yuri V Fedorov

Olga A N Fedorova

Synthesis and spectral properties of fluorescent dyes based on 4-styryl-1,8-naphthalimide

Keywords: naphthalimide, styryl dyes, intramolecular charge transfer, twisted intramolecular charge transfer, solvatochromism, fluorescence, Lippert-Mataga equation

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Nowadays, the methods of fluorescence spectroscopy are of great importance for the application in biological and biomedical research. [START_REF] Lakowicz | Principles of Fluorescent Spectroscopy[END_REF] With the appearance of confo cal fluorescence microscopy 2 the organic fluorophores have been used as molecular probes, imaging reagents, and sensors, allowing one to study the structure, dynamics, and function of biological macromolecules. [3][4][5][6] It is known that the emission peaks of the most intensively luminescent organic materials are located in a range of 400-600 nm. This spectral range is characterized by significant absorption of the excitation light by the bio logical sample. In addition, there is relatively strong fluorescent background in this spectral range, which great ly limits the choice of useful photoactive compounds.

Cyanine dyes 7-9 are used in many cases for in vivo optical studies, because at relatively small length of conju gated chain (about seven methine groups) their fluores cence maxima may be located near the border of the visible and near infrared (NIR) spectral regions, or even be in the NIR range. The disadvantages of the cyanine dyes include the complexity of their synthesis, relatively low photochemical stability, and low values of the Stokes shift, which usually do not exceed 25 nm. The latter feature of the spectral properties is not desirable when using the confocal fluorescence microscopy, since it leads to a significant reduction in the contrast of the images due to reflection/scattering of the excitation light by the test sample.

The derivatives of imide of naphthalic acid (1,8 naph thalimide) are practically important class of organic fluo rophores, which are used in many areas of science and technology, such as optical brightening, 10 fluorescent crack detection, 11 solar energy conversion, 12 fabrication of the optical memory elements, 13 and electrolumines cent devices. 14 Intensive fluorescence in the visible spec trum, high photostability, and high values of Stokes shift of 1,8 naphthalimides along with the simplicity of syn thetic modifications aimed to molecular structure of this type make these compound attractive for the application as a photoactive component of ratiometric chemosensors suitable for the analysis of ions in living cells 15, 16 as well as fluorescent dyes for applications in biology and medi cine. 17, [START_REF] Stewart | [END_REF] It has been shown in earlier works devoted to the spectroscopic study of 1,8 naphthalimide derivatives that the introduction of polarizing substituents having strong electron donating properties in positions 4 and 5 of the naphthalene nucleus leads to a bathofluoric shift of the emission band. 19,20 In most cases, the 4 substituted derivatives formed at this exhibit blue or yellow green emission (λ max = 450-550 nm). Much rarely the com pounds are found, in which naphthalimide chromophore emits at longer wavelength region of the spectrum (λ max > > 600 nm). [21][22][23] Exactly such derivatives are of the great est practical interest for the study of biological samples with fluorescent methods.

In this paper, the synthesis and detailed study of spec tral luminescent properties of 1,8 naphthalimides 1-3 (Scheme 1), containing styryl fragment at atom C(4) and differing in the number and nature of the electron donat ing substituent in the phenyl ring, are considered. Such compounds are able to enter cells. They have potential use as in vivo fluorescent imaging reagents. 23 However, their optical properties were investigated in a lesser extent than the properties of 4 amino, 4 (acyl)amino, and 4 alkoxy 1,8 naphthalimides.

Results and Discussion

Target 4 styryl substituted derivatives of 1,8 naph thalimide 1-3 were prepared starting from acenaphthene (4) according to Scheme 1. The bromination of 4 to 4 bromo acenaphthene (5) followed by the oxidation led to 4 bromonaphthalic anhydride (6), which further was converted to naphthalimide 7 using n butylamine in etha nol. The introduction of styryl fragment into position 4 of the naphthalimide nucleus at the final step was carried out by the Heck reaction using commercially available styrene derivatives. 24 The structures and compositions of pre pared compounds 1-3 were proved by a combination of physico chemical analytic techniques (see Experimental).

The absorption and fluorescence emission spectra of naphthalimides 1-3 were registered in fifteen different solvents, among them were five protic and ten aprotic solvents. Stokes shifts (Δν ~), fluorescence quantum yields (ϕ fl ), and excited state lifetimes (τ) were also determined. The data are presented in the Table 1.

The long wavelength band in the absorption spectra of investigated compounds is connected to intramolecular charge transfer (ICT) from electron donating styryl frag ment to carbonyl groups of dicarbonylimide moiety as evidenced by the distribution of electron density in the frontier molecular orbitals (HOМО and LUМО) of 1-3 (Fig. 1). As examples the absorption and fluorescence spectra of 1-3 in ethyl acetate are presented in the Fig. 2. It is clear from Fig. 2 that an increase of electron donating properties of the substitutent in the position 4 of the naphthalene ring from monomethoxy derivative 1 to dimethoxystyrylnaphthalimide 2 and further to 3 leads to the bathochromic shift, which corresponds to conver gence of energy levels S 0 and S 1 and an increase of the efficiency of the formation of the ICT state.

An increase in the solvent polarity and its ability to form hydrogen bonds also causes displacement of the maxima of absorption bands (λ abs max ) and fluorescence (λ fl max ) to longer wavelength with simultaneous growth of Δν ~ value (see Table 1). Significant solvatochromism and solvatofluorochromism of 4 styrylnaphthalimide deriva tives allowed estimation of the change of dipole moment of these molecules upon the transition into excited state. The Lippert-Mataga equation 25, 26 was used for the anal ysis of influence of solvent on the emission spectra of the compounds under investigation:

(1) (2) where Δν ~ is the Stokes shift, cm -1 ; Δν ~abs , Δν ~fl are the wave numbers corresponding to spectral maxima in ab sorption and fluorescence spectra, respectively, cm -1 ; μ e and μ g are the dipole moments of compound in solu tion in excited and ground states, respectively, D (1 D = = 1•10 -18 cm 5/2 g 1/2 s -1 ); h is the Planck constant (h = 6.626•10 -27 erg s); с is the speed of light in vacuum (с = 2.998•10 10 cm s -1 ); а is the effective radius of Onsager cavity (radius of cavity, where fluorophore is placed), cm; ε and n are the dielectric permittivity and refractive index of solvent, respectively; Δf is the orienta tion polarizability of solvent. Equation ( 2) is given in CGS system. Notes: ε is the solvent dielectric constant; λ abs max and λ fl max are the maxima in absorption and fluorescence spectra, respectively; ε λ is the extinction coefficient in the point corresponding to λ abs max ; λ ex is the excitation wavelength; Δν ~ is the Stokes shift; ϕ fl is the fluorescence quantum yield; τ is the excited state lifetime.

The values of parameter Δf for used here protic and aprotic solvents and corresponding values of Stokes shifts for compounds 1-3 are represented in the Fig. 3. In considered cases both protic and aprotic solvents demon strate good linear correlation. The changes of dipole mo ments upon the transition into excited state were deter mined using the slope of the lines in the Fig. 3. Calculated values (μ e -μ g ) consisted of 20.78, 21.96, and 22.95 D for 1, 2, and 3, respectively. Half of the distance between N atom or O atom in para position to double bond in styryl fragment and O atom farthest from С(4) substitutent of carbonyl group was taken as the radius of the Onsager cavity. This is similar to approach taken for 4 substituted naphthalimide derivative earlier. 27,28 The data of quan tum chemical calculations for the compounds 1-3 by РМ6 method (МОРАС 2012) were used to determine this distance. The values of a for investigated fluoro phores consisted of 6.85 (1), 6.80 (2), and 6.89 Å (3).

It is known that a value of 4. The fluorescence quantum yield of compounds 1-3 is changed differently by varying the nature of the solvent. In the case of compounds 1 and 2 the efficiency of radia tive deactivation is approximately the same in both polar and non polar solvents, while for compound 3 the growth of solvent polarity and its proton donating properties causes the fluorescence quenching (see Table 1). A similar de pendence can be traced also for the excited states lifetime values. These observations point to the persistence of radi ative rate constant of studied compounds in solvents of different nature, as well as to suggestion for compound 3 on the existence of relaxation channel, constituting a sig nificant competition to the fluorescence in a polar envi ronment.

According to current concepts, to explain the low ϕ fl values for fluorophores of ICT type in polar protic sol vents the model that postulates the formation of a twisted state of the charge transfer (twisted intramolecular charge transfer -TICT) 32 can be involved. This model assumes the existence of two energy minima on the potential ener gy surface of the excited state: the first one corresponds to locally excited state with quasi planar arrangement of π system and the donor group (Me 2 NC 6 H 4 in the case of naphthalimide 3); the second one corresponds to a state with a charge transfer from a donor to an acceptor group with quasi perpendicular location of π system and the donor group. In the frameworks of TICT model the for mation of twisted state with charge transfer includes two steps: the charge transfer and following rotation of donor in respect to the rest of the molecule. TICT model has been suggested for the description of two band fluores cence of 4 N,N dimethylaminobenzonitrile. 33, 34 How ever, in most cases the TICT states relax nonradiative and their formation decreases the quantum yield and fluores cence decay time. 32 Apparently, the transition to TICT state is more probable for compound 3 than for com pounds 1 and 2 because 4 (dimethylamino)styryl group, having the highest electron donating effect, contributes significantly to the charge separation during photoexcita tion. It should be stressed out again that another factor (in addition to the electronic effects of substituents in the chromophore), which promote the formation of the twist ed state is the solvation. In a strongly polar solvent the formation of non fluorescent TICT form may be the dom inant process. In particular, this results in a significant decrease in fluorescence quantum yield and lifetime of the excited state for compound 2 in methanol (see Table 1). Thus, in the course of this work the naphthalimides 1-3, differing in the structure of the styryl moiety, were synthesized. The analysis of spectral luminescent proper ties showed that all three compounds are ICT fluoro phores and exhibit significant solvatochromism. The ab sorption maxima (400-420 nm) and the fluorescence maxima (500-570 nm) of monometoxy derivative 1 are located at approximately the same wavelengths as in the case of 4 aminonaphthalimide. 19 As it is noted above, 4 aminonaphthalimide has substantial limitations for us ing as a fluorescent component of molecular devices in biochemical research. 4 (N,N Dimethylamino)styryl substituted compound 3 is the most long wavelength flu orophore. However, the fluorescence quantum yield of this compound is low in proton polar environment due to the high probability of formation of twisted state with charge transfer. At the same time, it was shown that the presence of two electron donating methoxy groups in the phenyl nucleus in compound 2 leads to bathofluoric shift of the maximum to a value of 550-630 nm while main taining high fluorescent signal intensity in polar solvents.

Experimental

1 Н NMR spectra were registered using Avance 400 and Avance 600 spectrometers (Bruker). The solutions were prepared in deuter ated benzene, dimethylsulfoxide, and chloroform. The chemical shift of nuclei 1 H and 13 С were determined with deviation of 0.01 ppm in respect to the residue signals of solvents and recalculat ed to internal standard (ТМS). The coupling constants were mea sured with a precision of 0.1 Hz. Numeration of carbon atoms in naphthalimide nucleus, styryl fragment, and butyl group, used for the description of 1 Н and 13 С NMR spectra of compounds 1-5 are represented in Scheme 1. The assignment of signals was carried out using two dimensional methods HSQC, HMBС, and 1 Н COSY with pulse field gradients.

Mass spectra with electrospray ionization at the atmosphere pressure (electrospray ionization method, ESI) were registered in the mode of total scanning of positive ions masses with tandem dynamic mass spectrometer Finnigan LCQ Advantage. Melting point were determined in glass capillary using Mel Temp device The absorption spectra were measured using two channel spec trometer Varian Cary 5G. The fluorescence spectra were measured using spectrofluorimeter FluoroMax 3 at temperature 20±1 °С. Observed fluorescence was registered perpendicular to exciting beam. The fluorescence spectra were corrected in respect to sensi tivity of the photomultiplier. The solvents of spectroscopic grade (Sigma Aldrich, purity not less than 99.5%) were used for the ab sorption and fluorescence spectra. The spectra were registered in solvents with a concentration of ∼10 -6 mol L -1 .

The fluorescence quantum yields were determined in air satu rated solutions at temperature 20±1 °С in respect to coumarin 481 standard in acetonitrile (ϕ fl = 0.08). 35 To calculate quantum yield following equation was used 36 (3) where ϕ fl i and ϕ fl 0 are the quantum yields, D i and D 0 are the absorptions, S i and S 0 are the integrals of fluorescence spectra of analyzed compound and standard, respectively; n i and n 0 are the refractive indices of solvents for studied compound and standard, respectively.

Time dependent fluorescence spectra were registered using a system consisting of spectrograph Chromex 250, connected to Hamamatsu 5680 streak camera with the module of fast scanning M5676 with a time resolution of 2 ps. Excitation pulses were gener ated using light optical parametric oscillator pumped by the funda mental emission of femtosecond laser system Ti-sapphire Femto power Compact Pro. All values of lifetime of excited states were obtained using depolarized excitation light. Maximum pulse energy of the fluorescence excitation was not higher than 100 nJ, average power was 0.1 mW, pulse repetition rate was 1 kHz. The excitation beam of 0.1 mm diameter was focused onto quartz cuvette (l = 10 mm). The analysis of florescence kinetics was carried out by curve fitting using method of Levenberg-Marquardt least squares applying the solutions of differential equations describing the be havior of one of the excited state in time without taking into account changes in the population of the ground state according to the equation (4) where I(t) is the intensity of fluorescence, τ is the lifetime of the excited state, Gauss is the Gauss profile of exciting pulse, t 0 is the time position of maximum, Δt is the pulse width, A is the pulse amplitude. Initial conditions were I(-∞) = 0. By selecting the solu tion the values of χ 2 (Pearson criterion) was always smaller than 1•10 -4 , and correlation coefficient R > 0.999. Error of calculation of the lifetime did not exceed 1%. Fluorescence accumulation time in the experiments did not exceed 90 s. The registration of the fluorescence spectra with time resolution has been made on the equipment of the Aquitaine Waves and Matter Laboratory, Univer sity of Bordeaux/CNRS (France).

Quantum chemical calculations were carried out with half empirical method РМ6 37 using the software package МОРАС 2012. Iterative procedure was continued as long as the molecular energy difference of two successive iterations did not exceed 0.01 kcal mol -1 . Influence of solvent nature was taken into account in accordance with the model COSMO (Сonductor like Screening Model), included in МОРАС 2012. It was assumed in the calcula tions that the solvent has a dielectric constant ε = 20 and refractive index n such that n 2 = 2.

5 Bromo 1,2 dihydroacenaphthylene (5). To the suspension of 10.0 g (0.065 mol) 1,2 dihydroacenaphthylene (4) in 35 mL of DMF under continuous stirring the solution of 11.3 g (0.064 mol) N bromosuccinimide in 35 mL of DMF was added drop by drop during 30 min. After the addition of the solution was complete the reaction mixture was stirred for another 2 h at room temperature and then was poured into 1 L of water. Formed precipitate was separated by filtration and washed in the filter with ethanol. The product was purified by crystallization from methanol. The yield was 12.5 g (82%), m.p. 50-52 °С (see Ref. 38: m.p. 51-52 °С). 6 Bromobenzo[d,e]isochromene 1,3 dione (6). The mixture of 12.5 g (0.053 mol) 5 brormoacenaphtene ( 5) and 125 mL of acetic acid was heated to 90 °С. To this stirred solution 78.0 g (0.262 mol) Na 2 Cr 2 O 7 •2H 2 O was added by small portions in order to maintain temperature not higher than 90 °С. Then reaction mass was heated to reflux and was kept at reflux with condenser for 5.5 h. Afterwards, the reaction mass was cooled to room temperature and poured into 750 mL of water. Formed precipitate was separated by the filtration and washed on the filter by diluted hydrochloric acid and then by water. This precipitate was suspended in 500 mL of 10% aqueous solution of Na 2 CO 3 and boiled for 1 h. Obtained solution was cooled down to room temperature and insoluble precipitate was separated by filtration. The filtrate was acidified by concentrat ed hydrochloric acid, formed precipitate of 4 bromonaphtalic acid was separated by filtration, washed with water and dried. In order to obtain anhydride the product was recrystallized from acetic acid. The yield was 6.6 g (44%), m.p. 218-220 °С (see Ref. Synthesis of compounds 1-3 (general procedure). 1 mmol of 4 bromo N butylnaphthalimide 7, 0.01 mmol of palladium ace tate, 0.06 mmol of tris (orto tolyl)phosphine, 1 mL of triethylamine, and 1.2 mmol of corresponding styrene were dissolved in 10 mL of DMF in argon atmosphere. The reaction mass was kept at 105 °С for 15-24 h, then cooled down to room temperature, diluted with water, and extracted with dichloromethane. The extract was dried over anhydrous MgSO 4 , evaporated, and the residue was separated using silica gel with hexane ethyl acetate as eluent with increasing gradient of eluent polarity. Obtained product was recrystallized from ethanol. 7)). 13

  8 D corresponds to the dipole moment arising in the separation of unit charges at a distance of 1 Å. Consequently, the change of dipole moment of molecules 1, 2, and 3 at the excitation by values of 20.78, 21.96, and 22.95 D corresponds to the separation of unit charges by a distance of 4.33, 4.58, and 4.78 Å. Such character of the electronic density distribu tion upon absorption of light signifies the formation of excited states with charge transfer and corresponds to the values of (μ e -μ g ), obtained 27-31 for naphthalimides de rivative, containing different electron donating groups in the position 4 of naphthalimide nucleus.

Fig. 1 .

 1 Fig. 1. Distribution of electron density of the frontier orbitals HOMO and LUMO of compounds 1-3. Data obtained by calculation with РМ6 method.

Fig. 2 .

 2 Fig. 2. Absorption spectra (1-3) and normalized fluorescence emis sion spectra (4-6) of compounds 1 (1, 4), 2 (2, 5), and 3 (3, 6) in ethyl acetate.

Fig. 3 .

 3 Fig. 3. Dependence of Stokes shift on polarity function of solvent for compounds 1 (a), 2 (b), and 3 (c). Strait lines correspond to linear correlation between these parameters. The approximation of the data was obtained by least square method, correlation coefficients consist of 0.955, 0.974, and 0.978 for 1, 2, and 3, respectively. Solvents: 1, propylene carbonate; 2, dimethylsulfoxide; 3, aceto nitrile; 4, acetone; 5, 3 methylbutane 2 one; 6, 4 methylpentane 2 one; 7, 1,2 dimethoxyethane; 8, ethyl acetate; 9, diethyl ether; 10, cyclohexane; 11, methanol; 12, ethanol; 13, n butanol; 14, n hexanol; 15, n decanol.

1 H

 1 NMR spectrum (400.13 MHz, C 6 D 6 , 27 °С), δ: 3.21-3.36 (m, 4 Н, 2 СН 2 ); 7.04 (d, 1 Н, Н(3), J = 7.3 Hz); 7.23 (d, 1 Н, Н(6), J = 7.0 Hz); 7.45 (dd, 1 Н, Н(7), J = 8.3 Hz, J = = 7.0 Hz); 7.56 (d, 1 Н, Н(4), J = 7.3 Hz); 7.67 (d, 1 Н, Н(8), J = 8.3 Hz).

  39: m.p. 219-220 °С). 1 H NMR (400.13 MHz, DMSO d 6 , 27 °С, δ): 8.05 (dd, 1 Н, Н(6), J = 7.5 Hz, J = 7.9 Hz); 8.27 (d, 1 Н, Н(3), J = 7.5 Hz); 8.37 (d, 1 Н, Н(2), J = 7.5 Hz); 8.61-8.65 (m, 2 Н, Н(5), Н(7)). 6 Bromo 2 butyl 1Н benzo[d,e]isoquinoline 1,3(2Н) dione (7). To suspension of 500 mg (1.8 mmol) of 4 bromonaphtalic anhydride 6 in 35 mL of ethanol 228 μL (2.3 mmol) of butylamine was added. The reaction mass was heated to reflux, kept at reflux for 6 h, and cooled down to room temperature. Precipitate of N substi tuted naphthalimide was separated by filtration, washed on filter with 5% hydrochloric acid, 10% solution of Na 2 CO 3 , water, and ethanol. The product was dried at 80 °С. The yield was 534 mg (89%), m.p. 100-102 °С (see Ref. 40: m.p. 101-102 °С). 1 Н NMR (400.13 MHz, DMSO d 6 , 21 °С, δ): 0.94 (t, 3 Н, H(12), J = 8.4 Hz); 1.29-1.40 (m, 2 Н, H(11)); 1.56-1.65 (m, 2 Н, H(10)); 4.03 (т, 2 Н, H(9), J = 8.4 Hz); 8.00 (dd, 1 Н, Н(6), J = = 7.3, J = 8.5 Hz); 8.21 (d, 1 Н, Н(3), J = 8.1 Hz); 8.32 (d, 1 Н, Н(2), J = 8.1 Hz); 8.52-8.59 (м, 2 Н, Н(7), Н(5)). MS (ESI), found: m/z 331.07 [M] + , calculated: 331.02.

  C 25 H 23 NO 3 . Calculated (%): С, 77.89; Н, 6.02; N, 3.64. 2 Butyl 6 (3,4 dimethoxystyryl) 1Н benzo[d,e]isoquonoline 1,3(2Н) dione (2). The yield was 18%, m.p. 155-157 °С.1 Н NMR (400.13 MHz, CDCl 3 , 21 °С, δ): 0.99 (t, 3 Н, H(12), J = 8.4 Hz); 1.43-1.52 (m, 2 Н, H(11)); 1.70-1.78 (m, 2 Н, H(10)); 3.96 (s, 3 Н, ОСН 3 ); 4.02 (s, 3 Н, ОСН 3 ); 4.20 (t, 2 Н, H(9), J = = 8.4 Hz); 6.94 (d, 1 Н, H(18), J = 8.2 Hz); 7.18-7.24 (m, 2 Н, H(15), H(19)); 7.30 (d, 1 Н, Н(13b), J = 16.0); 7.72-7.82 (m, 2 Н, Н(13a), Н(6)); 7.98 (d, 1 Н, Н(3), J = 7.7 Hz); 8.56-8.62 (m, 2 Н, Н(2), Н(5)); 8.65 (d, 1 Н, Н(7), J = 8.3 Hz). 13 C NMR (150.93 MHz, CDCl 3 , 21 °С, δ): 13.98 (С(12)), 20.89 (С(11)), 30.56 (С(10)), 40.45 (С(9)), 55.26 (2 ОСН 3 ), 109.78 (С(19)), 112.01 (С(18)), 121.63 (С(15)), 121.86 (С(1)), 122.06 (С(13а)), 123.88 (С(8)), 123.97 (С(3)), 127.44 (С(6)), 129.83 (С(8а)), 130.69 (С(14)), 130.86 (С(4а)), 131.11 (С(5)), 131.89 (С(7)), 131.91 (С(2)), 136.07 (С(13b)), 142.16 (С(4)), 149.75 (С(16)), 150.07 (С(17)), 164.37 (С(8b)), 164.48 (С(8с)). MS (ESI), found: m/z 415.22 [M] + , calculated: 415.18. Found (%): С, 75.21; Н, 6.13; N, 3.43. C 26 H 25NO 4 . Calculated (%): С, 75.15; Н, 6.07; N, 3.37. 2 Butyl 6 (4 (dimethylamino)styryl) 1Н benzo[d,e]iso quionoline 1,3(2Н) dione (3). The yield was 28%, m.p. 181-184 °С. 1 Н NMR (400.13 MHz, CD 3 Cl, 23 °С, δ): 0.98 (t, 3 Н, H(12), J = 8.4); 1.42-1.51 (m, 2 Н, H(11)); 1.69-1.78 (m, 2 Н, H(10)); 3.07 (s, 6 Н, N(СН 3 ) 2 ); 4.19 (t, 2 Н, H(9), J = 8.4 Hz); 6.73-7.00 (m, 2 Н, Н(16), Н(18)); 7.33 (d, 1 Н, Н(13b), J = 16.0 Hz); 7.58 (d, 2 Н, Н(15), Н(19), J = 8.6 Hz); 7.69-7.80 (d, 2 Н, Н(6), Н(13а)); 7.99 (d, 1 Н, Н(3), J = 7.7 Hz); 8.55-8.65 (m, 3 Н, Н(2), Н(5), Н(

Table 1 .

 1 Absorption spectra data and fluorescent characteristics of compounds 1-3 in different solvents at 20

	°С

  were not corrected. Elemental analysis was carried out in the laboratory of microanalysis of the Institute of Organoelement Com pounds of Russian Academy of Sciences. The control of the reac tion and of purity of obtained compounds was performed using TLC with Sorbfil UV 254 (silica gel SТХ 1VE) and DC Alufolien Kieselgel 60 F 254 (Merck) plates. The column chromatography was carried out using silica gel Kieselgel 60, particle size was 0.063-0.200 mm (Merck).

	The approximation of the
	data was obtained by least square method, correlation coefficients
	consist of 0.955, 0.974, and 0.978 for 1, 2, and 3, respectively.

Solvents: 1, propylene carbonate; 2, dimethylsulfoxide; 3, aceto nitrile; 4, acetone; 5, 3 methylbutane 2 one; 6, 4 methylpentane 2 one; 7, 1,2 dimethoxyethane; 8, ethyl acetate; 9, diethyl ether; 10, cyclohexane; 11, methanol; 12, ethanol; 13, n butanol; 14, n hexanol; 15, n decanol. and

  C NMR (150.93 MHz, CDCl 3 , 22 °С, δ): 13.02 (С(12)), 20.03 (С(11)), 29.16 (С(10)), 38.76 (С(9)), 38.94 (2 N(СН 3 ) 2 ), 112.06 (С(16), С(18)), 117.96 (С(13а)), 119.87 (С(1)), 122.12 (С(3)), 122.97 (С(8)), 124.84 (С(8а)), 126.23 (С(6)), 129.07 (С(15)), С(19)), 129.79 (С(14)), 130.39 (С(4а)), 130.56 (С(5)), 130.81 (С(7)), 130.89 (С(2)), 136.07 (С(13b)), 142.01 (С(4)), 144.07 (С(17)), 161.97 (С(8b)), 162.08 (С(8с)). MS (ESI), found: m/z 398.27 [M] + , calculated: 398.20. Found (%): С, 78.43; Н, 6.56; N, 7.08. C 26 H 26 N 2 O 2 . Calculated (%): С, 78.35; Н, 6.58; N, 7.03. The work was performed with financial support of ERA.NET RUS Plus 311 DONOS Project and Ministry of Education and Science of the Russian Federation (Agreement No. 14.616.21.0037(RFMEFI61615X0037)).


Roland Schmitz

Shujun Li

Christos Grecos

Xinpeng Zhang

A New Approach to Commutative Watermarking-Encryption

We propose a new approach to commutative watermarkingencryption (CWE). A permutation cipher is used to encrypt the multimedia data, which leaves the global statistics of the multimedia data intact. Therefore, any non-localized watermarking scheme that depends only on global statistics of the multimedia data can be combined with the permutation cipher to form a CWE scheme. We demonstrate this approach by giving a concrete implementation, which manipulates the global histogram to achieve watermark embedding/detection. *: n is the number of iterations of the cat map. **: m denotes the length of the low-pass and high-pass wavelet filters.

Introduction

Encryption and watermarking are both important tools in protecting digital contents, e.g. in digital rights management (DRM) systems. While encryption is used to protect the contents from unauthorized access, watermarking can be deployed for various purposes, ranging from ensuring authenticity of content to embedding metadata, e.g. copyright or authorship information, into the contents.

The concept of commutative watermarking-encryption (CWE) was discussed in [START_REF] Herrera-Joancomartí | ECRYPT European Network of Excellence in Cryptology, first summary report on hybrid systems[END_REF] with special emphasis on watermarking in encrypted domain. Four properties about watermarking in encrypted domain are formulated in [1, Sec. 2.2]:

-Property 1. The marking function M can be performed on an encrypted image. -Property 2. The verification function V is able to reconstruct a mark in the encrypted domain when it has been embedded in the encrypted domain. -Property 3. The verification function V is able to reconstruct a mark in the encrypted domain when it has been embedded in the clear domain. -Property 4. The decryption function does not affect the integrity of the watermark.

As is pointed out in [START_REF] Herrera-Joancomartí | ECRYPT European Network of Excellence in Cryptology, first summary report on hybrid systems[END_REF], Properties 2 and 3 are equivalent, if the encryption function E and the marking function M commute, that is,

M(E K (I), m) = E K (M(I, m)) ( 1
)
where E is the encryption function, K is the encryption key, I is the plaintext media data and m is the mark to be embedded.

Previous approaches to CWE are essentially based on one of the following two techniques: Homomorphic Encryption, where the encryption function is commutative to some basic arithmetic operations like addition or multiplication that can support a further watermarking step, or Partial Encryption, where only a part of the multimedia data is encrypted and the remaining data are watermarked. In the present contribution we propose a novel approach, namely to use a cipher in the sense that it encrypts the multimedia data fully but leaves some global properties untouched which are then used to embed the watermark. As a proof of concept of this new approach, we propose a CWE scheme for digital images by combining a permutation based cipher and a "non-localized" watermarking scheme working with the global image histogram in the spatial domain.

The rest of the paper is organized as follows. Previous work on CWE, histogrambased watermarking and joint encryption-watermarking are reviewed in Sec. 2. In Sec. 3 we describe our proposed CWE framework in greater detail. In Secs. 4 and 5 we analyze the security and computational complexity of our proposed CWE scheme. In Sec. 6 we show some experimental results. We conclude the paper in Sec. [START_REF] Ni | Reversible data hiding[END_REF], where we also give some directions for further research.

Related Work

Commutative Watermarking-Encryption

One approach to commutative watermarking is provided by deploying homomorphic encryption techniques so that some basic algebraic operations such as addition and multiplication on the plaintexts can be transferred onto the corresponding ciphertexts, i.e., they are transparent to encryption [1, Sec. 2.1]. Especially, if both the encryption and the watermarking process consist of the same homomorphic operation, one gets a commutative watermarking-encryption scheme. Examples of homomorphic operations are exponentiation modulo n, multiplication modulo n and addition modulo n (including the bitwise XOR operation). One major drawback of this approach is the influence of encryption on robustness of the watermarking algorithm: After strong encryption there is no visual information available for the watermark embedder to adapt itself to in order to increase robustness while at the same time minimizing visual quality degradation [START_REF] Lian | Multimedia Content Encryption[END_REF]Sec. 9.4]. Another drawback is that the modular addition operation may cause overflow/underflow pixels that have to be handled separately, thus making the system "quasi-commutative" [START_REF] Lian | Quasi-commutative watermarking and encryption for secure media content distribution[END_REF]. The XOR operation does not suffer from the overflow/underflow problem, though.

In partial encryption schemes, the plaintext multimedia data is partitioned into two disjoint parts, where one part is encrypted and the other part is watermarked. Since the encryption part is independent of the watermarking part, they are naturally commutative. To take a typical example, in [START_REF] Lian | Commutative watermarking and encryption for media data[END_REF], the multimedia data is partitioned into two parts after a four-level discrete wavelet transformation. The lowest-level coefficients are fully encrypted, while in the medium-and high-level coefficients only the signs are encrypted. In this case, the unencrypted absolute values of medium-level coefficients can be watermarked either before or after encryption (if after, without access to the encryption key). However, there is a certain danger that an attacker might tamper with the encrypted, un-watermarked part. Depending on the encryption algorithm used, this might go unnoticed by the recipient.

Because there is some information leakage through the unencrypted parts, in order to get a high level of perceptual security, the data parts which are significant for perception are encrypted, while only the perceptually unimportant parts are watermarked, leaving the door open for an attacker trying to remove the watermark. In order to overcome these difficulties, in another recent proposal [START_REF] Battisti | Joint watermarking and encryption of color images in the Fibonacci-Haar domain[END_REF], a key-dependent transform domain, the Fibonacci-Haar transform, is used for both watermarking and encryption to increase protection for the unencrypted, watermarked part. After a first-order Fibonacci-Haar transform, the LL subband of each color component is fully encrypted. The remaining detail subbands are then watermarked. The main drawback of this approach is that neither decryption nor watermark detection is possible without knowledge of the key for the Fibonacci-Haar transform, which means that Property 3 cannot be fulfilled. Thus, by adding another layer of encryption, the original commutativity property of watermarking and encryption is lost. We call such schemes joint watermarking-encryption (JWE) to differentiate them from CWE schemes.

Thus, for both approaches to CWE there is a lack of robustness against malicious attacks, if strong encryption is used. This seems to be a general problem with CWE schemes (see also Sec. 4.1).

Asymmetric Joint Watermarking-Encryption

A very interesting approach is put forward in [START_REF] Boato | A joint asymmetric watermarking and image encryption scheme[END_REF], where a permutation-based cipher is combined with an additive watermarking scheme acting on the 25 × 25 upper left corner of the DCT coefficients of an image. This scheme is truly asymmetric in the sense that different keys are used for embedding and detection of the watermark. Detection of the watermark in the encrypted domain is possible because the public key D used for detection contains some side information on the watermarked feature ψ and the encrypted watermarked feature ξ. This scheme is not a CWE scheme, however, because the watermark detection requires information on the encryption process.

Histogram Based Information Hiding

In [START_REF] Ni | Reversible data hiding[END_REF] it is shown how a reversible information hiding scheme can be built by hiding data within the histogram of an image. The basic idea is to shift the grey levels of all pixels having a grey level between g min and g max towards g min , where g min and g max denote the grey level with the lowest and the highest heights in the histogram, respectively. Such a shift will make the histogram bin at the position g max + 1 or g max -1 empty, thus "making space" for the data to be hidden.

Histogram Based Watermarking Schemes

The most widely studied approach to histogram based watermarking is so-called exact histogram specification [START_REF] Coltuc | Robust watermarking by histogram specification[END_REF][START_REF] Chareyron | Watermarking and authentication of color images based on segmentation of the xyY color space[END_REF][START_REF] Roy | Watermarking color histograms[END_REF][START_REF] Lin | Histogram-oriented watermarking algorithm: colour image watermarking scheme robust against geometric attacks and signal processing[END_REF], where the histogram of the original image or a (randomly and secretly selected) sub-region of it is modified toward a target histogram, which is then used as the signature for watermark detection. The histogram is not limited to be the one built from pixel values, but can also be a 2-D or 3-D histogram built from other features of the image [START_REF] Chareyron | Watermarking and authentication of color images based on segmentation of the xyY color space[END_REF][START_REF] Roy | Watermarking color histograms[END_REF][START_REF] Lin | Histogram-oriented watermarking algorithm: colour image watermarking scheme robust against geometric attacks and signal processing[END_REF]. To minimize visual quality distortion caused by the histogram manipulation, an optimization model can be used to find a globally optimum solution as demonstrated in [START_REF] Roy | Watermarking color histograms[END_REF].

However, most histogram based information hiding schemes cannot be used for secret watermarking because they do not involve a secret embedding/detection key. In what follows, we describe one approach that does use a secret watermarking key and whose basic principle is used in the example implementation of our proposed CWE framework.

The scheme proposed by Chrysochos et al. [START_REF] Chrysochos | Reversible image watermarking based on histogram modification[END_REF] is based on the idea of (selectively) swapping two selected neighboring histogram bins a and b so that a message bit is encoded by the heights of the two bins (denoted by hist(a) and hist(b)): a 1-bit is encoded by hist(a) > hist(b) and a 0-bit by hist(a) < hist(b). Here, swapping two histogram bins a and b means changing all pixel values a to b and vice versa. In order to embed an N -bit watermark into a 8-bit grey-level image, a watermarking key composed of a bin distance 1 ≤ step ≤ 9 and a start bin index 0 ≤ a 1 ≤ 255 -step is needed. The i-th bin pair is selected by increasing a 1 by i but skipping those bin pairs breaking at the right boundary of the histogram. As the pixel values are changed by an amount of step when embedding the watermark, the step is upper bounded to nine in order to limit visual quality degradation. The embedding capacity of the scheme depends on the number of candidate histogram bin pairs whose heights are not equal (which is dependent on the image and the step), but it is bounded by 128 bits for 8bit grey-level images and 384 bits for RGB images. Besides these low capacity bounds, the main problem of this scheme is the very small key space, which contains only 9 step=1 (256 -step) = 2259 different watermarking keys.

The Proposed CWE Framework

In order to design a CWE scheme, the encryption/decryption function must keep some features of the original image free from distortion so that they can be used for watermark embedding either before or after encryption. For instance, homomorphic encryption preserves the locations of all pixels so that the watermark embedding process can still happen on the intended pixels as long as the embedding function is commutative to the encryption function. Partial encryption preserves both locations and pixel values of part of an image so that watermark embedding can happen without any constraints. Neither of the existing approaches to CWE tries to preserve pixel values and distorts locations of all pixels. This led us to propose a third approach for designing a CWE scheme: using a permutation cipher to encrypt the image to preserve all pixel values intact for watermarking embedding. What a permutation cipher does is to simply shuffle the locations of all pixels under the control of a secret key. Although no change is made to any pixel value, the ciphertext image normally looks random enough to achieve the goal of concealing almost all visual information carried by the original image. Since no pixel value is changed by a permutation cipher, the global histogram of the image remains intact. If a watermarking scheme only uses the global histogram of the image for embedding and detection, which we call non-localized watermarking, the permutation (as an encryption function) and the watermarking processes will become commutative, satisfying all the four properties listed in Sec. 1. Examples include the image watermarking schemes proposed in [START_REF] Roy | Watermarking color histograms[END_REF][START_REF] Chrysochos | Reversible image watermarking based on histogram modification[END_REF] and the video watermarking scheme proposed in [START_REF] Chen | Temporal statistic based video watermarking scheme robust against geometric attacks and frame dropping[END_REF]. The last scheme makes use of both the spatial histograms of single frames and the temporal histogram for a given video sequence.

An obvious advantage of this new approach is that the robustness of the watermarking algorithm remains intact because all information (global statistics) required by the algorithm is not changed by encryption. In this aspect, the new approach outperforms the homomorphic cryptography based CWE approach. Compared with the partial encryption based approach, our proposed scheme can provide a higher level of security since total encryption is applied here.

Watermarking Part

The watermarking part is designed following the basic principle of the histogram based watermarking scheme proposed in [START_REF] Chrysochos | Reversible image watermarking based on histogram modification[END_REF]. However, since this scheme suffers from two severe limitations, namely a very small key space and a small capacity, we have devised a modified watermarking scheme to overcome both problems.

Basic Scheme For embedding the watermark, we select each bin pair randomly from all remaining candidates rather than in a sequential order as in the original scheme [START_REF] Chrysochos | Reversible image watermarking based on histogram modification[END_REF], which leads to a significantly bigger key space. The process is driven by a stream cipher that serves as a secret pseudo-random number generator. The watermark is encrypted so that the order of selected bin pairs matters in the extraction of the watermark. Given an N -bit watermark, the bin pairs selection, watermark embedding and detection processes can be described as follows.

Bin pairs selection: For the i-th bin pair, run the stream cipher to create a random integer 0 ≤ x ≤ 255 -2i. Then pick the x-th unused bin as the first bin a i . Then, run the stream cipher to create a new integer max(-9, -a i ) ≤ step ≤ min(255 -a i , 9). Pick the (a i + step)-th bin as the second bin b i . If b i has been used or if the two bins have the same height, re-generate a new integer x and a new step until two valid bins are selected to form a new bin pair.

Watermark embedding: First encrypt the watermark W = {w i } N i=1 by the stream cipher to get W * = {w * i } N i=1 . The heights of the two selected bin pairs a i and b i should encode w * i as follows: if w * i = 1, hist(a i ) < hist(b i ) should hold, and if w * i = 0, hist(a i ) > hist(b i ) should hold, where hist(x) denotes the height of the bin x. If this is not the case, the two bins a i and b i are swapped.

Watermark extraction: First, reconstruct the same sequence of bin pairs {a i , b i } N i=1 at the detector side. Then, extract the encrypted watermark as follows:

W * = {w * i } N i=1
, where w * i = 0 if hist(a i ) > hist(b i ) and w * i = 1 if hist(a i ) < hist(b i ). Finally, decrypt W * to recover the plaintext watermark W .

Figure 1 shows the results of embedding a 64-bit watermark "12345678" into the blue channel of the test image "baboon" by using the modified watermarking scheme and by the original watermarking scheme. We ran both watermarking schemes on the Kodak true-color image database and measured the quality of the watermarked images by using ten objective visual quality assessment (VQA) metrics included in the MeTriX MuX VQA Package [START_REF] Gaubatz | MeTriX MuX visual quality assessment package[END_REF]. The results show that our changes to the original scheme does not compromise the visual quality of the watermarked image. To be more exact, the mean of the visual quality measured by all the ten VQA metrics remains similar for both schemes but our scheme seems to have a smaller variance in the measured visual quality, which can be partly explained by the stronger random effect of the bin selection process. Figure 2 shows the PSNR and SSIM (two VQA metrics) values of 24 images watermarked by the two schemes.

Enhancing the Capacity The capacity of the basic scheme described above is limited to the number of candidate bin pairs, which is upper bounded by 128 bits. It can be greatly enhanced by dividing the cover work into sub-images and applying the basic scheme to those sub-images independently. In order to keep the visual distortions at a level comparable to that of the basic scheme, the subimages should have roughly similar histogram shapes as the underlying image. This can be achieved either by randomly assigning image pixels to sub-images or by doing this using a predefined fixed pattern, where each pixel in an n × m block is assigned to one of n × m sub-images. Both approaches yield histograms similar to the original one. For simplicity reasons, we chose the latter approach in our prototype implementation. More specifically, for a pixel p(i, j) in the original image I, we compute k = i mod n and = j mod m and assign p(i, j) to subimage S(k, ). Figure 3 shows one resulting sub-image and the corresponding histograms for the blue channel of the baboon image in the case n = m = 8.

The maximum capacity achievable by this approach depends on the size of the sub-images. For our prototype, we chose the sub-images to be s×s images, where s is a common divisor of width W and height H of the underlying image. This choice was motivated by our use of Arnold's cat Map for encrypting the image (see Sec. 3.2), but in principle non-square sub-images are also possible. Moreover, the sub-image size does not need to be a divisor of W and H. In the most general case, the maximum capacity per colour channel is C max (P ) = 128• W H/P bits, where P is the number of pixels in one sub-image.

In our prototype implementation, we set s ≥ 50 to ensure a meaningful histogram of each sub-image. Thus, here the overall maximum capacity is C max = 128 • W H/s 2 bits per colour channel, where s is the smallest common divisor of W and H that is ≥ 50. See Table 2 for some experimental results.

Encryption Part

Permutation ciphers have been very popular in securing analog Pay-TV services [START_REF] Slater | Scrambler: TV signal encryption[END_REF] and digital multimedia data in general [START_REF] Zeng | Efficient frequency domain selective scrambling of digital video[END_REF] because they can be easily implemented and perceptual information about the ciphertext can be effectively concealed. A permutation cipher acting on an W × H image can be modeled by a W × H permutation matrix M = {m(x, y) = (x , y )} 0≤x,x ≤W -1 0≤y,y ≤H-1

, where (i , j )

denotes the new location of the pixel (i, j) after permutation [START_REF] Li | A general quantitative cryptanalysis of permutation-only multimedia ciphers against plaintext attacks[END_REF]Sec. 2]. Note that the same permutation matrix can be used for encryption and decryption because the permutation is always a bijection. In principle, one can use the permutation matrix as the secret key, however, which occupies too much space so that the key management becomes difficult. A common practice is to use an algorithm to generate a permutation matrix under the control of a few parameters, which are used as the secret key. One of the simplest algorithms is as follows: generate a sequence of W H random numbers, then sort them, and finally take the 1-D indices which can be converted into 2-D coordinates to form the permutation matrix. Here, the random sequence can be generated by a stream cipher so that the permutation matrix is secret. The main drawback of this simple algorithm is about its complexity: the average complexity of a fast sorting algorithm is O(W H log 2 (W H)) and the worst-case complexity is O((W H) 2 ) [START_REF] Knuth | The Art of Computer Programming[END_REF]. While the complexity is actually not very high, when W H is large, the factor log 2 (W H) can still be significant. For instance, for full HD videos log 2 (W H) = log 2 (1920 × 1080) ≈ 21.

Many researchers have suggested iterating a parameterized 2-D discrete map to generate the permutation matrix. The average and worst-case complexities of such an approach is both O(nW H), where n is the number of iterations. If the image size is known in advance, the permutation matrix in each iteration can be pre-computed, thus leading to a reduced computational complexity of O(W H).

For our prototype implementation of the proposed CWE framework, we choose Arnold's cat map [START_REF] Arnold | Ergodic Problems of Classical Mechanics[END_REF], which was used by several researchers for encrypting square images [START_REF] Fridrich | Symmetric ciphers based on two-dimensional chaotic maps[END_REF][START_REF] Chen | A symmetric image encryption scheme based on 3D chaotic cat maps[END_REF]. Non-square images have to be either padded to be a square image or decomposed into a union of smaller square sub-images, like we did in the enhanced watermarking scheme described in Sec. 3.1. Arnold's cat map in its original form is defined on the unit square by

x i+1 y i+1 = 1 1 1 2 • x i y i mod 1, (2)
where "mod 1" means taking the fractional part of the argument.

Given an H × H image, one discretized version [START_REF] Chen | A symmetric image encryption scheme based on 3D chaotic cat maps[END_REF] is defined as follows:

x i+1 y i+1 = 1 a b ab + 1 • x i y i mod H, (3)
where a and b are parameters that can serve as the secret key if the function is used for encryption purposes. Figure 4 shows the results of applying Arnold's cat map to the test images "baboon" and "parrots", respectively. The baboon image was encrypted in its original form, while the parrots image was subdivided into 2 × 3 square sub-images before encryption. After that, each sub-image was encrypted using a different key.

Optional Information Hiding Part

Histogram based data hiding schemes like the one in [START_REF] Ni | Reversible data hiding[END_REF] are localized due to the need of bookkeeping the locations of some pixels, therefore, they cannot be used for watermarking in the context of our applications. However, they may still be used for the encryption part, e.g. to transport part of the key and other meta-information needed for the decryption process (cf. Sec. 4.2).

Security Analysis

As the watermarking and encryption schemes deployed are completely independent, they do not interfere with each other and their security can be assessed separately. Further, we can restrict our analysis to the basic scheme, as the sub-images are watermarked and encrypted independently from each other.

Watermarking Part

Unauthorized Embedding and Detection The watermarking scheme described in Sec. 3.1 is driven by a stream cipher selecting the candidate histogram bin pairs for embedding. The number of all possible selections of different bin pairs, denoted by S(N ), depends on N , the length of the embedded watermark W . The size of the key space is therefore min(2 |K| , S(N )), where K is the key of the stream cipher and |K| is the its bit size.

In this subsection we derive two lower bounds on S(N ), which correspond to two different ranges of the length of embedded watermark N . To simplify our discussion, we assume W is a sequence of bits

W = b 0 b 1 . . . b N -1 , where N ≥ 8. 1. Case 1: 8 ≤ N < 20. Since S(N 1 ) < S(N 2 ) if N 1 < N 2 ,
we calculate the lower bound for N = 8. We limit ourselves to those histogram bins with 18 neighbors to make our calculation easier. There are 256-18 such bins. After having embedded i watermark bits, 2i bins have already been used. Likewise, at most 2i bins in the neighborhood of the first selected bin for embedding b i+1 are occupied by previously selected bins. Combining these two facts, we immediately have the following lower bound:

S(N ) > 7 i=0 ((256 -18) -2i) × (18 -2i)) ≈ 2 89 . (4)
2. Case 2: 20 ≤ N ≤ 128. A lower bound can be obtained by considering only a subset of all the possible keys. A simple subset can be obtained as follows (without loss of generality, assuming 256 can be divided by N ): partition all the 256 bins into N disjoint parts of equal size 256/N , then randomly select a permutation of the N parts, and finally randomly pick two bins in each part whose distance is not greater than nine grey levels. Since in each part the number of bins may be smaller than nine, there are 256 N • min 9, 256 N -1 possibilities for each part. Thus, we get the following lower bound:

S(N ) > N ! • 256 N • min 9, 256 N -1 N . (5)
For N = 32, the lower bound is already well beyond 200 bits key length.

Unauthorized Removal Unfortunately, the watermark cannot withstand a malicious attacker manipulating the image histogram. The watermark may be removed by either randomly swapping neighbouring histogram bins or shifting the whole histogram by a small amount. This problem seems unavoidable since such attacks can simply resemble the original embedding algorithm.

Robustness Histogram based watermarks are known to be resistant against geometric attacks since the histogram is largely invariant to geometric transformations. More precisely, according to [START_REF] Hadjidemetriou | Histogram preserving image transformations[END_REF], the histogram is preserved by image transformations Ψ t : D → R 2 , where D ⊂ R 2 is the domain of the image and t ∈ R is the parameter of the transformation, with the property div d dt Ψ t = 0. When working in the encrypted domain, most signal processing operations can be ruled out in the robustness discussion, as the resulting image cannot be decrypted anymore. However, images encrypted by a permutation cipher can be lossily compressed [START_REF] Zhang | Lossy compression and iterative reconstruction for encrypted image[END_REF]. Robustness against this kind of compression will be subject of further research.

Encryption Part

It is well known that pure permutation-based ciphers are vulnerable to knownand chosen-plaintext attacks. A quantitative study was reported in [START_REF] Li | A general quantitative cryptanalysis of permutation-only multimedia ciphers against plaintext attacks[END_REF], where it is shown that for an H × H square image with L grey levels O(log L H 2 ) known plaintexts are sufficient to recover half of the plaintext pixels. The computational complexity of these attacks is O(p • H 4 ), where p is the number of known ciphertexts used, making these attacks practical. Therefore, we propose to use image-varying keys, e.g. image-dependent keys derived from the (normal or visual) hash of the image. The key is divided into one long-term secret master key and one short-term public image-dependent session key. The latter can be embedded into the encrypted image by using a reversible information hiding scheme such as those described in Sec. 2.3. It is combined with the secret master key to form the key for decrypting the image.

Arnold's cat map used in our prototype implementation suffers from a small key space of H 2 , if the same parameters are used for all iterations. In addition, it is well known that any discrete area-preserving map is periodic (upper bounded by the total number of finite states) and the discrete cat map applied to binary images has a period upper bounded by 3H [START_REF] Dyson | Period of a discrete cat mapping[END_REF]. For some "bad" parameters, the period can be very short. For example, selecting a = 40, b = 8 yields the original image again after five iterations if H = 124 [START_REF] Wong | Image encryption using chaotic maps[END_REF].

The security problems with Arnold's cat map can be mitigated by using different keys for different iterations, which can increase the key space to H 2n and also reduce the influence of bad parameters on the final result. We generated 1000 random keys with parameters H = 124 and n = 20, and none of the generated permutation matrix degenerates to the identity matrix. This led us to believe that the combination of n different keys is strong enough for our purpose.

If the sorting based approach mentioned in Sec 3.2 is used to generate a random permutation matrix, the security problems with Arnold's cat map will disappear. In this case, the key space becomes (H 2 )! and the short period does not exist anymore since we stop depending on iterating a 2-D map repeatedly.

Complexity Analysis

Without loss of generality, we assume that the plaintext image is an H × H image with L grey levels, that the watermark is an N -bit pattern, and that N is much smaller than H 2 , so that the derived complexity can be more compact. As in Sec. 4, we restrict the analysis to the basic scheme with no sub-images. In addition, we only consider the average complexity because the worst-case complexity can be quite different and less meaningful.

Watermarking Complexity

Generating the histogram corresponds to H 2 operations. To select N bin pairs from the histogram, ≈ 2N operations are needed. To embed all the N bits, averagely N/2 bin pairs need swapping, whose complexity is N H 2 /L. To detect the watermark, only N comparisons of bin heights are needed. To sum up, the overall computational complexity of the watermark embedding process is O(N H 2 /L) and that of the watermark detection process is O(H 2 ).

Encryption/Decryption Complexity

Since any permutation cipher can be represented by an H × H permutation matrix, encrypting an image requires merely H 2 look-up table operations and H 2 assignments. Iterating the discrete 2-D cat map n times requires nH 2 look-up table operations and pixel value assignments. Generating the permutation matrix requires 3H 2 multiplications and 3H 2 addition/assignments. We can ignore the 3H 2 additions/assignments, because multiplications are computationally much heavier. Thus, the overall complexity becomes O((n + 5)H 2 ) = O(nH 2 ). When the sorting based approach is used to generate the permutation matrix, the overall complexity is O(log 2 (H)H 2 ). Since the decryption can be done by using the same matrix, the computational complexity remains the same.

Comparison with Existing Schemes

Table 1 shows the complexities of our proposed CWE scheme and some existing ones following the other two approaches to CWE.

Experimental Results

Table 2 shows the results of applying the proposed CWE scheme including subdivision into square sub-images to four test images. By design, the watermarkedencrypted image and the encrypted-watermarked image are the same. In all images, a random bit sequence of maximum length was embedded into the blue channel. The PSNR and SSIM values were calculated by comparing the blue channels of the cover work and the marked image.

The watermark could be successfully extracted either from the encrypted marked image E K (M(I, m)) (Property 3) or from the marked encrypted image M(E K (I), m) (Property 2). In all cases, decrypting either M(E K (I), m) or E K (M(I, m)) leads to the marked plaintext image M(I, m), from which the watermark could still be successfully extracted (Property 4).

Conclusion and Further Work

We have presented a novel approach to building commutative watermarkingencryption schemes based on permutation-only ciphers and non-localized watermarking schemes. A concrete CWE scheme was designed by combining a histogram based watermarking scheme with a permutation cipher based on a discrete 2-D chaotic map. It satisfies all the four properties formulated in [START_REF] Herrera-Joancomartí | ECRYPT European Network of Excellence in Cryptology, first summary report on hybrid systems[END_REF]. Due to its simplicity, the proposed scheme is well suited for applications with high performance requirements, such as video content protection or authenticity of large amounts of encrypted transcoded data in heterogenous networks.

In our future work, we will study a possible generalization of the proposed CWE scheme to compressed domain, where the key questions include how to apply permutations without compromising compression efficiency and how to make the watermarking scheme more robust to lossy compression. We will also investigate if reversible CWE schemes can be designed within the proposed framework.

Fig. 1 :

 1 Fig. 1: Embedding a 64-bit watermark "12345678" into an image's blue channel: (a) original image; (b) image watermarked by the modified scheme (PSNR = 42.57); (c) image watermarked by the original scheme (PSNR = 42.36).

Fig. 2 :

 2 Fig. 2: Visual quality comparison of the modified watermarking scheme and the original one, measured by PSNR and SSIM.

Fig. 3 :

 3 Fig. 3: Splitting the cover work into 64 parts: (a) a sub-image; (b) histogram of the original image; (c) histogram of the sub-image (a).

Fig. 4 :

 4 Fig. 4: Encryption results of the permutation cipher based on Arnold's cat map: (a) and (c) plain images; (b) and (d) ciphered images.

Table 1 :

 1 Complexities of our CWE proposed scheme and some existing ones.

	Scheme	Watermarking embedding complexity	Watermarking detection complexity	Encryption complexity
	Proposed CWE scheme*	O((N/L + 1)H 2 )	O(H 2 )	O(nH 2 )
	Homomorphic CWE schemes in [2, Sec. 9.3]	O(H 2 )	O(H 2 )	O(H 2 )
	Partial encryption based CWE scheme in [4]**	O(mH 2 )	O(mH 2 )	O(mH 2 )

Table 2 :

 2 Some experimental results.

	Plain Image I	Cmax n × m*	Marked Image M(I, m)	PSNR SSIM	EK (M(I, m)) = M(EK (I), m)
		8192		36.69
		8 × 8		0.966
		8192		36.56
		8 × 8		0.913
		12288		36.45
		8 × 12		0.876

*: n × m denotes the size of the sub-image array


Jan Hajny
email: jan.hajny@phd.feec.vutbr.cz

Lukas Malina
email: lukas.malina@phd.feec.vutbr.cz

Practical Revocable Anonymous Credentials

Keywords: Privacy, Revocation, Credential Systems, Anonymity

Currently, there are many solutions for authentication. Mostly, the authentication protocols based on traditional cryptographic constructions, such as digital signatures, hash functions and symmetric encryption schemes, are used. To provide more privacy protection, credential systems were introduced. Using these systems, users can anonymously prove that they possess some attributes. The attributes can represent anything from the age of users to their citizenship or, e.g., driving license possession. The main problem of these systems is revocation since it is currently impossible to efficiently revoke invalid users, attackers or users who use stolen identities. In this paper, a novel conception for anonymous credentials with practical revocation is proposed.

Scheme Description

In this paper, we present a new concept for credential systems. The concept supports all privacy-enhancing features individually provided by related solutions, namely anonymity, unlinkability, untraceability, non-transferability and attribute proofs. Additionally, our novel concept allows efficient and practical off-line revocation. There are 4 entities in our credential scheme. They are the Issuer (I) who issues attributes, the Verifier (V) who verifies attributes, the User and the Public Authority (PA) who allows revocation. Each attribute (like citizenship, age or driving license possession) is assigned a unique public value A j . The list of these links between A j 's and their meaning is published and maintained by PA. All Users in the system who want to be issued j th attribute can download its value A j from this public list. All Users share the same values thus it is not possible to distinguish particular Users by the attribute value A j . To exclude unauthorized users, each valid user is given private keys for each attribute in the Issuance phase.

Credential Issuance Phase

To use A j for verification, proper keys must be provided to the User by PA and Issuer. Thus, each valid user is provided an attribute A j together with keys (w j , w j ) by I and PA before he can give proofs about the attribute ownership. The attribute value A j is the same for all Users but keys (w j , w j ) are unique for each User. The keys are the discrete logarithm representation of A with respect to generators g 1 , g 2 in modulo n such that A j = g wj 1 g w j 2 mod n. In our proposal, we use Okamoto-Uchiyama (OU) group [START_REF] Okamoto | A new public-key cryptosystem as secure as factoring[END_REF] defined by generators g 1 , g 2 and modulus n = r 2 s where r, s are large primes. There is a huge number of possible representations of A j so it is possible to provide all Users with unique keys. By employing an advanced cryptographic protocol for issuance, keys are provided to Users only, no other entity learns them.

Credential Verification Phase

Having the proper keys, a User can run the credential verification protocol which is a proof of knowledge of discrete logarithm of A j with respect to g 1 , g 2 . The protocol can be denoted as P K{(w j , w j ) : A j = g wj 1 g w j 2 }. Users unaware of proper keys are always rejected by the protocol because they don't know the representation. Valid users are stuck to their keys because of the binding property of A j (it is infeasible to compute different representation of A j without factoring n). This protocol is completely zero-knowledge so no extra information leaks except that the User has proper keys (w j , w j ). Each session is randomized by a random number r which stays secret but is present in the form of a verifiable encryption (VE) in the protocol. The randomization makes all sessions completely unlinkable thus verifiers cannot create user profiles. Since all users share the same A j , it is impossible to trace the User, identify the User or profile the User.

Credential Revocation Phase

In some cases, it is necessary to revoke Users. For this reason, an entity called Public Authority is introduced. The Public Authority knows a trapdoor to Okamoto-Uchiyama group, thus can decrypt randomness r used in the verification protocol. Using the randomness, PA can reconstruct unique keys (w j , w j ). These keys can be later used to identify malicious users and attackers, but only in cooperation with Issuers. By such a distribution, we protect Users against privacy disclosure done by a single entity. The approach is based on the assumption that it is unlikely that more entities (both Issuer and PA) would cooperate in unlawful breaking of Users' privacy. The full system specification is still in progress and the cryptographic details will be provided in the full paper. In the meanwhile, we enlist the constructions used: Okamoto-Uchiyama trapdoor one-way function [START_REF] Okamoto | A new public-key cryptosystem as secure as factoring[END_REF], Σ-protocols [2], Bao's verifiable encryption [START_REF] Bao | An efficient verifiable encryption scheme for encryption of discrete logarithms[END_REF] and discrete logarithm commitments. The scheme conception is depicted in Figure 1 1 .

Conclusion

Using the proposed system, users can anonymously provide proofs about their age, citizenship or other attributes. This functionality significantly improves privacy since users are not required to unnecessary disclose their identity and private data any more. Unlike existing systems, our system provides efficient revocation. The conception proposed in this paper is currently being implemented on smart-cards. The first implementation results show that the scheme is highly practical, with the time of verification under 1 s using an off-the-shelf smart-card.

Fig. 1 .

 1 Fig. 1. Proposed Principle

Jan Hajny was supported by the Fulbright stipend.

Please be advised that (w8, w 8 ) of User 1 is different from (w8, w 8 ) of User

Although not distinguished by notation, User keys are always different, even for same attributes.

Acknowledgment

Jan Hajny is the Holder of Brno Ph.D. Talent Financial Aid -Sponsored by Brno City Municipality. Research was sponsored by the Technology Agency of the Czech Republic and the MSMT grant FRVS 823/2012/F1.